Advent Of Code

Yeah - dumped out the input into GraphViz, and then inspected it 'by eye' to get the swaps. Nearly finished in the top 100 in the world, too. Feels like a really bad way to get the solution, though.

If you add eg. 1111 and 1111 and expect 11110, then you'll get an output like 11010 if there's a mistake in "bit 2". Can try all the swaps between x2 / y2 / z2 until you get the "right answer", and then continue. There's only about five different ops for each "bit" of the input, so trying all of them won't take too long.

It is definitely possible to do it programmatically but like most people including me simply did it manually. though I did do this:

#
    # we step through a proper Ripple Carry adder and check if the gate is correct for the given input.
    # first level is will start with all the initial input gates.
    # these must have XOR and AND as gates.
    marked_problem_gates = defaultdict(lambda: defaultdict(list))
    # dict of the full adder as the index and the value of what the next wires lead to.
    full_adder_dict = defaultdict(lambda: defaultdict(lambda: defaultdict(list)))
    for i in range(len(wire_states)//2):
        for (a_key,gate,b_key),output_wire in connections['x'+str(i).rjust(len(next(iter(wire_states)))-1, '0')]:
            if i == 0:
                matching_z_wire = 'z' + str(i).rjust(len(next(iter(wire_states)))-1, '0')
                # we check the first adder as it should have the correct output wire connections for a half adder type.
                if gate == 'XOR' and output_wire != matching_z_wire:
                    # for the half adder the final sum output bit should be a matching z wire.
                    marked_problem_gates[i][gate].append(((a_key,gate,b_key),output_wire))
                elif gate == 'AND' and (output_wire.startswith('z') and (output_wire[1:].isdigit())):
                    # for the half adder the carry over bit should not be a z wire.
                    marked_problem_gates[i][gate].append(((a_key,gate,b_key),output_wire))
                if output_wire in connections:
                    full_adder_dict[i][gate][output_wire].extend(connections[output_wire])
            else:
                # since the first adder is a half-adder, we only need to check the other adders to verify that their output wire is not to a z wire.
                if (output_wire.startswith('z') and (output_wire[1:].isdigit())):
                    # if the output wire is a z wire, we mark the gate as a problem.
                    marked_problem_gates[i][gate].append(((a_key,gate,b_key),output_wire))
                else:
                    # we get what the output wires to the next step in the adder would be.
                    full_adder_dict[i][gate][output_wire].extend(connections[output_wire])
    
    # for the next step in the full adders, we expect the carry over bit from the previous step in the adder should be have.
    # 
    
    print(marked_problem_gates)
    print(full_adder_dict)

I then took the printed output and cleaned it up a little.

This really just me looking at it and seeing to make sure outputs are connected to the right locations. just took a minute but the highlighting of the selected work helped out. simply faster than just trying to think of some complex logic

basically bruteforce part 2 with our eyes lol

I did notice that most of the swaps where within the fulladders and not accross the entire circuit, so it was a little easier than anticipated.

I only parse each of the initial gates that the input wires to the full adders have x and y The only exception is that the first input wires go into a half adder and not a full adder.
So we only verify that the XOR gate is connected to an output wire z00 and that the AND gate does not output to a z wire. Every AND output wire should be connected to one logic gate and that is the OR gate for the carry bit.
The XOR gate should have the output wire connected to the two gates that take in the carry bit wire from the previous adder.

from there I just used my memory and intuition about full adders to clean up the output and all that to see which of the full adders have bad output wire configs.

I also solved part2 manually today, by outputting the correct addition and program output in binary and then reversing the path for all wrong outputs.

Then I just had to compare that to the formulas for a full adder and I found my swaps pretty quickly that way.

I did all of this in Kotlin and on paper, with a handy helper method to construct the paths.

It's at the very bottom of this file on Github.

I suspect that comparing the bits and then comparing the paths to the full adder formulas can also be done 'automatically' decently easily, but I was too lazy to implement that today.

Yeah, same here. Graphviz to get an overview (although I didn't actually need it in the end), plus some helper functions. I've got an idea for how to do it in code, though, when I get a moment.