year2016/
day25.rs

1use crate::assembunny::Interpreter;
2use std::collections::HashSet;
3use std::ops::ControlFlow;
4use utils::prelude::*;
5
6/// Finding patterns in interpreted assembunny assembly output.
7///
8/// ```text
9///  cpy $N $r3
10///  jnz $r2 2
11///  jnz 1 6
12///  dec $r2
13///  dec $r3
14///  jnz $r3 -4
15///  inc $r1
16///  jnz 1 -7
17/// ```
18/// can be replaced with `$r1 += $r2 / $N`, followed by `$r3 = $N - ($r2 % $N)` and `$r2 = 0`.
19/// This reduces the number of simulated cycles for ~300 times when using the previously implemented
20/// addition optimization, and ~400 times compared to a naive implementation.
21///
22/// See also [2016 day 12](crate::Day12) and [2016 day 23](crate::Day23).
23#[derive(Clone, Debug)]
24pub struct Day25 {
25    interpreter: Interpreter<false, true>,
26}
27
28impl Day25 {
29    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
30        Ok(Self {
31            interpreter: Interpreter::new(input)?,
32        })
33    }
34
35    #[must_use]
36    pub fn part1(&self) -> i32 {
37        let mut seen = HashSet::new();
38        for i in 1..=i32::MAX {
39            let mut last = 1;
40            let mut found_solution = false;
41            seen.clear();
42
43            self.interpreter.execute([i, 0, 0, 0], |v, state| {
44                if (last == 1 && v != 0) || (last == 0 && v != 1) {
45                    return ControlFlow::Break(());
46                }
47                last = v;
48
49                if seen.insert((v, state)) {
50                    ControlFlow::Continue(())
51                } else {
52                    // Looped to previously seen state that produces the correct pattern
53                    found_solution = true;
54                    ControlFlow::Break(())
55                }
56            });
57
58            if found_solution {
59                return i;
60            }
61        }
62
63        panic!("no solution found")
64    }
65
66    #[must_use]
67    pub fn part2(&self) -> &'static str {
68        "🎄"
69    }
70}
71
72examples!(Day25 -> (i32, &'static str) []);
year2016/day25.rs

year2016/
day25.rs
