Advent of Code

A very enjoyable but slightly painful one for day 24. This time we’re doing some circuitry, and I’ve never been good with circuits.

All the xXX and yYY are inputs, all the zZZ are outputs, all the three-letter names are wires inside the circuit.

Part 1 - circuit simulation

In part 1, we just have to simulate what happens with the circuit and determine the outputs based on the given inputs. The zZZ outputs need to be interpreted as a binary representation of an integer, wit z00 the least significant bit. So for the above circuit, we would have:

z02z01z00 is 100, so the integer value is 4. In our actual input file, we have 45 bits in the x and y wires, and 46 z outputs.

To parse the input, we first separate the two parts – inputs and circuit – then store the inputs in a dict and the circuit as a list of operations, each encoded as a tuple with operator, op1, op2, out. The first part is easily done with split, for the second part I also used a simple RegEx to get the operator and operands.

Operation = tuple[str, str, str, str]

def parse_input() -> tuple[dict[str, int], list[Operation]]:
    with open("day24", 'r') as fp:
        data = fp.read().strip()

    inputs, network = data.split('\n\n')

    # parse inputs
    inputs = [line.split(': ') for line in inputs.split('\n')]
    inputs = {key: int(v) for key, v in inputs}

    # parse network
    ops = []
    opregex = r'(.*) (XOR|OR|AND) (.*)'
    for line in network.split('\n'):
        op, out = line.split(' -> ')
        op1, operator, op2 = re.match(opregex, op).groups()
        ops.append((operator, op1, op2, out))

    return inputs, ops

Then, to simulate the circuit, we need to perform all the operations. To make things a bit easier and avoid big if/elif chains, I put the operations as lambda functions in a global dict. As we go through the operations, we store the output values in a dict.

operations = {
    'AND': lambda a, b: a & b,
    'OR': lambda a, b: a | b,
    'XOR': lambda a, b: a ^ b
}

def do_ops(inputs: dict[str, int], ops: list[tuple[Callable, str, str, str]]):
    values = inputs.copy()
    for operation, op1, op2, out in ops:
        values[out] = operations[operation](values[op1], values[op2])
    return values

If we just run that on our list op operations, it will not work, because they are not properly sorted in the input file: some operations have in their operands a value that only appears as output later in the list. So we also need to sort the operations:

def sort_ops(inputs: dict[str, int], ops: list[tuple[Callable, str, str, str]]):
    sorted_ops = []
    has_value = list(inputs.keys())
    while len(ops) > 0:
        op = ops.pop(0)
        if op[1] in has_value and op[2] in has_value:
            sorted_ops.append(op)
            has_value.append(op[3])
        else:
            ops.append(op)
    return sorted_ops

Finally for the answer we need to convert the binary values of the z wires (or any other collection of wires) into an integer. I had to fairly often get the xXX, yYY or zZZ names so I also made a helper lambda for that.

cname = lambda p, x: p+str(x).zfill(2)

def getint(values, s: str) -> int:
    vout = 0
    bit = 0
    while (vname := cname(s, bit)) in values:
        vout += values[vname] << bit
        bit += 1
        
    return vout

inputs, ops = parse_input(False)
ops = sort_ops(inputs, ops) 
values = do_ops(inputs, ops)

print(f"Part 1 answer: {getint(values, 'z')}")

Part 2 - we’ve got some rewiring to do.

In part 2, we learn what the circuit is supposed to do: add two binary numbers. But it doesn’t work right now: some of the operation outputs have been swapped. We need to swap four pairs of operation outputs so that the circuit does what it’s supposed to do.

There are several possible approaches here, and I had a hard time deciding which one to use. The first one is to brute-force all possible swaps until we get a correct answer on a bunch of test input/output values. I wanted to actually look into the circuit. I played a bit with the list of operations to try to map what was going on, and determined the kind of “adder” that it was. So here’s how it’s supposed to work:

Starting with a single bit, the result of x00 + y00 will be a two-bit number, such that z00 = x00 ^ y00 and the “carry” is c00 = x00 & y00. So for bit 1, we now have to add x01 + y01 + c00. Do do that, we need a few steps: first we XOR ^01 = x01 ^ y01, then we XOR again to get the output z01 = ^01 ^ c00. To get the new carry, we need to perform (x01 & y01) | (^01 & c00), so we need first &01 = x01 & y01 and b01 = ^01 & c00 so that we can do c01 = &01 | b01. We can repeat those steps for every next bit, and at the very end the last “carry” is our last output zNN.

