Intcode computer to use bigints and unlimited memory space!

Also started a more complete error reporting scheme.

3 files changed, 152 insertions, 99 deletions

diff --git a/src/bin/day_2.rs b/src/bin/day_2.rs
index ce8fcaa..ba9e189 100644
--- a/src/bin/day_2.rs
+++ b/src/bin/day_2.rs
@@ -41,7 +41,9 @@ fn main() {
     match (opt.noun, opt.verb, opt.output) {
         (Some(noun), Some(verb), _) => {
             let result = exit_on_failed_assertion(
-                program.with_noun_verb_input(noun, verb).execute(),
+                program
+                    .with_noun_verb_input(noun, verb)
+                    .execute_returning_memory_0(),
                 "Program errored",
             );
             println!("{}", result);
@@ -52,7 +54,8 @@ fn main() {
             println!("({}, {})", noun, verb);
         }
         (None, None, None) => {
-            let result = exit_on_failed_assertion(program.execute(), "Program errored");
+            let result =
+                exit_on_failed_assertion(program.execute_returning_memory_0(), "Program errored");
             println!("{}", result);
         }
         _ => {
@@ -77,17 +80,17 @@ fn find_input(
     output: Intcode,
 ) -> Result<(Intcode, Intcode), IntcodeProgramError> {
     (0..99)
-        .flat_map(|noun| (0..99).map(move |verb| (noun, verb)))
+        .flat_map(|noun| (0..99).map(move |verb| (Intcode::from(noun), Intcode::from(verb))))
         .map(|(noun, verb)| {
             (
-                noun,
-                verb,
+                noun.clone(),
+                verb.clone(),
                 program
                     .with_noun_verb_input(noun, verb)
                     .execute_returning_memory_0(),
             )
         })
-        .find(|(_noun, _verb, out)| *out == Ok(Some(output)))
+        .find(|(_noun, _verb, out)| *out == Ok(output.clone()))
         .map(|(noun, verb, _out)| Ok((noun, verb)))
-        .unwrap_or(Err(IntcodeProgramError))
+        .unwrap_or(Err(IntcodeProgramError::Unknown))
 }
diff --git a/src/bin/day_7.rs b/src/bin/day_7.rs
index 0abf215..9b9177a 100644
--- a/src/bin/day_7.rs
+++ b/src/bin/day_7.rs
@@ -52,12 +52,12 @@ fn find_max_power(
     feedback_loop_mode: bool,
 ) -> Result<Intcode, IntcodeProgramError> {
     PhaseSetting::all(feedback_loop_mode)
-        .map(|phase| AmplifierArray::new(program, phase).execute())
+        .map(|phase| AmplifierArray::new(program, &phase).execute())
         .collect::<Result<Vec<Intcode>, _>>()
-        .map(|powers| powers.into_iter().max().unwrap_or(0))
+        .map(|powers| powers.into_iter().max().unwrap_or(Intcode::from(0)))
 }
 
-#[derive(Debug, Clone, Copy)]
+#[derive(Debug, Clone)]
 struct PhaseSetting([Intcode; 5]);
 
 impl PhaseSetting {
@@ -69,7 +69,7 @@ impl PhaseSetting {
         }
     }
 
-    fn permute(min: Intcode, max: Intcode) -> impl Iterator<Item = PhaseSetting> {
+    fn permute(min: i32, max: i32) -> impl Iterator<Item = PhaseSetting> {
         // This is an absolutely atrocious way to do the permutation,
         // but luckily it's only 5 elements long.
         (min..max)
@@ -77,12 +77,14 @@ impl PhaseSetting {
                 (min..max).flat_map(move |b| {
                     (min..max).flat_map(move |c| {
                         (min..max).flat_map(move |d| {
-                            (min..max).map(move |e| PhaseSetting([a, b, c, d, e]))
+                            (min..max).map(move |e| {
+                                PhaseSetting([a.into(), b.into(), c.into(), d.into(), e.into()])
+                            })
                         })
                     })
                 })
             })
-            .filter(move |phase| (min..max).all(|x| phase.0.contains(&x)))
+            .filter(move |phase| (min..max).all(|x| phase.0.contains(&x.into())))
     }
 }
 
@@ -92,7 +94,7 @@ struct AmplifierArray {
 }
 
 impl AmplifierArray {
-    fn new(program: &IntcodeProgram, phase: PhaseSetting) -> AmplifierArray {
+    fn new(program: &IntcodeProgram, phase: &PhaseSetting) -> AmplifierArray {
         AmplifierArray {
             amplifiers: (0..5)
                 .map(|n| AmplifierArray::new_amp(program, phase, n))
@@ -100,11 +102,11 @@ impl AmplifierArray {
         }
     }
 
-    fn new_amp(program: &IntcodeProgram, phase: PhaseSetting, n: usize) -> IntcodeProgram {
+    fn new_amp(program: &IntcodeProgram, phase: &PhaseSetting, n: usize) -> IntcodeProgram {
         if n == 0 {
-            program.with_input(list![phase.0[n], 0])
+            program.with_input(list![phase.0[n].clone(), Intcode::from(0)])
         } else {
-            program.with_input(list![phase.0[n]])
+            program.with_input(list![phase.0[n].clone()])
         }
     }
 
@@ -122,7 +124,7 @@ impl AmplifierArray {
         self.amplifiers
             .first()
             .and_then(|amp| amp.input.first().cloned())
-            .ok_or(IntcodeProgramError)
+            .ok_or(IntcodeProgramError::Unknown)
     }
 
     fn is_terminated(&self) -> bool {
diff --git a/src/lib.rs b/src/lib.rs
index 717505e..5a5f9b3 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1,18 +1,21 @@
+use num::bigint::BigInt;
+use num::traits::identities::Zero;
+use rpds::RedBlackTreeMap;
 use rpds::{list::List, vector::Vector};
 use std::fmt;
 use std::iter;
 use std::iter::FromIterator;
 use std::iter::IntoIterator;
 
-pub type Intcode = i32;
+pub type Intcode = BigInt;
 
 #[derive(Debug, Clone)]
 pub struct IntcodeProgram {
-    instruction_pointer: usize,
-    pub error: bool,
+    instruction_pointer: Intcode,
+    pub error: Option<IntcodeProgramError>,
     pub halted: bool,
     pub awaiting_input: bool,
-    memory: Vector<Intcode>,
+    memory: RedBlackTreeMap<Intcode, Intcode>,
     pub input: List<Intcode>,
     pub output: Vector<Intcode>,
 }
@@ -20,11 +23,15 @@ pub struct IntcodeProgram {
 impl FromIterator<Intcode> for IntcodeProgram {
     fn from_iter<I: IntoIterator<Item = Intcode>>(iter: I) -> Self {
         IntcodeProgram {
-            instruction_pointer: 0,
-            error: false,
+            instruction_pointer: Intcode::from(0),
+            error: None,
             halted: false,
             awaiting_input: false,
-            memory: iter.into_iter().collect(),
+            memory: iter
+                .into_iter()
+                .enumerate()
+                .map(|(addr, val)| (Intcode::from(addr), val))
+                .collect(),
             input: List::new(),
             output: Vector::new(),
         }
@@ -33,7 +40,8 @@ impl FromIterator<Intcode> for IntcodeProgram {
 
 impl IntcodeProgram {
     pub fn with_noun_verb_input(&self, noun: Intcode, verb: Intcode) -> IntcodeProgram {
-        self.with_memory_set(1, noun).with_memory_set(2, verb)
+        self.with_memory_set(1.into(), noun)
+            .with_memory_set(2.into(), verb)
     }
 
     pub fn with_input(&self, input: List<Intcode>) -> IntcodeProgram {
@@ -61,7 +69,7 @@ impl IntcodeProgram {
         self.run_to_termination().output_into_result()
     }
 
-    pub fn execute_returning_memory_0(&self) -> Result<Option<Intcode>, IntcodeProgramError> {
+    pub fn execute_returning_memory_0(&self) -> Result<Intcode, IntcodeProgramError> {
         self.run_to_termination().memory_0_into_result()
     }
 
@@ -81,7 +89,7 @@ impl IntcodeProgram {
         .unwrap()
     }
 
-    fn with_instruction_pointer(&self, instruction_pointer: usize) -> IntcodeProgram {
+    fn with_instruction_pointer(&self, instruction_pointer: Intcode) -> IntcodeProgram {
         IntcodeProgram {
             instruction_pointer,
             ..self.clone()
@@ -90,19 +98,16 @@ impl IntcodeProgram {
 
     fn with_instruction_pointer_offset(&self, offset: usize) -> IntcodeProgram {
         IntcodeProgram {
-            instruction_pointer: self.instruction_pointer + offset,
+            instruction_pointer: self.instruction_pointer.clone() + offset,
             ..self.clone()
         }
     }
 
-    fn with_memory_set(&self, address: usize, value: Intcode) -> IntcodeProgram {
-        self.memory
-            .set(address, value)
-            .map(|memory| IntcodeProgram {
-                memory,
-                ..self.clone()
-            })
-            .unwrap_or(self.error())
+    fn with_memory_set(&self, address: Intcode, value: Intcode) -> IntcodeProgram {
+        IntcodeProgram {
+            memory: self.memory.insert(address, value),
+            ..self.clone()
+        }
     }
 
     fn with_input_consumed(&self) -> IntcodeProgram {
@@ -112,7 +117,7 @@ impl IntcodeProgram {
                 input,
                 ..self.clone()
             })
-            .unwrap_or(self.error())
+            .unwrap_or(self.error(IntcodeProgramError::Unknown))
     }
 
     fn with_output(&self, print: Intcode) -> IntcodeProgram {
@@ -123,25 +128,26 @@ impl IntcodeProgram {
     }
 
     fn output_into_result(&self) -> Result<Vector<Intcode>, IntcodeProgramError> {
-        if self.error {
-            Err(IntcodeProgramError)
-        } else {
-            Ok(self.output.clone())
+        match self.error {
+            Some(ref error) => Err(error.clone()),
+            None => Ok(self.output.clone()),
         }
     }
 
-    fn memory_0_into_result(&self) -> Result<Option<Intcode>, IntcodeProgramError> {
-        if self.error {
-            Err(IntcodeProgramError)
-        } else {
-            Ok(self.memory.get(0).cloned())
+    fn memory_0_into_result(&self) -> Result<Intcode, IntcodeProgramError> {
+        match self.error {
+            Some(ref error) => Err(error.clone()),
+            None => Ok(self
+                .memory
+                .get(&Intcode::from(0))
+                .cloned()
+                .unwrap_or(Intcode::from(0))),
         }
     }
     fn next(&self) -> IntcodeProgram {
-        //eprintln!("{:?}", self);
         self.memory
-            .get(self.instruction_pointer)
-            .map(|&opcode| match opcode % 100 {
+            .get(&self.instruction_pointer)
+            .map(|opcode| match opcode.to_radix_le(100).1[0] {
                 1 => self.add(opcode),
                 2 => self.multiply(opcode),
                 3 => self.input(opcode),
@@ -151,77 +157,79 @@ impl IntcodeProgram {
                 7 => self.less_than(opcode),
                 8 => self.equals(opcode),
                 99 => self.halt(),
-                _ => self.error(),
+                unknown => self.error(IntcodeProgramError::InvalidOpcode(unknown.clone())),
             })
-            .unwrap_or(self.error())
+            .unwrap_or(self.error(IntcodeProgramError::Unknown))
     }
 
-    fn add(&self, mode: Intcode) -> IntcodeProgram {
+    fn add(&self, mode: &Intcode) -> IntcodeProgram {
         match (self.get(1, mode), self.get(2, mode), self.get_immediate(3)) {
-            (Some(in1), Some(in2), Some(out)) => self
+            (in1, in2, out) => self
                 .with_instruction_pointer_offset(4)
-                .with_memory_set(out as usize, in1 + in2),
-            _ => self.error(),
+                .with_memory_set(out, in1 + in2),
         }
     }
 
-    fn multiply(&self, mode: Intcode) -> IntcodeProgram {
+    fn multiply(&self, mode: &Intcode) -> IntcodeProgram {
         match (self.get(1, mode), self.get(2, mode), self.get_immediate(3)) {
-            (Some(in1), Some(in2), Some(out)) => self
+            (in1, in2, out) => self
                 .with_instruction_pointer_offset(4)
-                .with_memory_set(out as usize, in1 * in2),
-            _ => self.error(),
+                .with_memory_set(out, in1 * in2),
         }
     }
 
-    fn input(&self, _mode: Intcode) -> IntcodeProgram {
+    fn input(&self, _mode: &Intcode) -> IntcodeProgram {
         match (self.input.first().cloned(), self.get_immediate(1)) {
-            (Some(input), Some(out)) => self
+            (Some(input), out) => self
                 .with_instruction_pointer_offset(2)
-                .with_memory_set(out as usize, input)
+                .with_memory_set(out, input)
                 .with_input_consumed(),
-            (None, Some(_out)) => self.await_input(),
-            _ => self.error(),
+            (None, _out) => self.await_input(),
         }
     }
 
-    fn output(&self, mode: Intcode) -> IntcodeProgram {
+    fn output(&self, mode: &Intcode) -> IntcodeProgram {
         match self.get(1, mode) {
-            Some(print) => self.with_instruction_pointer_offset(2).with_output(print),
-            _ => self.error(),
+            print => self.with_instruction_pointer_offset(2).with_output(print),
         }
     }
 
-    fn jump_if_true(&self, mode: Intcode) -> IntcodeProgram {
+    fn jump_if_true(&self, mode: &Intcode) -> IntcodeProgram {
         match (self.get(1, mode), self.get(2, mode)) {
-            (Some(pred), Some(to)) if pred != 0 => self.with_instruction_pointer(to as usize),
-            (Some(_), Some(_)) => self.with_instruction_pointer_offset(3),
-            _ => self.error(),
+            (ref pred, ref to) if !pred.is_zero() => self.with_instruction_pointer(to.clone()),
+            (_, _) => self.with_instruction_pointer_offset(3),
         }
     }
-    fn jump_if_false(&self, mode: Intcode) -> IntcodeProgram {
+    fn jump_if_false(&self, mode: &Intcode) -> IntcodeProgram {
         match (self.get(1, mode), self.get(2, mode)) {
-            (Some(pred), Some(to)) if pred == 0 => self.with_instruction_pointer(to as usize),
-            (Some(_), Some(_)) => self.with_instruction_pointer_offset(3),
-            _ => self.error(),
+            (ref pred, ref to) if pred.is_zero() => self.with_instruction_pointer(to.clone()),
+            (_, _) => self.with_instruction_pointer_offset(3),
         }
     }
 
-    fn less_than(&self, mode: Intcode) -> IntcodeProgram {
+    fn less_than(&self, mode: &Intcode) -> IntcodeProgram {
         match (self.get(1, mode), self.get(2, mode), self.get_immediate(3)) {
-            (Some(in1), Some(in2), Some(out)) => self
-                .with_instruction_pointer_offset(4)
-                .with_memory_set(out as usize, if in1 < in2 { 1 } else { 0 }),
-            _ => self.error(),
+            (in1, in2, out) => self.with_instruction_pointer_offset(4).with_memory_set(
+                out,
+                if in1 < in2 {
+                    Intcode::from(1)
+                } else {
+                    Intcode::from(0)
+                },
+            ),
         }
     }
 
-    fn equals(&self, mode: Intcode) -> IntcodeProgram {
+    fn equals(&self, mode: &Intcode) -> IntcodeProgram {
         match (self.get(1, mode), self.get(2, mode), self.get_immediate(3)) {
-            (Some(in1), Some(in2), Some(out)) => self
-                .with_instruction_pointer_offset(4)
-                .with_memory_set(out as usize, if in1 == in2 { 1 } else { 0 }),
-            _ => self.error(),
+            (in1, in2, out) => self.with_instruction_pointer_offset(4).with_memory_set(
+                out,
+                if in1 == in2 {
+                    Intcode::from(1)
+                } else {
+                    Intcode::from(0)
+                },
+            ),
         }
     }
 
@@ -246,41 +254,81 @@ impl IntcodeProgram {
         }
     }
 
-    fn error(&self) -> IntcodeProgram {
+    fn error(&self, error: IntcodeProgramError) -> IntcodeProgram {
         IntcodeProgram {
             halted: true,
-            error: true,
+            error: Some(error),
             ..self.clone()
         }
     }
 
-    fn get(&self, pointer_offset: usize, mode: Intcode) -> Option<Intcode> {
-        match mode / (10 as Intcode).pow(pointer_offset as u32 + 1) % 10 {
+    fn get(&self, pointer_offset: usize, mode: &Intcode) -> Intcode {
+        match mode
+            .to_radix_le(10)
+            .1
+            .get(pointer_offset + 2)
+            .cloned()
+            .unwrap_or(0)
+        {
             0 => self.get_position(pointer_offset),
             1 => self.get_immediate(pointer_offset),
-            _ => None,
+            _ => Intcode::from(0), // TODO: Relative mode
         }
     }
 
-    fn get_immediate(&self, pointer_offset: usize) -> Option<Intcode> {
+    fn get_immediate(&self, pointer_offset: usize) -> Intcode {
         self.memory
-            .get(self.instruction_pointer + pointer_offset)
+            .get(&(self.instruction_pointer.clone() + pointer_offset))
             .cloned()
+            .unwrap_or(Intcode::from(0))
     }
 
-    fn get_position(&self, pointer_offset: usize) -> Option<Intcode> {
-        self.get_immediate(pointer_offset)
-            .and_then(|r| self.memory.get(r as usize))
+    fn get_position(&self, pointer_offset: usize) -> Intcode {
+        self.memory
+            .get(&self.get_immediate(pointer_offset))
             .cloned()
+            .unwrap_or(Intcode::from(0))
     }
 }
 
-#[derive(Debug, PartialEq)]
-pub struct IntcodeProgramError;
+#[derive(Debug, PartialEq, Clone)]
+pub enum IntcodeProgramError {
+    InvalidOpcode(u8),
+    Unknown,
+}
 
 impl fmt::Display for IntcodeProgramError {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        write!(f, "Unknown error")
+        use IntcodeProgramError::*;
+
+        match self {
+            InvalidOpcode(i) => write!(f, "{} is not a valid opcode", i),
+            Unknown => write!(f, "Unknown error"),
+        }
     }
 }
 impl std::error::Error for IntcodeProgramError {}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn day_2_example_1() {
+        let program: IntcodeProgram = vec![1, 0, 0, 0, 99]
+            .into_iter()
+            .map(Intcode::from)
+            .collect::<IntcodeProgram>()
+            .run_to_termination();
+
+        assert_eq!(program.error, None);
+        assert_eq!(
+            program.memory,
+            vec![2, 0, 0, 0, 99]
+                .into_iter()
+                .enumerate()
+                .map(|(i, val)| (Intcode::from(i), Intcode::from(val)))
+                .collect::<RedBlackTreeMap<Intcode, Intcode>>()
+        );
+    }
+}