Advent of Code, día 24

El juego de la vida en una grid hexagonal

El matemático John H. Conway, inventor del Juego de la Vida, falleció en Abril de 2020 por culpa del COVID-19. Tal vez por esa razón este año Eric Wastl ha incluido varios puzzles relacionados con el juego de autómatas celulares que inventó.

En este caso, es una variante del juego sobre un mundo de celdas hexagonales. Habiendo resuelto ya varios puzzles similares (día 11, y día 17), conviene recordar las claves:

• no representar explícitamente un espacio infinito
• usar un set() de coordenadas para representar las celdas activas
• encontrar de forma eficiente las celdas que pueden mutar en cada iteración (las celdas activas y sus vecinas)

La variante hexagonal no cambia estos principios. Únicamente tenemos que encontrar un sistema de coordenadas practicable:

• cada celda tiene unas coordenadas únicas
• podemos encontrar fácilmente los vecinos a una celda dada

Hay un excelente artículo sobre grids hexagonales https://www.redblobgames.com/grids/hexagons/ que propone varios sistemas de coordenadas que podemos utilizar. En mi caso elegí las coordenadas “cúbicas”: cada celda tiene 3 coordenadas que deben sumar 0.

Sistema de coordenadas para una grid hexagonal de https://www.redblobgames.com/grids/hexagons/#coordinates-cube

Parte 1

Hay una pequeña complicación en el parseo de los movimientos: algunos tienen un carácter y otros dos. Una forma de hacer el parseo más sencillo es reemplazar los tokens por tokens de 1 carácter para facilitar el parseo:

E = '1'
SE = '2'
SW = '3'
W = '4'
NW = '5'
NE = '6'

y entonces podemos hacer

steps = (line
    .replace('se', SE).replace('sw', SW)
    .replace('nw', NW).replace('ne', NE)
    .replace('e', E).replace('w', W)
)

Cada dirección es un delta (en el sistema de coordenadas hexagonal)

DIRECTIONS = {
    E: (+1, -1, 0),
    SE: (0, -1, +1),
    SW: (-1, 0, +1),
    W: (-1, +1, 0),
    NW: (0, +1, -1),
    NE: (+1, 0, -1),
}

Y la función de desplazamiento, parecida a la del día 12 sin nada especial, excepto verificar que se cumple la suposición del sistema de coordenadas x+y+z == 0:

def move(pos, step):
    new_pos = (pos[0] + step[0], pos[1] + step[1], pos[2] + step[2])
    assert sum(new_pos) == 0
    return new_pos

Una vez calculadas las coordenadas de cada punto, lo añadimos o quitamos del set() para activar o desactivar la celda:

def solve(input):
    black = set()
    for line in input.strip().split('\n'):
        steps = (line
            .replace('se', SE).replace('sw', SW)
            .replace('nw', NW).replace('ne', NE)
            .replace('e', E).replace('w', W)
        )
        pos = (0, 0, 0)
        for step in steps:
            pos = move(pos, DIRECTIONS[step])

        if pos in black:
            black.remove(pos)
        else:
            black.add(pos)

    return len(black)

Part 2

Para resolver la parte dos, tenemos que iterar 100 veces en el “juego de la vida” hexagonal.

...
for i in range(100):
    black = next_gen(black)
    print(i, len(black))
return len(black)

Y la función para calcular la siguiente generación es prácticamente idéntica al código del día 17

def next_gen(black):
    seen = set()
    next_black = set()
    for tile in black:
        for nearby_tile in neighbours(tile, BLOCK):
            if nearby_tile in seen:
                continue
            seen.add(nearby_tile)
            count = sum(
                neighbour in black 
                for neighbour in neighbours(nearby_tile, NEIGHBOURS)
            )
            if (nearby_tile in black and 1 <= count <= 2) or \
               (nearby_tile not in black and count == 2):
                next_black.add(nearby_tile)
    return next_black

Penúltimo puzzle completado, ya se ve el final…

El código completo aquí: https://github.com/jabadia/adventOfCode2020/tree/main/d24