Module day08

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

parse

part1

part2

Type Aliases

Input 🔒