≡ Day 13 of Advent of Code in q

Author - Rory Kemp

--- Day 13: Claw Contraption ---
Next up: the lobby of a resort on a tropical island. The Historians take a moment to admire the hexagonal floor tiles before spreading out.

Fortunately, it looks like the resort has a new arcade! Maybe you can win some prizes from the claw machines?

The claw machines here are a little unusual. Instead of a joystick or directional buttons to control the claw, these machines have two buttons labeled A and B. Worse, you can't just put in a token and play; it costs 3 tokens to push the A button and 1 token to push the B button.

With a little experimentation, you figure out that each machine's buttons are configured to move the claw a specific amount to the right (along the X axis) and a specific amount forward (along the Y axis) each time that button is pressed.

Each machine contains one prize; to win the prize, the claw must be positioned exactly above the prize on both the X and Y axes.

You wonder: what is the smallest number of tokens you would have to spend to win as many prizes as possible? You assemble a list of every machine's button behavior and prize location (your puzzle input). For example:
Button A: X+94, Y+34
Button B: X+22, Y+67
Prize: X=8400, Y=5400

Button A: X+26, Y+66
Button B: X+67, Y+21
Prize: X=12748, Y=12176

Button A: X+17, Y+86
Button B: X+84, Y+37
Prize: X=7870, Y=6450

Button A: X+69, Y+23
Button B: X+27, Y+71
Prize: X=18641, Y=10279
This list describes the button configuration and prize location of four different claw machines.

For now, consider just the first claw machine in the list:

Pushing the machine's A button would move the claw 94 units along the X axis and 34 units along the Y axis.

Pushing the B button would move the claw 22 units along the X axis and 67 units along the Y axis.

The prize is located at X=8400, Y=5400; this means that from the claw's initial position, it would need to move exactly 8400 units along the X axis and exactly 5400 units along the Y axis to be perfectly aligned with the prize in this machine.

The cheapest way to win the prize is by pushing the A button 80 times and the B button 40 times. This would line up the claw along the X axis (because 80*94 + 40*22 = 8400) and along the Y axis (because 80*34 + 40*67 = 5400). Doing this would cost 80*3 tokens for the A presses and 40*1 for the B presses, a total of 280 tokens.

For the second and fourth claw machines, there is no combination of A and B presses that will ever win a prize.

For the third claw machine, the cheapest way to win the prize is by pushing the A button 38 times and the B button 86 times. Doing this would cost a total of 200 tokens.

So, the most prizes you could possibly win is two; the minimum tokens you would have to spend to win all (two) prizes is 480.

You estimate that each button would need to be pressed no more than 100 times to win a prize. How else would someone be expected to play?

Figure out how to win as many prizes as possible. What is the fewest tokens you would have to spend to win all possible prizes?

Because this is Advent of Code, and we can be lazy with parsing properly, let's mask out anything that isn't a number, and use get, which will conveniently ignore spaces.

show i: get 0N!.Q.n .Q.n?0N!"c"$read1 `13.txt
"Button A: X+94, Y+34\nButton B: X+22, Y+67\nPrize: X=8400, Y=5400\n\nButton ..
"            94    34             22    67          8400    5400             ..
94 34 22 67 8400 5400 26 66 67 21 12748 12176 17 86 84 37 7870 6450 69 23 27 ..

Now, we want to reshape our long list of numbers into groups of 6, and each of those groups of 6 into 3 groups of 2.

show cases: 3 2#/:0N 6#i
94   34     22   67     8400 5400  
26    66    67    21    12748 12176
17   86     84   37     7870 6450  
69    23    27    71    18641 10279

Essentially, the problem asks us to solve a simultaneous equation.

We are given two vectors A and B, and a vector P, and asked to solve for x and y such that Ax + By = P.

This can be done in many ways, but one of the simplest is using Cramer's rule.

It sounds slightly scary, with big words like "determinant", but for this case with only two variables, it's straightforward enough.

First of all, we will need a function to calculate the determinant of a 2x2 matrix. The inputs will be two columns.

det:{(-) . x*reverse y}

Now, to solve our equation, the results can be expressed in terms of determinants.

{(det[z;y]; det[x;z]) % det[x;y]} ./: cases 
80       40      
141.4045 135.3953
38       86      
244.5016 65.56989

We can see that some are integers, which we will keep, and others are decimals, which will be discarded. The easiest way to do this is to check that the remainder is 0.

{n:(det[z;y]; det[x;z]); d:det[x;y]; $[all 0=n mod d; n div d; 0]} ./: cases 
80 40
0
38 86
0

We're told the cost in "tokens" is equal to 3 times the first value plus the second value.

tokens: {n:(det[z;y]; det[x;z]); d:det[x;y]; $[all 0=n mod d; sum 3 1*n div d; 0]}

So the result of part 1 is the sum of all token costs.

sum 0N!tokens ./: cases
280 0 200 0
480

Part 2:

Part 2 Original Description:

--- Part Two ---
As you go to win the first prize, you discover that the claw is nowhere near where you expected it would be. Due to a unit conversion error in your measurements, the position of every prize is actually 10000000000000 higher on both the X and Y axis!

Add 10000000000000 to the X and Y position of every prize. After making this change, the example above would now look like this:
Button A: X+94, Y+34
Button B: X+22, Y+67
Prize: X=10000000008400, Y=10000000005400

Button A: X+26, Y+66
Button B: X+67, Y+21
Prize: X=10000000012748, Y=10000000012176

Button A: X+17, Y+86
Button B: X+84, Y+37
Prize: X=10000000007870, Y=10000000006450

Button A: X+69, Y+23
Button B: X+27, Y+71
Prize: X=10000000018641, Y=10000000010279
Now, it is only possible to win a prize on the second and fourth claw machines. Unfortunately, it will take many more than 100 presses to do so.

Using the corrected prize coordinates, figure out how to win as many prizes as possible. What is the fewest tokens you would have to spend to win all possible prizes?

We now need to add 10000000000000 to the prize locations.

Luckily, as we have a closed form for the solution, this doesn't impact runtime.

sum tokens ./: cases +\: 0 0 10000000000000
875318608908

Recap:

The full solution is this.

cases:3 2#/:0N 6#get .Q.n@.Q.n?"c"$read1 `13.txt
det:{(-). x*reverse y}
tokens: {n:(det[z;y]; det[x;z]); d:det[x;y]; (all 0=n mod d)*sum 3 1*n div d}
sum tokens ./: cases
sum tokens ./: cases +\: 0 0 10000000000000