Module day17

Two Steps Forward

Brute force search over every possible path. Work is parallelized over multiple threads. Keeping each thread busy and spreading the work as evenly as possible is quite tricky. Some paths can dead-end quickly while others can take the majority of exploration time.

To solve this we implement a very simple version of work stealing. Threads process paths locally, stopping every now and then to return paths to a global queue. This allows other threads that have run out of work to pickup new paths to process.

The approach from “Waiting: Parking and Condition Variables” in the excellent book Rust Atomics and Locks prevent idle threads from busy looping on the mutex.

Structs

• Exclusive 🔒
• Shared 🔒
• State 🔒

Functions

• explore 🔒
  Explore at most 100 paths, stopping sooner if we run out. 100 is chosen empirically as the amount that results in the least total time taken.
• extend 🔒
  Convenience function to generate new path.
• parse
• part1
• part2
• worker 🔒
  Process local work items, stopping every now and then to redistribute items back to global pool. This prevents threads idling or hotspotting.

Type Aliases

• Input 🔒
• Item 🔒