Skip to content

The Advent of Code 2022 Day 19: Geode mode

Posted in Advent of Code

Yesterday morning, I was planning on telling you about how the Advent of Code 2022 Day 19 defeated me. I accepted that my effort from last weekend was in vain. A whole Saturday afternoon and early evening with nothing to show for it. Nothing, not quite, I did have the examples working for part one. Let me tell you all about how this changed yesterday.

Let’s start at the beginning, by that I don’t mean December 19th since we now established that the Advent of Code was not my priority then. Date nights, parties, World Cup, birthdays and so on. Right, the beginning of this one was on January 7th when I finally took some time to check this out. While a few people across various platforms and places warned me about how hard this would be I only half-believed them.

My pride told me that I was better and would have been in the top 100 worldwide had I done it on the day. Sure, misplaced ego and I guess this puzzle was perfect as it took it down a couple of notches. In the end, if we compound the time I spent on this, it probably mounts up to a working day and a half. Have I spent that long before on such a puzzle? Possibly. But somehow this still feels like the trickiest AoC puzzle I’ve ever done.

The gist of it is that we have some blueprints to compare in order to generate robots to collect resources. Each robot depends on resources that can be built by another kind of robot. Ultimately we want to build robots that can crack some geodes for us. Obviously, they need resources that can be built only by other robots and there is a time limit of 24 minutes or steps.

This felt like it should be easy but since this is a third-week puzzle, I knew it was harder than it seemed. Still, I coded away a badly written DFS (depth-first search) since this felt similar to Day 16. While it worked for that day, I suspect I only got lucky then all things considered. Within a half-an-hour, the test for the second example worked but not the first one.

I could feel that my logic was probably pruning some alternate universes with at least one yielding the right result. This stumped me for a bit and I decided to sleep on it. Which I did for a whole two weeks.

Fast-forward to January 21st, I finally got back to it. Since the original approach did not work, I decided to take a more object-oriented approach with proper state classes and all. And it kinda worked. Now both examples were green but the answer was still incorrect for the real input. At this point, frustration builds more but before it gets to my head I decide to sleep on it. For another week.

So close and I didn’t know it

Yesterday morning, I tried to have another look, already ready to surrender like a real English man. But I remembered my own saying about this Advent of Code. If you’re stuck, visualise. My terminal debugging code was pointless because there were too many entries for my IDE to handle. But I figured I could just write them all in a text file to read through and try to find the anomaly.

I have not changed the code except for a tiny optimisation to improve the speed and the file writing debug lines. Upon execution, the code hung. Still, I figured it was due to the sheer amount of entries that would be written. So after about 30 minutes away playing Smite, I got back to my computer.

Quick Smite-related parenthesis, while I do enjoy the game, I find it preposterous that after the game crashes we get a ban. If anyone working at Hi-Rez reads this please fix it.

Back to my computer, I found the imaginatively named debug.txt file being over a terabyte of log entries. I am definitely not reading that. But something is different. The result is slightly higher than the last one which was too low. I tried and entered it. It worked!

24 minutes, what were the odds?

This makes absolutely zero sense that adding text file debugging would do this. It ran for 24 minutes, I know like in the puzzle description, and yielded the right result. Finally clutched that elusive star.

Then curious, I commented out all the file writing stuff and I got the same good result but in 15 seconds this time. Crazy I know. I do suspect that my IDE did not recompile the app during my previous attempts, I can’t think of any other reason. It did happen in the past so maybe I will check that later.

Here the second part requires running the same code for more steps on a smaller set of input. Easy enough right? Absolutely not. At least not for me. The code hung for a while before yielding an oom of doom. OutOfMemoryException.

From there I spent some extra time trying to optimise my algorithm to get it to run in under a second. I hoped that I could get it to run fast enough that I don’t run out of memory. In retrospect, I didn’t really need that. At least if I properly coded my DFS which I didn’t realise yet.

I managed to get to a fifth of my OG time

At this point, I feel fortunate that I finally tackled the first part and decide that if I can’t do the second, so be it. Plus I had to go out for dinner with some friends to try an Italian restaurant in Fulham. I decide to leave AoC for the day.

The next morning, I go to my computer as soon as I wake up to open the IDE. I thought that maybe last night’s Limoncello-based drinks altered my brain chemistry enough to see through my mistakes. Scanning through the code, I realised that the priority queue sorts states by geode created, not by minutes. This means that I don’t necessarily go all through the depth of my DEPTH-first search algorithm. As a result, the code creates multiple branches or timelines before reaching the end for all of them thus filling up my heap memory and triggering the oom of doom.

Upon that realisation, I make the change and within ten seconds I get a result. 16. Which feels way too low. It feels like the result of one simulation but the result should be the product of three simulation results. From there I add some more logging and notice that it is in fact the result of the final simulation.

The test data has only two entries but the second part requires simulations of the top three entries. My code catered for that with some ternary and I messed up the parentheses. Upon fixing that, I got something that felt right.

I entered my “10672” result into the answer box and finally claimed the second star for this painful puzzle.

Still, 9 stars left to collect to wrap up AoC 2022

Thank you for reading my Advent of Code 2022 Day 19 log, I will see you when I see you. If you want to check out my previous entry, you can do so here. You can even read my entries from last year there. As usual, I will push the code to my repo for this year on Github. Also, if you want to test yourself against my AoC 2022 run, I’ve created a private leaderboard. The invite code is 382952-d065ee7a . Join, if you dare. I say dare but since I’m playing catch up, if you completed everything on time, you’re way ahead.

Cover by Jason Deines

Be First to Comment

    Leave a Reply

    This site uses Akismet to reduce spam. Learn how your comment data is processed.

    %d bloggers like this: