diff options
Diffstat (limited to 'src/bin/day_5.rs')
| -rw-r--r-- | src/bin/day_5.rs | 272 |
1 files changed, 272 insertions, 0 deletions
diff --git a/src/bin/day_5.rs b/src/bin/day_5.rs new file mode 100644 index 0000000..a6de781 --- /dev/null +++ b/src/bin/day_5.rs @@ -0,0 +1,272 @@ +use rpds::{list::List, 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 = i32; + +#[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. +/// +/// 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/5 for details. +struct Opt { + #[structopt(short = "i", long = "input")] + input: Vec<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::<Program>() + .with_input(opt.input.into_iter().collect()); + + let result = exit_on_failed_assertion(program.execute(), "Program errored"); + println!("{}", result); +} + +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>, + input: List<Intcode>, + output: 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(), + input: List::new(), + output: Vector::new(), + } + } +} + +impl Program { + fn with_input(&self, input: List<Intcode>) -> Program { + Program { + input, + ..self.clone() + } + } + + fn execute(&self) -> Result<Vector<Intcode>, ProgramError> { + self.run_to_termination().into_result() + } + + fn into_result(&self) -> Result<Vector<Intcode>, 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.codes + .get(self.program_counter) + .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)) => Program { + program_counter: self.program_counter + 4, + codes: self.codes.set(out as usize, in1 + in2).unwrap(), + ..self.clone() + }, + _ => 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)) => Program { + program_counter: self.program_counter + 4, + codes: self.codes.set(out as usize, in1 * in2).unwrap(), + ..self.clone() + }, + _ => self.error(), + } + } + + fn input(&self, _mode: Intcode) -> Program { + match self.get_immediate(1) { + Some(out) => Program { + program_counter: self.program_counter + 2, + codes: self + .codes + .set(out as usize, *self.input.first().unwrap()) + .unwrap(), + input: self.input.drop_first().unwrap(), + ..self.clone() + }, + _ => self.error(), + } + } + + fn output(&self, mode: Intcode) -> Program { + match self.get(1, mode) { + Some(print) => Program { + program_counter: self.program_counter + 2, + output: self.output.push_back(print), + ..self.clone() + }, + _ => self.error(), + } + } + + fn jump_if_true(&self, mode: Intcode) -> Program { + match (self.get(1, mode), self.get(2, mode)) { + (Some(pred), Some(to)) => Program { + program_counter: if pred != 0 { + to as usize + } else { + self.program_counter + 3 + }, + ..self.clone() + }, + _ => self.error(), + } + } + fn jump_if_false(&self, mode: Intcode) -> Program { + match (self.get(1, mode), self.get(2, mode)) { + (Some(pred), Some(to)) => Program { + program_counter: if pred == 0 { + to as usize + } else { + self.program_counter + 3 + }, + ..self.clone() + }, + _ => 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)) => Program { + program_counter: self.program_counter + 4, + codes: self + .codes + .set(out as usize, if in1 < in2 { 1 } else { 0 }) + .unwrap(), + ..self.clone() + }, + _ => 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)) => Program { + program_counter: self.program_counter + 4, + codes: self + .codes + .set(out as usize, if in1 == in2 { 1 } else { 0 }) + .unwrap(), + ..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, mode: Intcode) -> Option<Intcode> { + 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<Intcode> { + self.codes + .get(self.program_counter + pointer_offset) + .cloned() + } + + fn get_position(&self, pointer_offset: usize) -> Option<Intcode> { + self.get_immediate(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") + } +} +impl std::error::Error for ProgramError {} |