Expand description
Advent of Code 2022 Day 11: https://adventofcode.com/2022/day/11
I thought that part one of this challenge was relatively easy and was at
first surprised that part two was just to increase the number of rounds
and remove a division step. Then I ran into my first overflow, increased
my integers to u64 and then u128 and they were still too small. I
thought that the prompt’s instructions “you’ll need to find another way to
keep your worry levels manageable” was just flavor text. I started to
implement a crate that added support for u256+ sized integers until I
decided that I was missing something. I wasn’t really sure how to approach
the problem until I read something really helpful on
reddit:
Hint: you don’t care what the result of the division is, you just care whether the current worry level is divisible by the monkey’s test value. Is there a way you can keep the worry level small(er) while still being able to tell if it’s divisible?
I played around some trying to divide the original factor until I found the modulo method. During my cleanup phase I also read that it’s better to compute the least common multiple and use that instead of the product, but reading around some more it seems that may be bad advice. I already implemented it again using the LCM and the tests still pass so it can’t hurt, but I don’t understand the math well enough to know for sure one way or the other.
What follows is my attempt to explain why/how the modulo method is needed
and works. Inspecting the monkeys we can see that some (or rather one) of
them multiplies the item value by itself (i.e., value^2) each time that
it inspects an object (it must be really careless). In part one we have
a low enough number of rounds that reducing the worry factor by three each
time is enough to keep this value from getting too out of hand. It also
probably wouldn’t be a problem if we never had the exponential growth and
only multiplied (or added) by set, fixed values. In any case, as it is the
item values can grow crazy big crazy fast. The strategy then is to compute
a value that we can remove from the item’s value that will reduce its size
but keep in tact whether it’s divisible by all of the monkeys’ test values.
Consider some smaller, arbitrary numbers for the tests: 3, 5, and 7.
Let’s assume that we have an item with value 300 and that our overflow
is small say 500. If we have a monkey that multiplies the item value by
itself we’ll end up with a worry score of 90000 which would obviously
overflow. We also want to know whether the result is divisible by our
initial numbers and if not what the remainder is. 90000 % 3 and 90000 % 5 are both 0, but 90000 % 7 is 1. We can “take out” 857 copies of
our LCM 105 (857 * 105 == 89985) and be left with 15. 15 % 3 and
15 % 5 are both 0 and 15 % 7 is 1, just like our original, huge
number. We can safely replace that value with 15 which fits inside our
overflow. There are some much better, math filled explanations on the
Advent of Code subreddit that explain why/how this all works should you be
interested.
Functions§
- The solution for the day eleven challenge.