From 3b877bf4cc667eb8bcc787d145203600a4dba2d2 Mon Sep 17 00:00:00 2001 From: Prefetch Date: Sat, 25 Feb 2023 11:41:27 +0100 Subject: Initial commit --- d25/src/main.rs | 178 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 178 insertions(+) create mode 100644 d25/src/main.rs (limited to 'd25/src') diff --git a/d25/src/main.rs b/d25/src/main.rs new file mode 100644 index 0000000..ab740d8 --- /dev/null +++ b/d25/src/main.rs @@ -0,0 +1,178 @@ +use std::collections::HashMap; +use std::fs; + +// This implementation is more similar to day 23 than day 12 +#[derive(Copy, Clone, Debug)] +enum Arg<'a> { + Reg(&'a str), + Lit(isize), +} + +impl<'a> From<&'a str> for Arg<'a> { + fn from(s: &'a str) -> Self { + if s.chars().all(|c| c.is_ascii_digit() || c == '-') { // yes I know + Self::Lit(s.parse().unwrap()) + } else { + Self::Reg(s) + } + } +} + +#[derive(Copy, Clone, Debug)] +enum Oper<'a> { + Inc(Arg<'a>), + Dec(Arg<'a>), + Out(Arg<'a>), + Cpy(Arg<'a>, Arg<'a>), + Jnz(Arg<'a>, Arg<'a>), +} + +fn parse(lines: Vec<&str>) -> Vec { + let mut insts = Vec::new(); + + for line in lines { + let words: Vec<&str> = line.split_ascii_whitespace().collect(); + + if words[0] == "inc" { + insts.push(Oper::Inc(Arg::from(words[1]))); + } else if words[0] == "dec" { + insts.push(Oper::Dec(Arg::from(words[1]))); + } else if words[0] == "out" { + insts.push(Oper::Out(Arg::from(words[1]))); + } else if words[0] == "cpy" { + insts.push(Oper::Cpy(Arg::from(words[1]), Arg::from(words[2]))); + } else if words[0] == "jnz" { + insts.push(Oper::Jnz(Arg::from(words[1]), Arg::from(words[2]))); + } + } + + insts +} + +// We pause the program at each `Out' and save the state to resume later +#[derive(Clone, Debug, PartialEq)] +struct State<'a> { + regs: HashMap<&'a str, isize>, + ip: usize, +} + +impl<'a> From> for State<'a> { + fn from(init: Vec<(&'a str, isize)>) -> Self { + Self { + regs: init.into_iter().collect(), + ip: 0, + } + } +} + +// Execute the program until the next `Out` instruction, return the transmission +fn transmit_next<'a>(insts: &'a Vec, state: &mut State<'a>) -> Option { + let mut transmit = None; + + while state.ip < insts.len() && transmit.is_none() { + match insts[state.ip] { + Oper::Inc(arg) => { + if let Arg::Reg(dst) = arg { + *state.regs.entry(dst).or_insert(0) += 1; + } + }, + Oper::Dec(arg) => { + if let Arg::Reg(dst) = arg { + *state.regs.entry(dst).or_insert(0) -= 1; + } + }, + Oper::Out(arg) => { + let val = match arg { + Arg::Reg(reg) => state.regs.get(®).copied().unwrap_or(0), + Arg::Lit(lit) => lit, + }; + transmit = Some(val); + }, + Oper::Cpy(arg1, arg2) => { + // This `if let' is actually a leftover from day 23 + if let Arg::Reg(dst) = arg2 { + let val = match arg1 { + Arg::Reg(src) => state.regs.get(&src).copied().unwrap_or(0), + Arg::Lit(lit) => lit, + }; + *state.regs.entry(dst).or_insert(0) = val; + } + }, + Oper::Jnz(arg1, arg2) => { + let val = match arg1 { + Arg::Reg(reg) => state.regs.get(®).copied().unwrap_or(0), + Arg::Lit(lit) => lit, + }; + if val != 0 { + let off = match arg2 { + Arg::Reg(reg) => state.regs.get(®).copied().unwrap_or(0), + Arg::Lit(lit) => lit, + }; + // Subtract 1 to compensate for `state.ip += 1;' below + state.ip = ((state.ip as isize) + off - 1) as usize; + } + }, + }; + + state.ip += 1; + } + + transmit +} + +fn solve_part1(insts: &Vec) -> isize { + let mut a = 1; + loop { + // History of (transmission, state) for this value of `a'. + // We're looking for a periodic pattern in these tuples. + let mut history: Vec<(isize, State)> = Vec::new(); + + // Initialize a fresh state with the candidate value of `a' + let mut state: State = State::from(vec![("a", a)]); + + // This puzzle is basically Turing's halting problem, so for practicality + // we arbitrarily assume that the periodicity is at most 100 transmissions + for _i in 0..100 { + let ot = transmit_next(insts, &mut state); + + // Did the program exit? + if ot.is_none() { + break; + } + + // Did we transmit something other than 0 or 1? + let t = ot.unwrap(); + if t != 0 && t != 1 { + break; + } + + // Didn't we transmit 0 after 1, or 1 after 0? + if history.len() > 0 && history.last().unwrap().0 != 1 - t { + break; + } + + let ts = (t, state.clone()); + // Have we seen this state before? If yes, we've found a solution! + if history.contains(&ts) { + return a; + } else { + // But the transmission pattern seems promising so far; store it + history.push(ts); + } + } + + a += 1; + } +} + +fn main() { + // Read assembly from input text file and parse it + let input = fs::read_to_string("input.txt").unwrap(); + let lines = input.lines().collect(); + let insts = parse(lines); + + // Part 1 gives 158 for my input + println!("Part 1 solution: {}", solve_part1(&insts)); + + // There's no part 2, since this is the last day +} -- cgit v1.2.3