Day 25

2 files changed, 193 insertions, 0 deletions

diff --git a/input/day25.txt b/input/day25.txt
new file mode 100644
index 0000000..17779fc
--- /dev/null
+++ b/input/day25.txt
@@ -0,0 +1,30 @@
+cpy a d
+cpy 15 c
+cpy 170 b
+inc d
+dec b
+jnz b -2
+dec c
+jnz c -5
+cpy d a
+jnz 0 0
+cpy a b
+cpy 0 a
+cpy 2 c
+jnz b 2
+jnz 1 6
+dec b
+dec c
+jnz c -4
+inc a
+jnz 1 -7
+cpy 2 b
+jnz c 2
+jnz 1 4
+dec b
+dec c
+jnz 1 -4
+jnz 0 0
+out b
+jnz a -19
+jnz 1 -21
\ No newline at end of file
diff --git a/src/bin/day25.rs b/src/bin/day25.rs
new file mode 100644
index 0000000..9ecf487
--- /dev/null
+++ b/src/bin/day25.rs
@@ -0,0 +1,163 @@
+use std::io::{self, Read};
+use std::iter;
+
+#[derive(Clone, Copy)]
+enum Operand {
+    Register(u8),
+    Immediate(i32),
+}
+
+impl<'a> From<&'a str> for Operand {
+    fn from(s: &'a str) -> Self {
+        match s {
+            "a" => Operand::Register(0),
+            "b" => Operand::Register(1),
+            "c" => Operand::Register(2),
+            "d" => Operand::Register(3),
+            _ => Operand::Immediate(s.parse().unwrap()),
+        }
+    }
+}
+
+#[derive(Clone, Copy)]
+enum Operation {
+    Cpy(Operand, Operand),
+    Inc(Operand),
+    Dec(Operand),
+    Jnz(Operand, Operand),
+    Tgl(Operand),
+    Out(Operand),
+}
+
+impl<'a> From<&'a str> for Operation {
+    fn from(s: &'a str) -> Self {
+        let mut iter = s.split_whitespace();
+        match (iter.next().unwrap(), iter.next().unwrap()) {
+            ("cpy", a) => Operation::Cpy(Operand::from(a), Operand::from(iter.next().unwrap())),
+            ("inc", a) => Operation::Inc(Operand::from(a)),
+            ("dec", a) => Operation::Dec(Operand::from(a)),
+            ("jnz", a) => Operation::Jnz(Operand::from(a), Operand::from(iter.next().unwrap())),
+            ("tgl", a) => Operation::Tgl(Operand::from(a)),
+            ("out", a) => Operation::Out(Operand::from(a)),
+            _ => panic!("invalid instruction {}", s),
+        }
+    }
+}
+
+impl Operation {
+    fn toggle(self) -> Self {
+        match self {
+            Operation::Inc(a) => Operation::Dec(a),
+            Operation::Dec(a) | Operation::Tgl(a) => Operation::Inc(a),
+            Operation::Jnz(a, b) => Operation::Cpy(a, b),
+            Operation::Cpy(a, b) => Operation::Jnz(a, b),
+            _ => unimplemented!(),
+        }
+    }
+}
+
+#[derive(Default)]
+struct Vm {
+    registers: [i32; 4],
+    operations: Vec<Operation>,
+    index: i32,
+    output: Vec<i32>,
+}
+
+impl<'a> From<&'a str> for Vm {
+    fn from(s: &'a str) -> Self {
+        let mut vm = Self::default();
+        for line in s.lines() {
+            vm.operations.push(Operation::from(line));
+        }
+        vm
+    }
+}
+
+impl Vm {
+    fn step(&mut self) -> bool {
+        match self.operations[self.index as usize] {
+            Operation::Cpy(Operand::Immediate(imm), Operand::Register(reg)) => {
+                self.registers[reg as usize] = imm;
+                self.index += 1;
+            },
+            Operation::Cpy(Operand::Register(src), Operand::Register(dest)) => {
+                self.registers[dest as usize] = self.registers[src as usize];
+                self.index += 1;
+            },
+            Operation::Inc(Operand::Register(reg)) => {
+                self.registers[reg as usize] += 1;
+                self.index += 1;
+            },
+            Operation::Dec(Operand::Register(reg)) => {
+                self.registers[reg as usize] -= 1;
+                self.index += 1;
+            },
+            Operation::Jnz(Operand::Immediate(cond), Operand::Immediate(jump)) => {
+                if cond != 0 {
+                    self.index += jump;
+                } else {
+                    self.index += 1;
+                }
+            },
+            Operation::Jnz(Operand::Register(reg), Operand::Immediate(jump)) => {
+                if self.registers[reg as usize] != 0 {
+                    self.index += jump;
+                } else {
+                    self.index += 1;
+                }
+            },
+            Operation::Jnz(Operand::Immediate(cond), Operand::Register(reg)) => {
+                if cond != 0 {
+                    self.index += self.registers[reg as usize];
+                } else {
+                    self.index += 1;
+                }
+            },
+            Operation::Tgl(Operand::Register(reg)) => {
+                let index = self.index + self.registers[reg as usize];
+                if let Some(operation) = self.operations.get_mut(index as usize) {
+                    *operation = operation.toggle();
+                }
+                self.index += 1;
+            },
+            Operation::Out(Operand::Immediate(imm)) => {
+                self.output.push(imm);
+                self.index += 1;
+            },
+            Operation::Out(Operand::Register(reg)) => {
+                self.output.push(self.registers[reg as usize]);
+                self.index += 1;
+            },
+            _ => {
+                self.index += 1;
+            },
+        }
+
+        (self.index as usize) < self.operations.len()
+    }
+}
+
+fn solve(input: &str) -> i32 {
+    for i in 0.. {
+        let mut vm = Vm::from(input);
+        vm.registers[0] = i;
+        while vm.output.len() < 50 {
+            assert!(vm.step());
+        }
+
+        let target = iter::once(0).chain(iter::once(1)).cycle().take(50);
+        if vm.output.into_iter().eq(target) {
+            return i;
+        }
+    }
+
+    unreachable!()
+}
+
+fn main() {
+    let mut input = String::new();
+    io::stdin().read_to_string(&mut input).unwrap();
+
+    println!("Part 1: {}", solve(&input));
+}