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 
3 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.
1 Like
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.
3 Likes
I think this is closer to the approach I was trying to figure out. Thanks for posting this. It does produce the correct result for my input. I am going to need to spend a bit more time on this to understand it fully and know for sure it’s doing what I think it is.
This is one aspect of elixir code that I haven’t really gotten comfortable with. For basic things the code seems so elegant and straightforward, but once things get complicated I seem to get lost and have a harder time visualizing what is actually getting passed between the functions. I’ve mostly done OOP stuff before and didn’t really experience this before. Maybe it’s more to do with the nature of Advent of Code than elixir in general. IDK
I would love a tool that could show visually what the parameters look like when you mouse over functions. I think that would be super cool and help a lot in these cases.
4 Likes
That sort of visualization would be awesome. I wonder if the gradual typing work is capable of doing something like this. Keeping track of the transformations of the shapes of data.
Yes, it would be appreciated if you could find out where my solution falls down.
I like your elegant solution!
1 Like
Inspired by @liamcmitchell’s solution and to better understand it, I implemented a solution in Erlang based on it:
2 Likes
Very nice!
I tried to iterate on the X inputs with the help of a correct adder.
Only provide x00 and x01, check the result from the correct added and the bad adder. If they are the same, so far so good, add x02 in the inputs and start over.
At some point the two adders give a different result. From there, I lookup the gates that were activated in that last run (I also tried with all the gates so far), and try to swap one by one with any other gates.
It works for the first swap, finds one of the inputs for the second swap, but then it it not viable.
So I looked up online and find some interesting information about the input, and then an implementation which spoiled the thing for me, so I just adapted it into Elixir and it’s actually pretty simple:
defp find_swappables(gates) do
Enum.reduce(gates, [], fn
# First gate is considered valid
{_, {:AND, "x00", "y00"}}, acc ->
acc
# AND gate should lead to an OR gate
{out, {:AND, _, _}}, acc ->
leads_to_or? =
Enum.find_value(gates, fn
{_, {:OR, ^out, _}} -> true
{_, {:OR, _, ^out}} -> true
_ -> false
end)
if leads_to_or?, do: acc, else: [out | acc]
{out, {:OR, _, _}}, acc ->
# OR pointing to Z output is invalid
acc =
case out do
"z45" <> _ -> acc
"z" <> _ -> [out | acc]
_ -> acc
end
# OR into OR is invalid, the current computation should be directed
# elsewhere.
leads_to_or? =
Enum.find_value(gates, fn
{_, {:OR, ^out, _}} -> true
{_, {:OR, _, ^out}} -> true
_ -> false
end)
if leads_to_or?, do: [out | acc], else: acc
{"z00", {:XOR, "x00", "y00"}}, acc ->
acc
# input XOR gate should be reused in another XOR
{out, {:XOR, <<x1, _, _>>, <<x2, _, _>>}}, acc when x1 == ?x when x2 == ?x ->
leads_to_xor? =
Enum.find_value(gates, fn
{_, {:XOR, ^out, _}} -> true
{_, {:XOR, _, ^out}} -> true
_ -> false
end)
if leads_to_xor?, do: acc, else: [out | acc]
# other XOR gates should be redirected to output
{"z" <> _out, {:XOR, _, _}}, acc ->
acc
{out, {:XOR, _, _}}, acc ->
[out | acc]
end)
end
I have gone back and looked at this again, and the only problem was that the leading 0s were getting stripped from the Zs. This also messed up the Z ordering, but it’s a simple fix and if you happened to not have a low numbered Z in your solution I don’t think you’d notice it.
1 Like
Thanks!
I’ve pushed a correction.
1 Like
I ended up checking every Bitwise.bxor(z, x + y) for k <- 0..43, x = y = 1 <<< k and manually checked every suspicious unit of my malfunctioning adder (2 XOR gates, 2 AND gates, and an OR gate). Draw.io helped a lot. I still don’t have code though.
I like this kind of puzzle, because it’s more of a debugging puzzle than a programming puzzle.
