Advent of Code 2020

r2d2rigo #631 Dic '20 Inocente

#630 no se yo que decirte, mas que la dificultad creo que el mayor detrimento es que sean aburridos o mal planteados.

A mi el de ayer me motivo bastante, el de hoy lo he hecho por obligacion.

1 respuesta

Ranthas #632 Dic '20

#631 Yo creo que buscan un equilibrio entre la dificultad y la diversión al resolverlo.

La propuesta del intcode del año pasado estuvo bien, pero escaló demasiado rápido, y el tener que refactorizar el puñetero intcode todos los días al final hizo lo que mandara a tomar por culo. Este año creo que han estado más acertados, si incluyen más problemas como el de ayer, o como el del día 4, pues de lujo.

O quizás algo tipo partiendo de un conjunto de instrucciones reducido, como en el problema de ayer, ir sacando más problemas apoyandose en ese set de reglas, pero sin tener que estarlas modificando a diario como el año pasado.

1 respuesta

S

sergioRG #633 Dic '20

#632 Yo prefiero problemas independientes entre sí, no hay nada que joda más que una cadena de problemas basada en una misma temática que no te gusta. Con un poco de variedad minimizas esto.

Es como los problemas de 20 apartados que dependen entre sí en los exámenes. Como te jodan desde la a...

1

test3y #634 Dic '20

A mí el de ayer me pareció chulo. Si van sacando más problemas de ir añadiendo complejidad a la máquina por mí bien. Del estilo como el de hoy, como no pongan entradas con una n mayor, pues le quitan algo de gracia.

días 8 y 9

R

RsTTa #635 Dic '20

Día 9. Para la parte uno he usado 2sum, asi que la complejidad se queda algo como O((N-25) * len(preambulo)), vamos O(N * K), donde K es 25 en este caso (la longitud del preambulo). Para la parte dos he usado dos punteros, windowing o un intento de ello. La complejidad diria que es O(N), pero si alguien confirma mejor xD

parte 1

def two_sum(target, nums):
    diff = set()
    for num in nums:
        if (target - num) in diff:
            return True
        diff.add(num)
    return False


if __name__ == '__main__':
    with open('input', 'r') as f:
        nums = [int(num) for num in f.readlines()]

start = 25
for idx in range(start, len(nums)):
    if not two_sum(nums[idx], nums[idx-25: idx]):
        print(nums[idx])

parte 2

def windowing_subset_sum(target, start_idx, min_subset_size, nums):
    idx1, idx2 = start_idx, start_idx + 1
    sum = (nums[idx1] + nums[idx2])
    idx2 += 1
    while (idx2 < len(nums)) and (sum < target):
        sum += nums[idx2]
        idx2 += 1
        while sum > target and idx1 <= idx2:
            sum -= nums[idx1]
            idx1 += 1
    return (idx1, idx2-1) if ((sum == target) and (idx2 - idx1) >= min_subset_size) else (None, None)


if __name__ == '__main__':
    with open('input', 'r') as f:
        nums = [int(num) for num in f.readlines()]

target = 375054920
idx1, idx2 = windowing_subset_sum(target, 0, 2, nums)
subset = nums[idx1: idx2+1]
smallest, largest = min(subset), max(subset)
print(smallest + largest)

1 respuesta

S

sergioRG #636 Dic '20

#635 Si, tu two pointers es lineal. idx2 incrementa a cada iteracion, idx1 siempre sera <= idx2 y solamente incrementa tambien, por lo que ese bucle realmente hace 2N operaciones a lo sumo, lo cual es lineal.

1

Traber #637 Dic '20

O se explican como el puto culo, o el de hoy es una puta real mierda pinchada en un palo.

1 respuesta

S

sergioRG #638 Dic '20

#637 El enunciado es una mierda, yo lo resumiría como:

Parte 1: Encuentra una manera de enchufar todos tus cacharros para que formen una cadena en la que no haya diferencias que no sean 1 o 3 entre dos cacharros adyacentes. Multiplica el número de diferencias de 1 por el número de diferencias de 3

Parte 2: Cuenta de cuantas maneras puedes conectar el cacharro de 0 al de max(numeros) + 3 habiendo diferencias de 1, 2 y 3 entre cacharros adyacentes.

Estos problemas recién levantao son una mierda xddd

Ranthas #639 Dic '20

Otra vez haciendo el idiota porque no leí que al final hay que usar también tu adaptador....

ciza #640 Dic '20

Pues a mi la parte 1 me ha parecido demasiado tonta mientras que la parte 2 tiene mas miga. Luego posteo la solución que he puesto.

1 respuesta

S

sergioRG #641 Dic '20

#640 Supongo que has hecho algo precido a mi solución, no?

spoiler

import sys

nums = list(sorted([int(x.strip()) for x in open(sys.argv[1]).readlines()]))

# parte 1
d = [nums[i] - nums[i - 1] for i in range(1, len(nums))]

print((d.count(1) + 1) * (d.count(3) + 1))

