summaryrefslogtreecommitdiff
path: root/2018
diff options
context:
space:
mode:
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.rs354
-rw-r--r--2018/src/device.rs354
-rw-r--r--2018/src/main.rs1
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;