Expand description
§Mode Maze
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 target. This will never overestimate the actual distance, which is an essential characteristic of the heuristic. Interestingly, benchmarking showed that adding the time to switch tools if we don’t have the torch to the heuristic slowed things down.
The various input files all have a target with a first coordinate less than 20, and a
second coordinate between 700 and 800. It is slightly faster to swap the coordinate system
to treat the first coordinate as the number of rows (height), and the second as the number of
columns (width), since memory is more efficient with row-major iteration and cross-row motion
when rows are short (the rest of this file generally avoids the terms x and y to minimize
confusion in relation to the puzzle statement).
Part two needs a larger grid than part one, but pre-populating the larger grid during the parse avoids repeated work for the portion of the grid used by both parts.
Using A* instead of Dijkstra results
in a 6x speedup on an unconstrained grid. This is because Dijkstra explores the grid evenly
in both axes, so if the target is 700 deep, then we will explore an area roughly 700 x 700
in size. In contrast, A* prefers reducing the distance to the target, exploring a narrower
area approximately 130 x 700 in size. On the other hand, use of an unconstrained grid does
unnecessary work, since all known input files can be solved with a grid of width 80. The smaller
grid benefits Dijkstra more than A*, although A* remains faster. The state is a tuple of
(location, tool) in order to track the time per tool separately.
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 range of the increase is from
0 (moving toward the target and not changing tools) to 7 (staying put and changing tools),
requiring 8 buckets total.
Structs§
Constants§
- BUCKETS 🔒
- SLOP_
HEIGHT 🔒 - SLOP_
WIDTH 🔒 - Amount of slop beyond the target to include in the grid. Too little, and this will miss paths that can take a detour to avoid a tool swap. Too large, and this will waste time exploring additional points in the frontier that end up not affecting the shortest path. The values picked here match empirical testing against multiple known input files, although it is conceivable that an alternative cave depth may need a larger height.
- TORCH 🔒
- The index of each tool is the tool that cannot be used in that region, for example Rocky => 0 => Neither, Wet => 1 => Torch, and Narrow => 2 => Climbing Gear.