Expand description
§Haunted Wasteland
We rely on the input having a very specific structure. Each node ending in A has a
corresponding node ending in Z that forms a cycle. The period of this cycle reaching the
node ending in Z is the LCM of the
length of the directions with the length of the cycle. This
visualization
shows the special structure.
A BFS from each start node finds the length of each cycle. We only need the total length of the directions.
Part one is then a special case of the nodes named AAA and ZZZ. The answer for part two is
the combined LCM of each individual cycle.
To combine the list of LCMs from each path we use the identity:
lcm(a, b, c) = lcm(lcm(a, b), c)
Functions§
Type Aliases§
- Input 🔒