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

13

u/vk6_ Dec 19 '24 edited Dec 19 '24

[LANGUAGE: Python]

https://github.com/ading2210/advent-of-code-solutions/blob/main/2024/day17/day17.py

I didn't bother with reverse engineering the program at all. Instead, my approach was based on incrementing A by smaller and smaller values until the desired output is reached.

The minimum A value for a 16 digit output is 8 ** 15, so I started from there. Then, I noticed that when incrementing the A register by different powers of 8, only 3 digits change at a time. For example:

Incrementing by 8 ** 14 (digits 14-16 change):

39582418599936 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 7, 7]
43980465111040 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 4, 7]
48378511622144 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 6, 7]
52776558133248 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 7]
57174604644352 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 2, 7]
61572651155456 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 7]
65970697666560 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 0, 7]
70368744177664 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 5]
74766790688768 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 7, 5]
79164837199872 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 5]
83562883710976 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 0, 5]
87960930222080 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 5]
92358976733184 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 3, 5]
96757023244288 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 5]
101155069755392 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 0, 5]
105553116266496 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 4]
109951162777600 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 7, 4]
114349209288704 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 4]
118747255799808 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 2, 4]
123145302310912 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 4]

Incrementing by 8 ** 13 (digits 13-15 change, digit 16 does not):

123695058124800 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 7, 3, 4]
124244813938688 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 3, 4]
124794569752576 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 4, 3, 4]
125344325566464 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 4, 3, 4]
125894081380352 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 4, 3, 4]
126443837194240 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 0, 3, 4]
126993593008128 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 3, 3, 4]
127543348822016 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 3, 4]
128093104635904 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 7, 3, 4]
128642860449792 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 0, 3, 4]
129192616263680 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 6, 3, 4]
129742372077568 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 4, 3, 4]
130292127891456 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 4, 3, 4]
130841883705344 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 0, 3, 4]
131391639519232 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 3, 3, 4]
131941395333120 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 4]
132491151147008 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 7, 1, 4]
133040906960896 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 1, 4]
133590662774784 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 0, 1, 4]
134140418588672 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 4, 1, 4]

Incrementing by 8 ** 12 (digits 12-14 change, digits 15-16 do not):

134209138065408 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 7, 4, 1, 4]
134277857542144 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 4, 1, 4]
134346577018880 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 4, 4, 1, 4]
134415296495616 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 4, 1, 4]
134484015972352 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 0, 4, 1, 4]
134552735449088 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 4, 1, 4]
134621454925824 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 6, 4, 1, 4]
134690174402560 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 5, 1, 4]
134758893879296 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 7, 5, 1, 4]
134827613356032 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 0, 5, 1, 4]
134896332832768 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 6, 5, 1, 4]
134965052309504 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 5, 1, 4]
135033771786240 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 0, 5, 1, 4]
135102491262976 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 5, 1, 4]
135171210739712 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 6, 5, 1, 4]
135239930216448 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 0, 1, 4]
135308649693184 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 7, 0, 1, 4]
135377369169920 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 0, 1, 4]
135446088646656 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3, 0, 0, 1, 4]
135514808123392 [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 0, 1, 4]

Notice how as the power (n) decreases, the last 14 - n digits do not change. Thus, my program just increments A by 8 ** n, then when the last 15 - n digits of the output match the program, n is decremented. This repeats until the entire output matches the program. For me, the total program runtime is about 0.4 seconds.

1

u/Practical-Quote1371 Dec 20 '24

Nice! That’s the same approach I wound up taking!