# parte 2
s = set(nums)
n = max(nums) + 4
# ponemos las dos puntas en la lista
s.add(0)
s.add(n - 1)

ways = [0] * n
ways[-1] = 1

for i in range(n - 2, -1, -1):
	if i in s:
		ways[i] = ways[i + 1] + ways[i + 2] + ways[i + 3]

print(ways[0])

1 1 respuesta

ciza #642 Dic '20

#641 de hecho la mia es menos imaginativa

spoiler

from itertools import combinations
import numpy as np

def check_subset(subset):
    removal_options = 1 # not removing elements is a valid option
    if not (len(subset) > 2):
        return removal_options
    remove_idx = np.arange(1,len(subset)-1)
    for n_remove in range(0, len(remove_idx)):      

        for removal in combinations(remove_idx, n_remove+1):
            if np.diff(np.delete(subset, removal)).max() <= 3:
                removal_options += 1
    return removal_options

data = np.loadtxt('input.txt')
data = np.append(data, [0, np.max(data) + 3])
data = np.sort(data)

one_v_diff = sum(np.diff(data) == 1)
three_v_diff = sum(np.diff(data) == 3)

print(f'Prob1: {one_v_diff * three_v_diff}')

can_be_removed = np.diff(data) != 3

prev_i = 0
solutions = 1
for i in range(data.shape[0]-1):
    if not can_be_removed[i]:
        solutions *= check_subset(data[prev_i:i+1])
        prev_i = i+1

print(f'Prob2: {solutions}')

1 respuesta

S

sergioRG #643 Dic '20

#642 Creo que no la acabo de entender muy bien tu solución.

1 respuesta

ciza #644 Dic '20

#643 es lo primero que se me ocurrio, basicamente:

spoiler

1 respuesta

S

sergioRG #645 Dic '20

#644 Aaaaaahhhhh, pues la verdad es que es bastante más creativo que lo que he hecho yo.

Lo que he hecho yo es básicamente lo que vine a explicar en #595 , que es un patrón que una vez lo dominas lo puedes aplicar bastante braindead.

Te tardaba mucho en ejecutarse?

2 respuestas

BeheritSp #646 Dic '20 Juntabrackets

Bueno, a mi este me ha gustado mucho también. Este me ha llevado más de 1 hora a lo tonto

Sobre la parte 2:

spoiler

Aquí el código:

Part 1

lines_list =[int(line.strip()) for line in open("input.txt").read().splitlines()]
# Adding built-in joltage 
lines_list.append(max(lines_list)+3)

def CheackAndReturnJolt(current_jolt):
    for i in [1,2,3]:
        new_jolt = current_jolt+i
        if new_jolt in lines_list:
            return new_jolt

jolt = 0
jolt_diff_list = []
while (jolt < max(lines_list)):
    new_jolt = CheackAndReturnJolt(jolt)
    jolt_diff_list.append(new_jolt - jolt)
    jolt = new_jolt
get_occurances = lambda x: len([i for i in jolt_diff_list if i == x])
print("Part 1 solution", get_occurances(1)*get_occurances(3))

Part 2

# Construct dict with combinations
jolt = 0
combinations = 0
main_dict_with_combinations = {}
lines_list.insert(0,0)
for jolt in lines_list:
    main_dict_with_combinations[jolt] = set()
    for i in [1,2,3]:
        new_jolt = jolt+i
        if new_jolt in lines_list:
            main_dict_with_combinations[jolt].add(new_jolt)

# EXPENSIVE, NOT USED
def RecursivelyCountOccurances(source_key):
    this_len = 0
    if len(main_dict_with_combinations[source_key])>0:
        for child in main_dict_with_combinations[source_key]:
            this_len += RecursivelyCountOccurances(child)
        return this_len
    else:
        return 1
# EXPENSIVE, NOT USED
# print("Part 2 solution", RecursivelyCountOccurances(0))

dict_with_occurances = {}
dict_with_occurances[lines_list[-1]] = 1
for key, value in sorted(main_dict_with_combinations.items())[::-1][1:]:
    this_len = 0
    for jolt in value:
        this_len += dict_with_occurances[jolt]
    dict_with_occurances[key] = this_len
    

print("Part 2 solution", dict_with_occurances[0])

Unrack #647 Dic '20

La segunda parte hay que tratar de ir sacando las permutaciones presentes en la cadena de tipo [1,1,1,3...] de la forma.

spoiler

ciza #648 Dic '20

#645 no lo he medido pero era instantaneo basicamente. De todos modos la lista es muy pequeña.
En ipython me saca en torno a 3ms de tiempo de ejecucion

Fyn4r #649 Dic '20 Inocente

Acabo de leer el de hoy, no me podía creer que la primera parte fuese una parida tan grande xD

Luego me pongo con la segunda

Ranthas #650 Dic '20

Estoy atascado con la segunda:

