Advent of Code 2024 Day 24

Day 24: Crossed Wires

https://adventofcode.com/2024/day/24

Some device is acting up and you need to fix it (but thankfully, it’s not a printer!). If works on a bunch of boolean logic.

An example input looks like this:

x00: 1
x01: 1
x02: 1
y00: 0
y01: 1
y02: 0

x00 AND y00 -> z00
x01 XOR y01 -> z01
x02 OR y02 -> z02

The top part is a bunch of wires with the boolean value they currently hold. eg. the wire called x00 is set to true, and y02 is set to false.

The bottom part describes the logic gates in the device.

Parsing

I could throw everything in a string and work with those, I could, but I didn’t.

#[derive(PartialEq, Eq, Clone, Copy)]
enum Operator {
    And,
    Or,
    Xor,
}

#[derive(Clone, Copy)]
struct Operation<'a> {
    lhs: &'a str,
    op: Operator,
    rhs: &'a str,
}

fn parse(input: &str) -> (HashMap<&str, bool>, HashMap<&str, Operation>) {
    let (top, bottom) = input.split_once("\n\n").unwrap();
    let mut wires = HashMap::new();
    for line in top.lines() {
        let (left, right) = line.split_once(": ").unwrap();
        wires.insert(left, right == "1");
    }
    let mut operations = HashMap::new();
    for line in bottom.lines() {
        let (left, right) = line.split_once(" -> ").unwrap();
        let (lhs, op, rhs) = left.split_whitespace().collect_tuple().unwrap();
        let op = match op {
            "AND" => Operator::And,
            "OR" => Operator::Or,
            "XOR" => Operator::Xor,
            _ => panic!("at the disco"),
        };
        operations.insert(right, Operation { lhs, op, rhs });
    }
    (wires, operations)
}

Part 1

After the logic gates do their thing completely (there are no loops).

The system is trying to procude a number by combining the bits on all wires starting with a z. z00 is the least significant bit.

The question asks what that number is in decimal.

Helpers

Adding a method to any Operator that actually does that bit operation.

impl Operator {
    fn execute(&self, a: bool, b: bool) -> bool {
        match self {
            Self::And => a & b,
            Self::Or => a | b,
            Self::Xor => a ^ b,
        }
    }
}

Now the actually interesting bit, the functon that recursively calculates the boolean on a given wire given the starting booleans on the wires and a map of all logic operations.

fn calc<'a>(
    wires: &mut HashMap<&'a str, bool>,
    ops: &HashMap<&'a str, Operation<'a>>,
    wire: &'a str,
) -> bool {
    if let Some(&on) = wires.get(wire) {
        return on;
    }
    let Operation { lhs, op, rhs } = &ops[wire];
    let lhs = calc(wires, ops, lhs);
    let rhs = calc(wires, ops, rhs);
    let res = op.execute(lhs, rhs);
    wires.insert(wire, res);
    res
}

Code

Gather all wires starting with a z
Order them in reverse
Calculate their boolean value
Concatenate them
Turn the resulting binary number into decimal

fn part_1(input: &str) -> u64 {
    let (mut wires, ops) = parse(input);
    ops.keys()
        // get all wires that start with z and sort them
        .filter(|name| name.starts_with('z'))
        .sorted()
        // least significant bit is first, reverse
        .rev()
        // calculate the bits those wires output
        .map(|name| calc(&mut wires, &ops, name))
        // concatenate the bits (with boolean math!)
        .fold(0, |acc, bit| acc << 1 | bit as u64)
}

Part 2

You know that first part of the input you parsed? Throw it away, it’s useless in part2!

The system is trying to add 2 binary numbers.

the bits on wires starting with x form a binary number.
the bits on wires starting with y form a binary number.
Those 2 number are (binary) added together and the resulting bits are output to wires starting with z

Again, 00 is the least significant bit, then 01, then 02, …

It’s wrong because 4 pairs of wires are swapped.

The question asks to print all wires that are wrong, sort them, and put a comma between them.

The code I used is Hyperneutrino’s code translated to Rust. For an explanation of the logic it performs please watch her video.

Basically, it starts a counter at 0 and checks how high it can go before a z wire with that number is wrong. It then bruteforce swaps wires and performs that check again for each swap. If the counter gets higher, it keeps that swap.

The interesting parts are the functions that check if a z wire has the correct output boolean.

fn make_wire(c: char, n: i32) -> String {
    format!("{}{:02}", c, n)
}

fn is_ok_z(ops: &HashMap<&str, Operation>, wire: &str, num: i32) -> bool {
    if let Some(Operation { lhs, op, rhs }) = ops.get(wire) {
        if *op != Operator::Xor {
            return false;
        }
        if num == 0 {
            let mut operands = [*lhs, *rhs];
            operands.sort();
            return operands == ["x00", "y00"];
        }
        return (is_ok_xor(ops, lhs, num) && is_ok_carry_bit(ops, rhs, num))
            || (is_ok_xor(ops, rhs, num) && is_ok_carry_bit(ops, lhs, num));
    }
    false
}

