Speeding up my Advent of Code solution with Dijkstra's Algorithm

I haven't yet attempted this year's AOC but I suspect this is one where working backwards from the bottom right and dynamically storing the best value at each cell would work much better than dijsktra.

And initially implemented it naively with wrong data structures. Which of course resulted in implementation working too slow for everything except first toy example.

Then I gradually optimized it bit by bit. I eventually landed on permanently sorted array of nodes to evaluate with simple insertion sort (with linear search) and it became blazing fast.

Along the way I learned the hard way that the heuristic in a* algorithm should never return higher value than the minimal value that that will be actually assigned to the path to destination. That is, if you want algorithm to result in optimal path. Because somehow I missed that when reading about a*.

I had a blast. Advent of code is absolutely wonderful thing.

Dijkstra's algorithm is the algorithm as specified with the runtime characteristics as specified. He wrote a different algorithm which can solve the same problem and works a lot like Dijkstra's but is much slower. Then he finally actually implemented Dijkstra's and the result was the speedup.

The title lead me to believe that he found some way to gain big speedups in Dijkstra's algorithm.

This is like me writing an article about prime factorization and doing naive trial division and then making claims like this when I instead choose to use a sieve.

I was working in Idris. I knew better, but figured the data was small enough that I could just do a linear scan for the next node instead of implementing a heap. In the fast version I ended up using a SortedMap (Int,(Int,Int)) () for the queue.

I only added points to the queue as I discovered them (neighbors of points that I visit), so it maxed out at 913 elements. It sounds like OP may have started out with all points in their queue?

(example: https://github.com/aldanor/aoc-2021/blob/master/src/day15/mo...)

> the possible moves are going right, down or up by one

but the actual problem (https://adventofcode.com/2021/day/15) allows moving in all four directions.

The difference is significant — the naïve attempt described in the article does not work on the actual problem.

The problem as stated in the article is actually quite interesting. The case where the only possible moves are down and right has a standard dynamic programming solution. A variation moving up is also allowed. The time complexity is O(n^2) where n is the grid size, which is faster than using Dijkstra's algorithm.

And regarding the title, I am glad you changed it, but I'd prefer something more similar to the article's new title, such as "Speeding up an Advent of Code solution with Dijkstra's". (At the time of writing, the HN title is "Finding an optimal shortest path algorithm", which doesn't provide much information, and the article's title is "Speeding up my AoC solution by a factor of 2700 with Dijkstra's".)

> [...]

> even if you have the right algorithm, the choice of how you represent auxillary data in the algorithm matters.

I think this is a very useful insight and the core of the piece. It just goes to show how important the layout data is with respect to the algorithm using it.

All steps are of length 1, so you can keep two arrays. In the first one all the things that you are currently visiting and push to the second array the neighbors that you'll visit in the next cycle. Once you are done swap arrays and start over.

But, you just need the sum, not the path. There's no need for a shortest path strategy.