Module aoc::year2021::day15

Chiton

Traversing a graph with different non-negative edge weights is a job for the classic Djisktra’s algorithm, explained really well in the linked blog post.

To speed things up we use a trick. Classic Djisktra uses a generic priority queue that can be implemented in Rust using a BinaryHeap. However the total cost follows a strictly increasing order in a constrained range of values, so we can use a much faster single purpose data structure instead.

The maximum possible increase in risk in 9, so we create an array of 10 vecs. The current list of items to process is at risk % 10 and each new item is added at risk % 10 + new_cost. Once we have processed the current risk level we clear the vec to avoid having to reallocate memory.

Structs

• Square

Functions

• dijkstra 🔒
  Implementation of Dijkstra’s algorithm without using the decrease-key functionality.
• parse
• part1
  Search the regular size grid.
• part2
  Create an expanded grid then search.