Note: This topic is to talk about Day 21 of the Advent of Code.
For general discussion about the Advent of Code 2018 and links to topics of the other days, see this topic.
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.
1 Like
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.
