https://kotlinlang.org logo
Join SlackCommunities
Powered by
<Advent of Code 2024 day 17> (spoilers) :thread:
# advent-of-code
a
j
p1 fun, for p2 I need a computer that'll run 8^16 tests in a valid time
j
Solved p1, p2 have found a nice trick to limit the needed steps for simutating with one number to <100 steps, still waiting for finish.
d
Ok yes I have done binary search to locate the range of possible values since the output size only increases
That is not a small enough range
And the problem has stopped being fun. Part 1 was very fun
m
I've found the range just experimenting, but yes the range is too big to brute force
➕ 3
d
I’m now trying to understand the program
b
i'm so bad at these types of problems
m
I've encountered a very interesting bug in my compiler and I can't seem to solve it. This is NEVER returning true, even with the toList() and the lists being [0] and [0]
d
int vs long
m
bruh
d
i had the same bug
m
frantically searching for his coffee
that has got to be the noobiest mistake I made today
😂
d
Screenshot 2024-12-16 at 11.26.53 PM.png
that’s my input
and what it means
…continuing to analyze
ah. look. a is only modified by shr 3
so
m
Yeah I've rewritten it in Kotlin, but not much luck yet actually doing something with it
d
yes this is reverse engineering for sure
So, there's just a mapping between the right most 3 bits of a to the output on any loop iteration
Build that map
Reverse it
Construct the input
Profit
m
That's what I thought, but it's not just the 3 bits because of the 
xor c
d
Ahhh yes c = a shr b
m
I dont know if this is the case for everyone, but every one of my 'iterations' has • grab last 3 bits from A and put in B • do some xoring on this B • output B • shift A 3 bits to the left • repeat until A is empty
d
b = a mod 7
Yes see my program above
Maybe the program can be run in reverse...
m
Well hint number 2 is, if your program is (2,4) and you know how to get ONLY output 4 from a starting value 'a'. How do I make sure that I keep 4 at the end of my output?
d
Ok actually. I think it only low 6 bits affect output?
On any iteration
Hmm
I need to actually simulate
Xor you're killing me here
Ok
print your registers in octal
pattern is clearer
m
I print everything in binary but it's not very clear to me. 😄
d
First loop
Copy code
306416164 4 0 []
306416164 3 0 []
306416164 3 30641616 []
30641616 3 30641616 []
30641616 30641615 30641616 []
30641616 30641612 30641616 []
30641616 30641612 30641616 [2]
30641616 30641612 30641616 [2]
Second loop
Copy code
30641616 6 30641616 [2]
30641616 1 30641616 [2]
30641616 1 14320707 [2]
3064161 1 14320707 [2]
3064161 14320706 14320707 [2]
3064161 14320701 14320707 [2]
3064161 14320701 14320707 [2, 1]
3064161 14320701 14320707 [2, 1]
Third loop
Copy code
3064161 1 14320707 [2, 1]
3064161 6 14320707 [2, 1]
3064161 6 30641 [2, 1]
306416 6 30641 [2, 1]
306416 30647 30641 [2, 1]
306416 30640 30641 [2, 1]
306416 30640 30641 [2, 1, 0]
306416 30640 30641 [2, 1, 0]
What do I see here lol
m
This is the spoiler thread so, but this is how I solved part 2
Day 17 Michael.cpp
d
I just want the solution at this point
OK nice
you build one triplet at a time
search for each triplet
m
yeah perhaps shl 3 is more obvious lemme edit
d
Winner winner chicken dinner
b
i also took the recursion approach when i noticed they seemed to be related to the octets
d
Yeah I was sort of seeing that in the output but it would have taken me a lot longer to get there
Last year I dropped out mid way because I spent far too much time on one problem and refused to get spoilers, don’t want a repeat
m
yeah at some point its fine to take hints, especially on problems with analyze solutions
but you work away assumptions by doing the operands bit by bit. At first I assumed the jump operator could jump to positions other than 0 because my input had 
... 3,3,0
in it which meant that it was possible for a 3 to appear after a 3, modifiying the jump instruction. That took me for a spin until I realized I could never get the instructions to jump to an offset
d
Yes, I put the instructions into a spreadsheet and saw jump is always at the end and always jumps to the beginning. I assumed there could be random jumps at first which made me pessimistic about analyzing.
m
putting the entire program in a class is clean, I should do that as well 👍
d
yeah i put it in a data class so I can just print the whole thing at any point
(and to be able to create/execute programs at will)
ah i actually don’t need the jump flag
Copy code
3 -> if (a != 0L) instructionPointer = operand - 2
m
I got it! Can't believe it
🧠 2
Looks like I'm very late to get the star, but oh well. 😄
Too tired to refactor further
d
Are everyone's instructions the same?
Actually yours is slightly different
Than mine
xor 1 vs xor 7 and some other diffs
Marcin it looks like you're doing search while Michael is just doing take first match
j
Solution for part 2 was neat after noticing that prefixes resulting in the last x instructions being correct can be extended by one digit (octal) to compute x+1 octal long digits that result in x + 1 long prefixes https://github.com/bulldog98/advent-of-code/blob/main/advent2024/src/main/kotlin/year2024/Day17.kt
j
uhhhh that was something. I had a lot of troubles figuring it out. FUN!
Copy code
Parsing took 4.875us
Part 1 took 2.125us, result is 1,4,6,1,6,4,3,0,3
Part 2 took 545.541us, result is 265061364597659
the trick was to figure out that if you replace one digit (base8) in a Register A, then the output after certain point don't change. I'm sure there are better approaches, but I had fun with mine, so I'm going to stick to it 🙂
(sad thing: I was so happy with my solution with DeepRecursiveFunction, but just switching from it to
Copy code
val q = mutableListOf(0L to 0)
    while (q.isNotEmpty()) {
        val (base, i) = q.removeLast()
        ...
and keeping the exact same computations, speeded up my part2 6 times, from 540ms to 90ms... Didn't know it's so heavy on processor, this DRF. Scratch that, I was so very wrong thinking that a stack will easily replace DRF
l
I finally manage to get through part 2. It is an interesting one indeed. I thought it has something to do with binary, but turn out it is octal. I think the algorithm I cooked is O(8^n), but too exhausted to find a more efficient one. https://github.com/CongLuanTran/Advent-of-Code-2024/blob/main/src/Day17.kt
m
Part 2 drove me mad. Wouldn't have made it without reading the hints about octals here. I then had the problem that at a certain position multiple octals yielded the correct output value but the selected (lowest) one didn't work with the later added octals. I now compute all possible values for a (it's only a handful) and select the minimum one in the end. https://github.com/fabmax/aoc-kt/blob/main/src/y2024/day17/Day17.kt
k
Whew! Part 2 took me for a massive spin. My initial solution worked for the sample but not for my input. I also tried reconstructing A from an int array of binary bits which became no-trivial as C kept moving around. Tbh, I ended up peeking at other approaches which made me realize that the path I was previously going down may be unnecessarily difficult. Solution
p
I got lost in so many errors and wrong roads, but I finally got the incremental search for part 2 working 🙂 https://github.com/glubo/adventofcode/blob/main/src/main/kotlin/cz/glubo/adventofcode/y2024/day17/Day17.kt#L203
j
Took way too long, but I’m there… key was searching for octets yes. It was annoying that I found a solution that worked for the test input, and then suddenly xor appeared in the real input and that ruined my initial solution
a
got my answer, after taking a long break. the progression is easier to see in binary: image shows all registers, but if we focus on just register A:
Copy code
11101011001101000100111101
11101011001101000100111
11101011001101000100
11101011001101000
11101011001101
11101011001
11101011
11101
11
0
j
I hope this visualization nicely shows how the registry A changes the output
Day17.mov
🤩 4
a
I wanted to cross-check what I had written and why it wasn't working, so I tried with @Jakub Gwóźdź code - while it found me "an answer", it was too high. (verified that it's correct by running Part One with that value in RegA). and then even looking at it in the registry A's values to compare against mine, and none of the smaller values matched in binary. (two separate octets were different, even though it matched the input.) this makes sense for the 3rd example input which provides 117_440 as an answer, also works with 1_166_016 and 3_001_024 - any number with the same lower octets of 117_440, plus 1 to 7. curious that a different method yields a match but not the correct answer 🤔. when I switched to just pad and go, it worked.
> xor appeared in the real input and that ruined my initial solution I have two XOR's in my input. 
1,2
& 
1,7
is that better or worse? 🙃 @Jaap Beetstra & @Jakub Gwóźdź could you DM me your actual input instructions (but not the answer), I want to check if my solution works in general or a fluke because of my input. (I know Mr. Wastl has asked ppl not to share inputs but we've already solved it and publishing online)
k
Finally got around to completing my alternative reconstruction solution. I'm at least happy that the thought process didn't hit a dead end 😄
j
I’m away from computer rn, but you can grab my input from the visualization above, @Anirudh 😁
👍 1
a
oh hahaha I didn't notice it was there 🙂
nope, it doesn't work 😭 (* it works, visualisation issue) even more interestingly, when I put in your answer and replace that for partOne, I get a different result. I've triple-checked for typos in the register number and instructions. my "instruction" handling code should be wrong since using your part2 code works for your part2 input (which checks output). but my code works for my input? I will clean up and paste it here
j
Untitled.cpp
Untitled.cpp
a
> Jakub: but you can grab my input from the visualization above > me: nope, it doesn't work > also me: I've triple-checked for typos in the register number and instructions. lol @Jakub Gwóźdź your visualisation has register A as 
267277567730587
but your output results further up has 
265061364597659
! 🙃 hahah, so yeah, that's the answer I was getting, the 
26506...
number so they match up even though the solution differs a bit
j
ooooooo 😮 Indeed, my correct answer was 265061364597659, I don't know why I messed it up for visualization.
a
hahaha that was an hour of debugging and looking for issues. waiting for Jaap Beetstra's confirmation if the answer I got for his is input is also correct. ✅ confirmed
here's my Part 2, cleaned up. summary: • keep shifting left by Octet and add 0 to 7 • check result vs same-last-length of instructions • go to step 1
aneroid_part2.kt
j
I can't f.... believe it. I had the correct solution obviously, but at some point I started "optimizing" for visualization purposes and messed it up, now I cannot figure out wha I changed 😆
a
oh hahha, let's hope you have it in your IDE history or git history
j
I know what happened. In pursuit of the speed, I changed my queue to a stack. Indeed it was way faster. Somehow the result was not the best one, tho 😛
I can only say - I'm terribly sorry @Anirudh 🙂
K 1
a
no worries @Jakub Gwóźdź! cheers it's all part of the AoC adventure 👍
j
Yeah it's tricky to make sure you return the minimum value sometimes; I think I had that bug as well while cleaning up code. Luckily I tested against the correct answer already
a
precisely. in the crime-code, I actually had a list-of-answerNums and then I was doing 
min()
. but then I realised, in 
(0..7L).map { prev shl 3 + it }
& 
try.remove*First()*
so 
0
is always getting checked first anyway, so I can return directly.
a
My solution for part 2 (and part 2 example too)
Copy code
fun solve(program: List<Int>): Long {
    var A = 0L
    var B = 0L
    var C = 0L
    var out = mutableListOf<Int>()

    fun getCombo(operand: Int): Long =
        when (operand) {
            in 0..3 -> operand.toLong()
            4 -> A
            5 -> B
            6 -> C
            else -> throw IllegalArgumentException("Invalid operand")
        }

    fun execute(opcode: Int, operand: Int) {
        when (opcode) {
            0 -> { // adv
                A /= (1 shl getCombo(operand).toInt())
            }
            1 -> { // bxl
                B = B xor operand.toLong()
            }
            2 -> { // bst
                B = getCombo(operand) and 0b111
            }
            3 -> { // jnz
                // IGNORE
            }
            4 -> { // bxc
                B = B xor C
            }
            5 -> { // out
                out.addFirst((getCombo(operand) and 0b111).toInt())
            }
            6 -> { // bdv
                B = A / (1 shl getCombo(operand).toInt())
            }
            7 -> { // cdv
                C = A / (1 shl getCombo(operand).toInt())
            }
            else -> throw IllegalArgumentException("Invalid operation")
        }
    }

    val pq = ArrayDeque<Pair<Long, List<Int>>>()
    pq.add(Pair(0, emptyList()))

    while (true) {
        val (potentialA, output) = pq.removeFirst()
        if (output == program) return potentialA

        val left = potentialA * 8
        val right = (potentialA+1) * 8 - 1
        for (num in left..right) {
            A = num
            out = output.toMutableList()
            program.windowed(2,2).forEach { execute(it[0], it[1]) }
            if (num != 0L && out == program.subList(program.size - out.size, program.size)) {
                pq.addLast(num to out)
            }
        }
    }
}
e
Day17.kt in the given program, high bits map to the end of output, so I just narrow down the search space one nibble at a time
r
Ship it!
advent of code intensifies 3
And here is a visualization of the search which if you squint looks like a Christmas tree:
Copy code
7
70
702
7026
70264
702642
7026424
70264245
702642452
702642455
7026424555
70264245557
702642455571
702642455576
70264246
702642463
7026425
70264252
702642523
7026425236
70264252365
702642523651
7026425236514
70264252365142
702642523651427
part2: 247839653009594
time: 17
🎄 2
d
n
Late to the game. I had a pretty good sense for what to do from the start, because this is basically a simplified version of a day 2X puzzle from some years past that broke my brain to splinters. Don’t remember which one it was, but it was the same idea. Huge number that you reverse engineer and keep plugging in bigger numbers that would result in the next step working out. I kept trying to find a solution that didn’t rely on any brute force at all and I’m not good enough at math for that. So eventually I gave up and just brute forced each number starting from 8 times the previous number (working backwards of course). Was fast enough.
e
because I'm ridiculous, I extended my pure-Kotlin solution with another one that translates the program into JVM bytecode and executes it: https://github.com/ephemient/aoc2024/blob/kt/day17jvm/kt/aoc2024-lib/src/jvmMain/kotlin/com/github/ephemient/aoc2024/Day17Jvm.kt
it has worse startup time but it does run part 2 faster
cleaned up my benchmarking a bit: • part1, part2, solve is pure Kotlin solution interpreting the instructions • part1_jvm, part2_jvm, solve_jvm is the same solution but using bytecode translation • ***_cached re-uses the parsing (and the bytecode) it seems that the JVM doesn't take very long to warm up the small function that the given program translates to, and once it does, it goes zoom
56 Views
Open in Slack
PreviousNext
Powered by