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 (except for inputs
46//!    `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 gates, except for final carry which must output to
49//!    `z45`.
50//!
51//! We only need to find swapped outputs (not fix them) so the result is the labels of gates
52//! that break the rules in alphabetical order.
53use std::collections::VecDeque;
54
55use crate::util::hash::*;
56use crate::util::iter::*;
57use crate::util::parse::*;
58
59type Input<'a> = (&'a str, Vec<[&'a str; 5]>);
60
61pub fn parse(input: &str) -> Input<'_> {
62    let (prefix, suffix) = input.split_once("\n\n").unwrap();
63    let gates = suffix.split_ascii_whitespace().chunk::<5>().collect();
64    (prefix, gates)
65}
66
67pub fn part1(input: &Input<'_>) -> u64 {
68    let (prefix, gates) = input;
69
70    // Using an array to store already computed values is much faster than a `HashMap`.
71    let mut todo: VecDeque<_> = gates.iter().copied().collect();
72    let mut cache = vec![u8::MAX; 1 << 15];
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 & 0x1f) << 10) + ((b[1] as usize & 0x1f) << 5) + (b[2] as usize & 0x1f)
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    (to_index("z00")..to_index("z46"))
108        .rev()
109        .filter(|&i| cache[i] != u8::MAX)
110        .fold(0, |result, i| (result << 1) | (cache[i] as u64))
111}
112
113pub fn part2(input: &Input<'_>) -> String {
114    let (_, gates) = input;
115
116    let mut output = FastSet::new();
117    let mut swapped = FastSet::new();
118
119    // Track the kind of gate that each wire label outputs to.
120    for &[left, kind, right, _, _] in gates {
121        output.insert((left, kind));
122        output.insert((right, kind));
123    }
124
125    for &[left, kind, right, _, to] in gates {
126        match kind {
127            "AND" => {
128                // Check that all AND gates point to an OR, except for first AND.
129                if left != "x00" && right != "x00" && !output.contains(&(to, "OR")) {
130                    swapped.insert(to);
131                }
132            }
133            "OR" => {
134                // Check that only XOR gates point to output, except for last carry which is OR.
135                if to.starts_with('z') && to != "z45" {
136                    swapped.insert(to);
137                }
138                // OR can never point to OR.
139                if output.contains(&(to, "OR")) {
140                    swapped.insert(to);
141                }
142            }
143            "XOR" => {
144                if left.starts_with('x') || right.starts_with('x') {
145                    // Check that first level XOR points to second level XOR, except for first XOR.
146                    if left != "x00" && right != "x00" && !output.contains(&(to, "XOR")) {
147                        swapped.insert(to);
148                    }
149                } else if !to.starts_with('z') {
150                    // Second level XOR must point to output.
151                    swapped.insert(to);
152                }
153            }
154            _ => unreachable!(),
155        }
156    }
157
158    let mut result: Vec<_> = swapped.into_iter().collect();
159    result.sort_unstable();
160    result.join(",")
161}
aoc/year2024/day24.rs

aoc/year2024/
day24.rs
