Day 16

2 files changed, 194 insertions, 1 deletions

diff --git a/2018/src/day16.rs b/2018/src/day16.rs
new file mode 100644
index 0000000..cc68949
--- /dev/null
+++ b/2018/src/day16.rs
@@ -0,0 +1,191 @@
+use std::io;
+use std::io::BufRead;
+
+#[derive(Copy, Clone)]
+enum Opcode {
+    Addr, Addi,
+    Mulr, Muli,
+    Banr, Bani,
+    Borr, Bori,
+    Setr, Seti,
+    Gtir, Gtri, Gtrr,
+    Eqir, Eqri, Eqrr,
+}
+
+impl Opcode {
+    fn from_id(id: u16) -> Opcode {
+        use self::Opcode::*;
+        static VALUES: [Opcode; 16] = [Addr, Addi, Mulr, Muli, Banr, Bani, Borr, Bori, Setr, Seti, Gtir, Gtri, Gtrr, Eqir, Eqri, Eqrr];
+        VALUES[id as usize]
+    }
+}
+
+struct Instr {
+    op: usize,
+    a: usize,
+    b: usize,
+    c: usize,
+}
+
+impl Instr {
+    fn from(line: &str) -> Self {
+        let mut iter = line.split(' ').map(|s| s.parse().unwrap());
+        let op = iter.next().unwrap();
+        let a = iter.next().unwrap();
+        let b = iter.next().unwrap();
+        let c = iter.next().unwrap();
+        Instr { op, a, b, c }
+    }
+}
+
+#[derive(PartialEq, Eq, Clone)]
+struct Machine {
+    regs: [usize; 4],
+}
+
+impl Machine {
+    fn from(line: &str) -> Self {
+        let mut machine = Machine { regs: [0; 4] };
+        let mut i = 0;
+        for num in line.split(", ").map(|s| s.parse().unwrap()) {
+            machine.regs[i] = num;
+            i += 1;
+        }
+        machine
+    }
+
+    fn exec(&mut self, op: Opcode, a: usize, b: usize, c: usize) {
+        match op {
+            Opcode::Addr => self.regs[c] = self.regs[a] + self.regs[b],
+            Opcode::Addi => self.regs[c] = self.regs[a] + b,
+            Opcode::Mulr => self.regs[c] = self.regs[a] * self.regs[b],
+            Opcode::Muli => self.regs[c] = self.regs[a] * b,
+            Opcode::Banr => self.regs[c] = self.regs[a] & self.regs[b],
+            Opcode::Bani => self.regs[c] = self.regs[a] & b,
+            Opcode::Borr => self.regs[c] = self.regs[a] | self.regs[b],
+            Opcode::Bori => self.regs[c] = self.regs[a] | b,
+            Opcode::Setr => self.regs[c] = self.regs[a],
+            Opcode::Seti => self.regs[c] = a,
+            Opcode::Gtir => self.regs[c] = if a > self.regs[b] { 1 } else { 0 },
+            Opcode::Gtri => self.regs[c] = if self.regs[a] > b { 1 } else { 0 },
+            Opcode::Gtrr => self.regs[c] = if self.regs[a] > self.regs[b] { 1 } else { 0 },
+            Opcode::Eqir => self.regs[c] = if a == self.regs[b] { 1 } else { 0 },
+            Opcode::Eqri => self.regs[c] = if self.regs[a] == b { 1 } else { 0 },
+            Opcode::Eqrr => self.regs[c] = if self.regs[a] == self.regs[b] { 1 } else { 0 },
+        }
+    }
+}
+
+struct Sample {
+    before: Machine,
+    after: Machine,
+    instr: Instr,
+}
+
+impl Sample {
+    fn behaves_as(&self) -> u16 {
+        let mut r = 0;
+
+        for id in 0..16 {
+            let op = Opcode::from_id(id);
+
+            let mut m = self.before.clone();
+            m.exec(op, self.instr.a, self.instr.b, self.instr.c);
+            if m == self.after {
+                r |= 1 << id;
+            }
+        }
+
+        r
+    }
+}
+
+fn parse_input<T: BufRead>(reader: T) -> io::Result<(Vec<Sample>, Vec<Instr>)> {
+    let mut line_iter = reader.lines();
+    let mut samples = Vec::new();
+    let program;
+
+    loop {
+        let line = line_iter.next().unwrap()?;
+        if line.len() == 0 {
+            line_iter.next();
+
+            program = line_iter.map(|l| Instr::from(&l.unwrap())).collect::<Vec<_>>();
+            break;
+        } else if &line[..1] == "B" {
+            let before = Machine::from(&line[9..line.len()-1]);
+
+            let line = line_iter.next().unwrap()?;
+            let instr = Instr::from(&line);
+
+            let line = line_iter.next().unwrap()?;
+            let after = Machine::from(&line[9..line.len()-1]);
+
+            samples.push(Sample { before, after, instr });
+
+            line_iter.next();
+        } else {
+            assert!(false);
+        }
+    }
+
+    Ok((samples, program))
+}
+
+fn resolve_helper(masks: &[u16; 16], res: &mut [u16; 16], at: usize, available: u16) -> bool {
+    if at == 16 {
+        return true;
+    }
+
+    let mut walker = available;
+
+    while walker != 0 {
+        let n = walker.trailing_zeros();
+        let bit = 1 << n;
+        walker &= !bit;
+
+        if (masks[at] & bit) != 0 {
+            res[at] = n as u16;
+            if resolve_helper(masks, res, at + 1, available & !bit) {
+                return true;
+            }
+        }
+    }
+
+    false
+}
+
+fn resolve_mapping(masks: &[u16; 16]) -> [u16; 16] {
+    let mut res = [0; 16];
+    assert!(resolve_helper(masks, &mut res, 0, 0xffff));
+    res
+}
+
+pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
+    let (samples, program) = parse_input(reader)?;
+
+    let mut num_geq_3 = 0;
+    let mut code_masks = [0xffff; 16];
+
+    for sample in samples {
+        let mask = sample.behaves_as();
+        if mask.count_ones() >= 3 {
+            num_geq_3 += 1;
+        }
+
+        code_masks[sample.instr.op] &= mask;
+    }
+
+    let part1 = num_geq_3;
+
+    let mapping = resolve_mapping(&code_masks);
+
+    let mut m = Machine { regs: [0; 4] };
+    for instr in program {
+        m.exec(Opcode::from_id(mapping[instr.op]), instr.a, instr.b, instr.c);
+    }
+
+    let part2 = m.regs[0];
+
+    Ok((part1.to_string(), part2.to_string()))
+}
diff --git a/2018/src/main.rs b/2018/src/main.rs
index 6154c99..4bc8d50 100644
--- a/2018/src/main.rs
+++ b/2018/src/main.rs
@@ -20,8 +20,9 @@ mod day12;
 mod day13;
 mod day14;
 mod day15;
+mod day16;
 
-static NUM_DAYS: i32 = 15;
+static NUM_DAYS: i32 = 16;
 
 fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> {
     match day {
@@ -40,6 +41,7 @@ fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> {
         13 => day13::main(reader),
         14 => day14::main(reader),
         15 => day15::main(reader),
+        16 => day16::main(reader),
         _ => Err(Error::new(ErrorKind::Other, "Invalid day"))
     }
 }