@Max posted some comments here, but that topic is for days 17, 18, and 19, so I figured a new thread was not useless.
I did it both ways using Breadth-First Search. Ada.Containers.*Queues don’t allow you to sort queues, and I have a vague memory that the last time I tried to use a priority queue it was a slow tool, the wrong tool, or both slow and wrong, so I queued elements up using a vector that I then sorted on each iteration. That … slows … things … … down … … … at least in Part 2, but it still gets the job done. I may revisit this at some point to look at Ada’s priority queue at some point.
Rather than fuss over visualizing a solution to Part 1 as a binary image, I fussed over visualizing it as text in an html page, here.
I wrote a deque and priority queue specifically for advent of code for this reason. Though I also just generally found the standard queues hard to use.
If you’d like to take a look @cantanima or even copy them I don’t mind. I make no guarantees about their quality but they’ve worked great for my aoc solutions.
Deques: spec | body (I’ll be honest this one is a bit quirky with the mod index type. I’ll probably revisit the design at some point, but I ran into a limitation with Ada generics.)
That’s what I thought I remembered, but I didn’t want to find out the hard way. I learned something else the hard way. At least I learned.
That said, I suspect the real slowdown in my code is the repeated sorting on each iteration. Perhaps a linked list would be quicker. I saw a clever approach on Reddit, too: maintain two separate queues: one for points straight ahead, and one for turns. The maze is small enough that the first queue always exhausts before the second. When that happens, swap the queues.
I don’t find the standard queues hard to use – well, not anymore, now that I’ve been using them for 5 years or so – so much as lacking in features. Plus, their terminology doesn’t harmonize with other containers. In particular, in place of .Length and Is_Empty they have .Current_Use.
Thanks, I may do that. I wrote my own a year or two ago for the same reason, and thought of reusing them this year, but when I studied them I didn’t see any feature for priority queues, which seems weird; I was sure they had that. Then again, maybe I’m looking in the wrong place.
For mazes I recycle Dijkstra’s algorithm from a previous solution. A point to be careful about is that the nodes in the graph are identified by the location on the maze and the direction.
For part 2, I did it very “concretely” by putting a road block along an optimal path and by seeing if the algorithm finds another optimal path.
At least I learned.