year2024/
day24.rs

1use std::collections::HashMap;
2use std::ops::ControlFlow;
3use utils::prelude::*;
4
5/// Finding swapped logic gates in an adder circuit.
6#[derive(Clone, Debug)]
7pub struct Day24 {
8    wires: Vec<Wire>,
9    wire_names: Vec<[u8; 3]>,
10    x_initial: u64,
11    y_initial: u64,
12    z_indexes: Vec<usize>,
13}
14
15#[derive(Copy, Clone, Debug, PartialEq)]
16enum Wire {
17    X(usize),
18    Y(usize),
19    And(usize, usize),
20    Or(usize, usize),
21    Xor(usize, usize),
22}
23
24impl Day24 {
25    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
26        let Some((initial_str, gate_str)) = input
27            .split_once("\n\n")
28            .or_else(|| input.split_once("\r\n\r\n"))
29        else {
30            return Err(InputError::new(input, 0, "expected inputs and gates"));
31        };
32
33        let mut wires = Vec::new();
34        let mut wire_names = Vec::new();
35        let mut indexes = HashMap::new();
36        let mut x_initial = 0;
37        let mut y_initial = 0;
38        let mut input_bits = 64;
39
40        let mut next = (b'x', 0);
41        for item in parser::byte_range(b'x'..=b'y')
42            .then(parser::byte_range(b'0'..=b'9'))
43            .then(parser::byte_range(b'0'..=b'9'))
44            .with_suffix(": ")
45            .then(parser::byte_range(b'0'..=b'1'))
46            .with_consumed()
47            .with_suffix(parser::eol())
48            .parse_iterator(initial_str)
49        {
50            let ((wire, b), line) = item?;
51            let n = ((wire.1 - b'0') * 10 + (wire.2 - b'0')) as usize;
52
53            if (wire.0, n) != next {
54                if next.0 == b'x' && wire == (b'y', b'0', b'0') {
55                    input_bits = next.1;
56                } else {
57                    return Err(InputError::new(input, line, "unexpected initial value"));
58                }
59            }
60
61            if wire.0 == b'x' {
62                x_initial |= u64::from(b == b'1') << n;
63                wires.push(Wire::X(n));
64            } else {
65                y_initial |= u64::from(b == b'1') << n;
66                wires.push(Wire::Y(n));
67            }
68            wire_names.push(wire.into());
69            indexes.insert(wire.into(), wires.len() - 1);
70
71            if n == input_bits - 1 {
72                next = (b'?', 0);
73            } else {
74                next = (wire.0, n + 1);
75            }
76        }
77
78        let mut z_indexes = vec![usize::MAX; input_bits + 1];
79        let wire = parser::byte().repeat_n::<3, _>(parser::noop());
80        for item in wire
81            .then(parser::literal_map!(
82                " AND " => Wire::And as fn(usize, usize) -> Wire,
83                " OR " => Wire::Or,
84                " XOR " => Wire::Xor,
85            ))
86            .then(wire.with_suffix(" -> "))
87            .then(wire)
88            .with_suffix(parser::eol())
89            .parse_iterator(gate_str)
90        {
91            let (in1, gate, in2, out) = item?;
92
93            let mut index_of = |n| {
94                *indexes.entry(n).or_insert_with(|| {
95                    wires.push(Wire::X(usize::MAX)); // Placeholder
96                    wire_names.push(n);
97                    wires.len() - 1
98                })
99            };
100
101            let in1_index = index_of(in1);
102            let in2_index = index_of(in2);
103            let out_index = index_of(out);
104
105            if wires[out_index] != Wire::X(usize::MAX) {
106                return Err(InputError::new(input, 0, "duplicate wire definition"));
107            }
108            if out[0] == b'z' {
109                let index = ((out[1] - b'0') * 10 + (out[2] - b'0')) as usize;
110                if index < z_indexes.len() {
111                    z_indexes[index] = out_index;
112                } else {
113                    return Err(InputError::new(input, 0, "too many z outputs"));
114                }
115            }
116
117            wires[out_index] = gate(in1_index, in2_index);
118        }
119
120        if wires.contains(&Wire::X(usize::MAX)) {
121            return Err(InputError::new(input, 0, "undefined wire"));
122        }
123        if z_indexes.contains(&usize::MAX) {
124            return Err(InputError::new(input, 0, "undefined z output"));
125        }
126
127        Ok(Self {
128            wires,
129            wire_names,
130            x_initial,
131            y_initial,
132            z_indexes,
133        })
134    }
135
136    #[must_use]
137    pub fn part1(&self) -> u64 {
138        let mut z = 0;
139        let mut cache = vec![None; self.wires.len()];
140        for (i, &index) in self.z_indexes.iter().enumerate() {
141            z |= u64::from(Self::evaluate(
142                index,
143                &self.wires,
144                self.x_initial,
145                self.y_initial,
146                &mut cache,
147            )) << i;
148        }
149        z
150    }
151
152    fn evaluate(index: usize, wires: &[Wire], x: u64, y: u64, cache: &mut [Option<bool>]) -> bool {
153        if let Some(c) = cache[index] {
154            return c;
155        }
156        let v = match wires[index] {
157            Wire::X(n) => return x & (1 << n) != 0,
158            Wire::Y(n) => return y & (1 << n) != 0,
159            Wire::And(a, b) => {
160                Self::evaluate(a, wires, x, y, cache) && Self::evaluate(b, wires, x, y, cache)
161            }
162            Wire::Or(a, b) => {
163                Self::evaluate(a, wires, x, y, cache) || Self::evaluate(b, wires, x, y, cache)
164            }
165            Wire::Xor(a, b) => {
166                Self::evaluate(a, wires, x, y, cache) ^ Self::evaluate(b, wires, x, y, cache)
167            }
168        };
169        cache[index] = Some(v);
170        v
171    }
172
173    #[must_use]
174    pub fn part2(&self) -> String {
175        let mut test_cases = Vec::new();
176        for i in 0..self.z_indexes.len() - 1 {
177            test_cases.push((i, 1u64 << i, 0u64));
178            test_cases.push((i, 0u64, 1u64 << i));
179            test_cases.push((i + 1, 1u64 << i, 1u64 << i));
180            test_cases.push((i + 1, (1u64 << (i + 1)) - 1, 1u64));
181            test_cases.push((i + 1, 1u64, (1u64 << (i + 1)) - 1));
182        }
183
184        let mut wires = self.wires.clone();
185        if self.find_swaps(&test_cases, &mut wires, None).is_continue() {
186            panic!("failed to find working combination");
187        }
188
189        let mut changes = Vec::new();
190        for (i, (&wire, &orig)) in wires.iter().zip(&self.wires).enumerate() {
191            if wire != orig {
192                changes.push(self.wire_names[i]);
193            }
194        }
195        assert_eq!(changes.len(), 8, "found incorrect number of changes");
196
197        changes.sort_unstable();
198        changes.into_iter().fold(String::new(), |mut acc, name| {
199            if !acc.is_empty() {
200                acc.push(',');
201            }
202            acc.push(name[0] as char);
203            acc.push(name[1] as char);
204            acc.push(name[2] as char);
205            acc
206        })
207    }
208
209    fn find_swaps(
210        &self,
211        test_cases: &[(usize, u64, u64)],
212        wires: &mut [Wire],
213        last: Option<usize>,
214    ) -> ControlFlow<()> {
215        let mut cache = vec![None; wires.len()];
216        let mut used = vec![false; wires.len()];
217        for &(n, x, y) in test_cases {
218            if Some(n) < last {
219                // Test case has already been checked and as only gates that were not previously
220                // used are candidates for swapping, must still be correct
221                continue;
222            }
223
224            cache.fill(None);
225            let sum = x + y;
226
227            // Check non-final bits in check pattern match
228            for i in 0..n {
229                let b = Self::evaluate(self.z_indexes[i], wires, x, y, &mut cache);
230                if ((sum >> i) & 1 != 0) != b {
231                    // Non-final bit in test case incorrect, previous swap must have been incorrect
232                    return ControlFlow::Continue(());
233                }
234            }
235
236            // Store which gates were used evaluating up to the non-final bit
237            for i in 0..wires.len() {
238                used[i] = cache[i].is_some();
239            }
240
241            let b = Self::evaluate(self.z_indexes[n], wires, x, y, &mut cache);
242            if ((sum >> n) & 1 != 0) == b {
243                // Test case matches
244                continue;
245            }
246
247            // Found output bit with a wrong gate
248            if last == Some(n) {
249                // Last swapped bit still wrong, return and try next combination
250                return ControlFlow::Continue(());
251            }
252
253            // Gates which were used for the first time this bit
254            let candidates1 = cache
255                .iter()
256                .zip(&used)
257                .enumerate()
258                .filter(|&(_, (&c, &u))| c.is_some() && !u)
259                .map(|(i, _)| i)
260                .collect::<Vec<_>>();
261            // Gates which weren't used previously and only contain current bits
262            let mask = (1 << (n + 1)) - 1;
263            let candidates2 = Self::used_bits(wires)
264                .iter()
265                .zip(&used)
266                .enumerate()
267                .filter(|&(_, (&b, &u))| b != 0 && b & mask == b && !u)
268                .map(|(i, _)| i)
269                .collect::<Vec<_>>();
270
271            // Try swapping each combination of candidates
272            for &c1 in &candidates1 {
273                for &c2 in &candidates2 {
274                    if c1 == c2 {
275                        continue;
276                    }
277
278                    (wires[c1], wires[c2]) = (wires[c2], wires[c1]);
279
280                    // Check swap didn't create a loop
281                    if !self.loops(wires, &[c1, c2]) {
282                        // Check swap fixed this test case before recursively calling and checking
283                        // all cases from the start
284                        cache.fill(None);
285                        let b = Self::evaluate(self.z_indexes[n], wires, x, y, &mut cache);
286                        if ((sum >> n) & 1 != 0) == b
287                            && self.find_swaps(test_cases, wires, Some(n)).is_break()
288                        {
289                            // This and future swaps work, found working combination
290                            return ControlFlow::Break(());
291                        }
292                    }
293
294                    // Failed, swap back and try next combination
295                    (wires[c1], wires[c2]) = (wires[c2], wires[c1]);
296                }
297            }
298
299            // No combinations worked, previous swap must be wrong
300            return ControlFlow::Continue(());
301        }
302
303        ControlFlow::Break(())
304    }
305
306    fn used_bits(wires: &[Wire]) -> Vec<u64> {
307        fn eval(index: usize, wires: &[Wire], used_bits: &mut [u64]) -> u64 {
308            if used_bits[index] != 0 {
309                return used_bits[index];
310            }
311            let v = match wires[index] {
312                Wire::X(n) => return 1 << n,
313                Wire::Y(n) => return 1 << n,
314                Wire::And(a, b) | Wire::Or(a, b) | Wire::Xor(a, b) => {
315                    eval(a, wires, used_bits) | eval(b, wires, used_bits)
316                }
317            };
318            used_bits[index] = v;
319            v
320        }
321
322        let mut used = vec![0; wires.len()];
323        for i in 0..wires.len() {
324            eval(i, wires, &mut used);
325        }
326        used
327    }
328
329    fn loops(&self, wires: &[Wire], to_check: &[usize]) -> bool {
330        #[derive(Copy, Clone, PartialEq)]
331        enum State {
332            Unvisited,
333            InStack,
334            Visited,
335        }
336
337        fn eval(index: usize, wires: &[Wire], states: &mut [State]) -> bool {
338            if states[index] != State::Unvisited {
339                return states[index] == State::InStack;
340            }
341            match wires[index] {
342                Wire::X(_) | Wire::Y(_) => {}
343                Wire::And(a, b) | Wire::Or(a, b) | Wire::Xor(a, b) => {
344                    states[index] = State::InStack;
345                    if eval(a, wires, states) || eval(b, wires, states) {
346                        return true;
347                    }
348                    states[index] = State::Visited;
349                }
350            }
351            false
352        }
353
354        let mut states = vec![State::Unvisited; wires.len()];
355        to_check.iter().any(|&i| eval(i, wires, &mut states))
356    }
357}
358
359examples!(Day24 -> (u64, &'static str) []);
year2024/day24.rs

year2024/
day24.rs
