diff options
| -rw-r--r-- | 2018/19_notes_1.txt | 36 | ||||
| -rw-r--r-- | 2018/input/19.txt | 37 | ||||
| -rw-r--r-- | 2018/src/day19.rs | 365 | ||||
| -rw-r--r-- | 2018/src/main.rs | 4 |
4 files changed, 441 insertions, 1 deletions
diff --git a/2018/19_notes_1.txt b/2018/19_notes_1.txt new file mode 100644 index 0000000..e317941 --- /dev/null +++ b/2018/19_notes_1.txt @@ -0,0 +1,36 @@ +L0: jmp L4 +L1: r5 <- 1 +L2: r2 <- 1 + r1 <- 2 + r1 <- 2 == r3 + rip <- r1 + 5 + jmp L3 + r0 <- r5 + r0 +L3: r2 <- r2 + 1 + r1 <- r2 > r3 + rip <- 10 + r1 + jmp L2 + r5 <- r5 + 1 + r1 <- r5 > r3 + rip <- r1 + 14 + jmp L1 + exit +L4: r3 <- r3 + 2 + r3 <- r3 * r3 + r3 <- 19 * r3 + r3 <- r3 * 11 + r1 <- r1 + 5 + r1 <- r1 * 22 + r1 <- r1 + 2 + r3 <- r3 + r1 + rip <- 25 + r0 + jmp L0 + r1 <- 27 + r1 <- r1 * 28 + r1 <- 29 + r1 + r1 <- 30 * r1 + r1 <- r1 * 14 + r1 <- r1 * 32 + r3 <- r3 + r1 + r0 <- 0 + jmp L0 diff --git a/2018/input/19.txt b/2018/input/19.txt new file mode 100644 index 0000000..3a7db07 --- /dev/null +++ b/2018/input/19.txt @@ -0,0 +1,37 @@ +#ip 4 +addi 4 16 4 +seti 1 9 5 +seti 1 5 2 +mulr 5 2 1 +eqrr 1 3 1 +addr 1 4 4 +addi 4 1 4 +addr 5 0 0 +addi 2 1 2 +gtrr 2 3 1 +addr 4 1 4 +seti 2 6 4 +addi 5 1 5 +gtrr 5 3 1 +addr 1 4 4 +seti 1 2 4 +mulr 4 4 4 +addi 3 2 3 +mulr 3 3 3 +mulr 4 3 3 +muli 3 11 3 +addi 1 5 1 +mulr 1 4 1 +addi 1 2 1 +addr 3 1 3 +addr 4 0 4 +seti 0 2 4 +setr 4 8 1 +mulr 1 4 1 +addr 4 1 1 +mulr 4 1 1 +muli 1 14 1 +mulr 1 4 1 +addr 3 1 3 +seti 0 0 0 +seti 0 2 4 diff --git a/2018/src/day19.rs b/2018/src/day19.rs new file mode 100644 index 0000000..5d1c23d --- /dev/null +++ b/2018/src/day19.rs @@ -0,0 +1,365 @@ +use std::io; +use std::io::BufRead; +use std::fmt; +use std::str; + +// Number of things taken from day16, also edited + +#[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], ip_reg: usize) { + let mut freq_map = vec![0; prog.len()]; + + let mut ip = 0; + while ip < prog.len() { + freq_map[ip] += 1; + if freq_map[ip] >= 3 { + let mut sm = SymbolicMachine::from(self); + sm.exec_find_loop(prog, ip_reg, ip); + } + + self.regs[ip_reg] = ip; + println!("{} ip={} {}", self, ip, prog[ip]); + self.exec(&prog[ip]); + ip = self.regs[ip_reg]; + ip += 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], ip_reg: usize, 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>, ip_reg: usize) -> Vec<Instr> { + for i in 0..instrs.len() { + instrs[i].inline_reg(ip_reg, Oper::Num(i)); + } + + instrs +} + +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, ip_reg); + m.regs[0] +} + +pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> { + let mut lines = reader.lines(); + let ip_reg = (lines.next().unwrap().unwrap().as_bytes()[4] - '0' as u8) as usize; + + let instrs = lines.map(|l| + Instr::from_raw_instr(&l.unwrap().parse().unwrap()) + ).collect::<Vec<Instr>>(); + + // for instr in &instrs { println!("{}", instr); } + + let instrs = optimise(instrs, ip_reg); + + for instr in &instrs { println!("{}", instr); } + + let part1 = run_program(&instrs, 0, ip_reg); + let part2 = run_program(&instrs, 1, ip_reg); + + Ok((part1.to_string(), part2.to_string())) +} diff --git a/2018/src/main.rs b/2018/src/main.rs index 08b96db..1c38fad 100644 --- a/2018/src/main.rs +++ b/2018/src/main.rs @@ -23,8 +23,9 @@ mod day15; mod day16; mod day17; mod day18; +mod day19; -static NUM_DAYS: i32 = 18; +static NUM_DAYS: i32 = 19; fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> { match day { @@ -46,6 +47,7 @@ fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> { 16 => day16::main(reader), 17 => day17::main(reader), 18 => day18::main(reader), + 19 => day19::main(reader), _ => Err(Error::new(ErrorKind::Other, "Invalid day")) } } |