aoc/year2024/
day24.rs

1//! # Crossed Wires
2//!
3//! Part one is a straightforward simulation of the gates. Part two asks us to fix a broken
4//! [ripple carry adder](https://en.wikipedia.org/wiki/Adder_(electronics)).
5//!
6//! The structure of the adder is:
7//!
8//! * Half adder for bits `x00` and `y00`. Outputs sum to `z00` and carry to `z01`.
9//! * Full adder for bits `x01..x44` and `y01..y44`. Outputs carry to next bit in the chain
10//!   "rippling" up to final bit.
11//! * `z45` is the carry output from `x44` and `y44`.
12//!
13//! Implemented in logic gates this looks like:
14//!
15//! ```none
16//!    Half Adder     Full Adder
17//!    ┌───┐ ┌───┐    ┌───┐ ┌───┐
18//!    |x00| |y00|    |x01| |y01|
19//!    └───┘ └───┘    └───┘ └───┘
20//!     | | ┌─┘ |      | | ┌─┘ |
21//!     | └───┐ |      | └───┐ |
22//!     | ┌-┘ | |      | ┌-┘ | |
23//!    ┌───┐ ┌───┐    ┌───┐ ┌───┐
24//!    |XOR| |AND|    |XOR| |AND|
25//!    └───┘ └───┘    └───┘ └───┘
26//!      |     |    ┌───┴┐     |
27//!      |     └──┬────┐ |     |
28//!      |   Carry| | ┌───┐    |
29//!      |    out | | |AND|    |
30//!      |        | | └───┘    |
31//!      |        | |   └────┐ |
32//!      |        | └────┐   | |
33//!      |        └────┐ |   | |
34//!      |            ┌───┐ ┌───┐
35//!      |            |XOR| |OR |                                  Carry
36//!      |            └───┘ └───┘                                   out
37//!      |              |     |                                      |
38//!    ┌───┐          ┌───┐   |                                    ┌───┐
39//!    |z00|          |z01| Carry    ...repeat for z01 to z44...   |z45|
40//!    └───┘          └───┘  out                                   └───┘
41//! ```
42//!
43//! Then we can deduce some rules for the output of each gate type:
44//!
45//! 1. **XOR** If inputs are `x` and `y` then output must be another XOR gate
46//!    (except for inputs `x00` and `y00`) otherwise output must be `z`.
47//! 2. **AND** Output must be an OR gate (except for inputs `x00` and `y00`).
48//! 3. **OR** Output must be both AND and XOR gate, except for final carry
49//!    which must output to `z45`.
50//!
51//! We only need to find swapped outputs (not fix them) so the result is the labels of gates
52//! that breaks the rules in alphabetical order.
53use crate::util::hash::*;
54use crate::util::iter::*;
55use crate::util::parse::*;
56use std::collections::VecDeque;
57
58type Input<'a> = (&'a str, Vec<[&'a str; 5]>);
59
60pub fn parse(input: &str) -> Input<'_> {
61    let (prefix, suffix) = input.split_once("\n\n").unwrap();
62    let gates = suffix.split_ascii_whitespace().chunk::<5>().collect();
63    (prefix, gates)
64}
65
66pub fn part1(input: &Input<'_>) -> u64 {
67    let (prefix, gates) = input;
68
69    // Using an array to store already computed values is much faster than a `HashMap`.
70    let mut todo: VecDeque<_> = gates.iter().copied().collect();
71    let mut cache = vec![u8::MAX; 1 << 15];
72    let mut result = 0;
73
74    // Convert each character to a 5 bit number from 0..31
75    // then each group of 3 to a 15 bit index from 0..32768.
76    let to_index = |s: &str| {
77        let b = s.as_bytes();
78        ((b[0] as usize & 31) << 10) + ((b[1] as usize & 31) << 5) + (b[2] as usize & 31)
79    };
80
81    // Add input signals to cache.
82    for line in prefix.lines() {
83        let prefix = &line[..3];
84        let suffix = &line[5..];
85        cache[to_index(prefix)] = suffix.unsigned();
86    }
87
88    // If both inputs are available then add gate output to cache
89    // otherwise push back to end of queue for reprocessing later.
90    while let Some(gate @ [left, kind, right, _, to]) = todo.pop_front() {
91        let left = cache[to_index(left)];
92        let right = cache[to_index(right)];
93
94        if left == u8::MAX || right == u8::MAX {
95            todo.push_back(gate);
96        } else {
97            cache[to_index(to)] = match kind {
98                "AND" => left & right,
99                "OR" => left | right,
100                "XOR" => left ^ right,
101                _ => unreachable!(),
102            }
103        }
104    }
105
106    // Output 46 bit result.
107    for i in (to_index("z00")..to_index("z46")).rev() {
108        if cache[i] != u8::MAX {
109            result = (result << 1) | (cache[i] as u64);
110        }
111    }
112
113    result
114}
115
116pub fn part2(input: &Input<'_>) -> String {
117    let (_, gates) = input;
118
119    let mut output = FastSet::new();
120    let mut swapped = FastSet::new();
121
122    // Track the kind of gate that each wire label outputs to.
123    for &[left, kind, right, _, _] in gates {
124        output.insert((left, kind));
125        output.insert((right, kind));
126    }
127
128    for &[left, kind, right, _, to] in gates {
129        match kind {
130            "AND" => {
131                // Check that all AND gates point to an OR, except for first AND.
132                if left != "x00" && right != "x00" && !output.contains(&(to, "OR")) {
133                    swapped.insert(to);
134                }
135            }
136            "OR" => {
137                // Check that only XOR gates point to output, except for last carry which is OR.
138                if to.starts_with('z') && to != "z45" {
139                    swapped.insert(to);
140                }
141                // OR can never point to OR.
142                if output.contains(&(to, "OR")) {
143                    swapped.insert(to);
144                }
145            }
146            "XOR" => {
147                if left.starts_with('x') || right.starts_with('x') {
148                    // Check that first level XOR points to second level XOR, except for first XOR.
149                    if left != "x00" && right != "x00" && !output.contains(&(to, "XOR")) {
150                        swapped.insert(to);
151                    }
152                } else {
153                    // Second level XOR must point to output.
154                    if !to.starts_with('z') {
155                        swapped.insert(to);
156                    }
157                }
158            }
159            _ => unreachable!(),
160        }
161    }
162
163    let mut result: Vec<_> = swapped.into_iter().collect();
164    result.sort_unstable();
165    result.join(",")
166}
aoc/year2024/day24.rs

aoc/year2024/
day24.rs
