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