Si encuentro un elemento que se puede eliminar, entonces tengo 2 permutaciones: está o no está
Si encuentro dos elementos que se pueden eliminar, entonces tengo 4 permutaciones: ab, a, b, o ninguno.
Si encuentro tres elementos "que se pueden eliminar", entonces tengo 7 permutaciones: abc, ab, ac, bc, a, b, c. No puedo quitar los 3 por la restriccion de la diferencia de 3.

Sin embargo, aplicando esta logica, el ejercicio nno me sale....algo se me debe estar escapando

2 respuestas

ciza #651 Dic '20

#650 cuando eliminas uno o dos, puede ser que otro que considerabas que se podia eliminar, ya no se pueda eliminar y te rompa la lógica.

1 respuesta

Unrack #652 Dic '20

#650 Empieza al reves. Si encuentras tres elementos que se pueden eliminar -> Si encuentro un elemento que se puede eliminar.

1 respuesta

Ranthas #653 Dic '20

#651 #652 Lo que hago es crear grupos, es decir, tengo X grupos de 3, Y grupos de 2 y Z grupos de 1. Tengo en cuenta que no se solapen, por ejemplo:

1,4,5,6,7,10 => de ahi sacaria solo un grupo de 2: {5,6}. No puede ser {5,6,7} por el 10, tampoco {4,5,6} por el 1.

Luego multiplico todo, 7^X * 4^Y * 2^Z, para obtener el nº de permutaciones total. Sin embargo me dice que mi solución es menor, por lo que me estoy dejando algo atrás; si fuese mayor, estaría repetidiendo/solapando permutaciones.

Después le doy otro intento

2 respuestas

QuitCat #654 Dic '20 Gafe

#645 Justo me acordé de ese comentario y es lo que apliqué en la segunda parte:

spoiler

Ordeno el array
Lo transformo en un array de "saltos" que se pueden dar desde cada índice [1, 1, 3, 2, 1, ...]
Recorro desde el final hacía el principio (para hacerlo en una pasada solo) apoyándome en un diccionario:

function solveSecond(numbers) {
  const orderedNumbers = [0, ...numbers.sort((a, b) => a - b)];
  const jumpsArray = orderedNumbers.map((x, i) => {
    return canReach(x, orderedNumbers.slice(i + 1, i + 4));
  });
  const map = new Map();
  // Sabemos que f(N) = 1, puesto que el punto final siempre es mayorVoltaje + 3
  map.set(orderedNumbers.length, 1);
  for (let i = jumpsArray.length - 1; i >= 0; i--) {
    let value = 0;
    const jumps = jumpsArray[i];
    for (let j = 1; j <= jumps; j++) {
      value += map.get(i+j);
    }
    map.set(i, value);
  }
  return map.get(0);
}

1

ciza #655 Dic '20

#653 he probado tu solución y funciona bien. Te estas dejando grupos...

1 respuesta

QuitCat #656 Dic '20 Gafe

#653 Acuérdate que se empieza desde 0 pero no está en la lista de voltajes

ciza #657 Dic '20

Con un poco de imaginación, mas las ideas del thread, seguramente esta es la solucion mas criptica ever

spoiler

from functools import reduce
import numpy as np

data = np.loadtxt('input.txt')
data = np.append(data, [-3,0, np.max(data) + 3])
data = np.sort(data)

permutations_dict = {1:1, 2:1, 3:2, 4:4, 5:7}
print(reduce((lambda x,y:x*y), [permutations_dict[i] for i in np.diff(np.where(np.diff(data) == 3))[0]]))

3

Fyn4r #658 Dic '20 Inocente

joe, que forma de escalar la segunda parte xD

Fyn4r #659 Dic '20 Inocente

Dobleposteo para decir que he terminado y tengo la solución más lamentable de la historia para la segunda parte

spoiler

adapters = read_input()

wall_plug = 0
my_device = max(adapters) + 3
adapters_end_to_end = [wall_plug] + adapters + [my_device]

jolts_diff = [y-x for x,y in zip(sorted(adapters_end_to_end)[:-1], sorted(adapters_end_to_end)[1:])]

possible_permutations = [1, 1, 2, 4, 7]
acc = 1
last_range = 0
for i in jolts_diff:
    if i == 1:
        last_range += 1
    elif i == 3:
        acc *= possible_permutations[last_range]
        last_range = 0

Saiko9 #660 Dic '20

Vuelvo a estar al día aunque tenga que hacer el de hoy aun:

Como siempre todo en c++.

dia 8:
https://github.com/Semedi/aoc_2020/blob/main/day8.cpp

dia9:
https://github.com/Semedi/aoc_2020/blob/main/day9.cpp

El dia 8 me ha molado pero mi codigo es una chapuza con bastantes lineas. Si alguien que maneje de c++ le echa un ojo (aunque sea a las estructuras) y me dice si estoy usando los shared_pointers bien se lo agradezco, porque no tengo ni idea xD (los gotos son la motivación máxima que me pedia el cuerpo).

¿Dónde me apunto?

Normas

Leaderboard privado para el pique sano

Las respuestas se postean en Spoiler + code

Usuarios habituales

Tags