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

aoc/year2022/
day11.rs
