Day 2: Intcode machine!

5 files changed, 270 insertions, 5 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 149a347..9a70fd1 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -5,6 +5,7 @@ name = "advent-of-code-2019"
 version = "0.1.0"
 dependencies = [
  "derive_more 0.99.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "im 14.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "structopt 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
@@ -31,6 +32,14 @@ version = "1.2.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
+name = "bitmaps"
+version = "2.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "typenum 1.11.2 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "clap"
 version = "2.33.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -63,6 +72,19 @@ dependencies = [
 ]
 
 [[package]]
+name = "im"
+version = "14.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "bitmaps 2.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_core 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_xoshiro 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "sized-chunks 0.5.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "typenum 1.11.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "version_check 0.9.1 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "libc"
 version = "0.2.66"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -94,6 +116,28 @@ dependencies = [
 ]
 
 [[package]]
+name = "rand_core"
+version = "0.5.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
+name = "rand_xoshiro"
+version = "0.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "rand_core 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "sized-chunks"
+version = "0.5.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "bitmaps 2.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "typenum 1.11.2 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "strsim"
 version = "0.8.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -138,6 +182,11 @@ dependencies = [
 ]
 
 [[package]]
+name = "typenum"
+version = "1.11.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "unicode-segmentation"
 version = "1.6.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -158,6 +207,11 @@ version = "0.8.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
+name = "version_check"
+version = "0.9.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "winapi"
 version = "0.3.8"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -180,22 +234,29 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum ansi_term 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ee49baf6cb617b853aa8d93bf420db2383fab46d314482ca2803b40d5fde979b"
 "checksum atty 0.2.13 (registry+https://github.com/rust-lang/crates.io-index)" = "1803c647a3ec87095e7ae7acfca019e98de5ec9a7d01343f611cf3152ed71a90"
 "checksum bitflags 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "cf1de2fe8c75bc145a2f577add951f8134889b4795d47466a54a5c846d691693"
+"checksum bitmaps 2.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "81e039a80914325b37fde728ef7693c212f0ac913d5599607d7b95a9484aae0b"
 "checksum clap 2.33.0 (registry+https://github.com/rust-lang/crates.io-index)" = "5067f5bb2d80ef5d68b4c87db81601f0b75bca627bc2ef76b141d7b846a3c6d9"
 "checksum derive_more 0.99.2 (registry+https://github.com/rust-lang/crates.io-index)" = "2159be042979966de68315bce7034bb000c775f22e3e834e1c52ff78f041cae8"
 "checksum heck 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)" = "20564e78d53d2bb135c343b3f47714a56af2061f1c928fdb541dc7b9fdd94205"
+"checksum im 14.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "a1f9b6540e530defef7f2df4ed330d45b739b10450548c74a9913f63ea1acc6b"
 "checksum libc 0.2.66 (registry+https://github.com/rust-lang/crates.io-index)" = "d515b1f41455adea1313a4a2ac8a8a477634fbae63cc6100e3aebb207ce61558"
 "checksum proc-macro-error 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)" = "aeccfe4d5d8ea175d5f0e4a2ad0637e0f4121d63bd99d356fb1f39ab2e7c6097"
 "checksum proc-macro2 1.0.6 (registry+https://github.com/rust-lang/crates.io-index)" = "9c9e470a8dc4aeae2dee2f335e8f533e2d4b347e1434e5671afc49b054592f27"
 "checksum quote 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)" = "053a8c8bcc71fcce321828dc897a98ab9760bef03a4fc36693c231e5b3216cfe"
+"checksum rand_core 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)" = "90bde5296fc891b0cef12a6d03ddccc162ce7b2aff54160af9338f8d40df6d19"
+"checksum rand_xoshiro 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "a9fcdd2e881d02f1d9390ae47ad8e5696a9e4be7b547a1da2afbc61973217004"
+"checksum sized-chunks 0.5.0 (registry+https://github.com/rust-lang/crates.io-index)" = "62db64dd92b3b54314b1e216c274634ca2b3fe8da8b3873be670cb1ac4dad30f"
 "checksum strsim 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)" = "8ea5119cdb4c55b55d432abb513a0429384878c15dde60cc77b1c99de1a95a6a"
 "checksum structopt 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)" = "30b3a3e93f5ad553c38b3301c8a0a0cec829a36783f6a0c467fc4bf553a5f5bf"
 "checksum structopt-derive 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)" = "ea692d40005b3ceba90a9fe7a78fa8d4b82b0ce627eebbffc329aab850f3410e"
 "checksum syn 1.0.11 (registry+https://github.com/rust-lang/crates.io-index)" = "dff0acdb207ae2fe6d5976617f887eb1e35a2ba52c13c7234c790960cdad9238"
 "checksum textwrap 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)" = "d326610f408c7a4eb6f51c37c330e496b08506c9457c9d34287ecc38809fb060"