fn is_ok_xor(ops: &HashMap<&str, Operation>, wire: &str, num: i32) -> bool {
    if let Some(Operation { lhs, op, rhs }) = ops.get(wire) {
        if *op != Operator::Xor {
            return false;
        }
        let mut operands = [*lhs, *rhs];
        operands.sort();
        return operands == [make_wire('x', num), make_wire('y', num)];
    }
    false
}

fn is_ok_carry_bit(ops: &HashMap<&str, Operation>, wire: &str, num: i32) -> bool {
    if let Some(Operation { lhs, op, rhs }) = ops.get(wire) {
        if num == 1 {
            if *op != Operator::And {
                return false;
            }
            let mut operands = [*lhs, *rhs];
            operands.sort();
            return operands == ["x00", "y00"];
        }
        if *op != Operator::Or {
            return false;
        }
        return (is_ok_direct_carry(ops, lhs, num - 1) && is_ok_recarry(ops, rhs, num - 1))
            || (is_ok_direct_carry(ops, rhs, num - 1) && is_ok_recarry(ops, lhs, num - 1));
    }
    false
}

fn is_ok_direct_carry(ops: &HashMap<&str, Operation>, wire: &str, num: i32) -> bool {
    if let Some(Operation { lhs, op, rhs }) = ops.get(wire) {
        if *op != Operator::And {
            return false;
        }
        let mut operands = [*lhs, *rhs];
        operands.sort();
        return operands == [make_wire('x', num), make_wire('y', num)];
    }
    false
}

fn is_ok_recarry(ops: &HashMap<&str, Operation>, wire: &str, num: i32) -> bool {
    if let Some(Operation { lhs, op, rhs }) = ops.get(wire) {
        if *op != Operator::And {
            return false;
        }
        return (is_ok_xor(ops, lhs, num) && is_ok_carry_bit(ops, rhs, num))
            || (is_ok_xor(ops, rhs, num) && is_ok_carry_bit(ops, lhs, num));
    }
    false
}

fn progress(ops: &HashMap<&str, Operation>) -> i32 {
    (0..)
        .find(|&idx| !is_ok_z(ops, &make_wire('z', idx), idx))
        .unwrap()
}

fn swap_wires<'a>(map: &mut HashMap<&'a str, Operation<'a>>, a: &'a str, b: &'a str) {
    let temp = map[a];
    map.insert(a, map[b]);
    map.insert(b, temp);
}

fn part_2(input: &str) -> String {
    let (_, mut ops) = parse(input);
    let mut swaps = Vec::new();

    let wires: Vec<&str> = ops.keys().copied().collect();
    for _ in 0..4 {
        let baseline = progress(&ops);
        for (a, b) in wires.iter().tuple_combinations() {
            swap_wires(&mut ops, a, b);
            if progress(&ops) > baseline {
                swaps.push([*a, *b]);
                break;
            }
            swap_wires(&mut ops, a, b);
        }
    }

    swaps
        .into_iter()
        .flatten()
        .sorted()
        .intersperse(",")
        .collect()
}

Final code

1
use itertools::Itertools;
2
use std::collections::HashMap;
3

4
#[derive(PartialEq, Eq, Clone, Copy)]
5
enum Operator {
6
    And,
7
    Or,
8
    Xor,
9
}
10

11
impl Operator {
12
    fn execute(&self, a: bool, b: bool) -> bool {
13
        match self {
14
            Self::And => a & b,
15
            Self::Or => a | b,
16
            Self::Xor => a ^ b,
17
        }
18
    }
19
}
20

21
#[derive(Clone, Copy)]
22
struct Operation<'a> {
23
    lhs: &'a str,
24
    op: Operator,
25
    rhs: &'a str,
26
}
27

28
fn parse(input: &str) -> (HashMap<&str, bool>, HashMap<&str, Operation>) {
29
    let (top, bottom) = input.split_once("\n\n").unwrap();
30
    let mut wires = HashMap::new();
31
    for line in top.lines() {
32
        let (left, right) = line.split_once(": ").unwrap();
33
        wires.insert(left, right == "1");
34
    }
35
    let mut operations = HashMap::new();
36
    for line in bottom.lines() {
37
        let (left, right) = line.split_once(" -> ").unwrap();
38
        let (lhs, op, rhs) = left.split_whitespace().collect_tuple().unwrap();
39
        let op = match op {
40
            "AND" => Operator::And,
41
            "OR" => Operator::Or,
42
            "XOR" => Operator::Xor,
43
            _ => panic!("at the disco"),
44
        };
45
        operations.insert(right, Operation { lhs, op, rhs });
46
    }
47
    (wires, operations)
48
}
49

50
fn calc<'a>(
51
    wires: &mut HashMap<&'a str, bool>,
52
    ops: &HashMap<&'a str, Operation<'a>>,
53
    wire: &'a str,
54
) -> bool {
55
    if let Some(&on) = wires.get(wire) {
56
        return on;
57
    }
58
    let Operation { lhs, op, rhs } = &ops[wire];
59
    let lhs = calc(wires, ops, lhs);
60
    let rhs = calc(wires, ops, rhs);
61
    let res = op.execute(lhs, rhs);
62
    wires.insert(wire, res);
63
    res
64
}
65

