aoc/year2024/
day17.rs

1//! # Chronospatial Computer
2//!
3//! Part one implements the computer specification then runs the provided program. The `b` and `c`
4//! registers are assumed to be always zero in the provided input. The computer uses a resumable
5//! `run` method that returns `Some(out)` to indicate output and `None` to indicate program end.
6//! This is the same flexible approach used by the 2019 [`Intcode`] computer.
7//!
8//! For part two, reverse engineering the assembly shows that it implements the following
9//! algorithm:
10//!
11//! ```none
12//! while a != 0 {
13//!     b = // Some hash based on value of a
14//!     out b
15//!     a >>= 3
16//! }
17//! ```
18//!
19//! This means that the final value of `a` must be zero. Starting with this knowledge we work
20//! backward digit by digit. The right shift wipes out the lowest 3 bits of `a` so there could
21//! be 8 possible previous values. We check each possible value recursively, exploring only
22//! those that result in the correct program digit.
23//!
24//! For each new item we check each of the 8 possible combinations against the next digit
25//! in reverse, and so on until we have all possible valid starting values of `a`.
26//!
27//! Although it may seem that checking could grow exponentially to 8¹⁶ potential values,
28//! in practice filtering by correct digit keeps the total less than 50.
29//!
30//! [`Intcode`]: crate::util::intcode
31use crate::util::parse::*;
32
33struct Computer<'a> {
34    program: &'a [u64],
35    a: u64,
36    b: u64,
37    c: u64,
38    ip: usize,
39}
40
41impl Computer<'_> {
42    /// The values of `b` and `c` are always 0 in the provided inputs.
43    fn new(input: &[u64], a: u64) -> Computer<'_> {
44        Computer { program: &input[3..], a, b: 0, c: 0, ip: 0 }
45    }
46
47    fn run(&mut self) -> Option<u64> {
48        while self.ip < self.program.len() {
49            let literal = self.program[self.ip + 1];
50            let combo = || match literal {
51                n @ 0..4 => n,
52                4 => self.a,
53                5 => self.b,
54                6 => self.c,
55                _ => unreachable!(),
56            };
57
58            // Computer specification.
59            match self.program[self.ip] {
60                0 => self.a >>= combo(),
61                1 => self.b ^= literal,
62                2 => self.b = combo() % 8,
63                3 => {
64                    if self.a != 0 {
65                        self.ip = literal as usize;
66                        continue;
67                    }
68                }
69                4 => self.b ^= self.c,
70                5 => {
71                    let out = combo() % 8;
72                    self.ip += 2;
73                    return Some(out);
74                }
75                6 => self.b = self.a >> combo(),
76                7 => self.c = self.a >> combo(),
77                _ => unreachable!(),
78            }
79
80            self.ip += 2;
81        }
82
83        None
84    }
85}
86
87pub fn parse(input: &str) -> Vec<u64> {
88    input.iter_unsigned().collect()
89}
90
91pub fn part1(input: &[u64]) -> String {
92    // We only care about the value of `a`.
93    let mut computer = Computer::new(input, input[0]);
94    let mut out = String::new();
95
96    while let Some(n) = computer.run() {
97        out.push(char::from(n as u8 + b'0'));
98        out.push(',');
99    }
100
101    // Remove the trailing comma.
102    out.pop();
103    out
104}
105
106pub fn part2(input: &[u64]) -> u64 {
107    // Start with known final value of `a`.
108    helper(input, input.len() - 1, 0).unwrap()
109}
110
111fn helper(program: &[u64], index: usize, a: u64) -> Option<u64> {
112    if index == 2 {
113        return Some(a);
114    }
115
116    // Try all 8 combinations of lower 3 bits.
117    (0..8).find_map(|i| {
118        let next_a = (a << 3) | i;
119        let out = Computer::new(program, next_a).run().unwrap();
120        if out == program[index] { helper(program, index - 1, next_a) } else { None }
121    })
122}
aoc/year2024/day17.rs

aoc/year2024/
day17.rs
