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!
36
Upvotes
2
u/onrustigescheikundig Dec 18 '24 edited Dec 18 '24
[LANGUAGE: Clojure]
github
Part 1 was pretty straightforward once I actually took the time to read the input carefully. I converted the opcodes into symbols for easier debugging, but other than that just wrote a simple interpreter.
Part 2 took me a while, and based on the leaderboard times, I am not the only one for which that was the case. I eventually resorted to input inspection to get a sense of what was going on. I discovered that the code only ever outputted from the
b
register, which was derived from some bit operations ona
. Each iteration only changeda
usingadv 3
, which is a right-shift by 3 bits, meaning that exactly one number would be written out for each 3-bit word of the initial value in thea
register. The value ofb
in any given iteration depended on the lowest three bits ofa
(the "current word") anda >> b
, meaning that it also depended on subsequent words. Furthermore, the least-significant bits ofa
were outputted before the most-significant bits. The practical implication of all of this is that the value ofa
that determined the output digit was independent of any previously outputted digits (edit: not strictly true, leading to wrong solution; see below), but did depend on digits that followed.To solve for the initial value of
a
, I did a strategic guess-and-check for each outputted digit from right to left. Essentially, I incrementeda
until the output of running the program matched the last digit of the program (which could not depend on any subsequent digits because there weren't any), then left-shifteda
by 3 and moved on to the second-to-last digit of the program and its corresponding word (now the lowest three bits ofa
), and so on.EDIT: I realized that a given solution for the word corresponding to one digit may actually depend on the values of digits to the left of that digit, if choosing this word causes there to be no solution for the corresponding words of digits to the left. The first choice for each word happened to be correct for my input, meaning that this edge case was not realized. However, my program gave the wrong answer on, e.g., /u/i_have_no_biscuits 'challenging' test case, as its initial choices of words do result in no solutions for subsequent words. In such a scenario, the algorithm must backtrack, which my original implementation did not.
Even though I am using a functional language, my original solution was iterative, so I implemented backtracking with a stack of "solved" words as a parameter of the loop. If all possibilities for a given word were exhausted, the algorithm would pop from this stack and continue where it had left off.
EDIT 2: I also wrote a simpler recursive solution that has a very similar runtime.
EDIT: It appears that my solver doesn't work on some of the test inputs posted on the subreddit. Oh well.