Hello everyone, it’s time for your Advent of Code 2021 Day 12 cruise log. Today we go exploring caves and figuring paths. Let’s jump into it!
First things first, the problem statement scrambled my brain for a bit. Anytime there is some sort of graph, the hardest part is figuring what data structure would work best. After that, you need to figure what algorithmic shape might help you solve this in the easiest manner.
In today’s case, the problem statement mentions figuring the best path from a start node to an end node. Reading further, you realise that you actually need to count all the possible paths while following certain rules. Some nodes you can visit an infinite amount of times and others you can visit only once. From there, I figured the best way to represent our graph would be to map all nodes using their label as key against all potential destinations.
Once I got that part right, I ran the first unit test in debug mode to ensure the map looked right. All was good. From there I wrote my bit of recursion with some validation to filter out which nodes could be visited from the rules we got. I ran the sample input unit test and it worked right away. No ifs nor buts it was just green. A surprise to be sure, but a welcome one. One star down, one to go.
Since I cruised through part one with ease, I actually expected part two to enter me into a world of pain. Now we could still visit small caves exactly once per path found with the exception of one. Exactly one small cave could be visited once. It took me about a literal minute to wrap my head around that mind. Then it hit me like Zeus’ thunder in Smite, I could change my recursive pathfinding method to add a boolean value. A boolean to let me know whether I already visited a small cave twice.
At this point, my thoughts ran through my fingers onto the keyboard. I typed faster than Katarina mains press R and within a couple of minutes and a tiny tweak, the code felt ready. Just to make sure it behaved as I expected I updated the first part code to use that method and it worked! The first part unit test was still green and so was the second part test once I ran it. Confident that I vanquished today’s beast, I ran my code against the input. The answer felt good so I entered it into the challenge prompt and there it was, the final star of the day.
Thank you for reading my Advent of Code 2021 Day 12 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 11 log right here.
Nice work.
Thank you Ron!