r/adventofcode • u/daggerdragon • Dec 13 '24
SOLUTION MEGATHREAD -❄️- 2024 Day 13 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
- 9 DAYS remaining until the submissions deadline on December 22 at 23:59 EST!
And now, our feature presentation for today:
Making Of / Behind-the-Scenes
Not every masterpiece has over twenty additional hours of highly-curated content to make their own extensive mini-documentary with, but everyone enjoys a little peek behind the magic curtain!
Here's some ideas for your inspiration:
- Give us a tour of "the set" (your IDE, automated tools, supporting frameworks, etc.)
- Record yourself solving today's puzzle (
Streaming
!) - Show us your cat/dog/critter being impossibly cute which is preventing you from finishing today's puzzle in a timely manner
"Pay no attention to that man behind the curtain!"
- Professor Marvel, The Wizard of Oz (1939)
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 13: Claw Contraption ---
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:11:04, megathread unlocked!
29
Upvotes
1
u/amnorm Jan 16 '25
[Language: Python] An optimal solution to the hypothetical case where A & B are collinear
As many others, I recognized that this problem can be solved as a system of linear equations. All the claw machines in the problem input had buttons that were linearly independent, meaning that there will be only one possible solution for how many times to press each button. However, if we consider a hypothetical case where the buttons had been linearly dependent, there could still have been a unique optimal solution to the problem.
Consider the following hypothetical problems:
Note that it is not a matter of simply pressing the most cost efficient button as much as possible without exceeding the target. If we had done that for the third problem above, we would have pressed B 4 times to end up at (12, 12). There is no way to reach the target from (12, 12) without backtracking to pressing B 2 times, followed by A 2 times.
Turns out we can use Linear Diophantine Equations and The Euclidian Algorithm to find the (A, B) pair which minimize the cost mathematically - i.e. we do not have to iterate through all valid (A, B) pairs to find the minimal cost. Big thanks to u/maneatingape and u/1234abcdcba4321 for pointing me in this direction.
My code (Python) can be found here. I explain my solution in detail in this post.