[2023 Day 17] In Review (Clumsy Crucible)

[u/musifter]

The lava is flowing again, and so the reindeer gives us a parachute and we return to Gear Island. Now we need to get the lava from the base of the lavafall to the parts factory, with minimal cooling, using hard to control crucible carts. And so we get a path search problem.

The input is a digit grid (141x141 in my input), with the digits 1-9 representing the cost (temperature loss) of crossing it. Just eyeballing the input it's easy to again see an ASCII art circular structure, and sure enough we have the large numbers more concentrated towards the middle, and the lower ones on the edges. There is no 0, so that's available if you want it for sentinels. And I do like my sentinel rings (only needed left and bottom for Perl and other languages with wrap around).

For part 1, our crucible can only move up to 3 tiles before needing to make a 90 degree turn (and reversing is not allowed). For part 2, it's an ultra crucible which must move at least 4 tiles and up to 10.

I remember this one well. First thought is that it's easy to build a state machine to do that movement. But then I thought that this is an intensive search, I'm going to want Dijkstra/A*, and I'm going to need to carry that state around. So after taking a break to think and put the tea on (it looked like it might take a while, but it didn't), I thought, "Is is really so bad to have a ply of 6?". And the answer is no... we'd get that sort of ply if we were doing this with moves in the 8 cardinal directions (backwards isn't allowed, leaving 7). And we wouldn't think twice then.

One thing to be careful about with large moves is jumping over a sentinel ring... that wasn't a problem for my code, because I generated them with a loop that takes one step at a time (even for part 2, where it just doesn't queue the first 3). You could also just make the ring thicker if you wanted to, or just go with checking the co-ordinates.

And so the idea was to queue moves for each range all at once. But you'd need the direction so you don't do a second move along it, or its reverse. And so then things coalesce... our atomic move is actually "turn and move a distance". The moves alternate between horizontal and vertical. And it eventually hit me that this is very much like splitters from yesterday... it doesn't matter exactly which direction you come into a tile, only the parity (horizontal or vertical), because there are only 2 sets of moves out. It doesn't matter if you came in from the left or right, every option from that point is the same. So the visit space is just 141x141x2.

I did throw in the basic heuristic of Manhattan distance to the end for my Perl solution. It doesn't really do anything though (times are the same). Especially for part 2, where as the examples showed, being too close is a problem, and your're going to need to loop around (and so it can be detrimental). And so I left that out when I did the Smalltalk solution. This is also one of the problems where my own Heap/Priority queue in Smalltalk outperforms the built in SortedCollection (14s to 16s).

The queue sizes max out at less than 6000 for part 1 and about 44000 for part 2. Which is a good sign, even with the large ply for part 2. An out-of-control queue size is typically a sign that your search space is too large and you're not pruning enough.

So this was a very nice problem... it's more about thinking about things than the algorithm. That's typically what makes a good search problem.

[u/terje_wiig_mathisen]

This one kept my subconcious thinking all night, not because it was hard to solve in Perl back then, but because my Rust is still an order of magnitude slower than u/maneatingape.

I am using a priority queue based on total loss up to the current cell (so effectively BFS), with manhattan as a tie breaker. My code still carries around the loss value in the seen[] array even though I only need two bits there now. I don't think that would make a huge difference...

I need to figure this out before I can look at his solution! :-)

[u/terje_wiig_mathisen → u/terje_wiig_mathisen]

I updated my code to only use [u8] for the seen[] array, that made it almost 50% faster. Any Dijkstra/A* version will have to go back to storing a lot more state at every cell, right?

32 bits as a pair of u16s for the minimum loss seen at this location+hor/vert does work, but I was stuck at the really bad remaining distance heuristic.

Filling in a second array with min_distance_remaining from a reverse single-step BFS seems like a very good idea: Still not correct, but guaranteed to not underestimate.

[u/DelightfulCodeWeasel]

Higher dimension A* for me on this one, encoding search state as [x, y, direction, moves left]. Priority is heat lost and the heuristic is just simple Manhattan, but now I'm wondering if there's a way to adapt an area sum table or a couple of prefix sum tables as min tables for better heat loss estimates. 

I don't remember this one taking super long, so I've not even looked at the queue sizes yet, but I suspect they might not be great: encoding moves left and single stepping rather than having all movement lengths as neighbours is likely going to balloon out the visited cache more than necessary.

[u/Boojum → u/DelightfulCodeWeasel]

