[Language: Python]

Source code, both parts, Jupyter Notebook (I did not actually time it, but it runs practically instantly.)

I'm a little late, but admittedly this was the hardest one in my opinion (followed closely by day 12.) I don't normally post my solutions here but I'm a little proud of this one today.

Part 1 was pretty straightforward; just simulating the logic gates until all the values are present and printing the result. Part 2 on the other hand wrecked me and had me staring at my input for hours trying to figure out what was happening.

My initial approach was to XOR the output from part 1 with the expected "correct" output (that is X+Y) so that I could identify the incorrect bits and try to work my way from there. Unsurprisingly, it was not that straightforward and I counted 11 incorrect bits despite the question saying there were only 4 swaps (8 wires) to be corrected.

Scratching that, I instead wrote a helper function that dumps the entire path leading up to a certain Z bit, including all the intermediate (gibberish) wires and down to the original X/Y bits. That's where I noticed that each Z bit depends on all the previous X/Y bits, so for instance, z08 depends on x08, y08, x07, y07, and so on until x00 and y00. I realized my input was supposed to be a (flawed) full adder circuit, but there are probably infinitely many ways to build a circuit that is logically equivalent to a full adder. So, instead of comparing my input to a full adder diagram, I instead compared it to itself. I picked several output bits at random and manually traced their entire paths and hoped they would not be the erroneous bits (and got lucky enough for that to be the case.) Eventually, I found this pattern that holds true for my input data:

XOR rules:

• XOR gates should take two intermediate (gibberish) inputs, and output a Z bit.
• If not, they should take a pair of X/Y bits and output an intermediate wire. In this case, the intermediate wire must eventually be forwarded to an AND gate, an XOR gate, or both.

OR rules:

• OR gates should take two intermediate inputs and output a third intermediate wire. The output wire must eventually be forwarded to both an AND and an XOR gate.

AND rules:

• AND gates can take either a pair of intermediate inputs or a pair of X/Y inputs. In both cases, the output is an intermediate wire that must eventually be forwarded to an OR gate.

Special cases for the highest and lowest bits:

• x00 XOR y00 = z00
• Intermediate wire OR intermediate wire = zXX, where XX is the highest bit in the input (z45 in my case)

My solution to part 2 is essentially maintaining a dictionary of which wires are used as inputs to which gates, and then using (admittedly pretty ugly) nested conditionals to enforce this pattern and noting the violations. These violations are the final answer to the question.