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//! A neat trick is that each item can be treated individually. This allows the processing to be
41//! parallelized over many threads. To speed things up even more, we notice that items form cycles,
42//! repeating the same path through the monkeys. Once we find a cycle for an item, then we short
43//! circuit the calculation early without having to calculate the entire 10,000 rounds.
44//!
45//! [`iter_unsigned`]: ParseOps::iter_unsigned
46use crate::util::hash::*;
47use crate::util::parse::*;
48use crate::util::thread::*;
49
50type Input = (Vec<Monkey>, Vec<Pair>);
51type Pair = (usize, usize);
52
53pub struct Monkey {
54    items: Vec<usize>,
55    operation: Operation,
56    test: usize,
57    yes: usize,
58    no: usize,
59}
60
61enum Operation {
62    Square,
63    Multiply(usize),
64    Add(usize),
65}
66
67#[derive(Clone, Copy)]
68struct Business([usize; 8]);
69
70impl Business {
71    fn zero() -> Self {
72        Business([0; 8])
73    }
74
75    fn inc(&mut self, from: usize) {
76        self.0[from] += 1;
77    }
78
79    fn level(mut self) -> usize {
80        self.0.sort_unstable();
81        self.0.iter().rev().take(2).product()
82    }
83
84    fn add(mut self, rhs: Self) -> Self {
85        self.0.iter_mut().zip(rhs.0).for_each(|(a, b)| *a += b);
86        self
87    }
88
89    fn sub(mut self, rhs: Self) -> Self {
90        self.0.iter_mut().zip(rhs.0).for_each(|(a, b)| *a -= b);
91        self
92    }
93
94    fn mul(mut self, rhs: usize) -> Self {
95        self.0.iter_mut().for_each(|a| *a *= rhs);
96        self
97    }
98}
99
100/// Extract each Monkey's info from the flavor text. With the exception of the lines starting
101/// `Operation` we are only interested in the numbers on each line.
102pub fn parse(input: &str) -> Input {
103    let lines: Vec<_> = input.lines().collect();
104
105    let monkeys: Vec<_> = lines
106        .chunks(7)
107        .map(|chunk: &[&str]| {
108            let items = chunk[1].iter_unsigned().collect();
109            let tokens: Vec<_> = chunk[2].split(' ').rev().take(2).collect();
110            let operation = match tokens[..] {
111                ["old", _] => Operation::Square,
112                [y, "*"] => Operation::Multiply(y.unsigned()),
113                [y, "+"] => Operation::Add(y.unsigned()),
114                _ => unreachable!(),
115            };
116            let test = chunk[3].unsigned();
117            let yes = chunk[4].unsigned();
118            let no = chunk[5].unsigned();
119            Monkey { items, operation, test, yes, no }
120        })
121        .collect();
122
123    let pairs: Vec<_> = monkeys
124        .iter()
125        .enumerate()
126        .flat_map(|(from, monkey)| monkey.items.iter().map(move |&item| (from, item)))
127        .collect();
128
129    (monkeys, pairs)
130}
131
132pub fn part1(input: &Input) -> usize {
133    let (monkeys, pairs) = input;
134    let mut business = Business::zero();
135
136    for &(mut from, mut item) in pairs {
137        let mut rounds = 0;
138
139        while rounds < 20 {
140            let worry = match monkeys[from].operation {
141                Operation::Square => item * item,
142                Operation::Multiply(y) => item * y,
143                Operation::Add(y) => item + y,
144            };
145            item = worry / 3;
146
147            let to = if item.is_multiple_of(monkeys[from].test) {
148                monkeys[from].yes
149            } else {
150                monkeys[from].no
151            };
152
153            business.inc(from);
154
155            // Only increase the round when the item is passes to a previous monkey
156            // which will have to be processed in the next turn.
157            rounds += usize::from(to < from);
158            from = to;
159        }
160    }
161
162    business.level()
163}
164
165pub fn part2(input: &Input) -> usize {
166    let (monkeys, pairs) = input;
167
168    // Use as many cores as possible to parallelize the calculation.
169    let result = spawn_parallel_iterator(pairs, |iter| {
170        iter.map(|&(from, item)| play(monkeys, from, item)).collect::<Vec<_>>()
171    });
172
173    // Merge results.
174    result.into_iter().flatten().fold(Business::zero(), Business::add).level()
175}
176
177/// Play 10,000 rounds adjusting the worry level modulo the product of all the monkey's test values.
178/// Look for cycles in each path so that we don't have to process the entire 10,000 rounds.
179fn play(monkeys: &[Monkey], mut from: usize, mut item: usize) -> Business {
180    let product: usize = monkeys.iter().map(|m| m.test).product();
181
182    let mut round = 0;
183    let mut business = Business::zero();
184
185    let mut path = Vec::new();
186    let mut seen = FastMap::new();
187
188    path.push(business);
189    seen.insert((from, item), path.len() - 1);
190
191    while round < 10_000 {
192        let worry = match monkeys[from].operation {
193            Operation::Square => item * item,
194            Operation::Multiply(y) => item * y,
195            Operation::Add(y) => item + y,
196        };
197        item = worry % product;
198
199        let to = if item.is_multiple_of(monkeys[from].test) {
200            monkeys[from].yes
201        } else {
202            monkeys[from].no
203        };
204
205        business.inc(from);
206
207        // Only increase the round when the item is passes to a previous monkey
208        // which will have to be processed in the next turn.
209        if to < from {
210            round += 1;
211            path.push(business);
212
213            // If we have found a cycle, then short ciruit and return the final result.
214            if let Some(previous) = seen.insert((to, item), path.len() - 1) {
215                let cycle_width = round - previous;
216
217                let offset = 10_000 - round;
218                let quotient = offset / cycle_width;
219                let remainder = offset % cycle_width;
220
221                let full = business.sub(path[previous]).mul(quotient);
222                let partial = path[previous + remainder].sub(path[previous]);
223                return business.add(full).add(partial);
224            }
225        }
226
227        from = to;
228    }
229
230    business
231}
aoc/year2022/day11.rs

aoc/year2022/
day11.rs
