Module day11

Monkey in the Middle

This problem is the combination of two Advent of Code classics, extracting numbers from a wall of flavor text and modular arithmetic. For the first problem, our utility iter_unsigned method comes in handy.

For the second problem, the key insight for part 2 is that a % m is the same as (a % n) % m if m is a factor of n.

For example:

  a = 23
  m = 3
  n = 15
  23 % 3 = 2
  23 % 15 = 8
  8 % 3 = 2

To keep the worry level manageable we need to find a number such that each monkey’s test is a factor of that number. The smallest number that meets this criteria is the least common multiple.

However before you rush off to implement the LCM algorithm, it’s worth examining the input. Each monkey’s test number is prime, so in this specific case the LCM is simply the product of all monkey’s test numbers. For example if we also need to test modulo 5 then the previous factor of 15 will work for both 3 and 5.

  a = 23
  m = 5
  n = 15
  23 % 5 = 3
  23 % 15 = 8
  8 % 5 = 3

A neat trick is that each item can be treated individually. This allows the processing to be parallelized over many threads. To speed things up even more, we notice that items form cycles, repeating the same path through the monkeys. Once we find a cycle for an item, then we short circuit the calculation early without having to calculate the entire 10,000 rounds.

Structs

Business 🔒

Monkey

Enums

Operation 🔒

Functions

parse

Extract each Monkey’s info from the flavor text. With the exception of the lines starting Operation we are only interested in the numbers on each line.

part1

part2

play 🔒

Play 10,000 rounds adjusting the worry level modulo the product of all the monkey’s test values. Look for cycles in each path so that we don’t have to process the entire 10,000 rounds.

Type Aliases

Input 🔒

Pair 🔒