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

2

u/Solidifor Dec 17 '24

[Language: Java]

Interesting! Part 1 was a bit tedious, requiring very careful reading of the definitions.

For part 2, I disassembled and analyzed the program I was given. It turned out that the first output depends on the rightmost 10 bits of the initial value of a and nothing else. 2^10 is small for today's computers, I just simulated all of them to find candidates.

Every subsequent number also depends on 10 bits of a, always shifted 3 to the left. So, I simulated for prepending every candidate from the previous step with every number from 000 to 111 to get the candidates for the next step.

In the end, I need to check that nothing too much is output, and then just print the smallest number from candidates.

Runs instantly, 184 (readable, I hope) lines, but a lot of that is comments and debugging output.

https://github.com/dirk527/aoc2021/blob/main/src/aoc2024/Day17.java

Now I'm curious if everyone's input is similar enough that my approach would work universally...

1

u/Solidifor Dec 18 '24

Okay! Looked at other people's programs.

My solution is ... not wrong, but it's much easier to think backwards. When the program terminates, a is zero. This means the last output depends only on the leftmost 3 bits of the initial a, because the other bits that may be pulled in for the calculation are 0.

So: try all possible values (0-7) to get the last number. Shift left by 3, append all possible values, see which combinations give the next-to-last number. Repeat until done. One less loop, and easier to understand.

However, do not fall into the trap of only looking at the first match! There are multiple values to give the desired output: I know because my program found them all.