1use std::collections::VecDeque;
2
3#[derive(Debug, Clone)]
4pub struct IntcodeVM {
5 memory: Vec<i64>,
6 pc: usize,
7 halted: bool,
8 input: VecDeque<i64>,
9 output: VecDeque<i64>,
10}
11
12#[derive(Debug, Clone, PartialEq)]
13pub enum ExecutionError {
14 InvalidPC,
15 InvalidAddress,
16 AlreadyHalted,
17 NeedsInput,
18 ImmediateModeWrite,
19 UnknownOpcode(i64),
20 UnknownMode(u8),
21}
22
23type Result<T> = std::result::Result<T, ExecutionError>;
24
25#[derive(Debug, Clone, Copy, PartialEq)]
26pub enum ParameterMode {
27 Position,
28 Immediate,
29}
30
31impl ParameterMode {
32 pub fn from_opcode(opcode: i64, parameter_index: u32) -> Result<Self> {
33 let place_value = 10i64.pow(parameter_index + 2);
34
35 let mode_value = ((opcode / place_value) % 10) as u8;
36
37 match mode_value {
38 0 => Ok(ParameterMode::Position),
39 1 => Ok(ParameterMode::Immediate),
40 unknown => Err(ExecutionError::UnknownMode(unknown)),
41 }
42 }
43}
44
45#[derive(Debug, Clone, PartialEq)]
46pub enum Opcode {
47 Add(ParameterMode, ParameterMode, ParameterMode),
48 Multiply(ParameterMode, ParameterMode, ParameterMode),
49 Input(ParameterMode),
50 Output(ParameterMode),
51 JumpIfTrue(ParameterMode, ParameterMode),
52 JumpIfFalse(ParameterMode, ParameterMode),
53 LessThan(ParameterMode, ParameterMode, ParameterMode),
54 Equals(ParameterMode, ParameterMode, ParameterMode),
55 Halt,
56}
57
58impl Opcode {
59 pub fn from_raw(raw: i64) -> Result<Self> {
64 match raw % 100 {
65 1 => Ok(Self::Add(
66 ParameterMode::from_opcode(raw, 0)?,
67 ParameterMode::from_opcode(raw, 1)?,
68 ParameterMode::from_opcode(raw, 2)?,
69 )),
70 2 => Ok(Self::Multiply(
71 ParameterMode::from_opcode(raw, 0)?,
72 ParameterMode::from_opcode(raw, 1)?,
73 ParameterMode::from_opcode(raw, 2)?,
74 )),
75 3 => Ok(Self::Input(ParameterMode::from_opcode(raw, 0)?)),
76 4 => Ok(Self::Output(ParameterMode::from_opcode(raw, 0)?)),
77 5 => Ok(Self::JumpIfTrue(
78 ParameterMode::from_opcode(raw, 0)?,
79 ParameterMode::from_opcode(raw, 1)?,
80 )),
81 6 => Ok(Self::JumpIfFalse(
82 ParameterMode::from_opcode(raw, 0)?,
83 ParameterMode::from_opcode(raw, 1)?,
84 )),
85 7 => Ok(Self::LessThan(
86 ParameterMode::from_opcode(raw, 0)?,
87 ParameterMode::from_opcode(raw, 1)?,
88 ParameterMode::from_opcode(raw, 2)?,
89 )),
90 8 => Ok(Self::Equals(
91 ParameterMode::from_opcode(raw, 0)?,
92 ParameterMode::from_opcode(raw, 1)?,
93 ParameterMode::from_opcode(raw, 2)?,
94 )),
95 99 => Ok(Self::Halt),
96 unknown => Err(ExecutionError::UnknownOpcode(unknown)),
97 }
98 }
99}
100
101impl IntcodeVM {
102 pub fn new<D: Into<Vec<i64>>>(data: D) -> Self {
104 Self {
105 memory: data.into(),
106 pc: 0,
107 halted: false,
108 input: VecDeque::new(),
109 output: VecDeque::new(),
110 }
111 }
112
113 pub fn from_stdin() -> std::io::Result<Self> {
115 use std::io::prelude::*;
116
117 let mut buffer = String::new();
118 std::io::stdin().read_to_string(&mut buffer)?;
119
120 let mut data = Vec::new();
121
122 for item in buffer.trim().split(',') {
123 let num: i64 = item
124 .parse()
125 .map_err(|e| std::io::Error::new(std::io::ErrorKind::Other, Box::new(e)))?;
126 data.push(num)
127 }
128
129 Ok(Self::new(data))
130 }
131
132 pub fn push_input(&mut self, input: i64) {
134 self.input.push_back(input)
135 }
136
137 pub fn push_inputs<I: IntoIterator<Item = i64>>(&mut self, input: I) {
139 self.input.extend(input)
140 }
141
142 pub fn pop_output(&mut self) -> Option<i64> {
144 self.output.pop_front()
145 }
146
147 pub fn iter_output<'a>(&'a self) -> impl Iterator<Item = &i64> {
149 self.output.iter()
150 }
151
152 pub fn current_raw_opcode(&self) -> Result<i64> {
154 self.get_memory(self.pc)
155 .map_err(|_| ExecutionError::InvalidPC)
156 }
157
158 pub fn get_memory(&self, index: usize) -> Result<i64> {
160 self.memory
161 .get(index)
162 .map(|v| *v)
163 .ok_or(ExecutionError::InvalidPC)
164 }
165
166 pub fn set_memory(&mut self, index: usize, value: i64) -> Result<()> {
168 self.memory
169 .get_mut(index)
170 .map(|v| *v = value)
171 .ok_or(ExecutionError::InvalidAddress)
172 }
173
174 pub fn get_memory_by_pointer(&self, index: usize) -> Result<i64> {
176 self.get_memory(Self::value_to_index(self.get_memory(index)?)?)
177 }
178
179 pub fn set_memory_by_pointer(&mut self, index: usize, value: i64) -> Result<()> {
181 self.set_memory(Self::value_to_index(self.get_memory(index)?)?, value)
182 }
183
184 pub fn get_parameter(&mut self, mode: ParameterMode, offset: usize) -> Result<i64> {
186 match mode {
187 ParameterMode::Immediate => self.get_memory(self.pc + offset),
188 ParameterMode::Position => self.get_memory_by_pointer(self.pc + offset),
189 }
190 }
191
192 pub fn set_parameter(&mut self, mode: ParameterMode, offset: usize, value: i64) -> Result<()> {
194 match mode {
195 ParameterMode::Immediate => Err(ExecutionError::ImmediateModeWrite),
196 ParameterMode::Position => self.set_memory_by_pointer(self.pc + offset, value),
197 }
198 }
199
200 pub fn memory(&self) -> &[i64] {
202 &self.memory
203 }
204
205 pub fn step(&mut self) -> Result<bool> {
212 if self.halted() {
213 return Err(ExecutionError::AlreadyHalted);
214 }
215
216 let opcode = Opcode::from_raw(self.current_raw_opcode()?)?;
217
218 match &opcode {
219 &Opcode::Add(in1, in2, out) => {
220 let val1 = self.get_parameter(in1, 1)?;
221 let val2 = self.get_parameter(in2, 2)?;
222 let result = val1 + val2;
223 self.set_parameter(out, 3, result)?;
224 self.pc_advance(&opcode);
225 }
226 &Opcode::Multiply(in1, in2, out) => {
227 let val1 = self.get_parameter(in1, 1)?;
228 let val2 = self.get_parameter(in2, 2)?;
229 let result = val1 * val2;
230 self.set_parameter(out, 3, result)?;
231 self.pc_advance(&opcode);
232 }
233 &Opcode::Input(out) => {
234 let val = self.input.pop_front().ok_or(ExecutionError::NeedsInput)?;
235 self.set_parameter(out, 1, val)?;
236 self.pc_advance(&opcode);
237 }
238 &Opcode::Output(in1) => {
239 let val = self.get_parameter(in1, 1)?;
240 self.output.push_back(val);
241 self.pc_advance(&opcode);
242 }
243 &Opcode::JumpIfTrue(in1, in2) => {
244 let val = self.get_parameter(in1, 1)?;
245 let new_loc = self.get_parameter(in2, 2)?;
246
247 if val != 0 {
248 self.pc = Self::value_to_index(new_loc)?;
249 } else {
250 self.pc_advance(&opcode);
251 }
252 }
253 &Opcode::JumpIfFalse(in1, in2) => {
254 let val = self.get_parameter(in1, 1)?;
255 let new_loc = self.get_parameter(in2, 2)?;
256
257 if val == 0 {
258 self.pc = Self::value_to_index(new_loc)?;
259 } else {
260 self.pc_advance(&opcode);
261 }
262 }
263 &Opcode::LessThan(in1, in2, out) => {
264 let val1 = self.get_parameter(in1, 1)?;
265 let val2 = self.get_parameter(in2, 2)?;
266 let result = if val1 < val2 { 1 } else { 0 };
267 self.set_parameter(out, 3, result)?;
268 self.pc_advance(&opcode);
269 }
270 &Opcode::Equals(in1, in2, out) => {
271 let val1 = self.get_parameter(in1, 1)?;
272 let val2 = self.get_parameter(in2, 2)?;
273 let result = if val1 == val2 { 1 } else { 0 };
274 self.set_parameter(out, 3, result)?;
275 self.pc_advance(&opcode);
276 }
277 &Opcode::Halt => self.halted = true,
278 };
279
280 Ok(!self.halted)
281 }
282
283 pub fn run_to_end(&mut self) -> Result<()> {
285 while self.step()? {}
286
287 Ok(())
288 }
289
290 pub fn next_output(&mut self) -> Result<Option<i64>> {
294 let mut keep_going = true;
295
296 while self.output.is_empty() && keep_going {
297 keep_going = self.step()?;
298 }
299
300 Ok(self.output.pop_front())
301 }
302
303 pub fn halted(&self) -> bool {
305 self.halted
306 }
307
308 fn pc_advance(&mut self, opcode: &Opcode) {
309 use Opcode::*;
310
311 let advance = match opcode {
312 Add(..) => 4,
313 Multiply(..) => 4,
314 Input(..) => 2,
315 Output(..) => 2,
316 JumpIfTrue(..) => 3,
317 JumpIfFalse(..) => 3,
318 LessThan(..) => 4,
319 Equals(..) => 4,
320 Halt => 1,
321 };
322
323 self.pc += advance;
324 }
325
326 fn value_to_index(value: i64) -> Result<usize> {
327 use std::convert::TryInto;
328
329 value.try_into().map_err(|_| ExecutionError::InvalidAddress)
330 }
331}
332
333impl Iterator for IntcodeVM {
334 type Item = i64;
335
336 fn next(&mut self) -> Option<Self::Item> {
337 self.output.pop_front()
338 }
339}
340
341#[cfg(test)]
342mod test {
343 use super::*;
344
345 #[test]
346 fn parse_parameter_mode() {
347 assert_eq!(
348 ParameterMode::from_opcode(1002, 0),
349 Ok(ParameterMode::Position)
350 );
351 assert_eq!(
352 ParameterMode::from_opcode(1002, 1),
353 Ok(ParameterMode::Immediate)
354 );
355 assert_eq!(
356 ParameterMode::from_opcode(1002, 2),
357 Ok(ParameterMode::Position)
358 );
359
360 assert_eq!(
361 ParameterMode::from_opcode(81002, 2),
362 Err(ExecutionError::UnknownMode(8))
363 );
364 }
365
366 #[test]
367 fn parse_opcode() {
368 use Opcode::*;
369 use ParameterMode::*;
370
371 assert_eq!(Opcode::from_raw(1), Ok(Add(Position, Position, Position)));
372 assert_eq!(
373 Opcode::from_raw(2),
374 Ok(Multiply(Position, Position, Position))
375 );
376 assert_eq!(Opcode::from_raw(3), Ok(Input(Position)));
377 assert_eq!(Opcode::from_raw(4), Ok(Output(Position)));
378 assert_eq!(Opcode::from_raw(5), Ok(JumpIfTrue(Position, Position)));
379 assert_eq!(Opcode::from_raw(6), Ok(JumpIfFalse(Position, Position)));
380 assert_eq!(
381 Opcode::from_raw(7),
382 Ok(LessThan(Position, Position, Position))
383 );
384 assert_eq!(
385 Opcode::from_raw(8),
386 Ok(Equals(Position, Position, Position))
387 );
388 assert_eq!(Opcode::from_raw(99), Ok(Halt));
389
390 assert_eq!(
391 Opcode::from_raw(1002),
392 Ok(Multiply(Position, Immediate, Position))
393 );
394 assert_eq!(
395 Opcode::from_raw(1101),
396 Ok(Add(Immediate, Immediate, Position))
397 );
398
399 assert_eq!(Opcode::from_raw(2101), Err(ExecutionError::UnknownMode(2)));
400
401 for opcode in 9..98 {
402 assert_eq!(
403 Opcode::from_raw(opcode),
404 Err(ExecutionError::UnknownOpcode(opcode))
405 );
406 }
407 }
408
409 #[test]
410 fn next_output() {
411 let mut vm = IntcodeVM::new(vec![104, 1, 104, 2, 104, 3, 99]);
413
414 assert_eq!(vm.next_output(), Ok(Some(1)));
415 assert_eq!(vm.next_output(), Ok(Some(2)));
416 assert_eq!(vm.next_output(), Ok(Some(3)));
417 assert_eq!(vm.next_output(), Ok(None));
418 assert_eq!(vm.next_output(), Err(ExecutionError::AlreadyHalted));
419 }
420
421 #[test]
422 fn mess_with_memory() {
423 let mut vm = IntcodeVM::new(vec![1, 2, 3, 4, 5]);
424
425 assert_eq!(vm.current_raw_opcode(), Ok(1));
426 assert_eq!(vm.get_memory(4), Ok(5));
427 assert_eq!(vm.set_memory(0, 2), Ok(()));
428 assert_eq!(vm.set_memory(4, 12), Ok(()));
429 assert_eq!(vm.current_raw_opcode(), Ok(2));
430 assert_eq!(vm.get_memory(4), Ok(12));
431 }
432
433 #[test]
434 fn run_after_halt() {
435 let mut vm = IntcodeVM::new(vec![1, 0, 0, 0, 99]);
436
437 vm.run_to_end().unwrap();
438 assert_eq!(vm.step(), Err(ExecutionError::AlreadyHalted));
439 }
440
441 #[test]
442 fn input_output() {
443 let mut single_io = IntcodeVM::new(vec![3, 0, 4, 0, 99]);
444 single_io.push_input(5);
445 single_io.run_to_end().unwrap();
446 assert_eq!(single_io.pop_output(), Some(5));
447
448 let mut flip_io = IntcodeVM::new(vec![3, 0, 3, 1, 4, 1, 4, 0, 99]);
449 flip_io.push_inputs([100, 200].iter().copied());
450 flip_io.run_to_end().unwrap();
451 assert_eq!(flip_io.pop_output(), Some(200));
452 assert_eq!(flip_io.pop_output(), Some(100));
453
454 let mut quadruple_sum = IntcodeVM::new(vec![
456 3, 0, 3, 1, 1, 0, 1, 0, 102, 4, 0, 0, 4, 0, 99,
462 ]);
463 quadruple_sum.push_inputs([4, 6].iter().copied());
464 quadruple_sum.run_to_end().unwrap();
465 assert_eq!(quadruple_sum.pop_output(), Some(40));
466 }
467
468 #[test]
469 fn opcode_based_on_input() {
470 let program = vec![
473 3, 0, 3, 1, 3, 6, 99, 0, 1,
477 2, 4, 2, 99, ];
481
482 let mut add_vm = IntcodeVM::new(program.clone());
483 add_vm.push_inputs([4, 5, 1].iter().cloned());
484 add_vm.run_to_end().unwrap();
485 assert_eq!(add_vm.pop_output(), Some(9));
486
487 let mut mul_vm = IntcodeVM::new(program.clone());
488 mul_vm.push_inputs([4, 5, 2].iter().cloned());
489 mul_vm.run_to_end().unwrap();
490 assert_eq!(mul_vm.pop_output(), Some(20));
491 }
492
493 #[test]
494 fn given_example_day2_1() {
495 let mut vm = IntcodeVM::new(vec![1, 9, 10, 3, 2, 3, 11, 0, 99, 30, 40, 50]);
496
497 assert_eq!(vm.step(), Ok(true));
498
499 assert!(!vm.halted());
500 assert_eq!(vm.memory(), &[1, 9, 10, 70, 2, 3, 11, 0, 99, 30, 40, 50]);
501
502 assert_eq!(vm.step(), Ok(true));
503
504 assert!(!vm.halted());
505 assert_eq!(vm.memory(), &[3500, 9, 10, 70, 2, 3, 11, 0, 99, 30, 40, 50]);
506
507 assert_eq!(vm.step(), Ok(false));
508 assert!(vm.halted());
509 }
510
511 #[test]
512 fn given_example_day2_2() {
513 let mut vm1 = IntcodeVM::new(vec![1, 0, 0, 0, 99]);
514 let mut vm2 = IntcodeVM::new(vec![2, 3, 0, 3, 99]);
515 let mut vm3 = IntcodeVM::new(vec![2, 4, 4, 5, 99, 0]);
516 let mut vm4 = IntcodeVM::new(vec![1, 1, 1, 4, 99, 5, 6, 0, 99]);
517
518 vm1.run_to_end().unwrap();
519 vm2.run_to_end().unwrap();
520 vm3.run_to_end().unwrap();
521 vm4.run_to_end().unwrap();
522
523 assert_eq!(vm1.memory(), &[2, 0, 0, 0, 99]);
524 assert_eq!(vm2.memory(), &[2, 3, 0, 6, 99]);
525 assert_eq!(vm3.memory(), &[2, 4, 4, 5, 99, 9801]);
526 assert_eq!(vm4.memory(), &[30, 1, 1, 4, 2, 5, 6, 0, 99]);
527 }
528
529 #[test]
530 fn given_examples_day5_2_comp() {
531 let eq_p = IntcodeVM::new(vec![3, 9, 8, 9, 10, 9, 4, 9, 99, -1, 8]);
532 let eq_i = IntcodeVM::new(vec![3, 3, 1108, -1, 8, 3, 4, 3, 99]);
533 let lt_p = IntcodeVM::new(vec![3, 9, 7, 9, 10, 9, 4, 9, 99, -1, 8]);
534 let lt_i = IntcodeVM::new(vec![3, 3, 1107, -1, 8, 3, 4, 3, 99]);
535
536 {
537 let mut eq_p_7 = eq_p.clone();
538 eq_p_7.push_input(7);
539 eq_p_7.run_to_end().unwrap();
540 assert_eq!(eq_p_7.pop_output(), Some(0));
541
542 let mut eq_p_8 = eq_p.clone();
543 eq_p_8.push_input(8);
544 eq_p_8.run_to_end().unwrap();
545 assert_eq!(eq_p_8.pop_output(), Some(1));
546
547 let mut eq_p_9 = eq_p.clone();
548 eq_p_9.push_input(9);
549 eq_p_9.run_to_end().unwrap();
550 assert_eq!(eq_p_9.pop_output(), Some(0));
551 }
552
553 {
554 let mut lt_i_7 = lt_i.clone();
555 lt_i_7.push_input(7);
556 lt_i_7.run_to_end().unwrap();
557 assert_eq!(lt_i_7.pop_output(), Some(1));
558
559 let mut lt_i_8 = lt_i.clone();
560 lt_i_8.push_input(8);
561 lt_i_8.run_to_end().unwrap();
562 assert_eq!(lt_i_8.pop_output(), Some(0));
563
564 let mut lt_i_9 = lt_i.clone();
565 lt_i_9.push_input(9);
566 lt_i_9.run_to_end().unwrap();
567 assert_eq!(lt_i_9.pop_output(), Some(0));
568 }
569
570 {
571 let mut lt_p_7 = lt_p.clone();
572 lt_p_7.push_input(7);
573 lt_p_7.run_to_end().unwrap();
574 assert_eq!(lt_p_7.pop_output(), Some(1));
575
576 let mut lt_p_8 = lt_p.clone();
577 lt_p_8.push_input(8);
578 lt_p_8.run_to_end().unwrap();
579 assert_eq!(lt_p_8.pop_output(), Some(0));
580
581 let mut lt_p_9 = lt_p.clone();
582 lt_p_9.push_input(9);
583 lt_p_9.run_to_end().unwrap();
584 assert_eq!(lt_p_9.pop_output(), Some(0));
585 }
586
587 {
588 let mut eq_i_7 = eq_i.clone();
589 eq_i_7.push_input(7);
590 eq_i_7.run_to_end().unwrap();
591 assert_eq!(eq_i_7.pop_output(), Some(0));
592
593 let mut eq_i_8 = eq_i.clone();
594 eq_i_8.push_input(8);
595 eq_i_8.run_to_end().unwrap();
596 assert_eq!(eq_i_8.pop_output(), Some(1));
597
598 let mut eq_i_9 = eq_i.clone();
599 eq_i_9.push_input(9);
600 eq_i_9.run_to_end().unwrap();
601 assert_eq!(eq_i_9.pop_output(), Some(0));
602 }
603 }
604
605 #[test]
606 fn test_given_examples_day5_2_jump() {
607 let pos = IntcodeVM::new(vec![
608 3, 12, 6, 12, 15, 1, 13, 14, 13, 4, 13, 99, -1, 0, 1, 9,
611 ]);
612 let imm = IntcodeVM::new(vec![3, 3, 1105, -1, 9, 1101, 0, 0, 12, 4, 12, 99, 1]);
613
614 let big = IntcodeVM::new(vec![
615 3, 21, 1008, 21, 8, 20, 1005, 20, 22, 107, 8, 21, 20, 1006, 20, 31, 1106, 0, 36, 98, 0,
616 0, 1002, 21, 125, 20, 4, 20, 1105, 1, 46, 104, 999, 1105, 1, 46, 1101, 1000, 1, 20, 4,
617 20, 1105, 1, 46, 98, 99,
618 ]);
619
620 {
621 let mut pos_0 = pos.clone();
622 pos_0.push_input(0);
623 pos_0.run_to_end().unwrap();
624 assert_eq!(pos_0.pop_output(), Some(0));
625
626 let mut pos_10 = pos.clone();
627 pos_10.push_input(10);
628 pos_10.run_to_end().unwrap();
629 assert_eq!(pos_10.pop_output(), Some(1));
630 }
631
632 {
633 let mut imm_0 = imm.clone();
634 imm_0.push_input(0);
635 imm_0.run_to_end().unwrap();
636 assert_eq!(imm_0.pop_output(), Some(0));
637
638 let mut imm_10 = imm.clone();
639 imm_10.push_input(10);
640 imm_10.run_to_end().unwrap();
641 assert_eq!(imm_10.pop_output(), Some(1));
642 }
643
644 {
645 let mut big_7 = big.clone();
646 big_7.push_input(7);
647 big_7.run_to_end().unwrap();
648 assert_eq!(big_7.pop_output(), Some(999));
649
650 let mut big_8 = big.clone();
651 big_8.push_input(8);
652 big_8.run_to_end().unwrap();
653 assert_eq!(big_8.pop_output(), Some(1000));
654
655 let mut big_9 = big.clone();
656 big_9.push_input(9);
657 big_9.run_to_end().unwrap();
658 assert_eq!(big_9.pop_output(), Some(1001));
659 }
660 }
661}