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

aoc/year2022/
day11.rs
