1use 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
100pub 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 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 let result = spawn_parallel_iterator(pairs, |iter| {
170 iter.map(|&(from, item)| play(monkeys, from, item)).collect::<Vec<_>>()
171 });
172
173 result.into_iter().flatten().fold(Business::zero(), Business::add).level()
175}
176
177fn 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 if to < from {
210 round += 1;
211 path.push(business);
212
213 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}