Segunda semana del Advent of Code. En esta semana ya hemos tenido algunos problemas muy interesantes. Intentaré comentarlos de la mejor manera posible. Todo el código está aquí y en este otro post comenté mis soluciones de la primera semana.

Día 8

El día 8 se nos propone un problema de grafos también. Básicamente se nos define un árbol, donde cada nodo puede tener hijos y metadatos. En la primera parte nos piden sumar todos los metadatos.

Aquí al contrario que en el día 7, no voy a usar networkx. Era más difícil adaptar networkx al problema que hacer el árbol a mano. Uno de los puntos complicados de este problema es el parseo de la entrada, que hice de forma recursiva. Cada nodo es un diccionario con las propiedades tamaño, una lista de metadatos y una lista de nodos hijo.

En la segunda parte se define el concepto de valor de nodo y como calcularlo. También es bastante sencillo de implementar. Finalmente hacemos un recorrido por el árbol de tipo primero en anchura (BFS) con una deque de Python.

from collections import deque
def read_node(start,numbers):
    length = 2
    child_nodes = numbers[start]
    metadata_entries = numbers[start+1]
    children = list()
    while child_nodes > 0:
        child_node = read_node(start+length,numbers)
        children.append(child_node)
        length += child_node["length"]
        child_nodes -= 1
    metadata = list()
    while metadata_entries > 0:
        metadata.append(numbers[start+length])
        length += 1
        metadata_entries -= 1
    node = dict([("length",length),("metadata",metadata),("children",children)])
    return node

def read_file(file):
    with open(file) as f:
        line = f.readline()
    numbers = [int(x) for x in line.split()]
    G = read_node(0,numbers)
    return G
def node_value(N):
    if len(N["children"]) == 0:
        return sum(N["metadata"])
    else:
        s = 0
        for i in N["metadata"]:
            if i-1 < len(N["children"]):
                s += node_value(N["children"][i-1])
        return s
        
def day8(file):
    G = read_file(file)
    to_visit = deque()
    to_visit.append(G)
    metadata_sum = 0
    while len(to_visit) > 0:
        N = to_visit.popleft()
        metadata_sum += sum(N["metadata"])
        to_visit.extend(N["children"])
    print("METADATA SUM: %d" % metadata_sum)
    print("NODE VALUE: %d" % node_value(G))

Día 9

Este día fue muy interesante. Se nos explica un juego, que consiste en ir añadiendo canicas en una circunferencia y cuando el número de canica que añadimos es múltiplo de 23, obtenemos puntos y quitamos una canica 7 puestos por detrás.

Aquí tuve una mala decisión de diseño ya que al principio quise hacer esto con una lista de Python (el equivalente a vector en otros lenguajes de programación). La idea era sencilla y funcionaba hasta que llegó la parte 2. La parte 2 te pedría calcular los puntos teniendo en cuenta 100 veces más canicas. Esto fue un grave problema para mi código. Calculo que tardaría 6 horas en calcularlo, pero antes optimicé. La optimización consistía en usar una lista circular doblemente enlazada. ¿Esto qué es? Se trata de una lista enlazada, doblemente, porque cada nodo tiene referencia al elemento siguiente y al anterior. Y es circular porque ambos extremos están unidos. Esto permite las inserciones y borrados en O(1). Además los movimientos relativos (en este problema todos son así) son extremadamente sencillos. La implementación de esta estructura de datos en Python es muy sencilla (en otros lenguajes es más complicado). No me molesté en hacer funciones que me hiciesen sencilla la vida y las conexiones/desconexiones las hago a mano directamente en el código del problema.

from collections import defaultdict
class Marble:
    def __init__(self,value,left=None,right=None):
        self.value = value
        self.left = left
        self.right = right
        if self.left == None:
            self.left = self
        if self.right == None:
            self.right = self

def day9(PLAYERS,LAST_MARBLE):
    SCORE = defaultdict(lambda: 0)
    player = 0
    marble = 0
    current_marble_pos = 0
    current_marble = None
    while marble <= LAST_MARBLE:
        if marble > 0 and marble % 23 == 0:
            SCORE[player] += marble
            pivote = current_marble.left.left.left.left.left.left.left
            SCORE[player] += pivote.value
            pivote.left.right = pivote.right
            pivote.right.left = pivote.left
            current_marble = pivote.right
        else:
            if current_marble == None:
                current_marble = Marble(marble)
            else:
                current_marble = Marble(marble,current_marble.right,current_marble.right.right)
                current_marble.left.right = current_marble
                current_marble.right.left = current_marble
        player += 1
        player = player % PLAYERS
        marble += 1
    return max(SCORE.values())

