1use std::convert::TryInto;
8use std::fmt;
9use std::thread::{self, JoinHandle};
10
11#[derive(Debug)]
13pub struct Machine {
14 mem: Vec<isize>,
15 ip: isize,
16 base: isize,
17}
18
19impl Machine {
20 pub fn new() -> Machine {
26 Machine {
27 mem: Vec::new(),
28 ip: 0,
29 base: 0,
30 }
31 }
32
33 pub fn with_program(program: &[isize]) -> Machine {
34 let mut machine = Machine::new();
35 machine.copy(0, program);
36 machine
37 }
38
39 pub fn mem(&self) -> &[isize] {
41 &self.mem
42 }
43
44 pub fn mem_mut(&mut self) -> &mut [isize] {
46 &mut self.mem
47 }
48
49 pub fn reserve(&mut self, size: usize) {
51 if self.mem.len() < size {
52 self.mem.resize(size, 0);
53 }
54 }
55
56 pub fn copy(&mut self, start: usize, values: &[isize]) {
58 self.reserve(start + values.len());
59 self.mem[start..start + values.len()].copy_from_slice(values);
60 }
61
62 fn read(&mut self, i: isize) -> Result<isize, Exit> {
63 let i: usize = i.try_into().map_err(|_| Exit::NegativePointer)?;
64
65 self.reserve(i + 1);
66 Ok(self.mem[i])
67 }
68
69 fn write(&mut self, i: isize, val: isize) -> Result<(), Exit> {
70 let i: usize = i.try_into().map_err(|_| Exit::NegativePointer)?;
71
72 self.reserve(i + 1);
73 self.mem[i] = val;
74 Ok(())
75 }
76
77 fn param(&mut self, offset: isize) -> Result<isize, Exit> {
78 let opcode = self.read(self.ip)?;
79 let arg = self.read(self.ip + offset)?;
80 let mode = (opcode / 10isize.pow(offset as u32 + 1)) % 10;
81
82 match mode {
83 0 => self.read(arg),
85
86 1 => Ok(arg),
88
89 2 => self.read(self.base + arg),
91
92 unknown => Err(Exit::IllegalMode(unknown)),
93 }
94 }
95
96 fn out(&mut self, offset: isize, val: isize) -> Result<(), Exit> {
97 let opcode = self.read(self.ip)?;
98 let arg = self.read(self.ip + offset)?;
99 let mode = (opcode / 10isize.pow(offset as u32 + 1)) % 10;
100
101 match mode {
102 0 => self.write(arg, val),
104
105 2 => self.write(self.base + arg, val),
107
108 unknown => Err(Exit::IllegalMode(unknown)),
109 }
110 }
111
112 pub fn step(&mut self, input: Option<isize>) -> Result<(), Exit> {
114 let opcode = self.read(self.ip)?;
115 let instruction = opcode % 100;
116
117 match instruction {
118 1 => {
120 let a = self.param(1)?;
121 let b = self.param(2)?;
122 self.out(3, a + b)?;
123 self.ip += 4;
124 Ok(())
125 }
126
127 2 => {
129 let a = self.param(1)?;
130 let b = self.param(2)?;
131 self.out(3, a * b)?;
132 self.ip += 4;
133 Ok(())
134 }
135
136 3 => {
138 let a = input.ok_or(Exit::Input)?;
139 self.out(1, a)?;
140 self.ip += 2;
141 Ok(())
142 }
143
144 4 => {
146 let a = self.param(1)?;
147 self.ip += 2;
148 Err(Exit::Output(a))
149 }
150
151 5 => {
153 let a = self.param(1)?;
154 let b = self.param(2)?;
155 if a != 0 {
156 self.ip = b;
157 } else {
158 self.ip += 3;
159 }
160 Ok(())
161 }
162
163 6 => {
165 let a = self.param(1)?;
166 let b = self.param(2)?;
167 if a == 0 {
168 self.ip = b;
169 } else {
170 self.ip += 3;
171 }
172 Ok(())
173 }
174
175 7 => {
177 let a = self.param(1)?;
178 let b = self.param(2)?;
179 self.out(3, if a < b { 1 } else { 0 })?;
180 self.ip += 4;
181 Ok(())
182 }
183
184 8 => {
186 let a = self.param(1)?;
187 let b = self.param(2)?;
188 self.out(3, if a == b { 1 } else { 0 })?;
189 self.ip += 4;
190 Ok(())
191 }
192
193 9 => {
195 let a = self.param(1)?;
196 self.base += a;
197 self.ip += 2;
198 Ok(())
199 }
200
201 99 => Err(Exit::Halted),
203
204 unknown => Err(Exit::IllegalInstruction(unknown)),
205 }
206 }
207
208 pub fn resume(&mut self, mut input: Option<isize>) -> Exit {
210 loop {
211 match self.step(input.take()) {
212 Ok(_) => {}
213 Err(e) => return e,
214 }
215 }
216 }
217
218 pub fn run<I, O>(&mut self, input: I, output: O) -> Exit
220 where
221 I: IntoIterator<Item = isize>,
222 O: FnMut(isize),
223 {
224 let mut input = input.into_iter().peekable();
225 let mut output = output;
226 let mut next_input = None;
227 loop {
228 match self.resume(next_input.take()) {
229 Exit::Input if input.peek().is_some() => {
230 next_input = input.next();
231 }
232 Exit::Output(a) => {
233 output(a);
234 }
235 other => return other,
236 }
237 }
238 }
239
240 pub fn spawn<I, O>(mut self, input: I, output: O) -> JoinHandle<(Machine, Exit)>
241 where
242 I: IntoIterator<Item = isize> + Send + 'static,
243 O: FnMut(isize) + Send + 'static,
244 {
245 thread::spawn(move || {
246 let result = self.run(input, output);
247 (self, result)
248 })
249 }
250}
251
252#[derive(Debug, PartialEq)]
254pub enum Exit {
255 NegativePointer,
257
258 IllegalMode(isize),
260
261 IllegalInstruction(isize),
263
264 Input,
266
267 Output(isize),
269
270 Halted,
272}
273
274impl fmt::Display for Exit {
275 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
276 match self {
277 Exit::NegativePointer => write!(f, "attempted to use a negative value as a pointer"),
278 Exit::IllegalMode(mode) => write!(f, "illegal mode: {}", mode),
279 Exit::IllegalInstruction(inst) => write!(f, "illegal instruction: {}", inst),
280 Exit::Input => write!(f, "need input"),
281 Exit::Output(a) => write!(f, "got output: {}", a),
282 Exit::Halted => write!(f, "halted"),
283 }
284 }
285}
286
287#[cfg(test)]
288mod tests {
289 use super::*;
290
291 fn run(program: &[isize], input: &[isize]) -> (Machine, Exit, Vec<isize>) {
292 let mut machine = Machine::with_program(program);
293 let mut output = Vec::new();
294
295 let exit = machine.run(input.iter().copied(), |a| output.push(a));
296 (machine, exit, output)
297 }
298
299 #[test]
300 fn day2a() {
301 let (machine, exit, _output) = run(&[1, 9, 10, 3, 2, 3, 11, 0, 99, 30, 40, 50], &[]);
302 assert_eq!(exit, Exit::Halted);
303 assert_eq!(machine.mem()[0], 3500);
304 }
305
306 #[test]
307 fn day5a_io() {
308 let (_machine, exit, output) = run(&[3, 0, 4, 0, 99], &[95243]);
309 assert_eq!(exit, Exit::Halted);
310 assert_eq!(output, &[95243]);
311 }
312
313 #[test]
314 fn day5a_mode() {
315 let (_machine, exit, _output) = run(&[1002, 4, 3, 4, 33], &[]);
316 assert_eq!(exit, Exit::Halted);
317 }
318
319 const DAY5B_CMP: &[isize] = &[
320 3, 21, 1008, 21, 8, 20, 1005, 20, 22, 107, 8, 21, 20, 1006, 20, 31, 1106, 0, 36, 98, 0, 0,
321 1002, 21, 125, 20, 4, 20, 1105, 1, 46, 104, 999, 1105, 1, 46, 1101, 1000, 1, 20, 4, 20,
322 1105, 1, 46, 98, 99,
323 ];
324
325 #[test]
326 fn day5b_cmp_lt() {
327 let (_machine, exit, output) = run(DAY5B_CMP, &[5]);
328 assert_eq!(exit, Exit::Halted);
329 assert_eq!(output, &[999]);
330 }
331
332 #[test]
333 fn day5b_cmp_gt() {
334 let (_machine, exit, output) = run(DAY5B_CMP, &[9]);
335 assert_eq!(exit, Exit::Halted);
336 assert_eq!(output, &[1001]);
337 }
338
339 #[test]
340 fn day5b_cmp_eq() {
341 let (_machine, exit, output) = run(DAY5B_CMP, &[8]);
342 assert_eq!(exit, Exit::Halted);
343 assert_eq!(output, &[1000]);
344 }
345
346 fn day7a(program: &[isize]) -> isize {
347 let mut result = isize::min_value();
348 for a in 0..5 {
349 let a_out = run(program, &[a, 0]).2[0];
350
351 for b in 0..5 {
352 if b == a {
353 continue;
354 }
355 let b_out = run(program, &[b, a_out]).2[0];
356
357 for c in 0..5 {
358 if c == a || c == b {
359 continue;
360 }
361 let c_out = run(program, &[c, b_out]).2[0];
362
363 for d in 0..5 {
364 if d == a || d == b || d == c {
365 continue;
366 }
367 let d_out = run(program, &[d, c_out]).2[0];
368
369 for e in 0..5 {
370 if e == a || e == b || e == c || e == d {
371 continue;
372 }
373 let e_out = run(program, &[e, d_out]).2[0];
374
375 result = result.max(e_out);
376 }
377 }
378 }
379 }
380 }
381
382 result
383 }
384
385 #[test]
386 fn day7a_1() {
387 const DAY7A_1: &[isize] = &[
388 3, 15, 3, 16, 1002, 16, 10, 16, 1, 16, 15, 15, 4, 15, 99, 0, 0,
389 ];
390
391 assert_eq!(day7a(DAY7A_1), 43210);
392 }
393
394 #[test]
395 fn day7a_2() {
396 const DAY7A_2: &[isize] = &[
397 3, 23, 3, 24, 1002, 24, 10, 24, 1002, 23, -1, 23, 101, 5, 23, 23, 1, 24, 23, 23, 4, 23, 99,
398 0, 0,
399 ];
400
401 assert_eq!(day7a(DAY7A_2), 54321);
402 }
403
404 #[test]
405 fn day7a_3() {
406 const DAY7A_3: &[isize] = &[
407 3, 31, 3, 32, 1002, 32, 10, 32, 1001, 31, -2, 31, 1007, 31, 0, 33, 1002, 33, 7, 33, 1, 33,
408 31, 31, 1, 32, 31, 31, 4, 31, 99, 0, 0, 0,
409 ];
410
411 assert_eq!(day7a(DAY7A_3), 65210);
412 }
413
414 fn day7b(program: &[isize]) -> isize {
415 use std::sync::mpsc;
416
417 let mut result = isize::min_value();
418
419 for a in 5..10 {
420 for b in 5..10 {
421 if b == a {
422 continue;
423 }
424 for c in 5..10 {
425 if c == a || c == b {
426 continue;
427 }
428 for d in 5..10 {
429 if d == a || d == b || d == c {
430 continue;
431 }
432 for e in 5..10 {
433 if e == a || e == b || e == c || e == d {
434 continue;
435 }
436
437 let (main_tx, a_rx) = mpsc::channel();
438 let (a_tx, b_rx) = mpsc::channel();
439 let (b_tx, c_rx) = mpsc::channel();
440 let (c_tx, d_rx) = mpsc::channel();
441 let (d_tx, e_rx) = mpsc::channel();
442 let (e_tx, main_rx) = mpsc::channel();
443
444 main_tx.send(a).unwrap();
445 a_tx.send(b).unwrap();
446 b_tx.send(c).unwrap();
447 c_tx.send(d).unwrap();
448 d_tx.send(e).unwrap();
449 main_tx.send(0).unwrap();
450
451 Machine::with_program(program)
452 .spawn(a_rx, move |x| a_tx.send(x).unwrap());
453 Machine::with_program(program)
454 .spawn(b_rx, move |x| b_tx.send(x).unwrap());
455 Machine::with_program(program)
456 .spawn(c_rx, move |x| c_tx.send(x).unwrap());
457 Machine::with_program(program)
458 .spawn(d_rx, move |x| d_tx.send(x).unwrap());
459 Machine::with_program(program)
460 .spawn(e_rx, move |x| e_tx.send(x).unwrap());
461
462 let mut last = 0;
463 for x in main_rx {
464 last = x;
465 let _ = main_tx.send(x);
466 }
467 result = result.max(last);
468 }
469 }
470 }
471 }
472 }
473
474 result
475 }
476
477 #[test]
478 fn day7b_1() {
479 const DAY7B_1: &[isize] = &[
480 3, 26, 1001, 26, -4, 26, 3, 27, 1002, 27, 2, 27, 1, 27, 26, 27, 4, 27, 1001, 28, -1, 28,
481 1005, 28, 6, 99, 0, 0, 5,
482 ];
483
484 assert_eq!(day7b(DAY7B_1), 139629729);
485 }
486
487 #[test]
488 fn day7b_2() {
489 const DAY7B_2: &[isize] = &[
490 3, 52, 1001, 52, -5, 52, 3, 53, 1, 52, 56, 54, 1007, 54, 5, 55, 1005, 55, 26, 1001, 54, -5,
491 54, 1105, 1, 12, 1, 53, 54, 53, 1008, 54, 0, 55, 1001, 55, 1, 55, 2, 53, 55, 53, 4, 53,
492 1001, 56, -1, 56, 1005, 56, 6, 99, 0, 0, 0, 0, 10,
493 ];
494
495 assert_eq!(day7b(DAY7B_2), 18216);
496 }
497
498 #[test]
499 fn day9_quine() {
500 const PROGRAM: &[isize] = &[109,1,204,-1,1001,100,1,100,1008,100,16,101,1006,101,0,99];
501
502 let (_machine, exit, output) = run(PROGRAM, &[]);
503 assert_eq!(exit, Exit::Halted);
504 assert_eq!(output, PROGRAM);
505 }
506
507 #[test]
508 fn day9_overflow_check() {
509 let (_machine, exit, output) = run(&[1102,34915192,34915192,7,4,7,99,0], &[]);
510 assert_eq!(exit, Exit::Halted);
511 assert_eq!(output, &[1219070632396864]);
512 }
513
514 #[test]
515 fn day9_read_check() {
516 let (_machine, exit, output) = run(&[104,1125899906842624,99], &[]);
517 assert_eq!(exit, Exit::Halted);
518 assert_eq!(output, &[1125899906842624]);
519 }
520}