Module day17 

Clumsy Crucible

Our high-level approach is an A* search. This fantastic blog is a great introduction to this algorithm.

A crucial insight speeds things up. We only need 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 implicitly 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.

Heuristic

The obvious heuristic is the Manhattan distance to the bottom right corner. This never overestimates the actual cost, however it is so weak that the search ends up visiting almost every state in the grid.

Instead we spend a little time up front computing a much sharper bound. Relaxing the puzzle by dropping the straight line rule entirely leaves a plain grid shortest path problem. Any real crucible route is also a valid route in the relaxed problem, so the relaxed distance from each square to the bottom right corner can never exceed the true remaining cost. The relaxed distances are computed once during parsing with a backwards Dijkstra from the bottom right corner then shared with both parts.

Implementation

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.

As the buckets are drained in increasing cost order, an entry is stale if its cost no longer agrees with the bucket it was found in. Checking this skips roughly half the states in part two.

Finally the grid is surrounded by a border of zero cost squares. A square is only worth visiting if it improves on the previous best cost, and nothing improves on zero, so the search can move blindly in a straight line without a single bounds check.

Structs

Input

Constants

BORDER 🔒

Border is the size of the longest possible straight line.

Functions

astar 🔒

Optimized A* search.

dijkstra 🔒

Cost to each square from the bottom right corner if the crucible could turn freely.

parse

Parse the input into a bordered grid then precompute the heuristic shared by both parts.

part1

Search with a maximum of 3 steps in any direction.

part2

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 5%, versus specifying the loop limits as regular parameters.