intcodeint/
lib.rs

1//! An intcode intepreter written in Rust!
2//!
3//! Intcode is a machine language specified in several challenges from
4//! [Advent of Code 2019](https://adventofcode.com/2019). This library provides a full
5//! implementation of the language that is compatible with every Intcode-based challenge.
6
7use std::convert::TryInto;
8use std::fmt;
9use std::thread::{self, JoinHandle};
10
11/// An instance of an Intcode virtual machine.
12#[derive(Debug)]
13pub struct Machine {
14    mem: Vec<isize>,
15    ip: isize,
16    base: isize,
17}
18
19impl Machine {
20    /// Constructs a new machine with the initial state:
21    ///
22    /// - empty `mem`;
23    /// - `ip` pointing to zero;
24    /// - `base` set at zero.
25    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    /// An immutable view into the virtual machine's memory.
40    pub fn mem(&self) -> &[isize] {
41        &self.mem
42    }
43
44    /// A mutable view into the virtual machine's memory.
45    pub fn mem_mut(&mut self) -> &mut [isize] {
46        &mut self.mem
47    }
48
49    /// Ensures that memory locations `0..size` are valid, extending memory with zeroes if needed.
50    pub fn reserve(&mut self, size: usize) {
51        if self.mem.len() < size {
52            self.mem.resize(size, 0);
53        }
54    }
55
56    /// Copies the given slice into memory at the given location.
57    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            // absolute pointer
84            0 => self.read(arg),
85
86            // immediate
87            1 => Ok(arg),
88
89            // relative pointer
90            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            // absolute pointer
103            0 => self.write(arg, val),
104
105            // relative pointer
106            2 => self.write(self.base + arg, val),
107
108            unknown => Err(Exit::IllegalMode(unknown)),
109        }
110    }
111
112    /// Executes a single instruction.
113    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            // add
119            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            // mul
128            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            // in
137            3 => {
138                let a = input.ok_or(Exit::Input)?;
139                self.out(1, a)?;
140                self.ip += 2;
141                Ok(())
142            }
143
144            // out
145            4 => {
146                let a = self.param(1)?;
147                self.ip += 2;
148                Err(Exit::Output(a))
149            }
150
151            // jt
152            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            // jf
164            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            // lt
176            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            // eq
185            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            // arb
194            9 => {
195                let a = self.param(1)?;
196                self.base += a;
197                self.ip += 2;
198                Ok(())
199            }
200
201            // halt
202            99 => Err(Exit::Halted),
203
204            unknown => Err(Exit::IllegalInstruction(unknown)),
205        }
206    }
207
208    /// Runs the program until the first error is encountered.
209    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    /// Runs the program using the given I/O interfaces.
219    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/// Errors that can occur during execution.
253#[derive(Debug, PartialEq)]
254pub enum Exit {
255    /// Attempted to use a negative value as a pointer.
256    NegativePointer,
257
258    /// Encountered an unknown parameter mode.
259    IllegalMode(isize),
260
261    /// Encountered an unknown instruction.
262    IllegalInstruction(isize),
263
264    /// The program encountered an `in` instruction and needs to take input.
265    Input,
266
267    /// The program encountered an `out` instruction and needs to return output.
268    Output(isize),
269
270    /// Encountered a halt instruction (99).
271    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}