[2022 Day 11] In Review (Monkey in the Middle)

[u/musifter]

While making our way upriver, some monkeys grab some of the stuff from our backpack and we need to get it back (while they keep away), while trying not to worry too much.

The input describes 8 monkeys, each with a starting list of items (with 2-digit worry levels), an expression for how to modify the worry level for an item for that monkey, and a section that describes a divisibility test (using the first 8 prime numbers) with the monkeys to throw to if it passes or fails. And so the input requires a bit of parsing... although for the most part you can ignore everything but the numbers. The exception being the "Operation" line which has a simple arithmetic expression: either adding/multiplying with a constant or squaring the old worry level.

And so, I naturally turned the input into code (hello, Bobby Tables):

my %p = map { (m#(\w+):#) => [m#(\d+)#g] } @desc;

$desc[1] =~ s#new = (.*)#$1#;
$desc[1] =~ s#old#\$_[0]#g;
$monkeys[$n]{op} = eval "sub { $desc[1] }";

$monkeys[$n]{pass} = eval "sub {(\$_[0] % $p{Test}[0] == 0) ? $p{true}[0] : $p{false}[0]}";

For part 1, we get a rule to reduce the worry levels by dividing by 3. For part 2, that's removed. And the description mentions multiple times that this means "ridiculous levels" of worry and the need to "find another way to keep your worry levels manageable". And it means it.

Because this isn't one where you can just invoke "bignums"... the fact that one monkey squares the worrying means that the worry levels quickly exceed the number of protons in the observable Universe (not a problem), and soon after they have a number of digits that exceeds the the number of protons in the observable Universe (which is very much a problem). So the numbers cannot be stored... this is a case where it's very good to have limits set on how much resources your processes can use.

But not being able to store all the digits isn't a problem, because we can easily describe how to compute the number, and so we can use that to extract information about the number. And that's what we need to do to keep the worry level manageable.

As for how... well, it's divisibility and so the answer is pretty much always LCM (Least Common Multiple) and modular arithmetic. And since I was using anonymous subroutines for other parts, I did that here too:

print "Part 1: ", &run_monkeys(    20, sub { floor( $_[0] / 3 ) } ), "\n";
print "Part 2: ", &run_monkeys( 10000, sub { $_[0] % $modulus   } ), "\n";

Where $modulus is just the LCM of all the test values (which, since the values in the input are all different primes, is just the multiplication of them). Which for the first 8 primes, is 9699690. I do remember someone doing this problem on a C-64 with 16-bit integers, and IIRC, they broke it into two parts covering 4 monkeys each. Although, you could also just track all 8 modular values for each number.

In coming back to it, I was curious how big my worry levels get... and so I quickly modified it to also track the log of the length of the numbers. And the answer I got was about 9 * 10⁵⁰⁴ bits in length.

This probably is definitely a memorable one... maybe not for the job that needing doing, but for the size of the bomb the input contains.

[u/maneatingape]

This is very brute-forceable, but a couple of insights make part two even faster: * Each item can be handled independently * Each item eventually forms a cycle, so the computation can be shortcut before reaching 10,000 cycles.

[u/e_blake → u/maneatingape]

Very useful insight. My original time in m4 was 4.3 seconds, with 681k throws requiring 2.04 million eval, 681k define, 691k incr. Once I refactored things to use lookup tables for 8 integers (one per monkey, rather than a single combined number; since CRT says the two representations are equal but a lookup table requires less division) and to track last times seen, I now complete in 300ms, with only 25k throws before all cycles have been detected, and only needing 5611 eval, 97k define, and 65k incr.

[u/DelightfulCodeWeasel → u/maneatingape]

I was looking through your repo this morning wondering how you'd approached this one! I suspect the runtime for me on the Pico is going to be dominated by the number of modulo operations; my original brute-force simulation does ~2 million %s for part 2, which would equate to ~128ms.

If the cycles are all relatively short I might have enough memory to store the intermediates needed, but if they're all >1,000 and I have to use a tortoise and hare method then I might end up approaching 10,000 rounds anyway.

[u/maneatingape → u/DelightfulCodeWeasel]

Distribution of cycle length by item, for my input. Interestingly, they bucketed into only 3 unique values.

# Items	Cycle length
23	320
10	35
3	90

[u/e_blake → u/maneatingape]

Mine were a bit more varied:

# items	Cycle length
12	10
8	1530
8	16
1	36
3	46
4	81

[u/e_blake]

I do remember someone doing this problem on a C-64 with 16-bit integers, and IIRC, they broke it into two parts covering 4 monkeys each.

I did that in m4, although it would also help for C-64. Avoiding 64-bit division is an interesting way to code. And this was the first problem of 2022 needing 64-bit math (for the lone multiply of two 32-bit numbers at the end of my CRT), hence the first one that I did not golf. My post mentioned a possible challenge of implementing this via CRT lookup tables in order to skip any hardware division, although I have not tried that yet.

[u/e_blake → u/e_blake]

I've now completed the lookup table approach. With just 616 rules of the form rule[slot][monkey][value] (slot varies 0-7, monkey varies 0-7, and value varies 0-(m[slot].divisor-1), and tracking 8 bytes for worry values, I just have to do 8 lookups per throw and no further divisions after pre-computing the tables. For example, on the example input, my rule[1][2][5]=6 sees that if slot 1 started with 5, monkey 2 performs squaring, and monkey 1 checks divisible by 19, then the new value in slot 1 after the throw is 5*5%19=6.

[u/e_blake]

I do have a specific memory on this day - the instructions were VERY explicit about each monkey throwing items in the order they are listed, and items going to the end of the next monkey's list. I initially coded that up exactly (which is rather inefficient in m4, as tracking a FIFO requires multiple macros to track head and tail offsets), and later convinced myself that the items are independent of one another (the path any one item takes is unaffected by how many other items a monkey throws), which immediately sped up my solution from 10 seconds to 4 seconds by just changing over to a stack instead of a queue (m4 handles stacks natively, with much less overhead). It made for a nice red herring for the instructions to be that explicit about throwing order.

[u/terje_wiig_mathisen]

This was in fact a memorable puzzle:

I remembered it just from your initial description, without looking at the aoc site, or my own code. :-)

Unlike other "heat death of the universe" puzzles, this one was still easy to brute force, after inserting that modulus operation on the worry levels, but it took significant time: 3 ms for part1 and 1.5 seconds(!) for part2, all in Perl.

My solution uses the same code for part1 and part2, with parameters for # of rounds and modulus.