this post was submitted on 23 Dec 2024
8 points (100.0% liked)
NotAwfulTech
384 readers
1 users here now
a community for posting cool tech news you don’t want to sneer at
non-awfulness of tech is not required or else we wouldn’t have any posts
founded 1 year ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
I did end up writing a code solution.
algorithm desc
So basically the problem boils down to this:A 1 bit full adder circuit with carry in/out is described as follows:
S~i~ = X~i~ ^ Y~i~ ^ Cin~i~
Cout~i~ = (X~i~ && Y~i~) || (Cin~i~ && (X~i~ ^ Y~i~))
Where S is the output bit, X and Y are the input bits, and Cin~i~ is the carry out bit of bit i-1. For the first and last bits of the output, the circuits are slightly different due to carry in/out not mattering in the 0/last bit case.
Note that as said in the problem statement any input is correctly labelled, while outputs might be incorrect. You can then categorise each gate input/output as any of the elements in an adder circuit. You can then use set differences and intersections to determine the errors between categories. That's all you need to do!
For example, you might have something like:
X && Y = err
if this output was used correctly, it should show up as an operand to an OR gate. So if you did:
(Set of all outputs of and gates) - (Set of all inputs to or gates), if something appears, then you know one of the and gates is wrong.
Just exhaustively find all the relevant differences and intersections and you're done! To correct the circuit, you can then just brute force the 105 combinations of pair swaps to find what ends up correcting the circuit.