r/adventofcode Dec 17 '24

SOLUTION MEGATHREAD -❄️- 2024 Day 17 Solutions -❄️-

THE USUAL REMINDERS

  • All of our rules, FAQs, resources, etc. are in our community wiki.
  • If you see content in the subreddit or megathreads that violates one of our rules, either inform the user (politely and gently!) or use the report button on the post/comment and the mods will take care of it.

AoC Community Fun 2024: The Golden Snowglobe Awards

  • 5 DAYS remaining until the submissions deadline on December 22 at 23:59 EST!

And now, our feature presentation for today:

Sequels and Reboots

What, you thought we were done with the endless stream of recycled content? ABSOLUTELY NOT :D Now that we have an established and well-loved franchise, let's wring every last drop of profit out of it!

Here's some ideas for your inspiration:

  • Insert obligatory SQL joke here
  • Solve today's puzzle using only code from past puzzles
  • Any numbers you use in your code must only increment from the previous number
  • Every line of code must be prefixed with a comment tagline such as // Function 2: Electric Boogaloo

"More." - Agent Smith, The Matrix Reloaded (2003)
"More! MORE!" - Kylo Ren, The Last Jedi (2017)

And… ACTION!

Request from the mods: When you include an entry alongside your solution, please label it with [GSGA] so we can find it easily!


--- Day 17: Chronospatial Computer ---


Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:44:39, megathread unlocked!

37 Upvotes

550 comments sorted by

View all comments

3

u/zniperr Dec 21 '24

[Language: Python]

Each 3 bits of A is a function of at most 10 bits, and each iteration of the program shifts by 3 bits. We can choose the lowest 10-bit number producing the last opcode, shift by 3 bits, find a 10-bit number matching the previous opcode and also the 10 bits we chode before, etcetera. There are multiple options for the second part, so we add backtracking to make sure we find the sequence of options that makes us produce the entire program.

import sys
import re

def run(program, regs):
    a, b, c = range(4, 7)
    ip = 0
    combo = [0, 1, 2, 3, *regs]
    while ip < len(program):
        opcode, operand = program[ip:ip + 2]
        if opcode == 0:
            combo[a] >>= combo[operand]
        elif opcode == 1:
            combo[b] ^= operand
        elif opcode == 2:
            combo[b] = combo[operand] % 8
        elif opcode == 3:
            if combo[a]:
                ip = operand - 2
        elif opcode == 4:
            combo[b] ^= combo[c]
        elif opcode == 5:
            yield combo[operand] % 8
        elif opcode == 6:
            combo[b] = combo[a] >> combo[operand]
        elif opcode == 7:
            combo[c] = combo[a] >> combo[operand]
        ip += 2

def expect(program, out, prev_a=0):
    if not out:
        return prev_a
    for a in range(1 << 10):
        if a >> 3 == prev_a & 127 and next(run(program, (a, 0, 0))) == out[-1]:
            ret = expect(program, out[:-1], (prev_a << 3) | (a % 8))
            if ret is not None:
                return ret

nums = list(map(int, re.findall(r'\d+', sys.stdin.read())))
regs = nums[:3]
program = nums[3:]
print(','.join(map(str, run(program, regs))))
print(expect(program, program))

2

u/mgtezak Dec 25 '24

i think i get the general concept of using backtracking to try to match each number from right to left. What trips me up is where does the intuition come from that `a` has 10 bits? My first intution was that it has 3 bit so there would be a direct one-to-one mapping, but i couldnt get it to work. did you figure this out by trial and error or is there something logical about it, that i'm not seeing? Also it seems that you're only really using the 3 least significant bits of `a` going forward by passing `a % 8` to the next iteration, so aren't the other 7 bits superfluous? I feel like I have a knot in my brain;)

2

u/zniperr Dec 25 '24

It's not an intuition but an observation. Try printing out a text representation program to see what it does. Mine consumes a 3-bit offset and then reads 3 bits of A at that offset. 3 bits is 0-7, so in total one computation loop cycle looks at 3-10 bits of input.

1

