aoc/year2021/day24.rs
1//! # Arithmetic Logic Unit
2//!
3//! There are two ways to solve this problem. We can brute force emulate the ALU, but even with
4//! memoization this takes a long time to solve. Instead analyzing and reverse engineering the code
5//! shows an insight that reduces the problem to a much simpler constraint satisfaction problem.
6//!
7//! ## Analysis Summary
8//!
9//! The code consists of 14 blocks of 18 instructions, each block starting with `inp w`.
10//!
11//! There are 7 "push" blocks and 7 "pop" blocks.
12//! * Push blocks use `z` as a stack, multiplying by 26 and adding `w` plus some constant `k₁`.
13//! Push blocks always add to the stack.
14//! * Pop blocks compare the top element of `z` plus some constant `k₂` to `w`. If the values are
15//! equal then `z` is "popped" by dividing by 26. Otherwise `z` is pushed again with `w`
16//! plus some constant.
17//!
18//! Since the push/pop blocks are equally numbered and we want `z` to be zero (empty stack) at the
19//! end of the program, the condition:
20//!
21//! `w₁ + k₁ + k₂ = w₂`
22//!
23//! must be true for each matching pair of push/pop blocks. Since we also know that each `w` is
24//! between 1 and 9 inclusive, that is enough information to determine maximum and minimum values
25//! for each of the fourteen `w` values.
26//!
27//! For example:
28//! * If `k₁ + k₂ = 7` then `w₁ + 7 = w₂`.
29//! * Maximum value of `w₁` is 2 when `w₂` is 9.
30//! * Minimum value of `w₁` is 1 when `w₂` is 8.
31//!
32//! ## Detailed Push block analysis
33//!
34//! ```none
35//! inp w // w = 1 to 9 inclusive
36//! mul x 0 // x = 0
37//! add x z // x = z
38//! mod x 26 // x = z % 26
39//! div z 1 // nop
40//! add x 13 // x = z % 26 + 13
41//! eql x w // if (z % 26 + 13) == w { x = 1 } else { x = 0 }
42//! // However since w is restricted to 1 to 9 this condition is always false
43//! // so x is always 0. Other blocks have different constants but always > 9.
44//! eql x 0 // x = 1 (as 0 == 0)
45//! mul y 0 // y = 0
46//! add y 25 // y = 25
47//! mul y x // y = 25 * 1 = 25
48//! add y 1 // y = 25 + 1 = 26
49//! mul z y // z = 26 * z
50//! mul y 0 // y = 0
51//! add y w // y = w
52//! add y 14 // y = w + 14 (k₁ = 14)
53//! mul y x // y = (w + 14) * 1 = (w + 14)
54//! add z y // z = (26 * z) + (w + 14)
55//! ```
56//!
57//! ## Detailed Push block analysis
58//!
59//! ```none
60//! inp w // w = 1 to 9 inclusive
61//! mul x 0 // x = 0
62//! add x z // x = z
63//! mod x 26 // x = z % 26
64//! div z 26 // z /= 26 (pop)
65//! add x -13 // x = z % 26 - 13 (k₂ = -13)
66//! eql x w // if (z % 26 - 13) == w { x = 1 } else { x = 0 }
67//! eql x 0 // if (z % 26 - 13) == w { x = 0 } else { x = 1 }
68//! // Inverts the previous conditional.
69//! // Unlike the push blocks, this may true or false
70//! // We'll split into 2 paths, depending on equals (x = 0) or
71//! // not equal (x = 1).
72//! | Equals (x = 0) | Not Equals (x = 1) |
73//! mul y 0 | y = 0 | y = 0 |
74//! add y 25 | y = 25 | y = 25 |
75//! mul y x | y = 25 * 0 = 0 | y = 25 * 1 = 25 |
76//! add y 1 | y = 0 + 1 = 1 | y = 25 + 1 = 26 |
77//! mul z y | z = z (nop) | z = 26 * z |
78//! mul y 0 | y = 0 | y = 0 |
79//! add y w | y = w | y = w |
80//! add y 4 | y = w + 4 | y = w + 4 |
81//! mul y x | y = (w + 4) * 0 | y = (w + 4) * 1 |
82//! add z y | z = z | z = (26 * z) * (w + 4) |
83//! ```
84use crate::util::parse::*;
85use Block::*;
86
87/// Blocks are either "push" or "pop".
88enum Block {
89 Push(i32),
90 Pop(i32),
91}
92
93/// Convert matching pairs of blocks into constraints.
94/// For the first digit `value` is `-(k₁ + k₂)` and second digit value is `k₁ + k₂`.
95pub struct Constraint {
96 index: usize,
97 value: i32,
98}
99
100/// Convert `k₁ + k₂` to min and max values, clamping at 1 and 9 respectively.
101impl Constraint {
102 fn min(&self) -> i32 {
103 (1 + self.value).max(1)
104 }
105
106 fn max(&self) -> i32 {
107 (9 + self.value).min(9)
108 }
109}
110
111pub fn parse(input: &str) -> Vec<Constraint> {
112 let lines: Vec<_> = input.lines().collect();
113 let blocks: Vec<_> = lines
114 .chunks(18)
115 .map(|chunk| {
116 // Parse the last token on the specified line within a block.
117 let helper = |i: usize| chunk[i].split_ascii_whitespace().last().unwrap().signed();
118 // The 5th instruction in "push" blocks is always a `div z 1`
119 // that we can use to figure out what type of block we're dealing with.
120 if helper(4) == 1 {
121 // `k₁` is always located at the 16th instruction.
122 Push(helper(15))
123 } else {
124 // `k₂` is always located at the 6th instruction.
125 Pop(helper(5))
126 }
127 })
128 .collect();
129
130 let mut stack = Vec::new();
131 let mut constraints = Vec::new();
132
133 for (index, blocks) in blocks.into_iter().enumerate() {
134 match blocks {
135 Push(value) => stack.push(Constraint { index, value }),
136 Pop(second_value) => {
137 // Find the matching "push" instruction at the top of the stack.
138 let mut first = stack.pop().unwrap();
139 // delta = k₁ + k₂
140 let delta = first.value + second_value;
141 // w₁ + delta = w₂ <=> w₁ = w₂ - delta
142 first.value = -delta;
143 let second = Constraint { index, value: delta };
144 constraints.push(first);
145 constraints.push(second);
146 }
147 }
148 }
149
150 // Sort by original ALU program order
151 constraints.sort_unstable_by_key(|c| c.index);
152 constraints
153}
154
155pub fn part1(input: &[Constraint]) -> String {
156 input.iter().map(|c| c.max().to_string()).collect()
157}
158
159pub fn part2(input: &[Constraint]) -> String {
160 input.iter().map(|c| c.min().to_string()).collect()
161}