Let’s quickly check that for four bit inputs, adding 11 (1011) and 6 (0110):

Great, now how does that help us? Well first, we can make a correct circuit for the right number of bits:

def make_circuit(bits: int = 45):
    ops = [("XOR", "x00", "y00", "z00"), ("AND", "x00", "y00", "c00")]

    for bit in range(1, bits):
        xorop = ("XOR", cname("x", bit), cname("y", bit), cname("^", bit))
        andop = ("AND", cname("x", bit), cname("y", bit), cname("&", bit))
        zop = ("XOR", cname("^", bit), cname("c", bit-1), cname("z", bit))
        bop = ("AND", cname("^", bit), cname("c", bit-1), cname("b", bit))
        cop = ("OR", cname("&", bit), cname("b", bit), cname("c", bit))
        ops += [xorop, andop, zop, bop, cop]
    
    lastcarry = ops.pop()
    ops.append((lastcarry[0], lastcarry[1], lastcarry[2], cname("z", bit+1))) 

    return ops

This gives us a template which we can use to find mistakes in the actual list of operations. To do that, we need to match the names of the outputs. Our main method is:

def match_circuits(circuit: list[Operation], reference: list[Operation]) -> tuple[bool, str|None, str|None]:
    nameref = {}

    for operand, op1, op2, out in reference:
        op1 = nameref.get(op1, op1)
        op2 = nameref.get(op2, op2)
        outref = find_match((operand, op1, op2, out), circuit)
        if outref is not None:
            nameref[out] = outref
        else:
            s1, s2 = find_partial((operand, op1, op2, out), circuit)
            if s1 is None:
                print(operand, op1, op2, out)
                raise ValueError()
            return False, s1, s2
    
    return True, None, None

We keep a running reference of name matched in a dict. For each operation in our reference “correct” circuit, if we already found a match, we replace the name, then try to find a match in the actual circuit. A “match” is an operation which has the same operator and inputs:

def find_match(op, reference):
    for ref in reference:
        if op[0] == ref[0] and ((op[1]==ref[1] and op[2]==ref[2]) or (op[1]==ref[2] and op[2]==ref[1])):
            return ref[3]
    return None

If there is a match, we add it to the reference dict. If we didn’t find anything, then we’ve it a problem spot, and we need to determine with which other operation we need to switch the outputs with. Let’s take an example, and say that we were expecting an operation: ('XOR', '^12', 'c11', 'z12'). We need to find an operation with the same operator and output, and one of the operands. The other operand needs to be switched with the expected one. So if for instance we found an operation ('XOR', '^12', 'hzf', 'z12'), that means that we need to switch c11 with hzf, a wire that we haven’t renamed yet.

def find_partial(op, reference):
    for ref in reference:
        if op[0] == ref[0] and (op[1]==ref[1] or op[2]==ref[2]):
            if op[1]==ref[1]:
                return ref[2], op[2]
            return ref[1], op[1]
        if op[0] == ref[0] and (op[1]==ref[2] or op[2]==ref[1]):
            if op[1]==ref[2]:
                return ref[1], op[2]
            return ref[2], op[1]
    return None, None

Our match_circuit method stops as soon as it finds a switch – or if it can match the whole circuit without error. Now we need to run this iteratively, applying the switches and going over the operations again until we’ve matched the whole circuit:

def do_switches(ops, s):
    sops = []
    ops = ops.copy()

    while len(ops) > 0:
        op = ops.pop(0)
        for out1, out2 in s:
            if op[3] == out1:
                op = (op[0], op[1], op[2], out2)
                break
            elif op[3] == out2:
                op = (op[0], op[1], op[2], out1)
                break
        sops.append(op)
    return sops

def find_switches(ops: list[Operation], reference: list[Operation]) -> list[tuple[str, str]]:
    to_switch = []

    ok, s1, s2 = match_circuits(ops, reference)
    while not ok:
        to_switch.append((s1, s2))
        sops = do_switches(ops, to_switch)
        ok, s1, s2 = match_circuits(sops, reference)

    return to_switch

And we can now put everything together to get the list of wires to switch. The final answer needs to be that list, alphabetically sorted, and joined with commas:

goodops = make_circuit(45)
to_switch = find_switches(ops, goodops)

sout = []
for s1, s2 in to_switch:
    sout += [s1, s2]
print("Part 2 answer:", ','.join(sorted(sout)))