Day 24. Lobby Layout
Problem statement
https://adventofcode.com/2020/day/24 (mirror)My solution
For a moment, let’s consider a triplet of unit vectors, as in the following image:
Position of each tile in the hexagonal grid can be described with an offset (α, β, γ) from the origin, i.e. our reference tile. Moving one step east means increasing α coordinate by one, etc.:
e → α++, w → α--, nw → β++, se → β--, sw → γ++, ne → γ--
Example:
nwwswee → nw,w,sw,e,e → β++,α--,γ++,α++,α++ → (α = 1, β = 1, γ = 1)
Of course, such a triplet of coordinates is not a basis in our hex grid – i.e., as mentioned in the problem description, it is possible that two different triplets describe the same tile position, like for example (0, 0, 0) and (1, 1, 1).
Fortunately, we can observe that one step east, one step north-west and one step south-west cancel each other:
So by adding ones to each coordinate (or analogously, subtracting ones from each coordinate), we don’t change the tile:
(α, β, γ) == (α + 1, β + 1, γ + 1) == (α - 1, β - 1, γ - 1)
Therefore we can always transform out triplet (α, β, γ) into a triplet (α - γ, β - γ, 0), which has the final coordinate equal to 0, and which describes the same point. Each tile can be equivalently described by a pair of coordinates.
This time, such pair is a basis! (There is a one-to-one relation between position in hex grid and our pair of coordinates).
To solve Part A, we just need to scan each line, calculate the (α, β, γ) triplet, then calculate the corresponding (α - γ, β - γ) pair, and memorize that pair as a tile to flip. Of course, if a pair is encountered for second time, we flip it back to starting color.
Creating a new TilePosition class was definitely an overkill for this problem, but it works. Each object of this class has both: triplet of coordinates int Alpha, int Beta, int Gamma, which come from scanning the input, and a pair (int, int) EquivClass, calculated internally as Alpha - Gamma and Beta - Gamma.
For Part B, we can simply reuse the solution from day 17 – we just need to adapt it by changing the active neighbour tolerances and update the directions in which we find neighbours in a hex grid. That’s all.