Advent of Code 2024, Day 24

Part 1 was easy: I computed the outputs of the wires on demand and then summed up the powers of two.

Part 2 was hard. I grepped for the first few wires and drew them up on paper. I noticed the following full-adder design:

input_xor[n] = x[n] ^ y[n]
input_and[n] = x[n] & y[n]

z[n]            = input_xor[n] ^ carry[n-1]
intermediate[n] = input_xor[n] & carry[n-1]
carry[n]        = input_and[n] | intermediate[n]

I then wrote some code with a lot of code duplication to populate and print dictionaries based on these assumptions. I noticed that 3 of the populated z values were no z wires at all; they were the first 3 (of the 4) swap pairs, and the easiest to find. For the last pair, I noticed that some of the intermediate and carry values were missing in my output. It took me some grepping and drawing and thinking to trace back which wire should go in which place in the problematic area. Only after finding and submitting the last pair did I notice that they were the input_xor and input_and values for the same n.

The code I give below for part 2 is an attempt to automate (and somewhat generalize) what I did semi-automatically; I think it should work for other inputs as well, assuming that the swaps are either swaps between a z wire and some other wire, or between input_xor and input_and wires for the same n, and all of them for different n that are not right at the border.

Part 1 (0.02 seconds)

import sys

wires = {}
with open(sys.argv[1]) as f:
    for line in f:
        line = line.strip()
        if ":" in line:
            k, digit = line.split()
            k, digit = k[:-1], int(digit)
            wires[k] = digit
        elif ">" in line:
            a, op, b, _, c = line.split()
            wires[c] = (a, op, b)

def fixval(k, wires):
    if type(wires[k]) is int: return
    a, op, b = wires[k]
    fixval(a, wires)
    fixval(b, wires)
    if op == "AND":
        wires[k] = wires[a] & wires[b]
    elif op == "OR":
        wires[k] = wires[a] | wires[b]
    elif op == "XOR":
        wires[k] = wires[a] ^ wires[b]

zs = []
for k in wires:
    if k[0] != "z": continue
    fixval(k, wires)
    zs.append((k, wires[k]))

print(sum(digit << i for i, (_, digit) in enumerate(sorted(zs))))

Part 2 (0.03 seconds)

import sys

wires = {}
with open(sys.argv[1]) as f:
    for line in f:
        line = line.strip()
        if ":" in line:
            k, digit = line.split()
            k, digit = k[:-1], int(digit)
            wires[k] = digit
        elif ">" in line:
            a, op, b, _, c = line.split()
            wires[c] = (a, op, b)

x, y = {}, {}
for k in wires:
    if k[0] == "x":
        n = int(k[1:])
        x[n] = k
    elif k[0] == "y":
        n = int(k[1:])
        y[n] = k

ns = sorted(x.keys())
assert ns == sorted(y.keys())

xor_and_pairs = {}
for k1, v1 in wires.items():
    if type(v1) is int: continue
    a1, op1, b1 = v1
    if op1 != "XOR": continue
    for k2, v2 in wires.items():
        if type(v2) is int: continue
        a2, op2, b2 = v2
        if op2 != "AND": continue
        if (a1, b1) not in ((a2, b2), (b2, a2)): continue
        xor_and_pairs[tuple(sorted((a1, b1)))] = (k1, k2)

input_xor, input_and = {}, {}
for n in ns:
    input_xor[n], input_and[n] = xor_and_pairs.pop((x[n], y[n]))

swaps = []
def swap(a, b):
    swaps.extend((a, b))
    wires[a], wires[b] = wires[b], wires[a]
    for d in (input_xor, input_and, z, intermediate, carry):
        ka, kb = None, None
        for k, v in d.items():
            if v == a: ka = k
            if v == b: kb = k
        if ka != None: d[ka] = b
        if kb != None: d[kb] = a

z, intermediate, carry = {}, {}, {}
z[0], carry[0] = input_xor[0], input_and[0]
for n in ns:
    if n == 0: continue
    if all(input_xor[n] not in t for t in xor_and_pairs):
        swap(input_xor[n], input_and[n])
    for ((a, b), (xor_res, and_res)) in xor_and_pairs.items():
        if input_xor[n] not in (a, b): continue
        xor_and_pairs.pop((a, b))
        if input_xor[n] == b:
            a, b = b, a
        z[n] = xor_res
        intermediate[n] = and_res
        carry[n-1] = b
        z_str = "z"+str(n).zfill(2)
        if z[n] != z_str:
            swap(z[n], z_str)
        break
    else: assert False
assert not xor_and_pairs

for n in ns:
    if n in carry and n in intermediate:
        a, b = input_and[n], intermediate[n]
        assert wires[carry[n]] in ((a, "OR", b), (b, "OR", a))

print(",".join(sorted(swaps)))

2024-12-24