summaryrefslogtreecommitdiff
path: root/2018/src
diff options
context:
space:
mode:
authortomsmeding <tom.smeding@gmail.com>2018-12-16 12:15:48 +0100
committertomsmeding <tom.smeding@gmail.com>2018-12-16 12:15:48 +0100
commit0195c76570a61331c72480c0053dadc2f68b08d9 (patch)
tree77318641588f0f35c09fb30a8422e84506115b9b /2018/src
parentac044d8bb94940cf479e10eefa946c30db2a811c (diff)
Day 16
Diffstat (limited to '2018/src')
-rw-r--r--2018/src/day16.rs191
-rw-r--r--2018/src/main.rs4
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"))
}
}