diff options
| -rw-r--r-- | input/day25.txt | 30 | ||||
| -rw-r--r-- | src/bin/day25.rs | 163 |
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)); +} |