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

Each item can be treated individually. This allows the processing to be parallelized over many threads, speeding things up in part two.

Structs

Exclusive 🔒

Monkey

Shared 🔒

Enums

Operation

Functions

parallel 🔒

Play 10,000 rounds adjusting the worry level modulo the product of all the monkey’s test values.

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 an arbitrary number of rounds for a single item.

sequential 🔒

Play 20 rounds dividing the worry level by 3 each inspection.

solve 🔒

Convenience wrapper to reuse common logic between part one and two.

worker 🔒

Multiple worker functions are executed in parallel, one per thread.

Type Aliases

Business 🔒

Pair 🔒