Module day15 

Chiton

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

The simplest possible heuristic in A* is to make no estimate at all, making the search behave the same as Dijkstra’s algorithm. With that heuristic, the search frontier visits nearly every tile, since only a few tiles near the target might have a total risk higher than the target itself. Slightly better is a heuristic of the Manhattan distance to the target, although this still underestimates and prunes no more than 5% of the total search space. Logically this makes sense: Manhattan distance only changes by 1 per tile, but with risks between 1-9, the average risk is closer to 5, and our best path averages closer to 3 risk per tile. But we can do much better with a heuristic that prunes about 75% of the search space, by assigning a value within 2% of the actual cost for each node. In the long run, it is faster to visit all 250,000 to set up a fairly close estimate which lets us prune the search space to under 60,000 nodes, than it is to skip the heuristic but have a search space near 250,000 nodes, since the effort of searching is less predictable than the effort to compute the heuristic.

The heuristic we use builds up an estimate for the minimum cost incurred from each node to the destination. The target itself starts with its risk level. Then for every diagonal line of tiles, starting next to the target and ending next to the origin, a given tile’s estimate is chosen to be its own risk level plus the minimum of the tile below, the tile to the right, or the minimum Manhattan distance to reach any other tile on the same diagonal with a better estimate. Building this up requires traveling each diagonal twice (the first pass captures any better tiles below and left, the second pass captures any tiles above and right). Allowing other tiles on the same diagonal to influence the current tile’s estimate covers the case where the optimal path moves up or left around an obstacle. Failure to consider the ability to reach other tiles on the same diagonal via an unseen path that loops around a wall would result in a heuristic that is not admissible in A*. At the same time, without actually verifying whether same-diagonal tiles can actually be reached in the estimated Manhattan distance, the heuristic is no longer perfectly consistent, which means in practice we can sometimes see a neighbor point inserted into the work queue with a priority one less than the current tile.

With our heuristic, the maximum possible increase in risk is 9, compounded with the maximum jump in the estimate table of another 9. A circular array of 32 buckets (for bitwise math windowing) can handle our empirical range of -1 to 18 in the set of active buckets, and we avoid having to allocate memory as the search gradually shifts the active window of buckets.

Structs

Square

Functions

astar 🔒

Implementation of A* algorithm without using the decrease-key functionality.

build_estimates 🔒

parse

part1

Search the regular size grid.

part2

Create an expanded grid then search.