+"checksum typenum 1.11.2 (registry+https://github.com/rust-lang/crates.io-index)" = "6d2783fe2d6b8c1101136184eb41be8b1ad379e4657050b8aaff0c79ee7575f9"
 "checksum unicode-segmentation 1.6.0 (registry+https://github.com/rust-lang/crates.io-index)" = "e83e153d1053cbb5a118eeff7fd5be06ed99153f00dbcd8ae310c5fb2b22edc0"
 "checksum unicode-width 0.1.6 (registry+https://github.com/rust-lang/crates.io-index)" = "7007dbd421b92cc6e28410fe7362e2e0a2503394908f417b68ec8d1c364c4e20"
 "checksum unicode-xid 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "826e7639553986605ec5979c7dd957c7895e93eabed50ab2ffa7f6128a75097c"
 "checksum vec_map 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)" = "05c78687fb1a80548ae3250346c3db86a80a7cdd77bda190189f2d0a0987c81a"
+"checksum version_check 0.9.1 (registry+https://github.com/rust-lang/crates.io-index)" = "078775d0255232fb988e6fccf26ddc9d1ac274299aaedcedce21c6f72cc533ce"
 "checksum winapi 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)" = "8093091eeb260906a183e6ae1abdba2ef5ef2257a21801128899c3fc699229c6"
 "checksum winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6"
 "checksum winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f"
diff --git a/Cargo.toml b/Cargo.toml
index 69a0b81..18b5ff5 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -1,11 +1,10 @@
 [package]
 name = "advent-of-code-2019"
 version = "0.1.0"
-authors = ["Justin Worthe <justin@worthe-it.co.za>"]
+authors = ["Justin Wernick <justin@worthe-it.co.za>"]
 edition = "2018"
 
-# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
-
 [dependencies]
 structopt = "0.3.5"
-derive_more = "0.99.2"
\ No newline at end of file
+derive_more = "0.99.2"
+im = "14.0.0"
\ No newline at end of file
diff --git a/inputs/day_2.txt b/inputs/day_2.txt
new file mode 100644
index 0000000..dd34cff
--- /dev/null
+++ b/inputs/day_2.txt
@@ -0,0 +1 @@
+1,0,0,3,1,1,2,3,1,3,4,3,1,5,0,3,2,9,1,19,1,19,5,23,1,23,6,27,2,9,27,31,1,5,31,35,1,35,10,39,1,39,10,43,2,43,9,47,1,6,47,51,2,51,6,55,1,5,55,59,2,59,10,63,1,9,63,67,1,9,67,71,2,71,6,75,1,5,75,79,1,5,79,83,1,9,83,87,2,87,10,91,2,10,91,95,1,95,9,99,2,99,9,103,2,10,103,107,2,9,107,111,1,111,5,115,1,115,2,119,1,119,6,0,99,2,0,14,0
diff --git a/src/bin/day_1.rs b/src/bin/day_1.rs
index f40237d..572d287 100644
--- a/src/bin/day_1.rs
+++ b/src/bin/day_1.rs
@@ -13,7 +13,7 @@ use structopt::StructOpt;
 /// The weight of each module is read from stdin, one module weight
 /// per line. See https://adventofcode.com/2019/day/1 for details.
 struct Opt {
-    /// Includes the weight of flue
+    /// Includes the weight of fuel
     #[structopt(short = "i", long = "include-fuel-weight")]
     include_fuel_weight: bool,
 }
