How to speed up a shortest route algorithm

Advanced Topics Advanced Help with Snap!
1

I've been trying to solve AoC 2023 day 17. It involves a shortest-route kind of puzzle, that can be modeled as a network of almost 40,000 nodes and up to 6 (part 1) or even 14 (part 2) outgoing links per node. So it's ... really big.

As it happened I wrote a shortest-route block in Snap! some time ago, based on Dijkstra's algorithm. As it turned out, it was far to slow to solve the problem within reasonable time (and it contained a bug, too). So I improved and optimized it (The code was updated, see post #6. The old version is still there within the same project. Look all the way down the main script to find the call to the algorithm), but it's still rather slow: solving the AoC 2023/17 puzzles will take many hours, if not a full night (and what if another bug surfaces?).

I identified a few parts that probably use a lot of runtime. Does anyone have suggestions for improvement?

AoC 2023_17 Snap! Forum script pic (1)
AoC 2023_17 Snap! Forum script pic (1)922×1111 183 KB

2

a bit off topic, (and does not help your problem at all) but why is day 20 between day 7 and 8?
image

3

Yeah, that really is off-topic.
Perhaps the problem of day 24 is going to be where day 25 is going to be located, based on the previous order of days. :smirk:

4

Slightly off-topic but heat-map of my test data, for value 1, has a large hole at the center

Costume (1)
Costume (1)568×564 4.19 KB

Maybe it can be useful as a hint to reduce initial data set.

.

Heat Map script pic (3)
Heat Map script pic (3)854×218 28.8 KB

5

So ... you're saying that there are no values "1" in a circle-shaped middle part of the puzzle input data? I agree that it's peculiar, and I don't know, of course, how this came about ... but it's of no apparent use for speeding up calculations, I'm afraid.
If you have any suggestions for improving the code, I'm open for it :slight_smile:

6

I did some thinking and experimenting myself. The code is so much faster now (somehow the link will not load; you may follow the project link in my Original Post).

If you’re looking for an efficient Snap! implementation of Dijkstra’s shortest route algorithm, look no further :smirk:

The most important change was replacing very frequently repeated operations involving KEEP, MAP, and FIND FIRST …with (equally frequently used) operations involving ITEM OF and INDEX OF.

Further suggestions are still welcomed, of course.