Day 19 part 1, part 2 WIP

2 files changed, 368 insertions, 1 deletions

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"))
     }
 }