From 551629a62bee37e33c3430272f1eb602324bf841 Mon Sep 17 00:00:00 2001 From: Justin Worthe Date: Fri, 21 Dec 2018 08:32:01 +0200 Subject: Day 21: Simulating overflows --- inputs/21.txt | 32 ++++++++++++++ src/bin/day_21.rs | 123 +++++++++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 153 insertions(+), 2 deletions(-) create mode 100644 inputs/21.txt diff --git a/inputs/21.txt b/inputs/21.txt new file mode 100644 index 0000000..aaebbac --- /dev/null +++ b/inputs/21.txt @@ -0,0 +1,32 @@ +#ip 2 +seti 123 0 4 +bani 4 456 4 +eqri 4 72 4 +addr 4 2 2 +seti 0 0 2 +seti 0 1 4 +bori 4 65536 1 +seti 16031208 7 4 +bani 1 255 3 +addr 4 3 4 +bani 4 16777215 4 +muli 4 65899 4 +bani 4 16777215 4 +gtir 256 1 3 +addr 3 2 2 +addi 2 1 2 +seti 27 3 2 +seti 0 9 3 +addi 3 1 5 +muli 5 256 5 +gtrr 5 1 5 +addr 5 2 2 +addi 2 1 2 +seti 25 7 2 +addi 3 1 3 +seti 17 4 2 +setr 3 1 1 +seti 7 5 2 +eqrr 4 0 3 +addr 3 2 2 +seti 5 1 2 diff --git a/src/bin/day_21.rs b/src/bin/day_21.rs index d1276b3..0d9a97c 100644 --- a/src/bin/day_21.rs +++ b/src/bin/day_21.rs @@ -3,16 +3,135 @@ use advent_of_code_2018::*; use std::error::Error; use std::path::PathBuf; +use std::u32; +use std::collections::HashMap; // cargo watch -cs "cargo run --release --bin day_21" +use std::i32; + +#[derive(Debug)] +struct Instruction { + op: Op, + a: i32, + b: i32, + c: i32 +} + +impl Instruction { + fn execute(&self, counter_register: usize, registers: &mut [i32; 6]) -> i32{ + use Op::*; + + registers[self.c as usize] = match self.op { + Addr => registers[self.a as usize].wrapping_add(registers[self.b as usize]), + Addi => registers[self.a as usize].wrapping_add(self.b), + Mulr => registers[self.a as usize].wrapping_mul(registers[self.b as usize]), + Muli => registers[self.a as usize].wrapping_mul(self.b), + Banr => registers[self.a as usize] & registers[self.b as usize], + Bani => registers[self.a as usize] & self.b, + Borr => registers[self.a as usize] | registers[self.b as usize], + Bori => registers[self.a as usize] | self.b, + Setr => registers[self.a as usize], + Seti => self.a, + Gtir => if self.a > registers[self.b as usize] { 1 } else { 0 }, + Gtri => if registers[self.a as usize] > self.b { 1 } else { 0 }, + Gtrr => if registers[self.a as usize] > registers[self.b as usize] { 1 } else { 0 }, + Eqir => if self.a == registers[self.b as usize] { 1 } else { 0 }, + Eqri => if registers[self.a as usize] == self.b { 1 } else { 0 }, + Eqrr => if registers[self.a as usize] == registers[self.b as usize] { 1 } else { 0 }, + }; + + registers[counter_register]+1 + } +} + +#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] +enum Op { + Addr, + Addi, + Mulr, + Muli, + Banr, + Bani, + Borr, + Bori, + Setr, + Seti, + Gtir, + Gtri, + Gtrr, + Eqir, + Eqri, + Eqrr +} + + fn main() -> Result<(), Box> { let input = read_file(&PathBuf::from("inputs/21.txt"))?; - println!("Input: {:?}", input); - + let mut input_iter = input.iter(); + let counter_register: usize = input_iter.next() + .map(|line| line.split_whitespace().nth(1).unwrap().parse().unwrap()) + .unwrap(); + let instructions: Vec = input_iter + .map(|line| { + let mut instruction_iter = line.split_whitespace(); + Instruction { + op: match instruction_iter.next().unwrap() { + "addr" => Op::Addr, + "addi" => Op::Addi, + "mulr" => Op::Mulr, + "muli" => Op::Muli, + "banr" => Op::Banr, + "bani" => Op::Bani, + "borr" => Op::Borr, + "bori" => Op::Bori, + "setr" => Op::Setr, + "seti" => Op::Seti, + "gtir" => Op::Gtir, + "gtri" => Op::Gtri, + "gtrr" => Op::Gtrr, + "eqir" => Op::Eqir, + "eqri" => Op::Eqri, + "eqrr" => Op::Eqrr, + _ => panic!("unknown instruction") + }, + a: instruction_iter.next().unwrap().parse().unwrap(), + b: instruction_iter.next().unwrap().parse().unwrap(), + c: instruction_iter.next().unwrap().parse().unwrap(), + } + }) + .collect(); + execute_program(&instructions, counter_register, [0, 0, 0, 0, 0, 0]); Ok(()) } + +fn execute_program(instructions: &Vec, counter_register: usize, registers: [i32; 6]) { + let mut instructions_executed: u64 = 0; + let mut counter_val: i32 = 0; + let mut registers = registers.clone(); + let mut halting_values = HashMap::new(); + + while counter_val >= 0 && counter_val < instructions.len() as i32 { + if counter_val == 28 { + if halting_values.contains_key(®isters[4]) { + break; + } + halting_values.entry(registers[4]).or_insert(instructions_executed+2); + } + registers[counter_register] = counter_val; + counter_val = instructions[counter_val as usize].execute(counter_register, &mut registers); + instructions_executed += 1; + } + + let (min_halting, min_halting_time) = halting_values.iter().min_by_key(|&(_, v)| v).unwrap(); + debug!(min_halting); + debug!(min_halting_time); + let (max_halting, max_halting_time) = halting_values.iter().max_by_key(|&(_, v)| v).unwrap(); + debug!(max_halting); + debug!(max_halting_time); + +} -- cgit v1.2.3