Advent of Code 2020 - Day 11

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.

Part 1

This puzzle is a small modification of Conway's Game of Life. There are lots of implementation, sites, and information of all kinds on this topic. The main changes is that the voids (the dots in the input) have to be considered as dead, and can never become alive; that translates into considering them dead, and skipping them in the update.

For the implementation, we will move directly to part 2, as they can be refactored together. Obviously, this was done after the fact originally, but the changes were not too large. The one point worth mentioning is the use of tuples to represent the board, and keeping the previous state to check when the system stabilizes. Also, having a non-mutable data structure ensures that we don't give in to the temptation of updating it in-place, which would result in erroneous updates.

Part 2

The difference in this part is that the voids do not count for the neighbourhood structure; instead, the first seat following the direction is the neighbour (unless the end of the matrix is reached before a seat).

The state update at each step and checking for the repeating state do not need additional comment. They are quite straightforward. The only part that is relatively tricky is defining the neighbours for each cell.

For that, we will make use of the symmetry of the neighbouring relation, visit each cell and add it as a neighbour to each cell that it 'sees' as a neighbour. We start by defining the 8 possible directions as the tuple of row and column increment of a step in that direction. We will store the neighbours in a defaultdict with the row, column pair identifying each cell as keys and the set of corresponding neighbours as values. The defaultdict(set) will helpfully provide an empty set when we first try to add a neighbour.

So we iterate over rows and cols. For void cells, we just skip to the next one; they are not neighbours to anyone (which is equivalent to counting them as dead, since we evaluate the number of live neighbours for the state change). For seats, we take each direction, and start stepping in that direction. We break out of the loop after the first step for part 1 (that's the condition of the while), if we step out of bounds of the board, or if we reach a seat. In the latter case, we add the current cell as a neighbour of that seat.