Last night, France made history, by taking down England in their first-ever direct elimination match. A closer game than I would have liked but it made sense France won. Similarly, my face-off with today’s puzzle was closer than I wished but eventually, I prevailed. Welcome to my Advent of Code 2022 Day 11 cruise log.
After the game last night, we went out to Chelsea with some friends to celebrate and it was great. And yes we were sporting our France jerseys outside but didn’t get into any trouble as expected. Everyone we ran into was sportsmanlike congratulating us on our homeland team’s triumph. Champagne flowed, laughter rang and smiles lightened the pub we ended in. All that to say that I woke up at 8 am this morning. It was all worth it.
Now, just like the last time I woke up so late, there is no reaching the top 100. However, the puzzles still need solving. Today we’re dealing with predictions of what some monkeys will do next with our valuable items.
First I wrote the parser, quite hacky but very effective and, dare I say, efficient. Once we parsed the input, we must have a collection of monkeys and we should be able to have code that will allow us to calculate to which monkey a given monkey will throw our item. There is a bit of math in there but nothing crazy for the first part. It’s without surprise that I swim through it and collect my first star within forty minutes. Things are looking good.
Now the second part is the classic. Okay, you had 20 iterations of repeating an algorithm, now do 10,000. Generally, I feel in danger when this happens but I tried the naive option of just trying to run the code by updating my iteration count to 10,000. We never know, even though deep down I did know. First mistake.
About a minute later, only 50 iterations went through due to a change of rules that get our calculations towards crazy values. As in bigger than a 32-bit integer which is the goto for numeric values when quickly writing code. That was my second mistake but we will get to that later.
The slowness lets me know that if I just let the code run as is, it will most likely take days or weeks to solve. I just cannot do that. Firstly, because the energy costs rose pretty hard so I don’t intend to let my computer run for that long. Lastly, I got a company leaderboard top spot to preserve. I need to figure out something else and it stinks of mathematics.
Back to that change of rules. The first part yielded a result pretty fast because that crutch allowed us to divide a certain value by 3. But the change requires that we drop that and figure out our own optimal crutch.
One of the things to do when this happens is to take a deep hard look at both the test and the real input data. Fairly quickly I notice something, it feels like the decisive values assigned to monkeys are all prime numbers. I quick check on Wikipedia confirms this.
From there it all makes sense. I need to apply to another certain value a modulo that will preserve congruence. Normally you would need to calculate the lowest common multiple for several divisors (monkey magical numbers). A nice property of prime numbers is that the lowest common multiple for a set of prime numbers is the product of said set. This is my modulo.
It sounded fast but it took me an extra couple of hours to figure that out. From there I updated the code and nothing. The test still fails. I submit an answer just in case. Another failure. I’m lost. The code is correct. The test output is close to the expected one. What gives?
I start debugging, going through each round from 1 to 10 and I can’t see anything. By now I fully sobered up from last night but cannot see what’s missing. Surely, somewhere I missed something.
Now I take a break, stroll around the house, have a good stretch and then get back to the desk. Off for another round of debugging, that’s when I see it. The values that we need to multiply to decide where items go, well some of them are negative. Which is impossible since the operations we perform are additions and multiplications. There is only one explanation, the value overflows.
When using 32-bit integers, the first bit determines the sign of the numeric value it contains. If I recall when set to 1 the value is negative and when set to 0 it’s positive, maybe the opposite. If a value is stored in a variable. Say it’s bigger than 32 bits, it could be a large positive integer which simply doesn’t fit but turns on the sign bit.
From there I refactor my code to use long integers which are 64-bit long, hence the name I guess. Now the test passes, I clutch my second star of the day while dreaming of France capturing a third one.
Thank you for reading my Advent of Code 2022 Day 11 log, I should see you tomorrow. 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.
Cover by vishnudeep dixit