Curiosamente, en la propia librería de Python deque tiene una operación llamada rotate que permite hacer este problema en poquísimas líneas y de forma muy eficiente. Pero desconocía la existencia de esa función (que lo que hace es mover la "cabeza" de la lista enlazada que es deque).

Día 10

Este problema es muy interesante. Se nos da una serie de puntos que van moviéndose por la pantalla. En un determinado momento estos puntos se juntan y forman un mensaje en pantalla.

Aquí lo interesante no es mover los puntos, eso es trivial, simplemente es sumar la velocidad cada vez las coordenadas. Lo interesante es saber cuando parar. Existen varias ideas:

• Revisión humana de cada iteración
• Comprobar que no haya puntos separados del resto (con grafos)
• Comprobar que el área de concentración de puntos es mínima

Y alguna más. Para el ejemplo la primera idea servía. Pero en la prueba real, era más complicado. A mí se me ocurrió la tercera opción, la cuál es bastante eficiente. En cada iteración calculamos el área que contiene a todos los puntos, cuando ese área ya no se reduce más, hemos llegado al mensaje.

import re
def read_file(file):
    stars = list()
    p = re.compile("position=<([ -][0-9]+), ([ -][0-9]+)> velocity=<([ -][0-9]+), ([ -][0-9]+)>")
    with open(file) as f:
        lines = f.readlines()
    for line in lines:
        m = p.match(line.strip())
        try:
            pos_x = int(m.group(1))
        except:
            print(line)
        pos_y = int(m.group(2))
        vel_x = int(m.group(3))
        vel_y = int(m.group(4))
        stars.append([pos_x,pos_y,vel_x,vel_y])
    return stars
def print_stars(stars):
    stars = sorted(stars,key=lambda x: x[0],reverse=True)
    min_width = stars[-1][0]
    max_width = stars[0][0]
    min_height = min(stars,key=lambda x: x[1])[1]
    max_height = max(stars,key=lambda x: x[1])[1]
    s = str()
    for j in range(min_height,max_height+1):
        p = [star for star in stars if star[1] == j]
        for i in range(min_width,max_width+1):
            if len(p) == 0:
                s += "."
            else:
                if any(map(lambda star: star[0] == i and star[1] == j,p)):
                    s += "#"
                else:
                    s += "." 
       s += "\n"
    return s
def step(stars):
    a = map(lambda x: [x[0]+x[2],x[1]+x[3],x[2],x[3]],stars)
    return list(a)
# LA RESPUESTA CORRECTA TIENE AREA MINIMA

def area(stars):
    stars = sorted(stars,key=lambda x: x[0], reverse=True)
    min_width = stars[-1][0]
    max_width = stars[0][0]
    min_height = min(stars,key=lambda x: x[1])[1]
    max_height = max(stars,key=lambda x: x[1])[1]
    area = (max_width-min_width)*(max_height-min_height)
    return area
def day10(file):
    stars = read_file(file)
    a = area(stars)
    steps = 0
    while area(step(stars)) < a:
        stars = step(stars)
        steps += 1
        a = area(stars)
    print_stars(stars)
    print(steps)

La parte de dibujado me costó y ahí tuve un fallo que me costó media hora aproximadamente en resolver. Una mejor opción, pero que no se me ocurrió, hubiese sido usar Pillow y crear una imagen. Es mucho más fácil que dibujar sobre una terminal (y posiblemente más rápido).

Día 11

Para este problema hay 3 posibles algoritmos. En la primera parte nos piden que de una matriz extraigamos el cuadrado de 3x3 con mayor valor. La matriz hay que construirla pero es trivial. Yo decido usar un diccionario, con clave la tupla de coordenadas. Vamos recorriendo todas las posiciones y calculamos el valor. Ahora para buscar el cuadrado, simplemente vamos probando todos los posibles cuadrados.

