[2024 Day 13] In Review (Claw Contraption)

Next up is the resort with the hexagonal life floor tiles, where we tried to have a vacation in 2020, only to be called back immediately. They now also have an arcade with claw machines, and so we set about calculating which prizes are winnable and how few tokens we'd need to spend to do that.

The input lists the configuration for each of 320 machines in paragraphs of 3 lines. There are two buttons: A and B (that cost 3 and 1 tokens to press respectively) that will move the claw some positive distance in the X and Y axis. The goal is to get it to the given prize coordinates. And since the buttons can't be partially pushed, that makes each a system of linear [Diophantine equations](https://en.wikipedia.org/wiki/Diophantine_equation).

My initial solution was just to brute force by looping from 0 to 100 for each button and testing them. This is the classic quick solution to see what exactly part 2 will be. Which is that the target just gets shifted by 10 trillion on each axis.

So I quickly did some algebra:

Button A: X+94, Y+34 Button B: X+22, Y+67 Prize: X=8400, Y=5400

Solve:

(94a + 22b = X) * 34 - (34a + 67b = Y) * 94

=> 34(22b) - 94(67b) = 34X - 94Y b * (34(22) - 94(67)) = 34X - 94Y

b = (34X - 94Y) / (34(22) - 94(67))

Can do the same for a. Test for integer solutions with (numer % denom == 0).

That's the note in the directory. Yes, I used numbers as variables... they're constants, and I find that its sometimes easier to see what's happening if everything isn't a letter. Of course, once you see this, you notice these are determinant/determinant, and so I had just derived [Cramer's Rule](https://en.wikipedia.org/wiki/Cramer%27s_rule). Making it a bit of a callback to the hailstones in Never Tell Me the Odds.

my $a_numer = $target->[X] * $b->[Y] - $target->[Y] * $b->[X]; my $b_numer = $target->[Y] * $a->[X] - $target->[X] * $a->[Y];

my $denom = $a->[X] * $b->[Y] - $a->[Y] * $b->[X];

# Test for integer solution if ($a_numer % $denom == 0 and $b_numer % $denom == 0) { return (A_COST * $a_numer / $denom + B_COST * $b_numer / $denom); }

There are other ways to get to this. For example, you could use Linear Algebra, and express things as `Ax = T` with matrices:

[91 22] [a] = [8400] [34 67] [b] [5400]

Then `x = A`^(-1) `* T` (after multiplying both sides by A^(-1) on the left). This is easy to solve if you remember the formula for the inverse of a 2x2:

-1 [ a b ] = 1 [ d -b ] [ c d ] --------- [-c a ] ad - bc

Note: the determinant = ad-bc, so constant in front is 1/det(A).

The nice thing about this problem is that this just works... none of the determinants for the button pushes is zero (and so this gives the unique solution, you just need to verify if it is integer). In serious code you'd need to protect against and handle that stuff. For AoC, I ran it and saw no division-by-zero errors pop up and submitted the answer. Because things turning out surprisingly nice isn't so surprising in AoC.

Of course this is a simple formula, so once we get rid of the non-digits in the input, dc can handle it easily (it also doesn't have negatives to worry about converting):

tr -c '[0-9]' ' ' <input | dc -e'?10000000000000' -e'so[dlar/3*rlbr/+ls+ss0]sS[lo+sylo+sxdlx*3Rdly*3Rr-sa3Rdlx*5Rdly*3R-sb4R*_3R*-ddlar%rlbr%+0=Ss.z0<M]dsMxlsp'

The use of `?` here is just to slurp the entire input in (tr is also replacing the newlines here) before putting the amount to shift the targets on top (change that to 0 for part 1), and so will work still with the new dc. Nothing really fancy here.

And so, this was a light algebra problem, very suitable for a day 13.