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

aoc/year2024/
day17.rs
