diff options
Diffstat (limited to '2018')
| -rw-r--r-- | 2018/19_notes.txt (renamed from 2018/19_notes_1.txt) | 0 | ||||
| -rw-r--r-- | 2018/src/day19.rs | 354 | ||||
| -rw-r--r-- | 2018/src/device.rs | 354 | ||||
| -rw-r--r-- | 2018/src/main.rs | 1 |
4 files changed, 366 insertions, 343 deletions
diff --git a/2018/19_notes_1.txt b/2018/19_notes.txt index c6c5532..c6c5532 100644 --- a/2018/19_notes_1.txt +++ b/2018/19_notes.txt 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())) */ diff --git a/2018/src/device.rs b/2018/src/device.rs new file mode 100644 index 0000000..7eaf8d3 --- /dev/null +++ b/2018/src/device.rs @@ -0,0 +1,354 @@ +#![allow(dead_code)] + +use std::fmt; +use std::io::{self, BufRead}; +use std::str; + +#[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)] +pub enum Oper { + Reg(usize), + Num(usize), +} + +impl Oper { + pub 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 mut next_string = move || iter.next().ok_or(io::Error::new(io::ErrorKind::Other, "Invalid raw instruction")); + macro_rules! next_int { + ( $var:ident ) => { + let $var = next_string()?.parse() + .or(Err(io::Error::new(io::ErrorKind::Other, "Invalid number in raw instruction")))?; + } + }; + + let op = next_string()?.parse()?; + next_int!(a); + next_int!(b); + next_int!(c); + Ok(RawInstr { op, a, b, c }) + } +} + +pub 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), + } + } + + pub 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), + }; + } + + pub 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)] +pub struct Machine { + pub regs: [usize; 6], +} + +impl Machine { + pub 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), + } + } + + pub fn exec_program(&mut self, prog: &[Instr], ip_reg: usize) { + let mut ip = 0; + while ip < prog.len() { + self.regs[ip_reg] = ip; + println!("{} ip={} {}", self, ip, prog[ip]); + self.exec(&prog[ip]); + ip = self.regs[ip_reg] + 1; + } + } + + pub 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(()) + } +} + +pub fn parse_program<T: BufRead>(reader: T) -> io::Result<(usize, Vec<Instr>)> { + let mut lines = reader.lines(); + let ip_reg = match lines.next() { + Some(line) => { + let line = line?; + if line.starts_with("#ip ") && line.len() == 5 { + (line.as_bytes()[4] - '0' as u8) as usize + } else { + return Err(io::Error::new(io::ErrorKind::Other, "Program parse error: initial line not '#ip n'")); + } + } + None => { + return Err(io::Error::new(io::ErrorKind::Other, "Program parse error: empty file")); + } + }; + + let instrs = lines.map(|l| { + Ok(Instr::from_raw_instr(&l?.parse()?)) + }).collect::<io::Result<Vec<Instr>>>()?; + + Ok((ip_reg, instrs)) +} + +#[derive(Clone, PartialEq, Eq)] +pub 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 { + pub 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; + } + } + + pub 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, + } + } +} + +pub struct SymbolicMachine { + pub regs: [SymVal; 6], +} + +impl SymbolicMachine { + pub 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 + } + + pub fn exec_oper(&self, oper: Oper) -> SymVal { + match oper { + Oper::Reg(r) => self.regs[r].clone(), + Oper::Num(n) => SymVal::Val(n), + } + } + + pub 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, ip_reg: 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 + } +} + diff --git a/2018/src/main.rs b/2018/src/main.rs index dece97e..34c3964 100644 --- a/2018/src/main.rs +++ b/2018/src/main.rs @@ -5,6 +5,7 @@ use std::process::exit; use argparse::{ArgumentParser, StoreTrue, Store}; mod benchmark; +mod device; mod day1; mod day2; mod day3; |