Hello everyone, it’s time for your Advent of Code 2021 Day 15 cruise log. Today I dumbed down a bit. I could have wrapped this up so fast, but I decided to unsuccessfully try to reinvent a well-known algorithm. One that I hadn’t implemented since my early school days. Definitely not something I’m able to do with a 6 am brain.
In today’s challenge, we basically have to load an integer grid and find the shortest path from the top-left point to the bottom-right one. First, I copied the code from my day 9 solution including the position inner class. That way I had the integer grid loaded and positions ready to use for the exploring.
From there the actual work was to figure which algorithm to use. Obviously, the only algorithm that fits is Dijkstra. Still, as the proud coding nagger that I am, I chose to try and reinvent the wheel. And I almost got there! Within half-an-hour I had something half-decent but not quite there.
After twenty more minutes of shenanigans, I decided to google Dijkstra’s algorithm and I found the pseudocode on Wikipedia. Then, I translated the pseudocode into java to fit into the monstrosity that I created.
Funnily enough, there was only one missing bit. I was not updating the distance correctly as in I never removed values from the stack which is dumb. Very dumb indeed but it’s what you get when you try and reinvent such an algorithm at 6 am with no coffee. One should know better by now. But at last, my code is passing the part one unit test and grants me my first star of the day.
Since I didn’t face enough challenges aside from my own hubris, part two messed with my brain. I could have taken a break after that algorithm fiasco. That would have been the perfect time to get some water, a coffee, clear my mind with a brisk walk outside. But nope, as the hibernation bear I am, I remained in my man cave to code some more.
That part was about creating a bigger grid by using the input as a tile to a bigger grid which would be five times bigger than the original. The tricky part is that each value from the other tiles have some derived transformation going on. After getting my first stab at it, I realised that my bigger grid didn’t quite match the sample data. My grid would only reproduce the first five lines rather than all ten.
After a bit more time, I realised that I used the wrong y modulo to apply my transformation from a tile to the next. I used the transformation multiplier rather than the height of my original grid. Classic scrambled brain. After fixing that, I got a good looking grid but the wrong answer.
Now I know that my pathfinding code using Dijkstra works perfectly so the issue has to come from the newly generated grid. Looking once more at the examples, I notice that there is some kind of subtraction going on to fit the derived values under ten.
Since I’m still in scrambled brain mode, I some modulo in there but still no luck. The test remains red but with a different flavour of failure. Another look at the example data makes me notice that there is no zero in there. This means that modulo is out of the question. After some more analysing, I realise that I only need to subtract nine to the value if it goes above nine. I manually check on the example data and it checks out.
Now I run the test once more, it still fails but the debugging print reveals that the horizontal transformations work but not the vertical ones. In order to wrap this up, I decided to split the logic to implement the vertical tile transformations separately from the first line of tiles. A few minutes later the part two test turned greed. My thirstiest star is at arm’s length and I grab it as I should. Let’s hope I learn from this for tomorrow.
Thank you for reading my Advent of Code 2021 Day 15 log, I will see you tomorrow. As usual, I will push the code to my repo for this year on Github. Feel free to check out my Day 14 log right here.
Photo by cottonbro from Pexels
