Advent of code: day 17

#adventofcode #python

Day 17: Conway Cubes

The title says it all: we're dealing with Conway's Game of Life. The input is a two-dimensional slice of a three-dimensional grid of "cubes" that can either active or inactive. Cubes change their state in cycles, considering the state of their neighbors. In three-dimensional space, each cube has a total of 26 neighbors (a 3x3x3 integer region in this space). The rules are the general of Conway's game of life:

If a cube is active and exactly 2 or 3 of its neighbors are also active, the cube remains active. Otherwise, the cube becomes inactive.
If a cube is inactive but exactly 3 of its neighbors are active, the cube becomes active. Otherwise, the cube remains inactive.

All the puzzle is asking is how many cubes will be active after 6 cycles.

I borrowed the "neighbors" processing from day 11 adjacent seat calculation and extrapolated for N dimensions. I thought we were either using this in a future puzzle, or there would be more dimensions in part 2.

from itertools import product

def neighborhood(*position: int) -> Iterator[Tuple[int]]:
    """
    Returns all "integer" neighbors of a point in an N-dimensional space.

    >>> for n in neighborhood(0, 0):
    ...     print(n, end=" ")
    ... (-1, -1) (-1, 0) (-1, 1) (0, -1) (0, 0) (0, 1) (1, -1) (1, 0) (1, 1)
    >>> for n in neighborhood(1, 2, 3):
    ...    print(n, end=" ")
    ... (0, 1, 2) (0, 1, 3) (0, 1, 4) (0, 2, 2) (0, 2, 3) (0, 2, 4) (0, 3, 2) # ...
    """
    for diff in product([-1, 0, 1], repeat=len(position)):
        neighbor = tuple(pos + diff[i] for i, pos in enumerate(position))
        yield neighbor

I start by processing the input, saving if they are active (#) or inactive (.) in a dictionary keyed by the point in 3 dimensions

initial = """
####.#..
.......#
#..#####
.....##.
##...###
#..#.#.#
.##...#.
#...##..
""".strip()

space = defaultdict(lambda: ".")
for x, line in enumerate(initial.splitlines()):
    for y, state in enumerate(line):
        cube = (x, y, 0)
        space[cube] = state

Because the space is infinite, cubes for other values of the third-dimension and outside the borders of the input need to be taken into account. Instead of finding the borders of the active nodes, I decided to go over each of the known cubes, and if they are added, I would increment a counter for each of these neighbors. I would end up with more points than the iteration before, and how many of these points have active neighbors.

cube_to_active_count = defaultdict(int)

for cube in space:
    for n in neighborhood(*cube):
        if n == cube:  # don't count the cube itself
            continue
        cube_to_active_count[n] += space[cube] == "#"

As I said earlier, dictionary cube_to_active_count will end up with more points than the space before. For each of those points I can now decide if they are active or inactive given how many of the original space were active. Here's the direct translation of the rules defined above:

for n, count in cube_to_active_count.items():
    if space[n] == "#":
        if count in [2, 3]:
            space[n] = "#"
        else:
            space[n] = "."
    elif space[n] == ".":
        if count == 3:
            space[n] = "#"

After running this 6 times (a simple for _ in range(6)), I just sum up the values of the space dictionary that are equal to the active state char #.

Part 2 of the puzzle just asked for running the same 6 cycles, but now in a four-dimensions space! No change was needed to the neighborhood calculation, so that was a win. I needed to change the input parsing to allow for another dimension:

 space = defaultdict(lambda: ".")
 for x, line in enumerate(initial.splitlines()):
     for y, state in enumerate(line):
-        cube = (x, y, 0)
+        cube = (x, y, 0, 0)
         space[cube] = state

Then I just copied the code verbatim from part 1 and got to the correct answer. It was taking a couple of seconds to run though, given that now we are growing the space in each cycle due to each cube now adding at most 80 cubes to the "known" space state.

I noticed that I was just counting active cubes in the first for loop to find the affected neighbors, adding a lot of references to new points but only saying these had 0 active cubes around them. So I edited the code to skip neighbor processing of inactive cubes (the majority of the iterations), and with a couple of adjustments, I had a solution running in 0.3 seconds. I then generalized it as well to run for multiple dimensions, with some nice tricks to parse the input. Here's the full code for the cycle:

def full_cycle(initial: str, dimensions: int) -> int:
    space = defaultdict(lambda: ".")
    padding = (0,) * (dimensions - 2)
    for x, line in enumerate(initial.splitlines()):
        for y, state in enumerate(line):
            cube = (x, y) + padding
            space[cube] = state

    for _ in range(6):
        cube_to_active_count = defaultdict(int)

        for cube in space:
            if space[cube] == ".":
                continue
            for n in neighborhood(*cube):
                # neighborhood contains cube and all its neighbors.
                # `cube_to_active_count[n] += n != cube` ensures
                # active cubes without active neighbors are counted
                # and proper deactivated by underpopulation in the
                # next for-loop.
                cube_to_active_count[n] += n != cube and space[cube] == "#"
        for n, count in cube_to_active_count.items():
            if space[n] == "#":
                if count in [2, 3]:
                    space[n] = "#"
                else:
                    space[n] = "."
            elif space[n] == ".":
                if count == 3:
                    space[n] = "#"

    return sum(state == "#" for state in space.values())

print("--- part 1 ---")
print(full_cycle(initial, 3))
print("--- part 2 ---")
print(full_cycle(initial, 4))

There are a couple of tricks to decrease the line count around the check if a cube becomes active or inactive, but it wouldn't add much in terms of performance. I'm pretty happy with this solution!