Advent of Code 2024 - Day 24: Crossed Wires

:: programming, python, puzzle

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
from advent import parse, atoms

wires, exprs = parse(24, lambda s: [ atoms(line) for line in str.split(s,'\n') ], sep='\n\n')

def part1():
    d = {}

    for wire, value in wires:
        d[wire] = value

    for (w1, op, w2, _, out) in exprs:
        d[out] = (op, w1, w2)

    def evaluate(expr):
        match expr:
            case int(value): return value
            case str(key):   return evaluate(d[key])
            case (op, w1, w2):
                a = evaluate(d[w1])
                b = evaluate(d[w2])
                match op:
                    case 'AND': return a & b
                    case 'OR':  return a | b
                    case 'XOR': return a ^ b

    return sum((evaluate(key) << i) for i, key in enumerate(sorted([ key for key in d if key[0] == 'z' ])))

# ---------------------------------------------------------------------------------------------

assert part1() == 56729630917616

Part 1

For part 1, we’re given two sets of input. The first is a list of binary values for x and y:

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

The second is a list of logic expressions:

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

We parse them as follows:

1
 
wires, exprs = parse(24, lambda s: [ atoms(line) for line in str.split(s,'\n') ], sep='\n\n')

We’ll store this information in a dict either as a specific value, or as a 3-tuple containing an operation in { AND, OR, XOR }, and two wires:

1
2
3
4
5
6
7
 
d = {}

for wire, value in wires:
    d[wire] = value

for (w1, op, w2, _, out) in exprs:
    d[out] = (op, w1, w2)

We’ll use a helper function to evaluate the list of expressions to set the values for the z wires:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
 
def evaluate(expr):
    match expr:
        case int(value): return value
        case str(key):   return evaluate(d[key])
        case (op, w1, w2):
            a = evaluate(d[w1])
            b = evaluate(d[w2])
            match op:
                case 'AND': return a & b
                case 'OR':  return a | b
                case 'XOR': return a ^ b

With the above, we can compute the resulting z value via:

1
 
return sum((evaluate(key) << i) for i, key in enumerate(sorted([ key for key in d if key[0] == 'z' ])))

I felt part 1 was straightforward, and Python made the implementation easy.

Part 2

I struggled with part 2 for a while. I knew the expressions should create a binary adder, and as explained, some of the expressions were incorrect, but after experimenting with a few approaches “long enough”, I finally gave in and looked for hints. The best help I could find came from lscddit on reddit. They use a few simple rules to determine the validity of gates, and add invalid gates to a set. It’s the most concise solution I found in my brief search :) I lacked the knowledge about ripple carry adders to find the appropriate patterns.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
def part2():
    operations = [ (key, val) for key, val in d.items() if isinstance(val, tuple) ]
    wrong      = set()

    for out, (op, w1, w2) in operations:
        if out[0] == 'z' and op != 'XOR' and out != 'z45':
            wrong.add(out)

        if op == 'XOR' and \
           out[0] not in ('x', 'y', 'z') and \
           w1[0] not in ('x', 'y', 'z') and \
           w2[0] not in ('x', 'y', 'z'):
            wrong.add(out)

        if op == 'AND' and 'x00' not in (w1, w2):
            for out2, (op2, w1_2, w2_2) in operations:
                if (out == w1_2 or out == w2_2) and op2 != 'OR':
                    wrong.add(out)

        if op == 'XOR':
            for out2, (op2, w1_2, w2_2) in operations:
                if (out == w1_2 or out == w2_2) and op2 == 'OR':
                    wrong.add(out)

    return ",".join(sorted(wrong))

While it can be gratifying to persevere with these puzzles, I’ve learned that there will probably be one puzzle where the payoff isn’t worth the effort for me, and this year it was Day 24 :)