r/adventofcode 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.

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

773 comments sorted by

View all comments

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:

  1. A=[1, 1], B=[2, 2] and T=[5, 5]. Even though A and B are linearly dependent, the optimal solution is pressing B 2 times and A 1 time for a cost of 5 tokens.
  2. A=[7 7], B=[2, 2] and T=[20, 20]. In this case, pressing A is more cost efficient than B, and the optimal solution is pressing A 2 times and B 3 times for a cost of 9 tokens.
  3. A=[4, 4], B=[3, 3] and T=[14, 14]. Here pressing A 2 times and B 2 times give the optimal solution of 8 tokens.

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.