Expand description
§Clumsy Crucible
Our high level approach is an A* search. This fantastic blog is a great introduction to this algorithm.
The heuristic is the Manhattan distance to the bottom right corner. This will never overestimate the actual distance which is an essential characteristic in the heuristic.
A crucial insight speeds things up. We only needs to store (position, direction) pairs in
the map of previously seen costs and do not also need to store the number of steps.
The reason is that each time we generate new states from the current state we loop over all
possible forward states. This implicitly means that every new state will always make a left or
right turn, alternating between horizontal and vertical movements.
It’s a little more subtle but we also don’t need to store 4 directions but only 2, horizontal and vertical. The reason is similar to not encoding the number of steps. As we are always implictly going to make a left or right turn immediately, entering a square from the opposite direction is equivalent. This reduces the storage space and time by half.
To speed things up even further we use a trick. Classic A* 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
bucket queue. The maximum possible increase in
heuristic is 10 * 9 from heat plus 10 for the distance change for a total of 100 buckets.
Functions§
- astar 🔒Optimized A* search.
- Parse the input into a 2D grid of
u8then convert tou32for convenience. - Search with a maximum of 3 steps in any direction.
- Search with a minimum of 4 and maximum of 10 steps in any direction. Using const generics to specify the limits allows the compiler to optimize and unroll loops, speeding things up by about 25%, versus specifying the loop limits as regular parameters.