Advent of Code, día 17

¡La vida en 3D o más!

El puzzle de hoy se me ha dado bien. Lo he leído en el móvil cuando no tenía el ordenador delante (estaba esperando a que saliera mi hija de clase de música), y creo que el ratito que ha pasado hasta que he podido empezar a escribir el código me ha venido muy bien para tener un par de intuiciones claras e ir directamente a la solución buena.

Parte 1

Desde el primer momento he tenido claro que NO había que representar explícitamente el espacio infinito. También tenía la intuición de que habría más celdas vacías que llenas, por lo que he pensado que solo debía representar las celdas llenas:

• cada celda es una tupla con sus coordenadas
• el “mundo” es un set() de las celdas que están ocupadas (o activas)

Cada iteración consiste en calcular el estado del mundo en el instante posterior a partir del estado del mundo en el instante actual.

Otra intuición importante es que — teniendo en cuenta las reglas de activación/desactivación de celdas — en cada iteración solo pueden cambiar las celdas que están ocupadas y sus celdas vecinas.

Con estos ingredientes ya podemos escribir el código:

NEIGHBOURS = [
    (i, j, k) 
    for i in (-1, 0, 1) 
    for j in (-1, 0, 1) 
    for k in (-1, 0, 1) 
    if not i == j == k == 0
]
BLOCK = NEIGHBOURS + [(0, 0, 0)]

def neighbours(cell, deltas):
    for delta in deltas:
        yield (
            cell[0] + delta[0], 
            cell[1] + delta[1], 
            cell[2] + delta[2]
        )


def solve(input):
    world = set()
    for i, row in enumerate(input.strip().split('\n')):
        for j, cell in enumerate(row):
            if cell == '#':
                world.add((i, j, 0))

    for cycle in range(6):
        seen = set()
        next_world = set()
        for active_cell in world:
            for nearby_cell in neighbours(active_cell, BLOCK):
                if nearby_cell in seen:
                    continue
                seen.add(nearby_cell)
                count = sum(
                   neigbr in world 
                   for neigbr in neighbours(nearby_cell, NEIGHBOURS)
                )
                if count == 3 or \
                              (count == 2 and nearby_cell in world):
                    next_world.add(nearby_cell)
        world = next_world

    return len(world)

Tengo dos listas de “deltas” precalculadas: una con los vecinos de una celda NEIGHBOURS y otra con los vecinos y la propia celda BLOCK. Así el cálculo de cuántas celdas adyacentes están ocupadas es un poco más sencillo evitando los 3 bucles anidados.

En cada iteración, tomo todas las celdas ocupadas y sus vecinas (que son las que pueden cambiar de estado) y aplico las reglas del enunciado para saber si las tengo que añadir al estado futuro next_world.

Además voy llevando la cuenta de las celdas que ya he examinado en esta iteración (en seen) para revisarlas una sola vez (confieso que no he medido el impacto de esta optimización, tal vez prematura).

Una última ventaja de usar un “set” con las celdas activas es que la respuesta al puzzle es inmediata: el tamaño del set.

Tiempo de ejecución para 6 iteraciones = 66ms

Parte 2

Para la parte 2 me esperaba que el enunciado nos pidiera hacer 60.000 millones de iteraciones o algo similar… pero Eric siempre nos sorprende con algo nuevo: ¡una nueva dimensión!

Afortunadamente el código es fácilmente extensible para 4 dimensiones con pocos cambios (en negrita):

NEIGHBOURS = [
    (i, j, k, l)
    for i in (-1, 0, 1)
    for j in (-1, 0, 1)
    for k in (-1, 0, 1)
    for l in (-1, 0, 1)
    if not i == j == k == l == 0
]
BLOCK = NEIGHBOURS + [(0, 0, 0, 0)]


def neighbours(cell, deltas):
    for delta in deltas:
        yield (
            cell[0] + delta[0],
            cell[1] + delta[1],
            cell[2] + delta[2],
            cell[3] + delta[3]
        )


def solve(input):
    world = set()
    for i, row in enumerate(input.strip().split('\n')):
        for j, cell in enumerate(row):
            if cell == '#':
                world.add((i, j, 0, 0))

    for cycle in range(6):
        seen = set()
        next_world = set()
        for active_cell in world:
            for nearby_cell in neighbours(active_cell, BLOCK):
                if nearby_cell in seen:
                    continue
                seen.add(nearby_cell)
                count = sum(
                  neigbr in world 
                  for neigbr in neighbours(nearby_cell, NEIGHBOURS)
                )
                if count == 3 or \
                              (count == 2 and nearby_cell in world):
                    next_world.add(nearby_cell)
        world = next_world
    return len(world)

Con 4 dimensiones, el código tarda un poquito más (2.5seg) para calcular la respuesta correcta.

La solución completa aquí: https://github.com/jabadia/adventOfCode2020/tree/main/d17