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