AoC - Day 17

:date: 2023-12-17 12:00

This was my waterloo.

First some personal history. When I was in the autonomous boat business, there was someone involved who would vacuously insist that the whole key to getting a boat to drive by itself was "A-star". What was clear to me was that the A-star path finding algorithm requires one to know a great deal about the situation  —  for example, where exactly are the navigable places? All bets are off if they're moving. But before one can even entertain those lofty thoughts, when it comes to field robotics like self-driving boats, one must first have a way to effect the boat. It doesn't matter if A* or some other algorithm has an idea of where you should go if your boat has no agency to go there. A* is commonly used for game pathfinding because if you want a monster to go to a certain point, you update its coordinates and it is there! After a lot of very hard work and finally getting to the stage where we (well, me personally single-handedly) had created a navigation system that could put the boat where it was told to go... The project was canceled.

I never forgot about A* and have always wanted to see it do something useful outside of video game NPC pathfinding. When I saw the challenge for day 17, I recognized it as a perfect application of the A* algorithm in a neat and tidy situation. Or at least that's what I thought. Since I'm interested in having a high performance implementation of this algorithm, I made the fateful decision to give it a go in C.

I already had the grid loading ready. The tricky thing was managing open and closed node lists. I made a simple linked list structure for that. But then you need to implement a way to search through the lists and extract some arbitrary node which involves juggling pointers and special cases for the ends. Ok, fine. Did all that. Then I spent a good many hours on some bug where something wasn't handling the lists quite right. Eventually though, I had all the infrastructure in place. I was basically on the starting line where I'd have been had I just used Python.

But now days had gone by since I started and since I'd read the puzzle description carefully. I spent most of my energy trying to get an A* algorithm correctly implemented and I feel that, after much effort, I pretty much did that. I then looked at the puzzle description again and saw the limitation of no more than 3 moves in one direction. Ouch. That is quite the complication it turns out. Trying to retrofit this back into my code was extremely ugly. I also took some measures to prevent moving to nodes that the agent just came from (also noted from reading the instructions carefully), however in hindsight I realize that A* should never have this problem. However with my hindsight in hindsight, I suppose the agent could juke over and then back just to avoid the 3 move rule. So... very, very ugly.

What was very disappointing was that my solution found the target, but it failed to follow the rules, and it failed to minimize the cost function. Here's a look at the correct solution which solves it in 102.

And here is my solution which clocks in at 127 (higher is worse). Note that it has streaks longer than 3 despite checks for this very thing.

I could debug the 3 streak thing but at this point I'd sunk so much time into this that any more would go far beyond ridiculous. I'll have to settle for a kind of A* algorithm sort of working. Here is an image of what my code does to the full data set (in 42 seconds on my laptop).

Is that for sure the best path? Well, it's not terrible. Just for a sanity check here's one where I contrived to make some zones worse (9) than others (1).

And it seems to do pretty much the right thing from an A* perspective. Why my checks for continuous runs aren't effective, I don't know but since it deeply disturbs the A* algorithm (without some serious redesign) I just called it a loss for the puzzle. Perhaps still a win for getting some practice with A* algorithms in C.