https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2024 day 24> (spoilers) :thread:
# advent-of-code
a
Advent of Code 2024 day 24 (spoilers) 🧵
h
One would have thought by Day 24, I'd have learned to just make everything a Long 🤦‍♂️
I'm guessing there is some trick to the interactions of AND, XOR and OR between 2 adjacent bits, that will yield a correct ADD result (with carry?) x00 XOR y00 -> z00 x00 AND y00 -> aaa x01 XOR y01 -> bbb aaa AND bbb -> z01
oh wait... This is going to be about finding full/half adders isn't it? I haven't delved into logic gates in a long long time (university CompSci courses were ~30 years ago now)
a
Bit 00:
Copy code
x00 XOR y00 -> z00
x00 AND y00 -> finalCarry
Every bit after 00:
Copy code
x01 XOR y01 -> firstResult
x01 AND y01 -> firstCarry
firstResult XOR previousFinalCarry -> z01
firstResult AND previousFinalCarry -> secondCarry
firstCarry OR secondCarry -> finalCarry
I just printed out all the gates that don't match the pattern and found the swapped pairs manually.
đź‘Ť 1
d
I think you can do this iteratively — make adding 1 bit numbers work, then 2 bit numbers, etc.
h
well... I'm sure my uni lecturers will be pleased to know some of what I learned is still rattling around inside my head all these years later! hahaha
d
But yes this adder has a fixed structure it’s supposed to be
(I’m not 100% sure iterative will work, trying it out)
h
@Dan Fingal-Surma yeah, I was manually doing the iterative part, which is kind of what triggered the half adder/full adder thing in my memory...
d
The wires might conveivably be too crossed
h
so, I'm hoping it works
d
You may instead need to write a structure analyzer yeah
(it may be the case that the input is designed to work with an iterative approach)
I played around with this, I think you can want to just analyze that the input conforms to the spec Albert gave
j
I was able to reason by hand what the solution for part 2 is. Now I have to think what a generic solution is
d
Yeah I’m trying to replicate that reasoning in code
a
You can try swapping each pair in an invalid group of 5 gates, so 10 tries per group. Shouldn't be too difficult. I did it by hand because I thought it's probably faster.
Oh, but under the premise that no pairs of gates in different groups are swapped.
d
My z18 looks like
Copy code
Wire(name=z18, input=AndGate(a=Wire(name=y18, input=InputGate(value=true)), b=Wire(name=x18, input=InputGate(value=true))))
which is clearly the first carry of bit 18, not z18
my first 8 bits are all correctly wired
as well
…maybe I will do this by hand and call it a night
ok now that I’m doing it by hand i think i can program it
b
yea you can just hardcode a search for the pattern (correct xN, yN)
i also just printed them out and looked at the patterns
messy
d
Copy code
java.lang.IllegalArgumentException: Swap z10 into sqr XOR mwq
Now we’re cooking
I’m just having it throw an exception when it finds an inconsistency
then I’ll manually record and fix
for now, to get the solve
Copy code
java.lang.IllegalArgumentException: Swap z18 into nqq XOR nfh
(when i have time, after Christmas probably, will make it auto-fix)
Copy code
java.util.NoSuchElementException: Key ([hsw, mrs], XOR) is missing in the map.
when trying to look up the rule that would produce z24. So now I find the rule that does produce z24, which is
Copy code
jmh XOR mrs -> z24
therefore hsw and jmh should be swapped i think
ding ding, 1 left
Copy code
java.lang.IllegalArgumentException: Swap z33 into wwp XOR cvt
winner
will get the star and link my code
got the star
Part 2 starts at 
data class Rule
it would be a straightforward extension to handle the errors, fix the 2 lines, then continue
So again looking at
Copy code
x01 XOR y01 -> firstResult
x01 AND y01 -> firstCarry
firstResult XOR previousFinalCarry -> z01
firstResult AND previousFinalCarry -> secondCarry
firstCarry OR secondCarry -> finalCarry
the key thing here is consistency. If e.g. firstResult on line #1 does not have the same name as firstResult on line #3, the one on #3 wins (input wires can’t change) and you need to swap whatever line currently outputs to the wire from #3 (which necessarily hasn’t been seen in prior bits) with the wire from #1
For me, that was only 1 of the 4 cases. 3 of the 4 cases were “firstResult XOR previousFinalCarry” exists but doesn’t point to z$i. So swap what it points to with z$i
h
Interesting... I also had 3 where the zWire was not on the firstResult XOR prevFinalCarry Gate... but my fourth case was the x XOR y and x AND y outputs were swapped. So I'm wondering if my solution (it actually detects and corrects the errors while processing) would actually work for other inputs?
Actually, now that I reread your "fix" for that case ("swap with whatever is outputting to the wire from #3"), it would appear that that is indeed exactly what my code is doing. It is finding the "real" firstResult from the inputs of XOR that outputs to the zWire (line #3)... then it finds the gate that is currently outputting to that "real" firstResult wire, and then swapping the two outputs
j
j
Can anyone please confirm whether https://github.com/jandurovec/adventofcode-in-kotlin/blob/main/src/aoc2024/Day24.kt works on your input too or someone has some other mutation/swap type?
p
after fighting for a long while, not getting anywhere, I ended up with only needing
Copy code
val r = xors.get(x, y).key
                val ca = ands.get(x, y).key

                xors.find(r)
                    .let { it ?: xors.find(ca)?.also { add(ca, r) } }
                    ?.let { (out) -> if (out != z) add(out, z) }
which finds just the 4 swaps I needed - annoying as I don't have any other inputs to check against
refactored and tidied up: https://github.com/tKe/aoc/blob/main/kt/src/main/kotlin/year2024/Day24.kt for some reason I thought I'd find more than just the 4 candidates to swap, and I'd have to try different combinations of them - maybe because my initial attempt was to try and brute force it (and prune the candidates that seemed fine based on an understanding of half-adders)
j
@Jan Durovec I tried your solution and it gives the correct answer for my input.
h
I'd appreciate it if someone could test this (fairly messy but it works) solution with their input https://github.com/HardCorePawn/AoC2024-Kotlin/blob/main/src/Day24.kt
d
Works on mine
Copy code
Bad wires at 10 - z10 is not on XOR gate
Gate(input1=Wire(name=kgd, value=1), input2=Wire(name=kqf, value=0), output=Wire(name=z10, value=1), type=OR)
SwapGate(input1=Wire(name=mwq, value=1), input2=Wire(name=sqr, value=1), output=Wire(name=mwk, value=0), type=XOR)
Bad wires at 18 - z18 is not on XOR gate
Gate(input1=Wire(name=x18, value=1), input2=Wire(name=y18, value=1), output=Wire(name=z18, value=1), type=AND)
SwapGate(input1=Wire(name=nfh, value=0), input2=Wire(name=nqq, value=0), output=Wire(name=qgd, value=0), type=XOR)
Bad wires at 24 - x XOR y gate output is wrong
Gate(input1=Wire(name=x24, value=1), input2=Wire(name=y24, value=0), output=Wire(name=hsw, value=1), type=XOR)
SwapGate(input1=Wire(name=x24, value=1), input2=Wire(name=y24, value=0), output=Wire(name=jmh, value=0), type=AND)
Bad wires at 33 - z33 is not on XOR gate
Gate(input1=Wire(name=cvt, value=0), input2=Wire(name=wwp, value=0), output=Wire(name=z33, value=0), type=AND)
SwapGate(input1=Wire(name=cvt, value=0), input2=Wire(name=wwp, value=0), output=Wire(name=gqp, value=0), type=XOR)
gqp,hsw,jmh,mwk,qgd,z10,z18,z33
đź‘Ť 1
h
Ta muchly... Merry Christmas everyone! 🎄🎅
🎅 4
e
d
My code now auto solves my input though doesn't handle all possible error cases
k
So. I've gone on a long journey of different paths to part 2, each leading me to interesting destinations, but never quite the one I wanted. Finally came around to solving it in a fairly straightforward manner (almost no recursion needed). Tidied up and pushed my solutions now
Copy code
Cold:
Part1: ~4ms. Part2: ~2ms

Warm:
Part1: ~240us. Part2: ~280us
My approach for part 2 doesn't work for the sample input though as I use an assumption that every gate operation in the input maps to a distinct output (not sure if some people got inputs where this isn't the case). If anyone is up for it, I'd appreciate some help to run it against your inputs and let me know if it still works fine
d
What do mean mean by maps to a distinct output?
scanning your code, it looks like you’re modeling the full adder
Copy code
x01 XOR y01 -> firstResult
x01 AND y01 -> firstCarry
firstResult XOR previousFinalCarry -> z01
firstResult AND previousFinalCarry -> secondCarry
firstCarry OR secondCarry -> finalCarry
which is the right approach
k
The sample input had gates like:
Copy code
x00 OR x03 = fst
x00 OR x03 = vdt
My part 2 doesn't work in such case
Yea. It's a full adder model
đź‘Ť 1
r
Solved it manually by looking at pattern (after inspecting the binary sum of x and y with z result) in graphviz - x,y to z.
j
Finally finished the visualization!
Day24.mov
advent of code intensifies 2
50 Views
Open in Slack
PreviousNext
Powered by