-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathday_21.rs
293 lines (242 loc) · 8.96 KB
/
day_21.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
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
// --- Day 21: Monkey Math ---
// The monkeys are back! You're worried they're going to try to steal your stuff
// again, but it seems like they're just holding their ground and making various
// monkey noises at you.
// Eventually, one of the elephants realizes you don't speak monkey and comes
// over to interpret. As it turns out, they overheard you talking about trying
// to find the grove; they can show you a shortcut if you answer their riddle.
// Each monkey is given a job: either to yell a specific number or to yell the
// result of a math operation. All of the number-yelling monkeys know their
// number from the start; however, the math operation monkeys need to wait for
// two other monkeys to yell a number, and those two other monkeys might also be
// waiting on other monkeys.
// Your job is to work out the number the monkey named root will yell before the
// monkeys figure it out themselves.
// For example:
// root: pppw + sjmn
// dbpl: 5
// cczh: sllz + lgvd
// zczc: 2
// ptdq: humn - dvpt
// dvpt: 3
// lfqf: 4
// humn: 5
// ljgn: 2
// sjmn: drzm * dbpl
// sllz: 4
// pppw: cczh / lfqf
// lgvd: ljgn * ptdq
// drzm: hmdt - zczc
// hmdt: 32
// Each line contains the name of a monkey, a colon, and then the job of that monkey:
// A lone number means the monkey's job is simply to yell that number.
// A job like aaaa + bbbb means the monkey waits for monkeys aaaa and bbbb to
// yell each of their numbers; the monkey then yells the sum of those two
// numbers.
// aaaa - bbbb means the monkey yells aaaa's number minus bbbb's number.
// Job aaaa * bbbb will yell aaaa's number multiplied by bbbb's number.
// Job aaaa / bbbb will yell aaaa's number divided by bbbb's number.
// So, in the above example, monkey drzm has to wait for monkeys hmdt and zczc
// to yell their numbers. Fortunately, both hmdt and zczc have jobs that involve
// simply yelling a single number, so they do this immediately: 32 and 2. Monkey
// drzm can then yell its number by finding 32 minus 2: 30.
// Then, monkey sjmn has one of its numbers (30, from monkey drzm), and already
// has its other number, 5, from dbpl. This allows it to yell its own number by
// finding 30 multiplied by 5: 150.
// This process continues until root yells a number: 152.
// However, your actual situation involves considerably more monkeys. What
// number will the monkey named root yell?
// --- Part Two ---
// Due to some kind of monkey-elephant-human mistranslation, you seem to have
// misunderstood a few key details about the riddle.
// First, you got the wrong job for the monkey named root; specifically, you got
// the wrong math operation. The correct operation for monkey root should be =,
// which means that it still listens for two numbers (from the same two monkeys
// as before), but now checks that the two numbers match.
// Second, you got the wrong monkey for the job starting with humn:. It isn't a
// monkey - it's you. Actually, you got the job wrong, too: you need to figure
// out what number you need to yell so that root's equality check passes. (The
// number that appears after humn: in your input is now irrelevant.)
// In the above example, the number you need to yell to pass root's equality
// test is 301. (This causes root to get the same number, 150, from both of its
// monkeys.)
// What number do you yell to pass root's equality test?
use std::collections::HashMap;
#[derive(Debug, Copy, Clone, Eq, PartialEq)]
enum Expr {
Immediate(i64),
Add([u8; 4], [u8; 4]),
Sub([u8; 4], [u8; 4]),
Mul([u8; 4], [u8; 4]),
Div([u8; 4], [u8; 4]),
Eq([u8; 4], [u8; 4]),
Var,
}
fn name(s: &str) -> [u8; 4] {
let mut n = [0; 4];
assert_eq!(s.len(), 4);
n.copy_from_slice(s.as_bytes());
n
}
fn compute(monkeys: &HashMap<[u8; 4], Expr>, name: &[u8; 4]) -> Option<i64> {
let monkey = monkeys[name];
match monkey {
Expr::Immediate(n) => Some(n),
Expr::Add(a, b) => Some(compute(monkeys, &a)? + compute(monkeys, &b)?),
Expr::Sub(a, b) => Some(compute(monkeys, &a)? - compute(monkeys, &b)?),
Expr::Mul(a, b) => Some(compute(monkeys, &a)? * compute(monkeys, &b)?),
Expr::Div(a, b) => Some(compute(monkeys, &a)? / compute(monkeys, &b)?),
Expr::Eq(a, b) => Some((compute(monkeys, &a)? == compute(monkeys, &b)?) as i64),
Expr::Var => None,
}
}
fn extract(expr_a: Expr, expr_b: Expr) -> (Expr, i64, bool) {
match (expr_a, expr_b) {
(Expr::Immediate(v), _) => (expr_b, v, true),
(_, Expr::Immediate(v)) => (expr_a, v, false),
_ => unreachable!("Example input only has x in one location"),
}
}
pub fn part_1(input: &str) -> i64 {
let monkeys = parse(input);
compute(&monkeys, b"root").unwrap()
}
pub fn part_2(input: &str) -> i64 {
let mut monkeys = parse(input);
let root = monkeys.get_mut(b"root").unwrap();
*root = match root {
Expr::Add(a, b) | Expr::Sub(a, b) | Expr::Mul(a, b) | Expr::Div(a, b) => Expr::Eq(*a, *b),
_ => unreachable!(),
};
let humn = monkeys.get_mut(b"humn").unwrap();
*humn = Expr::Var;
// Start by simplifying everything which doesn't reference `humn`.
let names = monkeys.keys().copied().collect::<Vec<_>>();
for n in &names {
if let Expr::Immediate(_) = monkeys[n] {
continue;
}
if let Some(v) = compute(&monkeys, n) {
*monkeys.get_mut(n).unwrap() = Expr::Immediate(v);
}
}
// Now, actually try to solve the root equation
let (a, b) = if let Expr::Eq(a, b) = monkeys[b"root"] {
(a, b)
} else {
unreachable!()
};
// In practice, since we only have one monkey which depends on the human, we
// know that one of the two values is an immediate, and the other is an
// expression.
let (mut expr, mut v, _) = extract(monkeys[&a], monkeys[&b]);
loop {
// This is true recursively, so just unroll the expression until we get
// the answer.
match expr {
Expr::Add(a, b) => {
let (expr_, v_, _) = extract(monkeys[&a], monkeys[&b]);
expr = expr_;
// a + b = v
// a = v - b
v -= v_;
}
Expr::Mul(a, b) => {
let (expr_, v_, _) = extract(monkeys[&a], monkeys[&b]);
expr = expr_;
// a * b = v
// a = v / b
v /= v_;
}
Expr::Sub(a, b) => {
let (expr_, v_, flipped) = extract(monkeys[&a], monkeys[&b]);
expr = expr_;
if flipped {
// b - a = v => a - b = -v
v = -v;
}
// a - b = v
// a = v + b
v += v_;
}
Expr::Div(a, b) => {
let (expr_, v_, flipped) = extract(monkeys[&a], monkeys[&b]);
expr = expr_;
if flipped {
// b / a = v
// b = v * a
// a = b / v
v = v_ / v;
} else {
// a / b = v
// a = v * b
v *= v_;
}
}
Expr::Var => return v,
Expr::Immediate(_) | Expr::Eq(_, _) => unreachable!(),
}
}
}
fn parse(input: &str) -> HashMap<[u8; 4], Expr> {
let mut monkeys = HashMap::new();
for line in input.lines() {
if line.is_empty() {
continue;
}
let (monkey_name, op) = line.split_once(": ").unwrap();
let job = match op.parse::<i64>() {
Ok(v) => Expr::Immediate(v),
Err(_) => {
let mut iter = op.split_whitespace();
let n1 = name(iter.next().unwrap());
let o = iter.next().unwrap();
let n2 = name(iter.next().unwrap());
match o {
"+" => Expr::Add(n1, n2),
"-" => Expr::Sub(n1, n2),
"/" => Expr::Div(n1, n2),
"*" => Expr::Mul(n1, n2),
_ => unreachable!("Unexpected {:?}", o),
}
}
};
monkeys.insert(name(monkey_name), job);
}
monkeys
}
#[cfg(test)]
pub mod tests {
use crate::day_21::{part_1, part_2};
const INPUTS: &str = r#"root: pppw + sjmn
dbpl: 5
cczh: sllz + lgvd
zczc: 2
ptdq: humn - dvpt
dvpt: 3
lfqf: 4
humn: 5
ljgn: 2
sjmn: drzm * dbpl
sllz: 4
pppw: cczh / lfqf
lgvd: ljgn * ptdq
drzm: hmdt - zczc
hmdt: 32"#;
#[test]
pub fn test_day_21_example_part1() {
assert_eq!(part_1(INPUTS), 152);
}
#[test]
pub fn test_day_21_part1() {
assert_eq!(part_1(include_str!("input/day_21.txt")), 83056452926300);
}
#[test]
pub fn test_day_21_example_part2() {
assert_eq!(part_2(INPUTS), 301);
}
#[test]
pub fn test_day_21_part2() {
assert_eq!(part_2(include_str!("input/day_21.txt")), 3469704905529);
}
}