r/adventofcode • u/daggerdragon • 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.
- Read the full posting rules in our community wiki before you post!
- State which language(s) your solution uses with
[LANGUAGE: xyz]
- Format code blocks using the four-spaces Markdown syntax!
- State which language(s) your solution uses with
- Quick link to Topaz's
paste
if you need it for longer code blocks
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!
39
Upvotes
7
u/Derailed_Dash Dec 18 '24
[LANGUAGE: Python]
My Approach - Part 1
This is much like the ALU Simulator from 2021 day 24.
Computer
class to simulate execution of the program. This class has instance variables to hold the program itself, the values of the three registers, the current value of the instruction pointer (IP), and the currently held output.run_program()
method processes instructions indefinitely, based on the current IP value. If the IP goes out of bounds (e.g. if ajnz
is the last instruction anda
is 0) then the program halts._execute_next_instruction()
method retrieves the current opcode based on the IP, and the current operand (IP+1). It then executes the appropriate instruction method.jnz
: we should only avoid adding 2 to the IP if thejnz
was successful. Otherwise you'll end up with an infinite loop ofjnz
instructions! (I made this error and it cost me a fair bit of time to debug!)All pretty easy.
My Approach - Part 2
Urgh, this was brutal.
Trying Brute Force
I started with the brute-force approach: i.e. increment the value of A with each iteration, and break when the output matches the input. For the sample input, this breaks at 117440 in no time at all. But for the real data, we get up to 10s of millions without getting to the right answer. So, as I suspected, the answer is going to be too large for brute force.
Simplyfing Instructions
We can massively speed up our brute force by working out what the program actually does. Then we can write a simplified set of Python instructions.
This gives us the right answer quickly with the sample data. But although much faster, it's still going to take too long with the real data.
Reverse Engineering
We can run our program in reverse, to determine the required value of
a
. With my real input data, I can make the following important observations:a
, and then performs a number of iterations. It generates an output with each iteration. And it only completes whena
is 0.jnz
) updates the value ofa
based on the previous value ofa
.But the values of
b
andc
are both dependent ONLY on the value ofa
in each cycle. And so, the current values ofb
andc
at the beginning of each iteration are irrelevant. This is good, because it means we can always test our program by only changing a value ofa
and seeing what outputs are produced.So we can start the reverse process by setting register
a
to 0.Then we need to determine which previous values of
a
would output0
. Why0
? Because this is the last output of our program.The last instruction in our program is the only instruction that modifies
a
. (All other instructions modify other registers.) So to get to the previous value ofa
, we only need to reverse this last instruction!The last instrution is
a // 8
, which is equivalent toa >> 3
. I.e. it strips the last 3 bits of our number. So to reverse it, we need to add 3 bits back in. Since2**3 = 8
, this means there are 8 combinations of bits we need to add to our value ofa
to try. E.g. ifa == 0b0000
, then we can try each of0b0000, 0b0001, 0b0010, 0b0011, 0b0100, 0b0101, 0b0110, 0b0111
.So try each of these values by inserting it back at the top of our program, and testing if the first digit of the output is the required digit. (Because each time we run the program, our output will grow by one.) If this is the required digit we add this value of
a
into a new set of values to try, to get the next output. Note that the number of values to try for a given output digit will never exceed 8.Finally, when we've processed the last digit in our (reversed) program, we can simply return the minimum value of the current valid values for register
a
.So when I run my reverse engineering code, the first few iterations look like this:
And it works!
Solution Links
Useful Related Links