I tried to solve, and in the end I succeeded (I had inserted a solution with extra white spaces so the answer was rejected even if substantially correct and this made me damn in the search for the error that was not in the algorithm but only in the construction of the final string), the day 24 problem of the AOC 2024.
I found two solutions for part 1: a brute force and one that uses a recursive function(some orders of magnitude more efficient).
For part 2 I had to first study the topic that I did not know: digital circuit Half-Adder and Full-Adder.
I used the functions of part 1 as a test tool and found a solution (to my input) for part 2, interactively and not programmatically.
I think that I could, with the use of many if then else and a lot of patience, write a function that does what I did by hand.
I wonder, however, about the possibility of other programmatic ways that, for example, do not make use of the specific knowledge of digital circuit models.
I can think of two possibilities, but I would like to hear opinions on these ideas and if and how they can be implemented in Julia.
I would also like to hear of other possible ways for both part 1 and part 2.
hypothesis 1
the use of AI systems that in this case would not be difficult to train (i.e. provide the correct input, output pairs).
hypothesis 2
the use of optimization tools by imposing for example the search for min for an objective function such as the sum of the squares of the differences between the desired input and the actual one for a series of appropriately chosen inputs. In this case, the series of powers of 2 could be used
I have a (probably non-complete) programmatic Julia solution for part 2. You can read it here. It relies on the fact that the structure of the circuit in the puzzle is very regular, it uses the adder circuits you mentioned in a repeating pattern. My solver builds a parallel structure, and compares it with the puzzle input. Whenever it finds a discrepancy, it attempts to identify the swap that fixes it. This relies on two observations:
the layers that we’ve already passed are correct;
the discrepancy can be solved with a single swap.
That being said, it is still possible that my solution wouldn’t work for all possible inputs – I worked on it only until it solved my own input.
As a curiosity, in one of the attempts I made in finding the solution, I used as input the combination of bits provided for (my) part 1 which was generic enough to seem “exhaustive”.
What I experienced instead is that after finding three swapped gates the result was correct and therefore I could not get any clues on where to look for the fourth pair.
This is a statement that requires further investigation.
What do you mean by input in this statement?
If, as inputs, you are referring to the possible combinations of bits X and Y, I believe that, according to what is reported in the problem description, having found the four inverted pairs there is no doubt that you have completely repaired the circuit.
The other possibility is that you are referring to the four inverted pairs as inputs. And so the doubt is whether your programmatic solution, in the sense of the function used, would also find “my” ((or any other) ) four pairs.
By “input”, I referred to the puzzle input, which describes the (faulty) circuit. So in your way of putting it, the latter, i.e., the four inverted pairs. I assume that my solution works on all inputs that the AoC site generates for this puzzle, but I haven’t tested it on other competitor’s inputs. And since the program contains a number of assumptions regarding the circuit, I can’t be certain.
I suspect that part 2 was designed to be solved interactively. My first observation was that 4 of the z variables were not computed from a XOR, which is unreasonable (well, at least if we assume that the additions are implemented without glaring redundancies) except for the the most significant bit. Then I made an analysis of which gates depended on which inputs, which provided likely candidates from where to swap in XORs.
For the fourth swap I checked the sums where x = y were powers of two to find at which bit things went wrong and compared the graph structure for that bit to the one for the previous bit to find another likely swap candidate.
As for your doubt about the “completeness” of the solution, I think it can be alleviated by the following argument. Each bit Z in a clean circuit depends on the input values X and Y and on the carry of the previous bit (which in turn depends, in general, on all previous bits). The dependency structure is that Zn = (Xn xor Yn) xor (U or V), with U and V depending in a complex way on the previous bits. The incorrect swaps are only at this (first) level (I think it is stated in the problem statement, but I am not sure because my English is not good enough).
But if this were not the case (i.e. it is not established a priori that the gate inversion is at the level of the current bit Z but could also be at a lower level (in any case the error does not propagate backwards)), by inspecting the circuit from the least significant bit to the “heaviest” bit we should gradually find and resolve the (4) faults always at the first level. So using as test input for X and Y the increasing series of powers of 2 we should have considered all possible cases. And therefore the solution should always be correct. Does this seem convincing to you?
I have no doubt that the systematic comparison of the desired and the actual gate structures, going from LSB to MSB, is a valid and comprehensive solution.
I’m not fully certain, though, that my Julia implementation is able to discover all sorts of discrepancies with the gates. In other words, that when an anomaly is found, it is able to correctly figure out which wire is swapped with which. I think it is able to do that, but I didn’t prove it, nor did I test it on other inputs, except my own.
Anyway, that’s all I have to say on the topic. Feel free to test my solution on your input, if you’d like.