diff options
Diffstat (limited to 'd25')
| -rw-r--r-- | d25/Cargo.toml | 6 | ||||
| -rw-r--r-- | d25/input.txt | 30 | ||||
| -rw-r--r-- | d25/src/main.rs | 178 |
3 files changed, 214 insertions, 0 deletions
diff --git a/d25/Cargo.toml b/d25/Cargo.toml new file mode 100644 index 0000000..483f9b6 --- /dev/null +++ b/d25/Cargo.toml @@ -0,0 +1,6 @@ +[package] +name = "d25" +version = "0.1.0" +edition = "2021" + +[dependencies] diff --git a/d25/input.txt b/d25/input.txt new file mode 100644 index 0000000..b684231 --- /dev/null +++ b/d25/input.txt @@ -0,0 +1,30 @@ +cpy a d +cpy 4 c +cpy 643 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 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<Oper> { + 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<Vec<(&'a str, isize)>> 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<Oper>, state: &mut State<'a>) -> Option<isize> { + 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<Oper>) -> 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 +} |