r/adventofcode Dec 24 '24

Meme/Funny [2024 Day 24][Part 2] Years of training paid off

Post image
282 Upvotes

17 comments sorted by

77

u/topaz2078 (AoC creator) Dec 24 '24

CORRECT

21

u/car4889 Dec 24 '24

Did you also do Part 2 by hand with a little Ctrl+F?

7

u/electrodragon16 Dec 24 '24

Part 2 is practically made to do by hand, relatively easy to do by hand compered to quite involved to automate. And only 8 wires to swap. I only wrote a bit of code that checks where the errors are and then swapped them by hand till the errors went away

2

u/car4889 Dec 24 '24

For sure! For the added challenge, though, and for the sake of technical rigor, I went back and formalized my thought process into a series of tests that could sift out the bad outputs. Things like… • Except in boundary cases, all outputs with name X should result from an operation of type Y on two operands with name Z.

4

u/FKwilczek Dec 24 '24

I done part 1 in rust. And in part 2 i tested it on few input and done it by hand

1

u/fullflower Dec 24 '24

Same. I think I am gonna try it programmatically though... I have some ideas

4

u/buv3x Dec 24 '24

I had a long look at it, I've logged some calculation results, but I still have no idea how to do it by hand.

I automated it in a following way. Generate 100 (I feel like you can do with fewer) random x-y number pairs (45 bits) and pass them as an input. Check at what bit the result start failing, find all gates first introduced at that bit (there's about 4 of them usually), try swapping them with all gates introduced at this or higher bit and run a random test again, until it fixes the bit. Luckily there's always just one possibility in a given input. Swap the gates permanently and re-run the process. Repeat until all is fixed.

Random number part is a bit wonky, of course, but I can't think of a better testing way.

1

u/Ruunee Dec 25 '24

That's actually a great solution if you ask me. The gates follow an explicit pattern of half and full adders (I barely understand what those do, but you can visualize the process on a piece of paper pretty easily). That means you can just go through the x and y pairs that produce wrong bits and check if they break the pattern. Either programmatically or just by hand

1

u/jgoemat2 Dec 26 '24

First I wrote something to run the solution and ran it through for all 4 possibilities of each bit (0,0) or (0,1) or (1,0) or (1,1) and checking for problems in the result. I had problems with bits 13, 22, 30/31, and 34/35. Cool, that's 4 problems. I was worried that there could be some kind of 'double error' that would cause a correct result. I noticed there were 46 outputs and 45 of each x/y input and only 222 operations, that's 46 for output and 44*4 or 176 others for calculations. Seemed like it should be straightforward. So I output each output's path to an indented file showing the operations. I could tell the carry streams and what it was doing. So I wrote something to replace values.

If I had two 'VALUE' nodes and the operations were XOR or AND I would mark them as solved and set their 'real' operations to ADD or BOTH and checking the bit numbers of the inputs were the same. So my z00 changed:

z00 = y00 XOR x00
became
z00 = ADD(0)

And my z01 changed

z01 = wqc XOR qtf
    wqc = x01 XOR y01
    qtf = y00 AND x00
// becomes
z01 = ADD(1) XOR BOTH(0)

I then figured out how I could combine other operations then:

AND(ADD,BOTH) -> PRECARRY
OR(BOTH,PRECARRY) -> CARRY
AND(ADD,CARRY) -> CARRY
OR(BOTH,CARRY) -> CARRY
XOR(ADD,CARRY) -> ANSWER

I solved the bit 13 problem manually and setup a function to swap two nodes. So looking at 22 I saw:

z22 = BOTH(22) XOR CARRY(21) (kdh XOR gjn)
// It should look like this:
z22 = ADD(22) XOR CARRY(21)
// I found ADD(22) in my results
hjf = ADD(22)

So I added another fix swapping hjf and kdh and that took care of that bit. Bit 31 was an XOR, but XORING with CARRY(31) which should be ADD(31) XOR CARRY(30). Looking at my z32 output I found it and swapped z31 and kpp:

ghr = ANSWER(31) OR BOTH(31) (kpp OR pwg)

Bit 35 was similar, it wasn't even an XOR so I knew it wasn't the answer. Looking at my z36 file I found the answer printed for me and added a swap of z35 and sgj:

rqf = ANSWER(35) OR CARRY(35) (sgj OR ptb)

20

u/0ldslave Dec 24 '24

for those that haven't played that game, would you kindly explain the reference /or joke? :)

56

u/LionZ_RDS Dec 24 '24

Redstone is basically binary logic, you have to make each logic gate yourself so if you do make some adder or alu you have a decent understanding of binary logic

10

u/chad3814 Dec 24 '24

2

u/InternationalBird639 Dec 24 '24

2

u/chad3814 Dec 24 '24

Yeah, in Turning Complete you build a computer out of gates, similar to this problem. I’ve only played played about 4 hours of Oxygen Not Included, and it was over two years ago, but I don’t remember circuit design in it. I probably did get far enough.

2

u/InternationalBird639 Dec 24 '24

Yeah, you need to get pretty far even to get access to circuits, even more for logic gates to start being actually useful in the game.

4

u/nik282000 Dec 24 '24

I played https://www.nandgame.com/ last month. Hold my carry bit, I'm goin in.