Advent of Code 2020 - Day 17

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

This is Conway's Game of Life (we have seen it before this year), only in higher dimensions. Since parts 1 and 2 just differ by the number of dimensions, we will just build a generic version that works in 2+ dimensions.

We will represent the state using a set of active cells. The input gives us the x and y coordinates for the active cells in the initial state (marked with '#'), and we just add zeros to pad the rest of dimensions.

Next we need to calculate the neighbours of a given cell. The 'steps' from the cell are given by the Cartesian product of {-1, 0, 1} for each dimension, excluding the specific combination (0, 0, ...), which corresponds to the cell itself. This is what we are doing in the line:

deltas = product(*(range(-1, 2) for _ in point))

Then we yield (cell + delta) for each delta, but we skip the zero vector (that's what the if any(delta) is there for). Note that product is itertools.product, which returns an iterator over the Cartesian product of its inputs.

We are now ready to calculate a step of the game. First, we will create a new state to update and return, so that we can refer to the old state throughout; in Game of Life all updates are simultaneous.

Since we are using a sparse representation, we cannot just go over all the board checking the rules, instead we need to explicitly build the set of candidate cells, the ones that may be active in the new state. Given the rules, that includes the currently active cells and their neighbours. A cell that is not neighbouring some currently active cells won't become active.

Then it's only a matter of checking the rules on the candidate cells and adding to the new state the ones that should be active there.

Just run for 6 steps with 3 and 4 dimensions respectively to get the solutions to parts 1 and 2.