Intcode computer to use bigints and unlimited memory space!

Also started a more complete error reporting scheme.

1 files changed, 129 insertions, 81 deletions

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>>()
+        );
+    }
+}