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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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?

I used zod to parse the inputs into structured data.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
const parser = z
    .array(z.string())
    .transform((values) => {
        const rounds = [];

        for (let i = 0; i < values.length; i += 4) {
            const buttonA = values[i]!;
            const buttonB = values[i + 1]!;
            const prize = values[i + 2]!;

            const buttonAMatch = buttonA.match(/X\+(\d+), Y\+(\d+)/)!;
            const buttonBMatch = buttonB.match(/X\+(\d+), Y\+(\d+)/)!;
            const prizeMatch = prize.match(/X=(\d+), Y=(\d+)/)!;

            const buttonAX = buttonAMatch[1];
            const buttonAY = buttonAMatch[2];

            const buttonBX = buttonBMatch[1];
            const buttonBY = buttonBMatch[2];

            const prizeX = prizeMatch[1];
            const prizeY = prizeMatch[2];

            rounds.push({
                aX: buttonAX,
                aY: buttonAY,
                bX: buttonBX,
                bY: buttonBY,
                prizeX,
                prizeY,
            });
        }

        return rounds;
    })
    .pipe(
        z.array(
            z.object({
                aX: z.coerce.number(),
                aY: z.coerce.number(),
                bX: z.coerce.number(),
                bY: z.coerce.number(),
                prizeX: z.coerce.number(),
                prizeY: z.coerce.number(),
            })
        )
    );

const values = parser.parse(input.split("\n"));

Once data is in a structured format, we can brute-force the solution by checking all possible combinations of button presses for every game. This only works because the search space is relatively low (100 * 100 = 10,000 possible combinations).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Brute-force check all possible combinations
let minTokens = Infinity;

// Decrement instead of increment, just to shake things up
for (let b = 100; b > 0; b -= 1) {
    for (let a = 100; a > 0; a -= 1) {
        const bXOffset = bX * b;
        const bYOffset = bY * b;

        const aXOffset = aX * a;
        const aYOffset = aY * a;

        if (bXOffset + aXOffset === prizeX && bYOffset + aYOffset === prizeY) {
            const tokens = b + 3 * a;

            if (tokens < minTokens) {
                minTokens = tokens;
            }
        }
    }
}

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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?

The zod parser for Part 2 is nearly identical to Part 1, but we add 10000000000000 to the prize coordinates.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
const parser = z
    .array(z.string())
    .transform((values) => {
        const rounds = [];

        for (let i = 0; i < values.length; i += 4) {
            const buttonA = values[i]!;
            const buttonB = values[i + 1]!;
            const prize = values[i + 2]!;

            const buttonAMatch = buttonA.match(/X\+(\d+), Y\+(\d+)/)!;
            const buttonBMatch = buttonB.match(/X\+(\d+), Y\+(\d+)/)!;
            const prizeMatch = prize.match(/X=(\d+), Y=(\d+)/)!;

            const buttonAX = buttonAMatch[1];
            const buttonAY = buttonAMatch[2];

            const buttonBX = buttonBMatch[1];
            const buttonBY = buttonBMatch[2];

            const prizeX = prizeMatch[1];
            const prizeY = prizeMatch[2];

            rounds.push({
                aX: buttonAX,
                aY: buttonAY,
                bX: buttonBX,
                bY: buttonBY,
                prizeX,
                prizeY,
            });
        }

        return rounds;
    })
    .pipe(
        z.array(
            z.object({
                aX: z.coerce.number(),
                aY: z.coerce.number(),
                bX: z.coerce.number(),
                bY: z.coerce.number(),
                prizeX: z.coerce.number().transform((value) => value + 10000000000000),
                prizeY: z.coerce.number().transform((value) => value + 10000000000000),
            })
        )
    );

const values = parser.parse(input.split("\n"));

The search space is far too large to brute-force the solution here. Instead, I used z3-solver to solve this.

Please note that the code below does NOT include the setup for z3-solver. If you're interested in how to get z3-solver working in your Next.js application, check out this blog post I've written.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const a = Int.const("a");

const b = Int.const("b");

const solver = new Solver();

solver.add(a.ge(0));
solver.add(b.ge(0));

// (a * aX) + (b * bX) = prizeX
solver.add(a.mul(aX).add(b.mul(bX)).eq(prizeX));

// (a * aY) + (b * bY) = prizeY
solver.add(a.mul(aY).add(b.mul(bY)).eq(prizeY));

const result = await solver.check();

if (result === "sat") {
    // Result found!
    const model = solver.model();
    const aPresses = z.coerce.number().parse(model.get(a).toString());
    const bPresses = z.coerce.number().parse(model.get(b).toString());

    const tokens = aPresses * 3 + bPresses;
}

To learn more about how this works, check the recap below.

I knew immediately that this was a systems of equations problem, just like the Advent of Code 2023 Day 24 problem.

I chose to brute-force Part 1 because I really didn't want to integrate a system of equations solver into my blog. When I saw Part 2, I knew there was no other choice.

I initially tried to use Math.js for this. Math.js provides numerous functions for solving systems of equations, but none of them worked for my use case. Specifically, I needed integer results, not floating-point results. I spent the better part of an hour trying to get Math.js configured and working, but to no avail.

After an hour of struggling with Math.js, I looked back at z3-solver. I used z3-solver last year while I was doing Advent of Code with Python, but I saw that the tool provides an npm package with JavaScript/TypeScript bindings to WASM. The setup for z3-solver in React/TypeScript/Next.js is midly challenging. If you're interested, check out this blog post I've written.

The equations we're solving for are fairly simple. Let's use this example:

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

Ultimately, we want to solve for the number of tokens used. Notably, the number of tokens used isn't outright defined in our equations, but derived from the results. Instead, we're solving for the number of presses for buttons A and B.

We're solving for two variables (# Button A Presses and # Button B Presses). Using a system of equations, we need two equations using these two variables. Fortunately, we have those!

To solve for these variables, we need to split our locations into their X and Y components:

In these equations, we have a few constants for each game we play. Using our example above, our constants are:

We can plug these constants into our equations:

Using z3-solver, we can then add these constraints into our solver:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// # A presses
const a = Int.const("a");

// # B presses
const b = Int.const("b");

const solver = new Solver();

// Cannot have "negative" button presses
solver.add(a.ge(0));
solver.add(b.ge(0));

// (a * aX) + (b * bX) = prizeX
solver.add(a.mul(94).add(b.mul(22)).eq(8400));

// (a * aY) + (b * bY) = prizeY
solver.add(a.mul(34).add(b.mul(67)).eq(5400));

Once we've added constraints, we can run the solver:

1
const result = await solver.check();

And then check the results:

1
2
3
4
5
6
7
8
9
if (result === "sat") {
    // Result found!
    const model = solver.model();
    const aPresses = z.coerce.number().parse(model.get(a).toString());
    const bPresses = z.coerce.number().parse(model.get(b).toString());

    // Solve for # of tokens used
    const tokens = aPresses * 3 + bPresses;
}

z3-solver can output results as a string. We then use zod to parse these values as numbers and solve for the number of tokens used.

If result !== "sat", then there's no valid solution for our constraints, so we can ignore that game.