aoc/year2022/
day11.rs

1//! # Monkey in the Middle
2//!
3//! This problem is the combination of two Advent of Code classics, extracting numbers from a wall
4//! of flavor text and modular arithmetic. For the first problem, our utility [`iter_unsigned`]
5//! method comes in handy.
6//!
7//! For the second problem, the key insight for part 2 is that
8//! `a % m` is the same as `(a % n) % m` if `m` is a factor of `n`.
9//!
10//! For example:
11//! ```none
12//!   a = 23
13//!   m = 3
14//!   n = 15
15//!   23 % 3 = 2
16//!   23 % 15 = 8
17//!   8 % 3 = 2
18//! ```
19//!
20//! To keep the worry level manageable we need to find a number such that each monkey's test is a
21//! factor of that number. The smallest number that meets this criteria is the
22//! [least common multiple](https://en.wikipedia.org/wiki/Least_common_multiple).
23//!
24//! However before you rush off to implement the LCM algorithm, it's worth examining the input. Each
25//! monkey's test number is prime, so in this specific case the LCM is simply the product of all
26//! monkey's test numbers.
27
28//! For example if we also need to test modulo 5 then the previous factor of 15 will work for both
29//! 3 and 5.
30//!
31//! ```none
32//!   a = 23
33//!   m = 5
34//!   n = 15
35//!   23 % 5 = 3
36//!   23 % 15 = 8
37//!   8 % 5 = 3
38//! ```
39//!
40//! Each item can be treated individually. This allows the processing to be parallelized over
41//! many threads, speeding things up in part two.
42//!
43//! [`iter_unsigned`]: ParseOps::iter_unsigned
44use crate::util::parse::*;
45use crate::util::thread::*;
46use std::sync::Mutex;
47
48pub struct Monkey {
49    items: Vec<u64>,
50    operation: Operation,
51    test: u64,
52    yes: usize,
53    no: usize,
54}
55
56pub enum Operation {
57    Square,
58    Multiply(u64),
59    Add(u64),
60}
61
62type Pair = (usize, u64);
63type Business = [u64; 8];
64
65struct Shared<'a> {
66    monkeys: &'a [Monkey],
67    mutex: Mutex<Exclusive>,
68}
69
70struct Exclusive {
71    pairs: Vec<Pair>,
72    business: Business,
73}
74
75/// Extract each Monkey's info from the flavor text. With the exception of the lines starting
76/// `Operation` we are only interested in the numbers on each line.
77pub fn parse(input: &str) -> Vec<Monkey> {
78    /// Inner helper function to keep the parsing logic readable.
79    fn helper(chunk: &[&str]) -> Monkey {
80        let items = chunk[1].iter_unsigned().collect();
81        let tokens: Vec<_> = chunk[2].split(' ').rev().take(2).collect();
82        let operation = match tokens[..] {
83            ["old", _] => Operation::Square,
84            [y, "*"] => Operation::Multiply(y.unsigned()),
85            [y, "+"] => Operation::Add(y.unsigned()),
86            _ => unreachable!(),
87        };
88        let test = chunk[3].unsigned();
89        let yes = chunk[4].unsigned();
90        let no = chunk[5].unsigned();
91        Monkey { items, operation, test, yes, no }
92    }
93    input.lines().collect::<Vec<&str>>().chunks(7).map(helper).collect()
94}
95
96pub fn part1(input: &[Monkey]) -> u64 {
97    solve(input, sequential)
98}
99
100pub fn part2(input: &[Monkey]) -> u64 {
101    solve(input, parallel)
102}
103
104/// Convenience wrapper to reuse common logic between part one and two.
105fn solve(monkeys: &[Monkey], play: impl Fn(&[Monkey], Vec<Pair>) -> Business) -> u64 {
106    let mut pairs = Vec::new();
107
108    for (from, monkey) in monkeys.iter().enumerate() {
109        for &item in &monkey.items {
110            pairs.push((from, item));
111        }
112    }
113
114    let mut business = play(monkeys, pairs);
115    business.sort_unstable();
116    business.iter().rev().take(2).product()
117}
118
119/// Play 20 rounds dividing the worry level by 3 each inspection.
120fn sequential(monkeys: &[Monkey], pairs: Vec<Pair>) -> Business {
121    let mut business = [0; 8];
122
123    for pair in pairs {
124        let extra = play(monkeys, 20, |x| x / 3, pair);
125        business.iter_mut().enumerate().for_each(|(i, b)| *b += extra[i]);
126    }
127
128    business
129}
130
131/// Play 10,000 rounds adjusting the worry level modulo the product of all the monkey's test values.
132fn parallel(monkeys: &[Monkey], pairs: Vec<Pair>) -> Business {
133    let shared = Shared { monkeys, mutex: Mutex::new(Exclusive { pairs, business: [0; 8] }) };
134
135    // Use as many cores as possible to parallelize the calculation.
136    spawn(|| worker(&shared));
137
138    shared.mutex.into_inner().unwrap().business
139}
140
141/// Multiple worker functions are executed in parallel, one per thread.
142fn worker(shared: &Shared<'_>) {
143    let product: u64 = shared.monkeys.iter().map(|m| m.test).product();
144
145    loop {
146        // Take an item from the queue until empty, using the mutex to allow access
147        // to a single thread at a time.
148        let Some(pair) = shared.mutex.lock().unwrap().pairs.pop() else {
149            break;
150        };
151
152        let extra = play(shared.monkeys, 10000, |x| x % product, pair);
153
154        let mut exclusive = shared.mutex.lock().unwrap();
155        exclusive.business.iter_mut().enumerate().for_each(|(i, b)| *b += extra[i]);
156    }
157}
158
159/// Play an arbitrary number of rounds for a single item.
160///
161/// The logic to adjust the worry level is passed via a closure
162/// so that we can re-use the bulk of the same logic between part 1 and 2.
163fn play(monkeys: &[Monkey], max_rounds: u32, adjust: impl Fn(u64) -> u64, pair: Pair) -> Business {
164    let (mut from, mut item) = pair;
165    let mut rounds = 0;
166    let mut business = [0; 8];
167
168    while rounds < max_rounds {
169        let worry = match monkeys[from].operation {
170            Operation::Square => item * item,
171            Operation::Multiply(y) => item * y,
172            Operation::Add(y) => item + y,
173        };
174        item = adjust(worry);
175
176        let to = if item.is_multiple_of(monkeys[from].test) {
177            monkeys[from].yes
178        } else {
179            monkeys[from].no
180        };
181
182        // Only increase the round when the item is passes to a previous monkey
183        // which will have to be processed in the next turn.
184        rounds += (to < from) as u32;
185        business[from] += 1;
186        from = to;
187    }
188
189    business
190}
aoc/year2022/day11.rs

aoc/year2022/
day11.rs