En la segunda parte nos dicen que bsuquemos el cuadrado máximo pero el tamaño puede ser cualquiera. Aquí con la fuerza bruta ya tarda demasiado. Mi solución fue usar programación dinámica, para ello la clave pasa a tener un valor más, el tamaño del cuadrado. Cuando creamos la tabla estamos asignando valor al cuadrado 1x1 de posición X,Y. Representado es la tupla (x,y,1). Según vamos avanzando hasta 300x300 vamos guardando los resultados intermedios, de modo que podamos reutilizarlos. Por ejemplo, el valor de (x,y,4) solamente es la suma de (x,y,2), (x+2,y,2), (x,y+2,2) y (x+2,y+2,2). Evidentemente esto solo funciona en los tamaños pares. En los tamaños impares decidí coger el cuadrado de dimensión inmediatamente menor y calcular los laterales con los cuadrados de tamaño 1. Este sistema funciona mucho mejor que la fuerza bruta pero es lento. Los profesionales usaron el algoritmo Summed Area Table (del que desconocía su existencia). Este algoritmo es el óptimo para este problema.

def generate_fuel(x,y,idg):
    fuel = (((x+10)*y)+idg)*(x+10)
    fuel %= 1000 
    fuel = (fuel // 100) - 5
    return fuel
def generate_table(idg):
    fuel = {(x,y,size):0 for x in range(1,301) for y in range(1,301) for size in range(1,301)}
    for x in range(1,301):
        for y in range(1,301):
            fuel[(x,y,1)] = generate_fuel(x,y,idg)
    return fuel
def find_best(fuel):
    max_point = [-1,-1]
    max_score = -1
    for x in range(1,301):
        for y in range(1,301):
            if x+3 > 301 or y+3 > 301:
                continue
            score = fuel[(x,y,1)]+fuel[(x+1,y,1)]+fuel[(x+2,y,1)]+fuel[(x,y+1,1)]+fuel[(x+1,y+1,1)]+fuel[(x+2,y+1,1)]+fuel[(x,y+2,1)]+fuel[(x+1,y+2,1)]+fuel[(x+2,y+2,1)]
            if score > max_score:
                max_score = score
                max_point = [x,y]
    return max_point[0],max_point[1]
def find_best_any_size(fuel):
    max_score = -1
    max_point = [-1,-1,-1]
    for size in range(2,300+1):
        for x in range(1,301):
            for y in range(1,301):
                if x+size > 301 or y+size > 301:
                    continue
                if size % 2 == 0:
                    mid = size // 2
                    fuel[(x,y,size)] = fuel[(x+mid,y,mid)]+fuel[(x,y+mid,mid)]+fuel[(x+mid,y+mid,mid)]+fuel[(x,y,mid)]
                else:
                    fuel[(x,y,size)] = fuel[(x,y,size-1)]
                    for i in range(x,x+size-1):
                        fuel[(x,y,size)] += fuel[(i,y+size-1,1)]
                    for j in range(y,y+size-1):
                        fuel[(x,y,size)] += fuel[(x+size-1,j,1)]
                    fuel[(x,y,size)] += fuel[(x+size-1,y+size-1,1)]
                score = fuel[(x,y,size)]
                if score > max_score:
                    max_score = score
                    max_point = [x,y,size]
    return max_point[0],max_point[1],max_point[2]
def day11():
    fuel = generate_table(1133)
    x,y = find_best(fuel)
    print("BEST POINT: %d,%d" % (x,y))
    x,y,size = find_best_any_size(fuel)
    print("BEST POINT ANY SIZE: %d,%d,%d" % (x,y,size))
if __name__ == "__main__":
    day11()

Día 12

El día 12 me trajo recuerdos de un algoritmo con el que me peleé mucho, el denominado HashLife. El problema es un autómata celular unidimensional. Las reglas vienen dadas como patrones. La única diferencia es que hay que guardar su posición para luego calcular un número. La primera parte es bastante sencilla.

import re
from collections import defaultdict

def read_file(file):
    rules = defaultdict(lambda: ".")
    rule_prog = re.compile("([.#]+) => ([.#])")
    with open(file) as f:
        lines = f.readlines()
    state = lines[0].split(": ")[1].strip()
    for line in lines[2:]:
        m = rule_prog.match(line.strip())
        rules[m.group(1)] = m.group(2)
    return state,rules

def parse_state(pots):
    state = dict()
    for i,p in enumerate(pots):
        state[i] = p
    return state

def find(rules,current):
    if current in rules:
        return rules[current]
    else:
        size = len(current)
        mid = size // 2
        left = find(rules,current[0:mid])
        right = find(rules,current[mid:])
        rules[current] = left + right
        return rules[current]


def iter(state,rules):
    new_state = dict()
    xmin = min(state.keys())
    xmax = max(state.keys())
    for x in range(xmin-2,xmax+3):
        current = ("%c%c%c%c%c" % (
                    state.get(x-2,"."),
                    state.get(x-1,"."),
                    state.get(x,"."),
                    state.get(x+1,"."),
                    state.get(x+2,".")
                    ))
        new = rules[current]
        if new == "#" or xmin <= x <= xmax:
            new_state[x] = new
    return new_state

def sum_pots(state):
    n = 0
    for pot in state:
        if state[pot] == "#":
            n += pot
    return n

def print_state(state):
    xmin = min(state.keys())
    xmax = max(state.keys())
    s = str("XMIN %d : " % xmin)
    for x in range(xmin-2,xmax+3):
        s += state.get(x,".")
    print(s)


def day12(file):
    state,rules = read_file(file)
    state = parse_state(state)
    for i in range(20):
        #print_state(state)
        state = iter(state,rules)
    #print_state(state)
    n = sum_pots(state)
    return n

if __name__ == "__main__":
    day12("input.txt")

La segunda parte nos pedía lo mismo pero para el número ¡50000000000! Inmediatamente pensé en optimizarlo de forma similar a HashLife. La idea consiste en almacenar patrones mayores a los de las reglas (que son todos de tamaño 5), para poder evitar cálculos innecesarios.Además añadí un recolector de basura para ir eliminando por la izquierda las celdas inútiles.

No obstante, y aunque es muchísimo más eficiente, sigue sin ser capaz de procesar tal bestialidad de número en un tiempo razonable.

Y he aquí lo que me ha cabreado, porque no he podido sacarlo. A partir de cierto momento, el dibujo siempre es el mismo pero desplazándose a la derecha. De modo que el valor del siguiente paso siempre es la suma de una constante. Finalmente modifiqué el código para que buscase una situación en la que el número fuese resultado de una suma de una constante. Una vez hecho eso, calcula con una multiplicación lo que valdría cuando llegase a 50000000000.

import re
from collections import defaultdict

XMIN = -2

def find(rules,current):
    if len(current) < 5:
        return ""
    if current in rules:
        return rules[current]
    elif len(current) == 5:
        return "."
    else:
        size = len(current)
        left=find(rules,current[0:size-1])
        right=find(rules,current[size-5:])
        rules[current] = left+right
        return rules[current]

def read_file(file):
    rules = defaultdict(lambda: ".")
    rule_prog = re.compile("([.#]+) => ([.#])")
    with open(file) as f:
        lines = f.readlines()
    state = lines[0].split(": ")[1].strip()
    for line in lines[2:]:
        m = rule_prog.match(line.strip())
        rules[m.group(1)] = m.group(2)
    return state,rules


def print_state(state):
    print(state)

def sum_pots(state):
    n = 0
    for i,c in enumerate(state):
        if c == "#":
            n += i + XMIN
    return n

def day12(file):
    global XMIN
    state,rules = read_file(file)
    XMAX = len(state)+1
    state = "..%s.." % state
    sums = list()
    i = 0
    while len(sums) < 3 or sums[-1]-sums[-2] != sums[-2]-sums[-3]:
        state = find(rules,"..%s.." % state)
        if state[0] == "." and state[1] == "." and state[2] == "." and state[3] == ".":
            state = state[2:]
            XMIN += 2
        if state[0] == "#" or state[1] == "#":
            state = "..%s" % state
            XMIN -= 2
        if state[-1] == "#" or state[-2] == "#":
            state = "%s.." % state
        sums.append(sum_pots(state))
        i += 1
    diff = sums[-1]-sums[-2]
    missing = 50000000000 - i
    n = missing*diff + sums[-1]

    return n

Y con esto pude finalmente calcular el resultado.

Día 13

El día 13 teníamos unas vías de tren. En estas vías había unos trenecitos que se desplazaban siguiendo unas normas. El objetivo en la primera parte era conocer el donde se producía el primer choque.

from PIL import Image

XMAX = 0
YMAX = 0
STEP = 0

nextDirection = dict()
nextDirection["start"] = "left"
nextDirection["left"] = "center"
nextDirection["center"] = "right"
nextDirection["right"] = "left"

def relative_direction(original,movement):
    print("CROSS")
    if movement == "center":
        return original
    if original == "v":
        if movement == "left":
            return ">"
        else:
            return "<"
    elif original == ">":
        if movement == "left":
            return "^"
        else:
            return "v"
    elif original == "^":
        if movement == "left":
            return "<"
        else:
            return ">"
    else:
        if movement == "left":
            return "v"
        else:
            return "^"

def day13(file):
    global XMAX
    global YMAX
    global STEP
    plano = dict()
    carts = list()
    with open(file) as f:
        lines = f.readlines()
    YMAX = len(lines)
    XMAX = len(lines[0])
    for y,line in enumerate(lines):
        for x,char in enumerate(line):
            # SI HAY UN CARRITO, DEDUCIR TIPO DE VIA
            if char == "^" or char == "v" or char == "<" or char == ">":
                if (x,y-1) in plano:
                    plano[(x,y)] = "|"
                else:
                    plano[(x,y)] = "-"
                carts.append([x,y,char,"left"])
            else:
                plano[(x,y)] = char
    
    end = False
    while not end:
        carts.sort(key=lambda x: x[1])
        carts.sort(key=lambda x: x[0])

        for cart in carts:
            # CHECK CRASH
            for crt in carts:
                if cart[0] == crt[0] and cart[1] == crt[1] and id(cart) != id(crt):
                    print("CRASH AT %d-%d" % (cart[0],cart[1]))
                    end = True
            try:
                x = cart[0]
                y = cart[1]
                print(cart)
                if cart[2] == ">":
                    if plano[(x+1,y)] == "/":
                        cart[2] = "^"
                    elif plano[(x+1,y)] == "\\":
                        cart[2] = "v"
                    elif plano[(x+1,y)] == "+":
                        cart[2] = relative_direction(cart[2],cart[3])
                        cart[3] = nextDirection[cart[3]]
                    cart[0] += 1
                elif cart[2] == "<":
                    if plano[(x-1,y)] == "/":
                        cart[2] = "v"
                    elif plano[(x-1,y)] == "\\":
                        cart[2] = "^"
                    elif plano[(x-1,y)] == "+":
                        cart[2] = relative_direction(cart[2],cart[3])
                        cart[3] = nextDirection[cart[3]]
                    cart[0] -= 1
                elif cart[2] == "^":
                    if plano[(x,y-1)] == "/":
                        cart[2] = ">"
                    elif plano[(x,y-1)] == "\\":
                        cart[2] = "<"
                    elif plano[(x,y-1)] == "+":
                        cart[2] = relative_direction(cart[2],cart[3])
                        cart[3] = nextDirection[cart[3]]
                    cart[1] -= 1
                elif cart[2] == "v":
                    print()
                    if plano[(x,y+1)] == "/":
                        cart[2] = "<"
                    elif plano[(x,y+1)] == "\\":
                        cart[2] = ">"
                    elif plano[(x,y+1)] == "+":
                        cart[2] = relative_direction(cart[2],cart[3])
                        cart[3] = nextDirection[cart[3]]
                    cart[1] += 1
            except:
                breakpoint()
        STEP += 1
        print_train(plano,carts)

def print_train(plano,carts):
    im = Image.new("RGB",(XMAX,YMAX))
    for x,y in plano:
        if plano[(x,y)] != " ":
            im.putpixel((x,y),(255,255,255))
        if plano[(x,y)] == "+":
            im.putpixel((x,y),(120,120,120))
    for cart in carts:
        if cart[2] == ">":
            im.putpixel((cart[0],cart[1]),(255,0,0))
        elif cart[2] == "<":
            im.putpixel((cart[0],cart[1]),(0,255,0))
        elif cart[2] == "^":
            im.putpixel((cart[0],cart[1]),(0,0,255))
        else:
            im.putpixel((cart[0],cart[1]),(0,120,120))

    im.save("train-%d.png" % STEP,"PNG")

if __name__ == "__main__":