Advent of Code - Day 22

Here is my solution for Day 22.

I finished part 1 one quickly.

Embarrassingly, I then spent a lot of time on part 2, only to discover that I had a bug in the erosion level calculation. Despite the bug, I got the correct result for both the example and my input for part 1.

When I had fixed the erosion calculation bug, my code for finding the fastest path worked the first time I tried running on the example.

Then, of course, it didn’t finish running on the real input data. I then added a heuristic to prune paths that couldn’t possibly be faster than the already found path.

With that final fix, my program finished in about one and a half minutes.

Here is my take. Part 1 is pretty straightforward. I solved part 2 by doing a breadth-first search in 3D. It finishes in 50sec which doesn’t make me happy, but on the upside, at least it worked in the first attempt. Reading on the reddit thread, I now see that Dijkstra’s algorithm would be the proper solution that would finish much faster. I’m somewhat annoyed that I didn’t even think of it, but such is life I guess

On the flipside I went with Dijkstra straight away, but it took me a considerable amount of time to realize that it cannot be applied as-is. The reason is that the relaxation rule (dist[u] + length(u, v) < dist[v]) breaks because going along the “longer” edge (that is, switching gear) may pay off better in the long run. To solve that, one needs to do a “3D” version of the algorithm, that is, keep the minimum (tentative) distance for each combination of location and gear.

Once I got that down and the example worked, the key thing was to use priority queue in the implementation. Since there is none in the standard lib, I used a plain MapSet+Enum.min_by with the tip from Wikipedia:

Instead of filling the priority queue with all nodes in the initialization phase, it is also possible to initialize it to contain only source ; then, inside the if alt < dist[ v ] block, the node must be inserted if not already in the queue (instead of performing a decrease_priority operation)

With that, I arrived at the solution after a couple of seconds even if I enlarged the cave by plain experimentation so that I could find the globally shortest path.