Anyone have a solution to Part 2 today? Part 1 was straight forward, but I can’t figure out a programatic way to do part 2. I understand the properly constructed machine would be a carry-forward adder, so besides visualizing the configuration and looking for mis-wirings I’m not sure how to approach it.
1 Like
I found the answer for my input just a few minutes ago, but I don’t have any code to share yet. (Too messy and it doesn’t solve the complete problem.)
What I did was to programmatically check for mis-wirings for each output (starting with z0). For my input, the first mis-wiring was for z18. Going from that to which wires to swap was not obvious, so I tried to figure it out by manually looking at how the gates were wired. I did a topological sort of the gates, which made it easier to try to understand what was happening.
I managed to figure out which two wires that were likely to fix the problems with z18, and tested that with my program. It fixed the problem and my checker gave me the next incorrect output. I quickly figured out two more pairs.
The final pair had a different kind of mis-wiring, which was harder to figure out manually. At that point I just added a brute-force search, testing swap each possible pair of wires. It finished in a few seconds.
I now think I now how this can be solved programmatically without any need for manual intervention. It might be a couple of days before I’ll have time to try that.
2 Likes
It turns out that it is viable to do a brute-force search for one pair at the time. My solution finishes in about 8 seconds. I will share my code when I’ve cleaned it up.
2 Likes
I built a computational graph from the input, and another computational graph of the correct Ripple Carry Adder, just that I don’t know how to compare those two graphs because the vertices have different names.
Here is my cleaned up solution.
For some reason, the runtimes fluctuate wildly, but it usually finished in 2 through 4 seconds.
1 Like
I plan to do that too tomorrow. Wires should be present at two different places in the graph, as input and output for well known “xyz” names so building a mapping should be possible.
At least I hope 
2 Likes
I managed to get the first part without too much trouble and am stuck on the second part. I think I understand the problem, but I’m not quite sure how to tackle it in code yet.
@bjorng, I tried your solution for part 2 but it didn’t seem to produce the correct result on my input. In manually looking at the binary X and Y values it would appear to be on the right track with which z’s are off, but not fully grasping the code yet I’m not sure where it goes wrong.
I like the graph idea as that seems like how I would approach the problem visually if I actually had such a physical device, but I’m not familiar with graphing so I wouldn’t know where to start. It seems like it would be super cool to pattern match on graphs or subsections of graphs though.
I fear I may end up having to do a lot of manual work to figure this one out and then back into a code solution.
1 Like
So does it produce an answer that is wrong? If that is the case, one bug I can think of is that my check for miswirings doesn’t catch all kinds of faulty wiring.
Another possible problem I can think of is that my code swaps an output more than once. That is expressly forbidden by the description. My code doesn’t try to prevent that.
So my brute force solution tries to limit the swap combos by only using nodes that are in the network between pairs of wrong outputs. Even with that it took overnight to produce a list of swaps that work. Funny thing is that the list is only 3 swaps long. This doesn’t make the machine a valid adder, but for these two operands (x and y), and only these two, the answer (z) is right.
Yes, the answer it produces is wrong for my input at least. I think it is correctly determining the bad outputs, but I don’t think it’s producing the correct swaps.
I’ll know more once I can spend some more time on it and figure out the correct answer and compare.
I think that’s how I’ve solved it.
Part 1 example (2.8ms): 2024
Part 1 input (5.0ms): 56620966442854
Part 2 input (96.2ms): "chv,jpj,kgj,rts,vvw,z07,z12,z26"
I make graphs of logic and input wires only, no intermediate names. This lets you easily test if a node is logically equal. I look up the intermediate names from a map when needed.