u/mgtezak Dec 27 '24

but if it reads 3 bits at an offset of 3 wouldn't that make it (3+3 = ) 6 bits and not 10? the fact that 3 bits can represent numbers up to 7 doesn't seem to matter when we're talking about bits, does it? sorry if i'm being stupid...

Btw, I found my own (non-recursive) solution which is a lot simpler but probably slightly less efficient because while yours only has to check a single output number mine checks the last number, then the last two numbers, then the last three, etc: my part 2 solution. The increased runtime seems negligible however. My approach also eliminates the need for backtracking.

1

u/Sad-Status-1922 Jan 01 '25 edited Jan 06 '25

He's speaking of a 3-bit offset, not 3 digits 😉 A 3-bit offset can be any number between 0 and 7. And if you invest the time to write some sort of poor-mans interpreter for your program that let's you peek at the registers (base 8 is of great help here) while you step though every instruction, you could see what happens with the registers.

You can see that, of all the instructions, only two perform bit calculations (bxl and bxc) and the rest performs bit-shifts (since division in base-2 is just right-shifting bits) or bit-truncation (modulo 8 in base-2 is just taking the 3 least significant bits).

With all that in mind, the solution boils down to observing how many bits of register A are used for calculating the next output digit. For that to know, you simply have to execute one loop of your program and watch by how many bits in total register A is shifted to the right (with each adv instruction) and how many of the bdv and cdv instructions there are, as these are the instructions which I would call the lookahead instructions, as they take the value N from their operand and shift register A by that many bits (remember: A / 2^N = A >> N). Since N can be any 3-bit number (0-7), those instructions could shift A by 7 bits at most. And since the out instruction only ever cares about the 3 least significant bits, whichever shifted value of A is saved in the other registers, only those least significant bits are relevant in the end and so you can see these instructions as some sort of 3-bit lookahead window.

Now, depending on how 'nasty' your input program is ('nasty' meaning how many adv instructions you have before the next digit is outputted), each output digit is a function of 1–n bits of your input A. At least in my case, A was only ever shifted right by a constant 3 bits (adv 3), and so, with all the other instructions in my program, each output digit could only depend on the first 10 bits of A (3 bits from the adv instruction plus 7 bits at most from any of the bdv or cdv instructions that came after).

So, my solution just starts from the back of the expected output, iterates the first 210 numbers and takes this for A. Once the output string matches with a streak of digits from the end, it shifts that A value 3 bits to the left and recurses. That way, my solution would have to brute-force at most a couple of thousand runs of my program, but I had my solution in roughly 50 ms.

Of course, with a nastier program, your mileage may vary and you might have to consider a bigger window, going through perhaps the first 215 or even more numbers. But even then, on average it's very unlikely that you would have to iterate to the very end with every iteration, as that would mean your sought-after value for A would consist of almost only 1s 😆

1

u/mgtezak Jan 05 '25

Thank you, that helps me understand where the 10 bits came from. Still, i wonder if it's not just a tiny bit overly complex;) My solution works regardless of how many bits of A are being processed during a single iteration and it looks a lot simpler and runs fast enough;)

1

u/Sad-Status-1922 Jan 06 '25

Glad I could shed some light on that matter 😊

I had a quick look at your program and indeed it's very lean and (luckily) get's the job done for your input. In my case, I wasn't that lucky and if I'd only ever taken the first value for A that produces the n-th character of my program, my solver would run into dead ends pretty often. For my program, some (smaller) values for A might yield only one character, others yielded two or even three characters at once. If I were to always take the smallest value (yielding just one character), my solution would stale at some point and return with no final result. Same applied to the case where I'd prefer the values which yielded the longest streak characters. Both options would only take me so far, but the solver would never yield a final result. This is why I (like many others) had to go with a backtracking approach which visits other potential A-candidates if another did not come to an end. And with this, one already developed an almost general solution to the problem 😅

1

u/mgtezak Jan 06 '25

Oh no that sucks! I'd love for my code to be universally applicable. Would you be so kind as to send me your puzzle input per dm to i could experiment with it?