diff options
Diffstat (limited to '2018/src/day19.rs')
| -rw-r--r-- | 2018/src/day19.rs | 354 |
1 files changed, 11 insertions, 343 deletions
diff --git a/2018/src/day19.rs b/2018/src/day19.rs index 05f0fd4..117f8c5 100644 --- a/2018/src/day19.rs +++ b/2018/src/day19.rs @@ -1,347 +1,20 @@ use std::io; use std::io::BufRead; -use std::fmt; -use std::str; +use crate::device::*; -// Number of things taken from day16, also edited - -const IP_REG: usize = 4; - -#[derive(Copy, Clone)] -enum RawOpcode { - Addr, Addi, - Mulr, Muli, - Banr, Bani, - Borr, Bori, - Setr, Seti, - Gtir, Gtri, Gtrr, - Eqir, Eqri, Eqrr, -} - -impl str::FromStr for RawOpcode { - type Err = io::Error; - - fn from_str(s: &str) -> io::Result<Self> { - Ok(match s { - "addr" => RawOpcode::Addr, - "addi" => RawOpcode::Addi, - "mulr" => RawOpcode::Mulr, - "muli" => RawOpcode::Muli, - "banr" => RawOpcode::Banr, - "bani" => RawOpcode::Bani, - "borr" => RawOpcode::Borr, - "bori" => RawOpcode::Bori, - "setr" => RawOpcode::Setr, - "seti" => RawOpcode::Seti, - "gtir" => RawOpcode::Gtir, - "gtri" => RawOpcode::Gtri, - "gtrr" => RawOpcode::Gtrr, - "eqir" => RawOpcode::Eqir, - "eqri" => RawOpcode::Eqri, - "eqrr" => RawOpcode::Eqrr, - _ => panic!("Invalid raw opcode"), - }) - } -} - -#[derive(Copy, Clone)] -enum Oper { - Reg(usize), - Num(usize), -} - -impl Oper { - fn map_reg<F: Fn(usize) -> Oper>(&mut self, func: F) { - *self = match *self { - Oper::Reg(r) => func(r), - Oper::Num(n) => Oper::Num(n) - }; - } -} - -impl fmt::Display for Oper { - fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { - match self { - Oper::Reg(r) => write!(w, "r{}", r), - Oper::Num(n) => write!(w, "{}", n), - } - } -} - -struct RawInstr { - op: RawOpcode, - a: usize, - b: usize, - c: usize, -} - -impl fmt::Display for RawInstr { - fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { - match self.op { - RawOpcode::Addr => write!(w, "r{} <- {} + {}", self.c, self.a, self.b), - RawOpcode::Addi => write!(w, "r{} <- {} + {}", self.c, self.a, self.b), - RawOpcode::Mulr => write!(w, "r{} <- {} * {}", self.c, self.a, self.b), - RawOpcode::Muli => write!(w, "r{} <- {} * {}", self.c, self.a, self.b), - RawOpcode::Banr => write!(w, "r{} <- {} & {}", self.c, self.a, self.b), - RawOpcode::Bani => write!(w, "r{} <- {} & {}", self.c, self.a, self.b), - RawOpcode::Borr => write!(w, "r{} <- {} | {}", self.c, self.a, self.b), - RawOpcode::Bori => write!(w, "r{} <- {} | {}", self.c, self.a, self.b), - RawOpcode::Setr => write!(w, "r{} <- {}", self.c, self.a), - RawOpcode::Seti => write!(w, "r{} <- {}", self.c, self.a), - RawOpcode::Gtir => write!(w, "r{} <- {} > {}", self.c, self.a, self.b), - RawOpcode::Gtri => write!(w, "r{} <- {} > {}", self.c, self.a, self.b), - RawOpcode::Gtrr => write!(w, "r{} <- {} > {}", self.c, self.a, self.b), - RawOpcode::Eqir => write!(w, "r{} <- {} == {}", self.c, self.a, self.b), - RawOpcode::Eqri => write!(w, "r{} <- {} == {}", self.c, self.a, self.b), - RawOpcode::Eqrr => write!(w, "r{} <- {} == {}", self.c, self.a, self.b), - } - } -} - -impl str::FromStr for RawInstr { - type Err = io::Error; - - fn from_str(line: &str) -> io::Result<Self> { - let mut iter = line.split(' '); - let op = iter.next().unwrap().parse().unwrap(); - let a = iter.next().unwrap().parse().unwrap(); - let b = iter.next().unwrap().parse().unwrap(); - let c = iter.next().unwrap().parse().unwrap(); - Ok(RawInstr { op, a, b, c }) - } -} - -enum Instr { - // src1, src2, dest - Add(Oper, Oper, usize), - Mul(Oper, Oper, usize), - Ban(Oper, Oper, usize), - Bor(Oper, Oper, usize), - Grt(Oper, Oper, usize), - Equ(Oper, Oper, usize), - Set(Oper, usize), -} - -impl Instr { - fn from_raw_instr(ins: &RawInstr) -> Self { - match ins.op { - RawOpcode::Addr => Instr::Add(Oper::Reg(ins.a), Oper::Reg(ins.b), ins.c), - RawOpcode::Addi => Instr::Add(Oper::Reg(ins.a), Oper::Num(ins.b), ins.c), - RawOpcode::Mulr => Instr::Mul(Oper::Reg(ins.a), Oper::Reg(ins.b), ins.c), - RawOpcode::Muli => Instr::Mul(Oper::Reg(ins.a), Oper::Num(ins.b), ins.c), - RawOpcode::Banr => Instr::Ban(Oper::Reg(ins.a), Oper::Reg(ins.b), ins.c), - RawOpcode::Bani => Instr::Ban(Oper::Reg(ins.a), Oper::Num(ins.b), ins.c), - RawOpcode::Borr => Instr::Bor(Oper::Reg(ins.a), Oper::Reg(ins.b), ins.c), - RawOpcode::Bori => Instr::Bor(Oper::Reg(ins.a), Oper::Num(ins.b), ins.c), - RawOpcode::Setr => Instr::Set(Oper::Reg(ins.a), ins.c), - RawOpcode::Seti => Instr::Set(Oper::Num(ins.a), ins.c), - RawOpcode::Gtir => Instr::Grt(Oper::Num(ins.a), Oper::Reg(ins.b), ins.c), - RawOpcode::Gtri => Instr::Grt(Oper::Reg(ins.a), Oper::Num(ins.b), ins.c), - RawOpcode::Gtrr => Instr::Grt(Oper::Reg(ins.a), Oper::Reg(ins.b), ins.c), - RawOpcode::Eqir => Instr::Equ(Oper::Num(ins.a), Oper::Reg(ins.b), ins.c), - RawOpcode::Eqri => Instr::Equ(Oper::Reg(ins.a), Oper::Num(ins.b), ins.c), - RawOpcode::Eqrr => Instr::Equ(Oper::Reg(ins.a), Oper::Reg(ins.b), ins.c), - } - } - - fn map_reads<F: Fn(usize) -> Oper>(&mut self, func: F) { - match self { - Instr::Add(a, b, _) => { a.map_reg(&func); b.map_reg(&func); }, - Instr::Mul(a, b, _) => { a.map_reg(&func); b.map_reg(&func); }, - Instr::Ban(a, b, _) => { a.map_reg(&func); b.map_reg(&func); }, - Instr::Bor(a, b, _) => { a.map_reg(&func); b.map_reg(&func); }, - Instr::Grt(a, b, _) => { a.map_reg(&func); b.map_reg(&func); }, - Instr::Equ(a, b, _) => { a.map_reg(&func); b.map_reg(&func); }, - Instr::Set(a, _) => a.map_reg(func), - }; - } - - fn inline_reg(&mut self, reg: usize, value: Oper) { - self.map_reads(|r| if r == reg { value } else { Oper::Reg(r) }); - } -} - -impl fmt::Display for Instr { - fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { - match self { - Instr::Add(a, b, c) => write!(w, "r{} <- {} + {}", c, a, b), - Instr::Mul(a, b, c) => write!(w, "r{} <- {} * {}", c, a, b), - Instr::Ban(a, b, c) => write!(w, "r{} <- {} & {}", c, a, b), - Instr::Bor(a, b, c) => write!(w, "r{} <- {} | {}", c, a, b), - Instr::Grt(a, b, c) => write!(w, "r{} <- {} > {}", c, a, b), - Instr::Equ(a, b, c) => write!(w, "r{} <- {} == {}", c, a, b), - Instr::Set(a, c) => write!(w, "r{} <- {}", c, a), - } - } -} - -#[derive(PartialEq, Eq, Clone)] -struct Machine { - regs: [usize; 6], -} - -impl Machine { - fn exec(&mut self, instr: &Instr) { - match instr { - &Instr::Add(a, b, c) => self.regs[c] = self.eval_oper(a) + self.eval_oper(b), - &Instr::Mul(a, b, c) => self.regs[c] = self.eval_oper(a) * self.eval_oper(b), - &Instr::Ban(a, b, c) => self.regs[c] = self.eval_oper(a) & self.eval_oper(b), - &Instr::Bor(a, b, c) => self.regs[c] = self.eval_oper(a) | self.eval_oper(b), - &Instr::Grt(a, b, c) => self.regs[c] = if self.eval_oper(a) > self.eval_oper(b) { 1 } else { 0 }, - &Instr::Equ(a, b, c) => self.regs[c] = if self.eval_oper(a) == self.eval_oper(b) { 1 } else { 0 }, - &Instr::Set(a, c) => self.regs[c] = self.eval_oper(a), - } - } - - fn exec_program(&mut self, prog: &[Instr]) { - let mut freq_map = vec![0; prog.len()]; - - self.regs[IP_REG] = 0; - while self.regs[IP_REG] < prog.len() { - let ip = self.regs[IP_REG]; - freq_map[ip] += 1; - if freq_map[ip] >= 3 { - let mut sm = SymbolicMachine::from(self); - sm.exec_find_loop(prog, ip); - } - - println!("{} ip={} {}", self, ip, prog[ip]); - self.exec(&prog[ip]); - self.regs[IP_REG] += 1; - } - } - - fn eval_oper(&self, oper: Oper) -> usize { - match oper { - Oper::Reg(r) => self.regs[r], - Oper::Num(n) => n, - } - } -} - -impl fmt::Display for Machine { - fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { - write!(w, "{}", self.regs[0])?; - for i in 1..6 { - write!(w, " {}", self.regs[i])?; - } - Ok(()) - } -} - -#[derive(Clone, PartialEq, Eq)] -enum SymVal { - Val(usize), - Add(Box<SymVal>, Box<SymVal>), - Mul(Box<SymVal>, Box<SymVal>), - Ban(Box<SymVal>, Box<SymVal>), - Bor(Box<SymVal>, Box<SymVal>), - Grt(Box<SymVal>, Box<SymVal>), - Equ(Box<SymVal>, Box<SymVal>), - If1(Box<SymVal>, Box<SymVal>, Box<SymVal>), -} - -impl Default for SymVal { - fn default() -> Self { - SymVal::Val(0) - } -} - -impl SymVal { - fn simplify(&mut self) { - let optres = match self { - SymVal::Val(n) => Some(SymVal::Val(*n)), - SymVal::Add(a, b) => { a.simplify(); b.simplify(); SymVal::eval_vals(&*a, &*b, |x, y| x + y) } - SymVal::Mul(a, b) => { a.simplify(); b.simplify(); SymVal::eval_vals(&*a, &*b, |x, y| x * y) } - SymVal::Ban(a, b) => { a.simplify(); b.simplify(); SymVal::eval_vals(&*a, &*b, |x, y| x & y) } - SymVal::Bor(a, b) => { a.simplify(); b.simplify(); SymVal::eval_vals(&*a, &*b, |x, y| x | y) } - SymVal::Grt(a, b) => { a.simplify(); b.simplify(); SymVal::eval_vals(&*a, &*b, |x, y| (x > y) as usize) } - SymVal::Equ(a, b) => { a.simplify(); b.simplify(); SymVal::eval_vals(&*a, &*b, |x, y| (x == y) as usize) } - SymVal::If1(c, t, e) => { - c.simplify(); t.simplify(); e.simplify(); - match **c { - SymVal::Val(1) => Some((**t).clone()), - SymVal::Val(_) => Some((**e).clone()), - _ => None, - } - } - }; - if let Some(res) = optres { - *self = res; - } - } - - fn eval_vals<F: Fn(usize, usize) -> usize>(a: &SymVal, b: &SymVal, func: F) -> Option<SymVal> { - match (a, b) { - (&SymVal::Val(x), &SymVal::Val(y)) => Some(SymVal::Val(func(x, y))), - _ => None, - } - } -} - -struct SymbolicMachine { - regs: [SymVal; 6], -} - -impl SymbolicMachine { - fn from(m: &Machine) -> Self { - let mut sm = SymbolicMachine { regs: Default::default() }; - for i in 0..6 { - sm.regs[i] = SymVal::Val(m.regs[i]); - } - sm - } - - fn exec_oper(&self, oper: Oper) -> SymVal { - match oper { - Oper::Reg(r) => self.regs[r].clone(), - Oper::Num(n) => SymVal::Val(n), - } - } - - fn exec(&mut self, instr: &Instr) { - let (c, mut val) = match instr { - &Instr::Add(a, b, c) => (c, SymVal::Add(Box::new(self.exec_oper(a)), Box::new(self.exec_oper(b)))), - &Instr::Mul(a, b, c) => (c, SymVal::Mul(Box::new(self.exec_oper(a)), Box::new(self.exec_oper(b)))), - &Instr::Ban(a, b, c) => (c, SymVal::Ban(Box::new(self.exec_oper(a)), Box::new(self.exec_oper(b)))), - &Instr::Bor(a, b, c) => (c, SymVal::Bor(Box::new(self.exec_oper(a)), Box::new(self.exec_oper(b)))), - &Instr::Grt(a, b, c) => (c, SymVal::Grt(Box::new(self.exec_oper(a)), Box::new(self.exec_oper(b)))), - &Instr::Equ(a, b, c) => (c, SymVal::Equ(Box::new(self.exec_oper(a)), Box::new(self.exec_oper(b)))), - &Instr::Set(a, c) => (c, self.exec_oper(a)), - }; - - val.simplify(); - self.regs[c] = val; - } - - fn exec_find_loop(&mut self, prog: &[Instr], start_ip: usize) -> bool { - let mut ip = start_ip; - while ip != start_ip { - self.regs[IP_REG] = SymVal::Val(ip); - // println!("{} ip={} {}", self, ip, prog[ip]); - self.exec(&prog[ip]); - self.regs[IP_REG].simplify(); - ip = match self.regs[IP_REG] { - SymVal::Val(v) => v, - _ => return false, - }; - } - - false - } -} - -fn optimise(mut instrs: Vec<Instr>) -> Vec<Instr> { +#[allow(dead_code)] +fn optimise(mut instrs: Vec<Instr>, ip_reg: usize) -> Vec<Instr> { for i in 0..instrs.len() { - instrs[i].inline_reg(IP_REG, Oper::Num(i)); + instrs[i].inline_reg(ip_reg, Oper::Num(i)); } instrs } -fn run_program(instrs: &[Instr], r0: usize) -> usize { +#[allow(dead_code)] +fn run_program(instrs: &[Instr], r0: usize, ip_reg: usize) -> usize { let mut m = Machine { regs: [r0, 0, 0, 0, 0, 0] }; - m.exec_program(&instrs); + m.exec_program(&instrs, ip_reg); m.regs[0] } @@ -353,24 +26,19 @@ fn main_alt() -> (String, String) { (divisor_sum(948).to_string(), divisor_sum(10551348).to_string()) } -pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> { +pub fn main<T: BufRead>(_reader: T) -> io::Result<(String, String)> { Ok(main_alt()) - /* let mut lines = reader.lines(); - let ip_reg = (lines.next().unwrap().unwrap().as_bytes()[4] - '0' as u8) as usize; - assert!(ip_reg == IP_REG); - let instrs = lines.map(|l| - Instr::from_raw_instr(&l.unwrap().parse().unwrap()) - ).collect::<Vec<Instr>>(); + /* let (ip_reg, instrs) = parse_program(reader)?; // for instr in &instrs { println!("{}", instr); } - let instrs = optimise(instrs); + let instrs = optimise(instrs, ip_reg); for instr in &instrs { println!("{}", instr); } // let part1 = run_program(&instrs, 0); - let part2 = run_program(&instrs, 1); + let part2 = run_program(&instrs, 1, ip_reg); // Ok((part1.to_string(), part2.to_string())) Ok((String::new(), String::new())) */ |