I took the same approach in terms of single steps and that particular priority and search state, except pure Djikstra rather than bothering with A*.

Though it seems like Manhattan should at least be a decent trivially-valid A* admissible heuristic for heat loss? You're always going to have a minimum heat loss of one per step, and there's no chance of that overestimating the remaining heat loss either. I wouldn't be surprised if simple Manhattan proves tough to beat as a heuristic.

[u/maneatingape → u/Boojum]

I'm experimenting with using a reverse relaxed Dijkstra from the end to the start, instead of Manhattan. (Relaxed = Allows you to make change direction at any point). This is strictly equal or better than the constrained crucible so should be an valid admissible metric.

The stronger heuristic cuts my time in half. Code is a mess at the moment, will clean it up and push later today.

EDIT: Benchmark went from 2.4ms to 1.1ms.

[u/e_blake → u/maneatingape]

I did precisely that in my m4 solution - an unconstrained Dijkstra from the end back to the start (shareable between parts 1 and 2) gave me a MUCH better A* heuristic for the subsequent two searches from the start to the end with constraints applied.

[u/DelightfulCodeWeasel → u/maneatingape]

Since you can only lose a maximum of 9 heat in a single step it might be worth experimenting with bucketed BFS instead of Dijkstra for the reverse search. I've had good results with bucketing on previous problems; each of the 9 10 queues are cache coherent and you're skipping the heap queue/dequeue entirely.

[u/musifter → u/Boojum]

The problem with it is that it offers such a weak estimate... the numbers are typically 2-9x larger that you're counting, and the movement rules make getting too close worse at times. So it might be better to not waste time on a heuristic at all. Dijksta performs pretty much the same for me as Manhattan A* already.

So the question is can you do a more accurate heuristic, using precalculation and tables like some people did with the Chiton problem.

[u/DelightfulCodeWeasel → u/musifter]

From the numbers you posted above (~33,000 max queue size) I think it'll be worth me spending some time to find a tighter heuristic. I can encode search state in 4 bytes for a queue size of ~130KiB, but that doesn't leave me a lot of breathing room. A 25% reduction would make things a lot more comfortable, if that's possible.

[u/Boojum → u/musifter]

Fair. And that sort of thing is why I don't think I've ever bothered with A* for AoC. One more potential source of bugs (in the heuristic), and if Dijkstra isn't fast enough then I probably have bigger issues elsewhere.

(And FWIW, my Part 2 max queue size is 6858.)

[u/DelightfulCodeWeasel → u/DelightfulCodeWeasel]

Something like h[x, y] = loss[x, y] + min(h[x+1, y], h[x, y+1]) feels like it might work. Going to have to give it a go over lunch.

EDIT: that does of course assume you're only ever going right or down for the shortest path, and I'm not totally sure that's valid.

EDIT 2: unless I just run a BFS across the whole of the grid starting from the end as a pre-step... That's not going to take all that long, and might pay off if it accelerates the A* enough.

[u/musifter → u/DelightfulCodeWeasel]

I decided to take a look at what the queue sizes were with Dijkstra, and they're only ~4300 and ~33000. That shows the disadvantage to pressing too much to the goal with this one.

EDIT: That gave me a little idea... I tried adding +3 to the distance if it's less than 4. That actually gives a bit of an improvement.

[u/e_blake]

My git history show that it took me over 24 hours to get my second star, with 50 seconds runtime, but by January, I had improved the runtime to just under 6 seconds by improving the A* heuristic to be the unconstrained (ie. turn allowed at any tile) Dijkstra distance from the end, rather than a Manhattan distance that vastly underestimates. This is one of my longest-running solutions for the year.

[u/TheZigerionScammer]

I reused a bunch of my code from 2021-15 when I did this one while modifying it for the extra restrictions and got a sharp lesson in technical debt when I did part 2, because I missed the part where the cart also had to travel 4 spaces before it can stop at the goal and was getting an answer that was too low at first. It took me analyzing the examples very closely before I realized what was wrong.

A couple days afterwards I decided to rewrite it from the ground up with the movement restrictions in mind and it worked a lot better. In my first program I had to keep track of position, direction, and distance traveled in the search space (for a total of 141 x 141 x 10 x 4 nodes) but in my second program I wrote the search similar to yours where it only had to consider the location and horizontal/vertical parity, and instead of advancing one step at a time it would add all of the locations you can reach from a square into the queue at once, which I called hopping in my program. Doing this would have also not introduced the Part 2 bug I encountered with my first program.