apologies for the audio quality, i'm traveling right now so this is not my usual computer or microphone and i was also trying not to wake up my girlfriend
The best thing I learned from the video is the analysis part where the author print, with indentation, how a znn value is calculated. Thanks a lot for sharing!
That was a fun one. In the brute force swapping method, things move along a _lot_ quicker if you add a starting bit to the progress function, and start progress at baseline (first baseline needs to be calculated starting from 0 of course), and update the baseline each time you fix two wires. That got me from ~18 seconds to 0.12.
Phew, this was a tough one. I also did a semi-manual solution, like so: Since we knew it was an adder I tested each pair of x and y input bits separately. Starting at the least significant bits x00 and y00 I feed the values 00, 01, 10 and 11 into them, and compared that with the expected z value sequence: 0, 1, 1, 0. If the output matches this, continue to the next bit, and do the same for x01 and y01, checking z01, etc. The interesting part is this: if the expected result does not match the current output z, look at the output patterns for all other gates instead. If any of them have the 0, 1, 1, 0 pattern, they could be a replacement. For the example of part 2 (which is not an adder, but a plain bitwise and, where the expected output is 0, 0, 0, 1) there is always exactly one matching gate, which can be swapped with the failing output automatically. For the real input however, there are 4 failing bits in total, and each of them have 2, 3 or 4 other gates matching the pattern. These could be brute-forced, but I looked at the input text and drew the adders at the failing bit on paper, and figured out the two outputs to swap by looking at them.. After re-doing this because of 2 mistakes I got it. ;)
I first drew a schematic for the first few output gates (z gates) of the circuit and noticed it was a normal n bit adder circuit with a bunch of full adders. So then i wrote a function to identify the carry and sum output gates for the next full adder given the previous carry and sum output gates of the previous full adder. Within that function I identify where an issue occurs and what type of operation operation should be there instead, if at all, in finding the next carry and sum output gates and the instruction input causing this issue is a candidate to swap with an instruction of the correct type. so then i try all possible instructions of that type to swap with until it fixes the full adder (saving the swap that fixes it). then I move on to the next full adder (doing this in a loop) until there's no issues.
I'm too late for the recap stream as I'm still catching up on the final aoc days. What I did (before I got stuck on what to do next) for part 2 was XOR-ing the result I got from part 1 with the result that an actual sum of the bits in x and the bits in y would be. I guess you could do that instead of your progress function. The least significant bit of that xor result that is 1 (non zero) should be the next gate to look at to swap? Edit: My wording isn't perfect, but what I mean is that that bit's position should denote which z-bit to look at. So if your XOR result is something like 0011010100 you should look at z02 first.
based on your Inspiration, I did it via this logic and got the answer within 0.1s. if not Z: swap(M, N); break if Z != zi: swap(Z, zi); break # M (intermediate sum) # N (intermediate carry) # Z (final sum) # zi=current z
Since it is supposed to add, could we instead add x and y, simulate the circuit, and locate the bit where z does not match the expected result? Then we can manually fix it or have the program swap some wires in that general region until that bit is fixed and then repeat.
Yes, you can xor the result you should get with the simulated result. The "last" (least significant) bit that is a 1 in that result is the position of the z bit you should try to fix.
I thought I was on a the right track by filtering for a bunch of rules, taken from the general schematic of a 1-bit adder: - Outputs zxx must always be the result of an XOR, except the z45 bit, which is the result of an OR - AND output always goes to an OR (except for z01 because there is no carry bit from z00, so it plugs into an XOR) - OR output goes to an XOR + AND - XOR output goes to XOR + AND This gave me 7 out of the 8 problematic wires extremely quickly. Only issue is now that I can't find the 8th. I bet it follows these rules just to thwart my solving 😁
Great content, as always! Could you help me with something unrelated: I have a SafePal wallet with USDT, and I have the seed phrase. (alarm fetch churn bridge exercise tape speak race clerk couch crater letter). How should I go about transferring them to Binance?
apologies for the audio quality, i'm traveling right now so this is not my usual computer or microphone and i was also trying not to wake up my girlfriend
The best thing I learned from the video is the analysis part where the author print, with indentation, how a znn value is calculated. Thanks a lot for sharing!
That was a fun one. In the brute force swapping method, things move along a _lot_ quicker if you add a starting bit to the progress function, and start progress at baseline (first baseline needs to be calculated starting from 0 of course), and update the baseline each time you fix two wires. That got me from ~18 seconds to 0.12.
Phew, this was a tough one. I also did a semi-manual solution, like so:
Since we knew it was an adder I tested each pair of x and y input bits separately. Starting at the least significant bits x00 and y00 I feed the values 00, 01, 10 and 11 into them, and compared that with the expected z value sequence: 0, 1, 1, 0. If the output matches this, continue to the next bit, and do the same for x01 and y01, checking z01, etc.
The interesting part is this: if the expected result does not match the current output z, look at the output patterns for all other gates instead. If any of them have the 0, 1, 1, 0 pattern, they could be a replacement.
For the example of part 2 (which is not an adder, but a plain bitwise and, where the expected output is 0, 0, 0, 1) there is always exactly one matching gate, which can be swapped with the failing output automatically.
For the real input however, there are 4 failing bits in total, and each of them have 2, 3 or 4 other gates matching the pattern. These could be brute-forced, but I looked at the input text and drew the adders at the failing bit on paper, and figured out the two outputs to swap by looking at them.. After re-doing this because of 2 mistakes I got it. ;)
I first drew a schematic for the first few output gates (z gates) of the circuit and noticed it was a normal n bit adder circuit with a bunch of full adders. So then i wrote a function to identify the carry and sum output gates for the next full adder given the previous carry and sum output gates of the previous full adder. Within that function I identify where an issue occurs and what type of operation operation should be there instead, if at all, in finding the next carry and sum output gates and the instruction input causing this issue is a candidate to swap with an instruction of the correct type. so then i try all possible instructions of that type to swap with until it fixes the full adder (saving the swap that fixes it). then I move on to the next full adder (doing this in a loop) until there's no issues.
I'm too late for the recap stream as I'm still catching up on the final aoc days. What I did (before I got stuck on what to do next) for part 2 was XOR-ing the result I got from part 1 with the result that an actual sum of the bits in x and the bits in y would be. I guess you could do that instead of your progress function. The least significant bit of that xor result that is 1 (non zero) should be the next gate to look at to swap?
Edit: My wording isn't perfect, but what I mean is that that bit's position should denote which z-bit to look at. So if your XOR result is something like 0011010100 you should look at z02 first.
@10:28
wire = "z"
bit = 1
wire_str = f"{wire}{bit:02}"
will produce 'z01'
i was trying to figure out how to do that with fstrings but didn't want to take too much time. thanks!
based on your Inspiration, I did it via this logic and got the answer within 0.1s.
if not Z:
swap(M, N); break
if Z != zi:
swap(Z, zi); break
# M (intermediate sum)
# N (intermediate carry)
# Z (final sum)
# zi=current z
Since it is supposed to add, could we instead add x and y, simulate the circuit, and locate the bit where z does not match the expected result? Then we can manually fix it or have the program swap some wires in that general region until that bit is fixed and then repeat.
Yes, you can xor the result you should get with the simulated result. The "last" (least significant) bit that is a 1 in that result is the position of the z bit you should try to fix.
I thought I was on a the right track by filtering for a bunch of rules, taken from the general schematic of a 1-bit adder:
- Outputs zxx must always be the result of an XOR, except the z45 bit, which is the result of an OR
- AND output always goes to an OR (except for z01 because there is no carry bit from z00, so it plugs into an XOR)
- OR output goes to an XOR + AND
- XOR output goes to XOR + AND
This gave me 7 out of the 8 problematic wires extremely quickly. Only issue is now that I can't find the 8th. I bet it follows these rules just to thwart my solving 😁
Great content, as always! Could you help me with something unrelated: I have a SafePal wallet with USDT, and I have the seed phrase. (alarm fetch churn bridge exercise tape speak race clerk couch crater letter). How should I go about transferring them to Binance?