Advent of Code &#- Day Claw Contraption

Day 13: Claw Contraption (Maths, Maths, and more Maths).

Link to Solution

Today's Challenge was done in Python for a change. This choice was made to:
a) test my python / learn more python
b) it looked like a very heavy mathematical puzzle today, so felt Python would be perfect, and I was NOT wrong - it was lightning fast.

Welcome to today's puzzle, a lesson in Maths sad face, I had no idea how to solve this one (Part2), at first I brute forced it, looping over (max of 100 times) until found the right "route".

Which worked fine for part 1 as expected. However, for Part 2 I knew this wasn't going to be the case, so went back and looked for a Mathematical approach, I had a hunch this would have to be what the team were pushing us towards. Googling around, and after a lot of hunting I came across Cramers Rule (first time I'd heard of it tbh).

The task was to:

Calculate the minimum cost to reach the prize using button presses.

For Part 1, determine if it's possible to reach the target with pressing buttons, and if it is what is the most amount of prizes you can successfully win within 100 presses and the cost to do so.

For Part 2, optimise performance by handling large coordinate offsets in essence removing the 100 button press limit, and pushing the prize location into the abyss.

Solution

Cramer's Rule seems to be an excellent approach for solving this problem because it allows you to efficiently solve linear equations that describe how to move the claw to reach the prize in each machine. Let's break down why and how Cramer's Rule applies:

Problem Breakdown

For each claw machine, we have two equations:

Equation 1 (from Button A):
a1 * A b1 * B = c1

Equation 2 (from Button B):
a2 * A b2 * B = c2

Where a1 and b1 are the movements along the X and Y axes for Button A, A is the number of times the A button is pressed, and c1 is the target position on the X axis (prize location).

where a2 and b2 are the movements along the X and Y axes for Button B, B is the number of times the B button is pressed, and c2 is the target position on the Y axis (prize location).

For each claw machine, we want to solve for the number of button presses A and B (the number of times buttons A and B need to be pressed) that will align the claw with the prize at coordinates (c1, c2) on the X and Y axes.

Why Cramer's Rule is Useful

Cramer's Rule is specifically designed to solve systems of linear equations. A system of linear equations is simply a set of two or more equations that share common variables, and the goal is to find values for those variables that satisfy all the equations at once.

In simpler terms:

Imagine you have multiple equations that describe how things are related.

Each equation uses the same variables (e.g., x and y), and you're trying to find values for these variables that make all of the equations true at the same time.

In this case, each machine's button configuration can be represented as a 2x2 system of linear equations, where we are solving for two unknowns, A (button A presses) and B (button B presses).

How would a developer know for the future to use Cramer's Rule ?

System of Equations: The first thing a developer does is identify that the problem requires solving a system of linear equations.

Pattern Recognition: Developers recognise that this is a 2x2 system and that Cramer's Rule is a straightforward way to solve it.

*Determinants and Matrices: * They recall that determinants can be used to solve for the unknowns in linear equations, and if the determinant is zero, it indicates a problem (no or infinite solutions).

Simplicity and Clarity: Cramer's Rule provides a simple, direct method to find the values of A and B without requiring iterative methods or complex algebra.

Example: First Claw Machine

The button movements and prize locations are as follows:

Button A moves the claw X+94, Y+34.
Button B moves the claw X+22, Y+67.
Prize location is at X=8400, Y=5400.

We have the system of equations:

94 * A + 22 * B = 8400   (Equation for X-axis)
34 * A + 67 * B = 5400   (Equation for Y-axis)

Step 1: Calculate Determinants
Main Determinant D:
The determinant D is calculated using the formula:

D = a1 * b2 - a2 * b1

Substituting the values:

D = (94 * 67) - (34 * 22)
D = 6298 - 748
D = 5550

Determinant for A, D_x:
Next, we calculate the determinant D_x using the formula:

D_x = c1 * b2 - c2 * b1

Substituting the values:

D_x = (8400 * 67) - (5400 * 22)
D_x = 562800 - 118800
D_x = 444000

Determinant for B, D_y:
Now, calculate the determinant D_y using the formula:

D_y = a1 * c2 - a2 * c1

Substituting the values:

D_y = (94 * 5400) - (34 * 8400)
D_y = 507600 - 285600
D_y = 222000

Step 2: Solve for A and B
Using Cramer's Rule, we now solve A and B:

A = D_x / D
B = D_y / D

Solve for A:

A = 444000 / 5550
A = 80

Solve for B:

B = 222000 / 5550
B = 40

Step 3: Check for Valid Integers
Both A and B are integers, which means that it is possible to win the prize for this claw machine.

Step 4: Calculate Total Cost
The cost to press Button A is 3 tokens, and the cost to press Button B is 1 token. So, the total cost to win the prize is:

Button A moves the claw X+94, Y+34.
Button B moves the claw X+22, Y+67.
Prize location is at X=8400, Y=5400.

Part2 - uses the same logic the only difference is we add the 10^13 offset to both the X and Y axis of the Prize co-ordinates.

I know that is a lot, and believe it took me a lot to understand / get my head around it too. Happy to have a chat , you can reach me at Twitter.

The above is the detailed content of Advent of Code &#- Day Claw Contraption. For more information, please follow other related articles on the PHP Chinese website!