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//! backwards 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::year2019::intcode
31use crate::util::parse::*;
32use std::ops::ControlFlow;
33
34pub fn parse(input: &str) -> Vec<u64> {
35    input.iter_unsigned().collect()
36}
37
38pub fn part1(input: &[u64]) -> String {
39    // We only care about the value of `a`.
40    let mut computer = Computer::new(input, input[0]);
41    let mut out = Vec::new();
42
43    while let Some(n) = computer.run() {
44        let digit = (n as u8 + b'0') as char;
45        out.push(digit);
46        out.push(',');
47    }
48
49    out.pop();
50    out.iter().collect()
51}
52
53pub fn part2(input: &[u64]) -> u64 {
54    // Start with known final value of `a`.
55    helper(input, input.len() - 1, 0).break_value().unwrap()
56}
57
58fn helper(program: &[u64], index: usize, a: u64) -> ControlFlow<u64> {
59    if index == 2 {
60        return ControlFlow::Break(a);
61    }
62
63    // Try all 8 combination of lower 3 bits.
64    for i in 0..8 {
65        let next_a = (a << 3) | i;
66        let out = Computer::new(program, next_a).run().unwrap();
67
68        if out == program[index] {
69            helper(program, index - 1, next_a)?;
70        }
71    }
72
73    ControlFlow::Continue(())
74}
75
76struct Computer<'a> {
77    program: &'a [u64],
78    a: u64,
79    b: u64,
80    c: u64,
81    ip: usize,
82}
83
84impl Computer<'_> {
85    /// The values of `b` and `c` are always 0 in the provided inputs.
86    fn new(input: &[u64], a: u64) -> Computer<'_> {
87        Computer { program: &input[3..], a, b: 0, c: 0, ip: 0 }
88    }
89
90    fn run(&mut self) -> Option<u64> {
91        while self.ip < self.program.len() {
92            // Convenience closures.
93            let literal = || self.program[self.ip + 1];
94            let combo = || match self.program[self.ip + 1] {
95                n @ 0..4 => n,
96                4 => self.a,
97                5 => self.b,
98                6 => self.c,
99                _ => unreachable!(),
100            };
101
102            // Computer specification.
103            match self.program[self.ip] {
104                0 => self.a >>= combo(),
105                1 => self.b ^= literal(),
106                2 => self.b = combo() % 8,
107                3 => {
108                    if self.a != 0 {
109                        self.ip = literal() as usize;
110                        continue;
111                    }
112                }
113                4 => self.b ^= self.c,
114                5 => {
115                    let out = combo() % 8;
116                    self.ip += 2;
117                    return Some(out);
118                }
119                6 => self.b = self.a >> combo(),
120                7 => self.c = self.a >> combo(),
121                _ => unreachable!(),
122            }
123
124            self.ip += 2;
125        }
126
127        None
128    }
129}
aoc/year2024/day17.rs

aoc/year2024/
day17.rs
