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 once again, only this time on a hexagonal grid. The first part deals with initialization, and the second one with the Game of Life itself.
Part 1
First, we need to decide on a coordinate system for the hexagonal grid. There are multiple approaches, with different tradeoffs, but for something simple as this we can opt for a straightforward one. We will not use the true Cartesian coordinates of the (centres of the) hexagons or the 3-component variants. Instead, we will number the columns so that to adjacent hexagons are separated by two units, allowing for the additional, vertically shifted, column that wedges between them. We do this based on columns because the movement directions are east (e), west (w), north-east (ne), north-west(nw), south-east (se), and south-west (sw); which puts a vertex on top and bottom and edges to the sides. Movements e and w then move 2 steps in the appropiate direction, while ne, nw (se, sw) move one step up (down) and one to the corresponding side.
This part sets the initial field by flipping some tiles. Each time, the specified tile is changed from its white or black state to the opposite, and all start white. The tile is specified as a sequence of e, w, ne, nw, se, sw movements starting from the origin. As we have done several times before, we will use complex numbers to make it very simple to operate with the 2d vectors. The real part grows towards the east, and the imaginary part towards the north. Thus, for instance, nw moves (-1+i).
When reading the sequence of movements we need to disambiguate whether the e's and w's stand on their own or as part of a ne, nw, se, sw movement. Since n and s cannot appear on their own, we can just take the next character (which must be e or w) as part of that movement, and any other e or w that we come across stands alone.
This means that we only have a complete movement on an e or w character. We can accumulate the movement as we go, starting with 0 (no movement). When we find an n or s, we increment the movement by i or -i accordingly; when we find an e or w, we increment by 1 or -1 if there is already some movement (i.e. right after n or s), or by 2 or -2 otherwise. In either case, we return the movement and reset it to 0. If we add up all the movements in the path, we get to the specified tile.
To answer this first part, we just need to count the tiles that were visited an odd number of times, as those are the ones that will be in a different state than at the beginning, therefore black.
Part 2
Now comes the Game of Life. The starting grid is given by part 1. We build it in the code by doing the flipping, but we could also just create a set of the tiles returned in part 1.
With an infinite grid, rather that checking all tiles, which is obviously impossible, we will only check those that can be black in the next step: the ones that are black now, and their neighbours (a white tile that is not adjacent to any black tiles will not become black).
We define the neighbours by adding each potential movement e, w, ne, nw, se, sw. We use this twice: once to determine the candidate tiles, and then again to count the number of black tiles adjacent to each candidate (which could also be calculated as the size of the intersection of the set of black tiles and the set of neighbours). The rest of the logic is trivial, especially after seeing several variants of the game in previous days.
