I did not bother introspecting the circuit. Instead I made the observation that the only way for 1s to occur in the state is from another 1. If you test x and y, bit by bit, you can test three operations (0+1=1, 1+0=1, 1+1=1 at next bit, carry). To automate finding the errors: - Find the 1s in the circuit when one of these bit operations fail for bit 'i' (group 1) - Find the reachable nodes by traversing the inputs from the output bit (z[i] or z[i+1]) which should be 1, but isn't (group 2) - The candidates for swaps are in these two groups (first is from the first group, the second is from the second) - For each of the candidate swaps perform it and count the number of errors after the swap. Total error count should go down and the bit operation should be fixed for a "good" swap. This is because one output can be swapped at most once (compare with sorting, the sort order should improve for a successful swap) - Emit the set of candidate swaps after testing all 45 input bits, this is a very limited set of candidates (26 pairs for my input) which can easily be brute forced. - For each of these swaps, emit unique sets of permutations for the swaps to try and perform them, first test the failed operations, if all succeed, test all bits if all succeeds, test a set of random additions, if succeeds you have your result. - Runs in about half a second on my machine
Congrats on rank 12, impressive! I took a very similar approach (like, build an adder from scratch, there should be an and gate whose inputs are "foo" and "bar", if there isn't, find an and gate whose one of the inputs is "foo", and swap the other input and "bar") - but it took me nearly 3h 😁
At first I have solved it by actually drawing the graph and searching manually for connections that do not fit the pattern. Thats how i have earned my star. However I haven't felt satisfied with that approach afterwards. So now i have been searching for the cables programatically. Works but takes something like 7-8 minutes to find the solution. Pretty sure i could be optimized a lot but I'm happy with it. Rank 12 is really really great.
One of those days where printing the graph and fixing it by hand was easier than doing it in code. At least the usual AI suspects are nowhere to be seen today. And a nice touch to make you use different inputs to find the final pair.
i used a similar approach, but just printed out the whole recursive tree into a file first, then looked for bad bits where adder breaks and referenced the tree with the eyes to see what's the issue with that bit :D
congrats! I've isolated which bits are wrong by adding "same" bits on x,y x,y = 0b0...0001 x,y = 0b0...0010 x,y = 0b0...0100 ... x,y = 0b1...0000 I've found 3 "z" not being XOR, but it took me very long to detect what is changed... nice trick with pprint ;-)
not a fan of these reverse engineering days, but really liked seeing how you approach finding the wrong gates. I developed a more general solution but had to make the assumption that for each wrong bit there is a single swap that fixes it (or what your referred as no obfuscation). same thing for the 3-bit computer quine challenge, I converted the program into a z3 expression and "solved it". manually solving just feels icky.
maybe one day you can make video describing your "setup", how you use this shell staff.. (if you haven't done it already...), thx; and good luck for final day! I know, a lot of AI "cheaters" are there this year, maybe they should admit it some settings and have a separate leaderboard
I did not bother introspecting the circuit. Instead I made the observation that the only way for 1s to occur in the state is from another 1. If you test x and y, bit by bit, you can test three operations (0+1=1, 1+0=1, 1+1=1 at next bit, carry). To automate finding the errors:
- Find the 1s in the circuit when one of these bit operations fail for bit 'i' (group 1)
- Find the reachable nodes by traversing the inputs from the output bit (z[i] or z[i+1]) which should be 1, but isn't (group 2)
- The candidates for swaps are in these two groups (first is from the first group, the second is from the second)
- For each of the candidate swaps perform it and count the number of errors after the swap. Total error count should go down and the bit operation should be fixed for a "good" swap. This is because one output can be swapped at most once (compare with sorting, the sort order should improve for a successful swap)
- Emit the set of candidate swaps after testing all 45 input bits, this is a very limited set of candidates (26 pairs for my input) which can easily be brute forced.
- For each of these swaps, emit unique sets of permutations for the swaps to try and perform them, first test the failed operations, if all succeed, test all bits if all succeeds, test a set of random additions, if succeeds you have your result.
- Runs in about half a second on my machine
@@bikkel77 Woah, that's a pretty cool pure algorithmic approach. Nice, thanks for sharing!
Thanks! I made a UA-cam video about my solution on my channel.
Congrats on rank 12, impressive! I took a very similar approach (like, build an adder from scratch, there should be an and gate whose inputs are "foo" and "bar", if there isn't, find an and gate whose one of the inputs is "foo", and swap the other input and "bar") - but it took me nearly 3h 😁
At first I have solved it by actually drawing the graph and searching manually for connections that do not fit the pattern. Thats how i have earned my star. However I haven't felt satisfied with that approach afterwards. So now i have been searching for the cables programatically. Works but takes something like 7-8 minutes to find the solution. Pretty sure i could be optimized a lot but I'm happy with it.
Rank 12 is really really great.
One of those days where printing the graph and fixing it by hand was easier than doing it in code. At least the usual AI suspects are nowhere to be seen today. And a nice touch to make you use different inputs to find the final pair.
i used a similar approach, but just printed out the whole recursive tree into a file first, then looked for bad bits where adder breaks and referenced the tree with the eyes to see what's the issue with that bit :D
congrats!
I've isolated which bits are wrong by adding "same" bits on x,y
x,y = 0b0...0001
x,y = 0b0...0010
x,y = 0b0...0100
...
x,y = 0b1...0000
I've found 3 "z" not being XOR, but it took me very long to detect what is changed...
nice trick with pprint ;-)
not a fan of these reverse engineering days, but really liked seeing how you approach finding the wrong gates. I developed a more general solution but had to make the assumption that for each wrong bit there is a single swap that fixes it (or what your referred as no obfuscation).
same thing for the 3-bit computer quine challenge, I converted the program into a z3 expression and "solved it". manually solving just feels icky.
what'd you do with Enzo?
Interesting that you unpacked the split line via indexing instead of just "a, op, b, _, out = line.split()". That way, you can't mess up the Indices.
@@1vader Ah shoot yeah that's just me being rusty - in general unpacking the split directly is good and less error-prone
Nice solve!
Don't forget to do day 18 before day 25 😬
Thanks! And yeah, I haven't forgotten haha. Although I do appreciate the reminder :)
maybe one day you can make video describing your "setup", how you use this shell staff.. (if you haven't done it already...), thx; and good luck for final day!
I know, a lot of AI "cheaters" are there this year, maybe they should admit it some settings and have a separate leaderboard
It's just the Python shell.
GG!
you look like paul dano i assume you've gotten that before. i have no clue what is going on in part 2 i am so lost lol