Advent of Code 2020

Menos mas que estos ultimos estan siendo faciles, asi puedo aprovechar para hacer todos los del finde que me entro toda la pereza y hasta entonces los llevaba todos al dia

Cuanto os tarda la parte 2 de hoy? Estoy utilizando maps para guardame la informacion y no tener que ir lista arriba, lista abajo, pero aun asi me tarda unos 5s, que aunque no es mucho no se porque se me antoja demasiado teniendo en cuenta que la complejidad es lineal xD

Si usamos de input inicial 0,1 tenemos lo que se llama la secuencia de Van Eck. Para esa secuencia esta demostrado que hay un numero infinito de ceros, que por su propia naturaleza no pueden ser consecutivos, por lo que significa que estaremos viendo infinitos numeros diferentes, asi que no puede haber loops. La proof esta en el link, es facil de seguir

http://oeis.org/A181391

#796 No sólo tienes que dar por sentado que es única, sino que han sido tan amables de hacerlo de forma que

Me he vuelto LOCO porque estaba multiplicando las posiciones entre sí, y no los valores correspondientes a esas posiciones en mi ticket. Sabía que la solución estaba bien, no entendía qué estaba pasando.

Dejo código chapucero de la parte 2

dict={}
validnumbers=np.array([])
for i in range(len(input)):
    if input[i] != 'your ticket':
        if input[i][0] in numberlist:
            [a,b,c,d]=[int(x) for x in re.findall(numbers,input[i])]
            dict[input[i-1]]=np.r_[a:b+1,c:d+1]
            validnumbers=np.concatenate((validnumbers, np.r_[a:b+1,c:d+1] ), axis=None)
    else:
        break
        

alltickets={}
alltickets[0]=[int(x) for x in input[i+1].split(',')] #My ticket
ticketsize=len(alltickets[0])

ticketnumber=1
for k in range(i+3,len(input)):
    ticket=[int(x) for x in input[k].split(',')]
    for n in range(len(ticket)):
        if ticket[n] not in validnumbers:
            break
        if n==len(ticket)-1:
            alltickets[ticketnumber]=ticket
            ticketnumber+=1
            

positiondict={}
for field in dict.keys(): 
    positiondict[field]=[]
    for position in range(ticketsize):
        for t in range(ticketnumber): 
            if int(alltickets[t][position]) not in dict[field]:
                break
            if t==ticketnumber-1: 
                positiondict[field].append(position)      

max=ticketsize
while max>1:
    for field in positiondict.keys():
        if len(positiondict[field])==1:
            number=positiondict[field][0]
            for field2 in positiondict.keys():
                if number in positiondict[field2]:
                    positiondict[field2].remove(number)
            positiondict[field].append(number)
    max-=1
    

result=1
for key in positiondict.keys():
    if 'departure' in key:
        result*= alltickets[0][positiondict[key][0]]
print(result)

#798 donde tú ves bipartire matching y lib de grafos yo veo 5 nested loops

Entretenido el de hoy.
Creo que este año son más fáciles que el año pasado. He ojeado alguno de 2019 a estas alturas, y ni me he enterado del enunciado

#798 Ahora que lo has dicho esta claro que tipo de problema es. Para la parte 2 del dia 8 implemente el algoritmo de Edmonds-Karp por lo que solo tendria que haberlo adaptado un poco, pero ni me he dado cuenta de que era un grafo bipartido. Por el otro lado, creo que me habria costado mas adaptar el codigo que hacerlo con los loops

@fyn4r añademe a la lista, user en el AoC y en github es Daverlo

#804 Mas que maxflow lo plantee como mincut. Monte un grafo donde los nodos son las instrucciones y hay una arista a->b si b se ejecuta despues de a (ya sea porque es la siguiente o porque hay un jump). En ese grafo habran minimo dos "componentes" una que contiene la primera instruccion y otra la ultima.

En el grafo incluyo tambien las aristas "complementarias", que son las que habrian si se cambia un noop por un jump y viceversa. Por la definicion del problema, al añadir estas aristas, ya deberia haber un camino entre la primera y la ultima instruccion. Poniendo las aristas complementarias con capacidad 1 y el resto 100, me aseguro que el mincut solo contenga aristas complementarias.

Esa es la teoria, pero... en la practica no funciono como me esperaba. Pensaba que el mincut contendria solo la solucion correcta, pero no cai en que si habia un camino alternativo cambiando varias instrucciones tambien formarian parte del mincut. Como ya lo tenia implementado simplemente lo hice por fuerza bruta en el conjunto reducido que devuelve.

https://github.com/Daverlo/aoc-2020/blob/master/src/days/day8/main.go

Bueno día 16 done, sin pena ni gloria, a base de pico y pala, ya que como habéis dicho el enunciado deja que desear.

He empezado asumiendo que no habría posiciones que cuadrasen en varias reglas, y me ha petado el assert de solo 6 "departure" fields. Debuggeando un poco he visto enseguida lo que comentaba #797, siempre hay una regla que solo encaja en una posición. Con un loop que de varias pasadas hasta ir encontrando la regla más restrictiva va que chuta.