Day 17 was a modified version of Conway’s Game of Life, played across three and four dimensions, where a cells state in the next time step is determined by the its current state and the state of its neighbors.

Challenge

The puzzle can be found here. The puzzle input is a two dimensional grid where a space is either inactive (.) or active (#). There are rules for how cells propagate in time based on the neighboring cells. If the space is active and has two or three neighbors active, it remains active. If a cell is inactive and has three neighbors active, it becomes active. Otherwise, the cell becomes inactive. This is a variation on Conway’s Game of Life.

In each part, I’m asked to step out six steps. In part one, I’ll handle the space as three dimensional, and in part two, four dimensional.

Solution

Part 1

I decided to keep my list in a set of coordinates rather than nesting arrays, which I was happy with when I say part two. First step is to read in the data and create the initial set:

with open(sys.argv[1], 'r') as f:
    raw_in = f.readlines()

cells = set()

for y,line in enumerate(raw_in):
    for x,cell in enumerate(line):
        if cell == '#':
            cells.add((x,y,0))

Now I’ll create a step function, but first two helper functions. get_bounds returns the outside edges of a set in each dimension:

def get_bounds(cells):
    res = []
    for i in range(3):
        res.append(min(cells, key=lambda x: x[i])[i] - 1)
        res.append(max(cells, key=lambda x: x[i])[i] + 2)
    return res

get_n_count returns the number of neighbors that are active given a point and a set:

def get_n_count(x, y, z, cells):
    res = 0
    for dx in range(-1,2):
        for dy in range(-1,2):
            for dz in range(-1,2):
                if not (dx == dy == dz == 0) and  ((x+dx, y+dy, z+dz) in cells):
                    res += 1
    return res

With those two, the step function is:

def step(cells):
    bounds = get_bounds(cells)
    next_cells = set()
    for x in range(bounds[0], bounds[1]):
        for y in range(bounds[2], bounds[3]):
            for z in range(bounds[4], bounds[5]):
                ns = get_n_count(x,y,z, cells)
                if (x,y,z) in cells and (ns == 2 or ns == 3):
                    next_cells.add((x,y,z))
                elif (x,y,z) not in cells and ns == 3:
                    next_cells.add((x,y,z))
    return next_cells

Now I can step through six times and return the length:

p1 = cells.copy()
for _ in range(6):
    p1 = step(p1)

print(f'Part 1: {len(p1)}')

This is not instant, but runs in 0.2 seconds, so fast.

Part 2

For part two, the fastest thing would be to completely copy the previous code and just edit it to just solve part two. I’ll actually update it so that it can still solve both. To do this, first I’ll try to solve part one but where everything is working in four dimension. To do that, for part one, I’ll just let every point have a w = 0.

Now reading in the data adds a forth coordinate to each point:

for y,line in enumerate(raw_in):
    for x,cell in enumerate(line):
        if cell == '#':
            cells.add((x,y) + (0,) * 2)

get_bounds now collects four pairs:

def get_bounds(cells):
    res = []
    for i in range(4):
        res.append(min(cells, key=lambda x: x[i])[i] - 1)
        res.append(max(cells, key=lambda x: x[i])[i] + 2)
    return res

I completely refactored get_n_count to use a list comprehension:

def get_n_count(point, cells):
    dim = len(point)
    diffs = product([-1, 0, 1], repeat=dim)
    return sum(
        [
            tuple([x1 + x2 for x1, x2 in zip(d, point)]) in cells
            for d in diffs
            if d != tuple([0] * dim)
        ]
    )

Now for step, I will have it loop over the min/max w bounds like the other coordinates in 4D, but for 3D I’ll just always have w be 0:

def step(cells, d=3):
    bounds = get_bounds(cells)
    next_cells = set()
    w_range = [0] if d == 3 else range(bounds[6], bounds[7])
    for x in range(bounds[0], bounds[1]):
        for y in range(bounds[2], bounds[3]):
            for z in range(bounds[4], bounds[5]):
                for w in w_range:
                    ns = get_n_count((x,y,z,w), cells)
                    if (x,y,z,w) in cells and (ns == 2 or ns == 3):
                        next_cells.add((x,y,z,w))
                    elif (x,y,z,w) not in cells and ns == 3:
                        next_cells.add((x,y,z,w))
    return next_cells

With that in place, I can check that my original loop over part one still returns the correct answer, and then add the solution to part two:

p1 = cells.copy()
for _ in range(6):
    print(len(p1))
    p1 = step(p1)

print(f'Part 1: {len(p1)}')

p2 = cells.copy()
for _ in range(6):
    p2 = step(p2, d=4)

print(f'Part 2: {len(p2)}')

Final Code

The code is slower now, as part one still takes less than a second, but part two takes 17 seconds:

$ time python3 day17.py 17-puz
Part 1: 230
Part 2: 1600

real    0m17.353s
user    0m17.343s
sys     0m0.004s

#!/usr/bin/env python3

import sys
from itertools import product


def get_bounds(cells):
    res = []
    for i in range(4):
        res.append(min(cells, key=lambda x: x[i])[i] - 1)
        res.append(max(cells, key=lambda x: x[i])[i] + 2)
    return res


def step(cells, d=3):
    bounds = get_bounds(cells)
    next_cells = set()
    w_range = [0] if d == 3 else range(bounds[6], bounds[7])
    for x in range(bounds[0], bounds[1]):
        for y in range(bounds[2], bounds[3]):
            for z in range(bounds[4], bounds[5]):
                for w in w_range:
                    ns = get_n_count((x, y, z, w), cells)
                    if (x, y, z, w) in cells and (ns == 2 or ns == 3):
                        next_cells.add((x, y, z, w))
                    elif (x, y, z, w) not in cells and ns == 3:
                        next_cells.add((x, y, z, w))
    return next_cells


def get_n_count(point, cells):
    dim = len(point)
    diffs = product([-1, 0, 1], repeat=dim)
    return sum(
        [
            tuple([x1 + x2 for x1, x2 in zip(d, point)]) in cells
            for d in diffs
            if d != tuple([0] * dim)
        ]
    )


with open(sys.argv[1], "r") as f:
    raw_in = f.readlines()

cells = set()

for y, line in enumerate(raw_in):
    for x, cell in enumerate(line):
        if cell == "#":
            cells.add((x, y) + (0,) * 2)

p1 = cells.copy()
for _ in range(6):
    p1 = step(p1)

print(f"Part 1: {len(p1)}")

p2 = cells.copy()
for _ in range(6):
    p2 = step(p2, d=4)

print(f"Part 2: {len(p2)}")