diff --git a/src/bin/day_2.rs b/src/bin/day_2.rs
new file mode 100644
index 0000000..184c06c
--- /dev/null
+++ b/src/bin/day_2.rs
@@ -0,0 +1,204 @@
+use im::vector::Vector;
+use std::fmt;
+use std::io;
+use std::io::prelude::*;
+use std::iter;
+use std::iter::FromIterator;
+use std::iter::IntoIterator;
+use std::process;
+use structopt::StructOpt;
+
+type Intcode = u32;
+
+#[derive(Debug, StructOpt)]
+#[structopt(name = "Day 2: 1202 Program Alarm")]
+/// Executes an Intcode program
+///
+/// The program is read from stdin as a series of comma-separated
+/// values. Newlines are ignored. When the program halts, the value at
+/// position 0 is returned.
+///
+/// If an output is provided, all possible inputs are tried to find
+/// the input that results in the desired output. In this case, the
+/// inputs are returned in the format (noun, verb).
+///
+///See https://adventofcode.com/2019/day/2 for details.
+struct Opt {
+    #[structopt(short = "n", long = "noun")]
+    noun: Option<Intcode>,
+    #[structopt(short = "v", long = "verb")]
+    verb: Option<Intcode>,
+    #[structopt(short = "o", long = "output")]
+    output: Option<Intcode>,
+}
+
+fn main() {
+    let stdin = io::stdin();
+    let opt = Opt::from_args();
+
+    let program: Program = stdin
+        .lock()
+        .split(b',')
+        .map(|x| exit_on_failed_assertion(x, "Error reading input"))
+        .map(|x| exit_on_failed_assertion(String::from_utf8(x), "Input was not valid UTF-8"))
+        .map(|x| exit_on_failed_assertion(x.trim().parse::<Intcode>(), "Invalid number"))
+        .collect();
+
+    match (opt.noun, opt.verb, opt.output) {
+        (Some(noun), Some(verb), _) => {
+            let result = exit_on_failed_assertion(
+                program.set_input(noun, verb).execute(),
+                "Program errored",
+            );
+            println!("{}", result);
+        }
+        (_, _, Some(output)) => {
+            let (noun, verb) =
+                exit_on_failed_assertion(program.find_input(output), "Program errored");
+            println!("({}, {})", noun, verb);
+        }
+        (None, None, None) => {
+            let result = exit_on_failed_assertion(program.execute(), "Program errored");
+            println!("{}", result);
+        }
+        _ => {
+            eprintln!("Either a noun and verb or an expected output must be provided");
+            process::exit(1);
+        }
+    }
+}
+
+fn exit_on_failed_assertion<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+    match data {
+        Ok(data) => data,
+        Err(e) => {
+            eprintln!("{}: {}", message, e);
+            process::exit(1);
+        }
+    }
+}
+
+#[derive(Debug, Clone)]
+struct Program {
+    program_counter: usize,
+    error: bool,
+    halted: bool,
+    codes: Vector<Intcode>,
+}
+
+impl FromIterator<Intcode> for Program {
+    fn from_iter<I: IntoIterator<Item = Intcode>>(iter: I) -> Self {
+        Program {
+            program_counter: 0,
+            error: false,
+            halted: false,
+            codes: iter.into_iter().collect(),
+        }
+    }
+}
+
+impl Program {
+    fn set_input(&self, noun: Intcode, verb: Intcode) -> Program {
+        Program {
+            codes: self.codes.update(1, noun).update(2, verb),
+            ..self.clone()
+        }
+    }
+
+    fn find_input(&self, output: Intcode) -> Result<(Intcode, Intcode), ProgramError> {
+        (0..99)
+            .flat_map(|noun| (0..99).map(move |verb| (noun, verb)))
+            .map(|(noun, verb)| (noun, verb, self.set_input(noun, verb).execute()))
+            .find(|(_noun, _verb, out)| *out == Ok(output))
+            .map(|(noun, verb, _out)| Ok((noun, verb)))
+            .unwrap_or(Err(ProgramError))
+    }
+
+    fn execute(&self) -> Result<Intcode, ProgramError> {
+        if self.run_to_termination().error {
+            Err(ProgramError)
+        } else {
+            Ok(self.run_to_termination().codes.head().unwrap().clone())
+        }
+    }
+
+    fn run_to_termination(&self) -> Program {
+        iter::successors(Some(self.clone()), |p| Some(Program::next(&p)))
+            .find(|p| p.halted)
+            .unwrap() // successors doesn't terminate, so this will never be none.
+    }
+
+    fn next(&self) -> Program {
+        //eprintln!("{:?}", self);
+        match self.codes.get(self.program_counter) {
+            Some(1) => self.add(),
+            Some(2) => self.multiply(),
+            Some(99) => self.halt(),
+            Some(_) => self.error(),
+            None => self.error(),
+        }
+    }
+
+    fn add(&self) -> Program {
+        match (
+            self.codes
+                .get(self.program_counter + 1)
+                .and_then(|r| self.codes.get(*r as usize)),
+            self.codes
+                .get(self.program_counter + 2)
+                .and_then(|r| self.codes.get(*r as usize)),
+            self.codes.get(self.program_counter + 3),
+        ) {
+            (Some(in1), Some(in2), Some(out)) => Program {
+                program_counter: self.program_counter + 4,
+                codes: self.codes.update(*out as usize, in1 + in2),
+                ..self.clone()
+            },
+            _ => self.error(),
+        }
+    }
+
+    fn multiply(&self) -> Program {
+        match (
+            self.codes
+                .get(self.program_counter + 1)
+                .and_then(|r| self.codes.get(*r as usize)),
+            self.codes
+                .get(self.program_counter + 2)
+                .and_then(|r| self.codes.get(*r as usize)),
+            self.codes.get(self.program_counter + 3),
+        ) {
+            (Some(in1), Some(in2), Some(out)) => Program {
+                program_counter: self.program_counter + 4,
+                codes: self.codes.update(*out as usize, in1 * in2),
+                ..self.clone()
+            },
+            _ => self.error(),
+        }
+    }
+
+    fn halt(&self) -> Program {
+        Program {
+            halted: true,
+            ..self.clone()
+        }
+    }
+
+    fn error(&self) -> Program {
+        Program {
+            halted: true,
+            error: true,
+            ..self.clone()
+        }
+    }
+}
+
+#[derive(Debug, PartialEq)]
+struct ProgramError;
+
+impl fmt::Display for ProgramError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "Unknown error")
+    }
+}
+impl std::error::Error for ProgramError {}