From af487fe8cb2d7732283971a416d015234e8f71cc Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Mon, 2 Dec 2019 22:08:56 +0200 Subject: Day 2: Intcode machine! --- Cargo.lock | 61 +++++++++++++++++ Cargo.toml | 7 +- inputs/day_2.txt | 1 + src/bin/day_1.rs | 2 +- src/bin/day_2.rs | 204 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 270 insertions(+), 5 deletions(-) create mode 100644 inputs/day_2.txt create mode 100644 src/bin/day_2.rs 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)", ] @@ -30,6 +31,14 @@ name = "bitflags" 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" @@ -62,6 +71,19 @@ dependencies = [ "unicode-segmentation 1.6.0 (registry+https://github.com/rust-lang/crates.io-index)", ] +[[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" @@ -93,6 +115,28 @@ dependencies = [ "proc-macro2 1.0.6 (registry+https://github.com/rust-lang/crates.io-index)", ] +[[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" @@ -137,6 +181,11 @@ dependencies = [ "unicode-width 0.1.6 (registry+https://github.com/rust-lang/crates.io-index)", ] +[[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" @@ -157,6 +206,11 @@ name = "vec_map" 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" @@ -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 "] +authors = ["Justin Wernick "] 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, + #[structopt(short = "v", long = "verb")] + verb: Option, + #[structopt(short = "o", long = "output")] + output: Option, +} + +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::(), "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(data: Result, 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, +} + +impl FromIterator for Program { + fn from_iter>(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 { + 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 {} -- cgit v1.2.3