From 003a62f1c38344c5a647170bd2472c4eab39cf75 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Wed, 11 Dec 2019 23:02:42 +0200 Subject: Intcode program into lib! It's shared code now. --- Cargo.lock | 18 ++-- Cargo.toml | 2 +- src/bin/day_2.rs | 155 +++++------------------------------ src/bin/day_4.rs | 4 - src/bin/day_5.rs | 235 +--------------------------------------------------- src/lib.rs | 246 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 281 insertions(+), 379 deletions(-) create mode 100644 src/lib.rs diff --git a/Cargo.lock b/Cargo.lock index 127971b..a8be1c4 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -1,7 +1,15 @@ # This file is automatically @generated by Cargo. # It is not intended for manual editing. [[package]] -name = "advent-of-code-2019" +name = "ansi_term" +version = "0.11.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "winapi 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "aoc2019" version = "0.1.0" dependencies = [ "derive_more 0.99.2 (registry+https://github.com/rust-lang/crates.io-index)", @@ -10,14 +18,6 @@ dependencies = [ "structopt 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)", ] -[[package]] -name = "ansi_term" -version = "0.11.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -dependencies = [ - "winapi 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)", -] - [[package]] name = "archery" version = "0.3.0" diff --git a/Cargo.toml b/Cargo.toml index 937d8e7..cef1cae 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -1,5 +1,5 @@ [package] -name = "advent-of-code-2019" +name = "aoc2019" version = "0.1.0" authors = ["Justin Wernick "] edition = "2018" diff --git a/src/bin/day_2.rs b/src/bin/day_2.rs index 172a89a..ce8fcaa 100644 --- a/src/bin/day_2.rs +++ b/src/bin/day_2.rs @@ -1,15 +1,9 @@ -use im::vector::Vector; -use std::fmt; +use aoc2019::*; 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 @@ -36,7 +30,7 @@ fn main() { let stdin = io::stdin(); let opt = Opt::from_args(); - let program: Program = stdin + let program: IntcodeProgram = stdin .lock() .split(b',') .map(|x| exit_on_failed_assertion(x, "Error reading input")) @@ -47,14 +41,14 @@ fn main() { match (opt.noun, opt.verb, opt.output) { (Some(noun), Some(verb), _) => { let result = exit_on_failed_assertion( - program.set_input(noun, verb).execute(), + program.with_noun_verb_input(noun, verb).execute(), "Program errored", ); println!("{}", result); } (_, _, Some(output)) => { let (noun, verb) = - exit_on_failed_assertion(program.find_input(output), "Program errored"); + exit_on_failed_assertion(find_input(&program, output), "Program errored"); println!("({}, {})", noun, verb); } (None, None, None) => { @@ -78,127 +72,22 @@ fn exit_on_failed_assertion(data: Result, message } } -#[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 { - self.run_to_termination().into_result() - } - - fn into_result(&self) -> Result { - if self.error { - Err(ProgramError) - } else { - Ok(self.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.get_deref(1), self.get_deref(2), self.get(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.get_deref(1), self.get_deref(2), self.get(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() - } - } - - fn get(&self, pointer_offset: usize) -> Option { - self.codes - .get(self.program_counter + pointer_offset) - .cloned() - } - - fn get_deref(&self, pointer_offset: usize) -> Option { - self.get(pointer_offset) - .and_then(|r| self.codes.get(r as usize)) - .cloned() - } -} - -#[derive(Debug, PartialEq)] -struct ProgramError; - -impl fmt::Display for ProgramError { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - write!(f, "Unknown error") - } +fn find_input( + program: &IntcodeProgram, + output: Intcode, +) -> Result<(Intcode, Intcode), IntcodeProgramError> { + (0..99) + .flat_map(|noun| (0..99).map(move |verb| (noun, verb))) + .map(|(noun, verb)| { + ( + noun, + verb, + program + .with_noun_verb_input(noun, verb) + .execute_returning_memory_0(), + ) + }) + .find(|(_noun, _verb, out)| *out == Ok(Some(output))) + .map(|(noun, verb, _out)| Ok((noun, verb))) + .unwrap_or(Err(IntcodeProgramError)) } -impl std::error::Error for ProgramError {} diff --git a/src/bin/day_4.rs b/src/bin/day_4.rs index 3cb8d38..d7d6b69 100644 --- a/src/bin/day_4.rs +++ b/src/bin/day_4.rs @@ -1,6 +1,3 @@ -use std::io; -use std::io::prelude::*; - use structopt::StructOpt; #[derive(Debug, StructOpt)] @@ -17,7 +14,6 @@ struct Opt { } fn main() { - let stdin = io::stdin(); let opt = Opt::from_args(); println!( diff --git a/src/bin/day_5.rs b/src/bin/day_5.rs index a3cf869..07f7af8 100644 --- a/src/bin/day_5.rs +++ b/src/bin/day_5.rs @@ -1,15 +1,9 @@ -use rpds::{list::List, vector::Vector}; -use std::fmt; +use aoc2019::*; 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 = i32; - #[derive(Debug, StructOpt)] #[structopt(name = "Day 5: Sunny with a Chance of Asteroids")] /// Executes an Intcode program @@ -27,13 +21,13 @@ fn main() { let stdin = io::stdin(); let opt = Opt::from_args(); - let program: Program = stdin + let program: IntcodeProgram = 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::() + .collect::() .with_input(opt.input.into_iter().collect()); let result = exit_on_failed_assertion(program.execute(), "Program errored"); @@ -49,226 +43,3 @@ fn exit_on_failed_assertion(data: Result, message } } } - -#[derive(Debug, Clone)] -struct Program { - instruction_pointer: usize, - error: bool, - halted: bool, - memory: Vector, - input: List, - output: Vector, -} - -impl FromIterator for Program { - fn from_iter>(iter: I) -> Self { - Program { - instruction_pointer: 0, - error: false, - halted: false, - memory: iter.into_iter().collect(), - input: List::new(), - output: Vector::new(), - } - } -} - -impl Program { - fn with_input(&self, input: List) -> Program { - Program { - input, - ..self.clone() - } - } - - fn with_instruction_pointer(&self, instruction_pointer: usize) -> Program { - Program { - instruction_pointer, - ..self.clone() - } - } - - fn with_instruction_pointer_offset(&self, offset: usize) -> Program { - Program { - instruction_pointer: self.instruction_pointer + offset, - ..self.clone() - } - } - - fn with_memory_set(&self, address: usize, value: Intcode) -> Program { - self.memory - .set(address, value) - .map(|memory| Program { - memory, - ..self.clone() - }) - .unwrap_or(self.error()) - } - - fn with_input_consumed(&self) -> Program { - self.input - .drop_first() - .map(|input| Program { - input, - ..self.clone() - }) - .unwrap_or(self.error()) - } - - fn with_output(&self, print: Intcode) -> Program { - Program { - output: self.output.push_back(print), - ..self.clone() - } - } - - fn execute(&self) -> Result, ProgramError> { - self.run_to_termination().into_result() - } - - fn into_result(&self) -> Result, ProgramError> { - if self.error { - Err(ProgramError) - } else { - Ok(self.output.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); - self.memory - .get(self.instruction_pointer) - .map(|&opcode| match opcode % 100 { - 1 => self.add(opcode), - 2 => self.multiply(opcode), - 3 => self.input(opcode), - 4 => self.output(opcode), - 5 => self.jump_if_true(opcode), - 6 => self.jump_if_false(opcode), - 7 => self.less_than(opcode), - 8 => self.equals(opcode), - 99 => self.halt(), - _ => self.error(), - }) - .unwrap_or(self.error()) - } - - fn add(&self, mode: Intcode) -> Program { - 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, in1 + in2), - _ => self.error(), - } - } - - fn multiply(&self, mode: Intcode) -> Program { - 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, in1 * in2), - _ => self.error(), - } - } - - fn input(&self, _mode: Intcode) -> Program { - match (self.input.first().cloned(), self.get_immediate(1)) { - (Some(input), Some(out)) => self - .with_instruction_pointer_offset(2) - .with_memory_set(out as usize, input) - .with_input_consumed(), - _ => self.error(), - } - } - - fn output(&self, mode: Intcode) -> Program { - match self.get(1, mode) { - Some(print) => self.with_instruction_pointer_offset(2).with_output(print), - _ => self.error(), - } - } - - fn jump_if_true(&self, mode: Intcode) -> Program { - 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(), - } - } - fn jump_if_false(&self, mode: Intcode) -> Program { - 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(), - } - } - - fn less_than(&self, mode: Intcode) -> Program { - 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(), - } - } - - fn equals(&self, mode: Intcode) -> Program { - 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(), - } - } - - fn halt(&self) -> Program { - Program { - halted: true, - ..self.clone() - } - } - - fn error(&self) -> Program { - Program { - halted: true, - error: true, - ..self.clone() - } - } - - fn get(&self, pointer_offset: usize, mode: Intcode) -> Option { - match mode / (10 as Intcode).pow(pointer_offset as u32 + 1) % 10 { - 0 => self.get_position(pointer_offset), - 1 => self.get_immediate(pointer_offset), - _ => None, - } - } - - fn get_immediate(&self, pointer_offset: usize) -> Option { - self.memory - .get(self.instruction_pointer + pointer_offset) - .cloned() - } - - fn get_position(&self, pointer_offset: usize) -> Option { - self.get_immediate(pointer_offset) - .and_then(|r| self.memory.get(r as usize)) - .cloned() - } -} - -#[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 {} diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..2591a54 --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,246 @@ +use rpds::{list::List, vector::Vector}; +use std::fmt; +use std::iter; +use std::iter::FromIterator; +use std::iter::IntoIterator; + +pub type Intcode = i32; + +#[derive(Debug, Clone)] +pub struct IntcodeProgram { + instruction_pointer: usize, + error: bool, + halted: bool, + memory: Vector, + input: List, + output: Vector, +} + +impl FromIterator for IntcodeProgram { + fn from_iter>(iter: I) -> Self { + IntcodeProgram { + instruction_pointer: 0, + error: false, + halted: false, + memory: iter.into_iter().collect(), + input: List::new(), + output: Vector::new(), + } + } +} + +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) + } + + pub fn with_input(&self, input: List) -> IntcodeProgram { + IntcodeProgram { + input, + ..self.clone() + } + } + + pub fn execute(&self) -> Result, IntcodeProgramError> { + self.run_to_termination().output_into_result() + } + + pub fn execute_returning_memory_0(&self) -> Result, IntcodeProgramError> { + self.run_to_termination().memory_0_into_result() + } + + fn with_instruction_pointer(&self, instruction_pointer: usize) -> IntcodeProgram { + IntcodeProgram { + instruction_pointer, + ..self.clone() + } + } + + fn with_instruction_pointer_offset(&self, offset: usize) -> IntcodeProgram { + IntcodeProgram { + instruction_pointer: self.instruction_pointer + 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_input_consumed(&self) -> IntcodeProgram { + self.input + .drop_first() + .map(|input| IntcodeProgram { + input, + ..self.clone() + }) + .unwrap_or(self.error()) + } + + fn with_output(&self, print: Intcode) -> IntcodeProgram { + IntcodeProgram { + output: self.output.push_back(print), + ..self.clone() + } + } + + fn output_into_result(&self) -> Result, IntcodeProgramError> { + if self.error { + Err(IntcodeProgramError) + } else { + Ok(self.output.clone()) + } + } + + fn memory_0_into_result(&self) -> Result, IntcodeProgramError> { + if self.error { + Err(IntcodeProgramError) + } else { + Ok(self.memory.get(0).cloned()) + } + } + + fn run_to_termination(&self) -> IntcodeProgram { + iter::successors(Some(self.clone()), |p| Some(IntcodeProgram::next(&p))) + .find(|p| p.halted) + .unwrap() // successors doesn't terminate, so this will never be none. + } + + fn next(&self) -> IntcodeProgram { + //eprintln!("{:?}", self); + self.memory + .get(self.instruction_pointer) + .map(|&opcode| match opcode % 100 { + 1 => self.add(opcode), + 2 => self.multiply(opcode), + 3 => self.input(opcode), + 4 => self.output(opcode), + 5 => self.jump_if_true(opcode), + 6 => self.jump_if_false(opcode), + 7 => self.less_than(opcode), + 8 => self.equals(opcode), + 99 => self.halt(), + _ => self.error(), + }) + .unwrap_or(self.error()) + } + + 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 + .with_instruction_pointer_offset(4) + .with_memory_set(out as usize, in1 + in2), + _ => self.error(), + } + } + + 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 + .with_instruction_pointer_offset(4) + .with_memory_set(out as usize, in1 * in2), + _ => self.error(), + } + } + + fn input(&self, _mode: Intcode) -> IntcodeProgram { + match (self.input.first().cloned(), self.get_immediate(1)) { + (Some(input), Some(out)) => self + .with_instruction_pointer_offset(2) + .with_memory_set(out as usize, input) + .with_input_consumed(), + _ => self.error(), + } + } + + fn output(&self, mode: Intcode) -> IntcodeProgram { + match self.get(1, mode) { + Some(print) => self.with_instruction_pointer_offset(2).with_output(print), + _ => self.error(), + } + } + + 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(), + } + } + 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(), + } + } + + 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(), + } + } + + 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(), + } + } + + fn halt(&self) -> IntcodeProgram { + IntcodeProgram { + halted: true, + ..self.clone() + } + } + + fn error(&self) -> IntcodeProgram { + IntcodeProgram { + halted: true, + error: true, + ..self.clone() + } + } + + fn get(&self, pointer_offset: usize, mode: Intcode) -> Option { + match mode / (10 as Intcode).pow(pointer_offset as u32 + 1) % 10 { + 0 => self.get_position(pointer_offset), + 1 => self.get_immediate(pointer_offset), + _ => None, + } + } + + fn get_immediate(&self, pointer_offset: usize) -> Option { + self.memory + .get(self.instruction_pointer + pointer_offset) + .cloned() + } + + fn get_position(&self, pointer_offset: usize) -> Option { + self.get_immediate(pointer_offset) + .and_then(|r| self.memory.get(r as usize)) + .cloned() + } +} + +#[derive(Debug, PartialEq)] +pub struct IntcodeProgramError; + +impl fmt::Display for IntcodeProgramError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "Unknown error") + } +} +impl std::error::Error for IntcodeProgramError {} -- cgit v1.2.3