66
fn part_1(input: &str) -> u64 {
67
    let (mut wires, ops) = parse(input);
68
    ops.keys()
69
        // get all wires that start with z and sort them
70
        .filter(|name| name.starts_with('z'))
71
        .sorted()
72
        // least significant bit is first, reverse
73
        .rev()
74
        // calculate the bits those wires output
75
        .map(|name| calc(&mut wires, &ops, name))
76
        // concatenate the bits (with boolean math!)
77
        .fold(0, |acc, bit| acc << 1 | bit as u64)
78
}
79

80
fn make_wire(c: char, n: i32) -> String {
81
    format!("{}{:02}", c, n)
82
}
83

84
fn is_ok_z(ops: &HashMap<&str, Operation>, wire: &str, num: i32) -> bool {
85
    if let Some(Operation { lhs, op, rhs }) = ops.get(wire) {
86
        if *op != Operator::Xor {
87
            return false;
88
        }
89
        if num == 0 {
90
            let mut operands = [*lhs, *rhs];
91
            operands.sort();
92
            return operands == ["x00", "y00"];
93
        }
94
        return (is_ok_xor(ops, lhs, num) && is_ok_carry_bit(ops, rhs, num))
95
            || (is_ok_xor(ops, rhs, num) && is_ok_carry_bit(ops, lhs, num));
96
    }
97
    false
98
}
99

100
fn is_ok_xor(ops: &HashMap<&str, Operation>, wire: &str, num: i32) -> bool {
101
    if let Some(Operation { lhs, op, rhs }) = ops.get(wire) {
102
        if *op != Operator::Xor {
103
            return false;
104
        }
105
        let mut operands = [*lhs, *rhs];
106
        operands.sort();
107
        return operands == [make_wire('x', num), make_wire('y', num)];
108
    }
109
    false
110
}
111

112
fn is_ok_carry_bit(ops: &HashMap<&str, Operation>, wire: &str, num: i32) -> bool {
113
    if let Some(Operation { lhs, op, rhs }) = ops.get(wire) {
114
        if num == 1 {
115
            if *op != Operator::And {
116
                return false;
117
            }
118
            let mut operands = [*lhs, *rhs];
119
            operands.sort();
120
            return operands == ["x00", "y00"];
121
        }
122
        if *op != Operator::Or {
123
            return false;
124
        }
125
        return (is_ok_direct_carry(ops, lhs, num - 1) && is_ok_recarry(ops, rhs, num - 1))
126
            || (is_ok_direct_carry(ops, rhs, num - 1) && is_ok_recarry(ops, lhs, num - 1));
127
    }
128
    false
129
}
130

131
fn is_ok_direct_carry(ops: &HashMap<&str, Operation>, wire: &str, num: i32) -> bool {
132
    if let Some(Operation { lhs, op, rhs }) = ops.get(wire) {
133
        if *op != Operator::And {
134
            return false;
135
        }
136
        let mut operands = [*lhs, *rhs];
137
        operands.sort();
138
        return operands == [make_wire('x', num), make_wire('y', num)];
139
    }
140
    false
141
}
142

143
fn is_ok_recarry(ops: &HashMap<&str, Operation>, wire: &str, num: i32) -> bool {
144
    if let Some(Operation { lhs, op, rhs }) = ops.get(wire) {
145
        if *op != Operator::And {
146
            return false;
147
        }
148
        return (is_ok_xor(ops, lhs, num) && is_ok_carry_bit(ops, rhs, num))
149
            || (is_ok_xor(ops, rhs, num) && is_ok_carry_bit(ops, lhs, num));
150
    }
151
    false
152
}
153

154
fn progress(ops: &HashMap<&str, Operation>) -> i32 {
155
    (0..)
156
        .find(|&idx| !is_ok_z(ops, &make_wire('z', idx), idx))
157
        .unwrap()
158
}
159

160
fn swap_wires<'a>(map: &mut HashMap<&'a str, Operation<'a>>, a: &'a str, b: &'a str) {
161
    let temp = map[a];
162
    map.insert(a, map[b]);
163
    map.insert(b, temp);
164
}
165

166
fn part_2(input: &str) -> String {
167
    let (_, mut ops) = parse(input);
168
    let mut swaps = Vec::new();
169

170
    let wires: Vec<&str> = ops.keys().copied().collect();
171
    for _ in 0..4 {
172
        let baseline = progress(&ops);
173
        for (a, b) in wires.iter().tuple_combinations() {
174
            swap_wires(&mut ops, a, b);
175
            if progress(&ops) > baseline {
176
                swaps.push([*a, *b]);
177
                break;
178
            }
179
            swap_wires(&mut ops, a, b);
180
        }
181
    }
182

183
    swaps
184
        .into_iter()
185
        .flatten()
186
        .sorted()
187
        .intersperse(",")
188
        .collect()
189
}

Date

Tagged

Part of series

Older post

Newer post