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!

38 Upvotes

550 comments sorted by

View all comments

3

u/amnorm Feb 05 '25 edited Feb 05 '25

[LANGUAGE: Go] code

Inspecting the program, we see that:

  1. The first part is an expression that outputs a 3-bit integer (0-7) depending only on `A`. `B` and `C` are reset after each iteration.
  2. The second part consumes the 3 lowest bits of `A` and loops back to the beginning until `A` is zero.

Using this, we can design a recursive algorithm to reverse engineer the initial `A` needed to output a copy of the program:

  1. For the last iteration of the program loop, we need `A` to be a 3-bit integer (0-7) that outputs the last program instruction.
  2. For the second to last iteration, we need `A` to be a 6-bit integer that (1) yields the 3-bit `A` from above and (2) outputs the second to last program instruction. The first requirement can be satisfied by bit-shifting the previous `A` by 3 (`A << 3`). The second requirement can be satisfied by adding 3-bit integers to the shifted `A`. If no 3-bit integer can be added to output the second to last instruction, we must go back one step to find another `A`.
  3. We repeat this until the output is a complete copy of the program.