aoc::year2024

Module day06

Source
Expand description

§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§

Functions§

  • is_cycle 🔒
  • Count distinct positions in the guard’s path, which will eventually leave the grid.
  • Follow the guard’s path, checking every step for a potential cycle.
  • worker 🔒