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) | u64::from(cache[i]))
111}
112
113pub fn part2(input: &Input<'_>) -> String {
114    let (_, gates) = input;
115
116    // Track the kind of gate that each wire label outputs to.
117    let output: FastSet<_> =
118        gates.iter().flat_map(|&[left, kind, right, _, _]| [(left, kind), (right, kind)]).collect();
119
120    let mut swapped: Vec<_> = gates
121        .iter()
122        .filter_map(|&[left, kind, right, _, to]| {
123            let invalid = match kind {
124                // All AND gates must point to an OR, except for first AND.
125                "AND" => left != "x00" && right != "x00" && !output.contains(&(to, "OR")),
126                // Only XOR gates can point to output, except for last carry which is OR.
127                // OR can never point to OR.
128                "OR" => (to.starts_with('z') && to != "z45") || output.contains(&(to, "OR")),
129                "XOR" => {
130                    if left.starts_with('x') || right.starts_with('x') {
131                        // First level XOR must point to second level XOR, except for first XOR.
132                        left != "x00" && right != "x00" && !output.contains(&(to, "XOR"))
133                    } else {
134                        // Second level XOR must point to output.
135                        !to.starts_with('z')
136                    }
137                }
138                _ => unreachable!(),
139            };
140
141            invalid.then_some(to)
142        })
143        .collect();
144
145    swapped.sort_unstable();
146    swapped.dedup();
147    swapped.join(",")
148}
aoc/year2024/day24.rs

aoc/year2024/
day24.rs
