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 gates, 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 break 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
73    // Convert each character to a 5 bit number from 0..31
74    // then each group of 3 to a 15 bit index from 0..32768.
75    let to_index = |s: &str| {
76        let b = s.as_bytes();
77        ((b[0] as usize & 31) << 10) + ((b[1] as usize & 31) << 5) + (b[2] as usize & 31)
78    };
79
80    // Add input signals to cache.
81    for line in prefix.lines() {
82        let prefix = &line[..3];
83        let suffix = &line[5..];
84        cache[to_index(prefix)] = suffix.unsigned();
85    }
86
87    // If both inputs are available then add gate output to cache
88    // otherwise push back to end of queue for reprocessing later.
89    while let Some(gate @ [left, kind, right, _, to]) = todo.pop_front() {
90        let left = cache[to_index(left)];
91        let right = cache[to_index(right)];
92
93        if left == u8::MAX || right == u8::MAX {
94            todo.push_back(gate);
95        } else {
96            cache[to_index(to)] = match kind {
97                "AND" => left & right,
98                "OR" => left | right,
99                "XOR" => left ^ right,
100                _ => unreachable!(),
101            }
102        }
103    }
104
105    // Output 46 bit result.
106    (to_index("z00")..to_index("z46"))
107        .rev()
108        .filter(|&i| cache[i] != u8::MAX)
109        .fold(0, |result, i| (result << 1) | (cache[i] as u64))
110}
111
112pub fn part2(input: &Input<'_>) -> String {
113    let (_, gates) = input;
114
115    let mut output = FastSet::new();
116    let mut swapped = FastSet::new();
117
118    // Track the kind of gate that each wire label outputs to.
119    for &[left, kind, right, _, _] in gates {
120        output.insert((left, kind));
121        output.insert((right, kind));
122    }
123
124    for &[left, kind, right, _, to] in gates {
125        match kind {
126            "AND" => {
127                // Check that all AND gates point to an OR, except for first AND.
128                if left != "x00" && right != "x00" && !output.contains(&(to, "OR")) {
129                    swapped.insert(to);
130                }
131            }
132            "OR" => {
133                // Check that only XOR gates point to output, except for last carry which is OR.
134                if to.starts_with('z') && to != "z45" {
135                    swapped.insert(to);
136                }
137                // OR can never point to OR.
138                if output.contains(&(to, "OR")) {
139                    swapped.insert(to);
140                }
141            }
142            "XOR" => {
143                if left.starts_with('x') || right.starts_with('x') {
144                    // Check that first level XOR points to second level XOR, except for first XOR.
145                    if left != "x00" && right != "x00" && !output.contains(&(to, "XOR")) {
146                        swapped.insert(to);
147                    }
148                } else if !to.starts_with('z') {
149                    // Second level XOR must point to output.
150                    swapped.insert(to);
151                }
152            }
153            _ => unreachable!(),
154        }
155    }
156
157    let mut result: Vec<_> = swapped.into_iter().collect();
158    result.sort_unstable();
159    result.join(",")
160}
aoc/year2024/day24.rs

aoc/year2024/
day24.rs
