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 part one, our utility [`iter_unsigned`]
5//! method comes in handy.
6//!
7//! For part two, the key insight 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 criterion 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.
25//! Each monkey's test number is prime, so in this specific case the LCM is simply the product of
26//! all 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 std::array::from_fn;
47use std::ops::{Add, Mul, Sub};
48
49use crate::util::hash::*;
50use crate::util::parse::*;
51use crate::util::thread::*;
52
53type Input = (Vec<Monkey>, Vec<Pair>);
54type Pair = (usize, usize);
55
56pub struct Monkey {
57    items: Vec<usize>,
58    operation: Operation,
59    test: usize,
60    yes: usize,
61    no: usize,
62}
63
64impl Monkey {
65    /// Inspecting an item raises its worry level.
66    fn inspect(&self, item: usize) -> usize {
67        match self.operation {
68            Operation::Square => item * item,
69            Operation::Multiply(y) => item * y,
70            Operation::Add(y) => item + y,
71        }
72    }
73
74    /// The divisibility test decides which monkey receives the item next.
75    fn throw(&self, item: usize) -> usize {
76        if item.is_multiple_of(self.test) { self.yes } else { self.no }
77    }
78}
79
80enum Operation {
81    Square,
82    Multiply(usize),
83    Add(usize),
84}
85
86#[derive(Clone, Copy, Default)]
87struct Business([usize; 8]);
88
89impl Business {
90    fn inc(&mut self, from: usize) {
91        self.0[from] += 1;
92    }
93
94    fn level(mut self) -> usize {
95        self.0.sort_unstable();
96        self.0.iter().rev().take(2).product()
97    }
98}
99
100/// Implement operators so that we can use `+`, `-` and `*` notation to combine partial results.
101impl Add for Business {
102    type Output = Self;
103
104    #[inline]
105    fn add(self, rhs: Self) -> Self {
106        Self(from_fn(|i| self.0[i] + rhs.0[i]))
107    }
108}
109
110impl Sub for Business {
111    type Output = Self;
112
113    #[inline]
114    fn sub(self, rhs: Self) -> Self {
115        Self(from_fn(|i| self.0[i] - rhs.0[i]))
116    }
117}
118
119impl Mul<usize> for Business {
120    type Output = Self;
121
122    #[inline]
123    fn mul(self, rhs: usize) -> Self {
124        Self(self.0.map(|n| n * rhs))
125    }
126}
127
128/// Extract each Monkey's info from the flavor text. With the exception of the lines starting
129/// `Operation` we are only interested in the numbers on each line.
130pub fn parse(input: &str) -> Input {
131    let lines: Vec<_> = input.lines().collect();
132
133    let monkeys: Vec<_> = lines
134        .chunks(7)
135        .map(|chunk| {
136            let items = chunk[1].iter_unsigned().collect();
137            let tokens: Vec<_> = chunk[2].rsplit(' ').take(2).collect();
138            let operation = match tokens[..] {
139                ["old", _] => Operation::Square,
140                [y, "*"] => Operation::Multiply(y.unsigned()),
141                [y, "+"] => Operation::Add(y.unsigned()),
142                _ => unreachable!(),
143            };
144            let test = chunk[3].unsigned();
145            let yes = chunk[4].unsigned();
146            let no = chunk[5].unsigned();
147            Monkey { items, operation, test, yes, no }
148        })
149        .collect();
150
151    let pairs = monkeys
152        .iter()
153        .enumerate()
154        .flat_map(|(from, monkey)| monkey.items.iter().map(move |&item| (from, item)))
155        .collect();
156
157    (monkeys, pairs)
158}
159
160pub fn part1(input: &Input) -> usize {
161    let (monkeys, pairs) = input;
162    let mut business = Business::default();
163
164    for &(mut from, mut item) in pairs {
165        let mut rounds = 0;
166
167        while rounds < 20 {
168            item = monkeys[from].inspect(item) / 3;
169            let to = monkeys[from].throw(item);
170
171            business.inc(from);
172
173            // Only increase the round when the item is passed to a previous monkey
174            // which will have to be processed in the next turn.
175            rounds += usize::from(to < from);
176            from = to;
177        }
178    }
179
180    business.level()
181}
182
183pub fn part2(input: &Input) -> usize {
184    let (monkeys, pairs) = input;
185
186    // Use as many cores as possible to parallelize the calculation.
187    let result = spawn_parallel_iterator(pairs, |iter| {
188        iter.map(|&(from, item)| play(monkeys, from, item)).collect::<Vec<_>>()
189    });
190
191    // Merge results.
192    result.into_iter().flatten().fold(Business::default(), Business::add).level()
193}
194
195/// Play 10,000 rounds adjusting the worry level modulo the product of all the monkey's test values.
196/// Look for cycles in each path so that we don't have to process the entire 10,000 rounds.
197fn play(monkeys: &[Monkey], mut from: usize, mut item: usize) -> Business {
198    let product: usize = monkeys.iter().map(|m| m.test).product();
199
200    let mut round = 0;
201    let mut business = Business::default();
202
203    let mut path = vec![business];
204    let mut seen = FastMap::build([((from, item), round)]);
205
206    while round < 10_000 {
207        item = monkeys[from].inspect(item) % product;
208        let to = monkeys[from].throw(item);
209
210        business.inc(from);
211
212        // Only increase the round when the item is passed to a previous monkey
213        // which will have to be processed in the next turn.
214        if to < from {
215            round += 1;
216            path.push(business);
217
218            // If we have found a cycle, then short circuit and return the final result.
219            if let Some(previous) = seen.insert((to, item), round) {
220                let cycle_width = round - previous;
221
222                let offset = 10_000 - round;
223                let quotient = offset / cycle_width;
224                let remainder = offset % cycle_width;
225
226                let full = (business - path[previous]) * quotient;
227                let partial = path[previous + remainder] - path[previous];
228                return business + full + partial;
229            }
230        }
231
232        from = to;
233    }
234
235    business
236}
aoc/year2022/day11.rs

aoc/year2022/
day11.rs
