Module day06

Guard Gallivant

Part two is sped up by pre-computing the next obstacle in each direction from any point in the grid. If there is nothing left in the way then coordinates outside the grid are used. One dimensional example:

    .#...
    Left: (-1, 2, 2, 2, 2)
    Right: (1, 1, 5, 5, 5)

This allows us to “shortcut” to each obstacle when looking for cycles. The remaining tricky part is including the extra obstacle which is different for each point on the guard’s path.

The search can be parallelized across multiple threads as each position is independent.

Structs

Shortcut 🔒

Functions

is_cycle 🔒

parse

part1

Count distinct positions in the guard’s path, which will eventually leave the grid.

part2

Follow the guard’s path, checking every step for a potential cycle.

worker 🔒