The Claaaaww!

AoC challenges like today's are probably my favourites: I was reading the specs while still in bed, and I already had the complete theoretical solution in my mind, way before accessing my laptop to implement it.

We are in an arcade with several claw machines (yes, I thought all along that the goal was to recover all the green aliens from Toy Story). Each machine has two buttons configured to move the claw ("THE CLAAAAWW!" 😮) a specific amount to the right and forward, such as

Button A: X+94, Y+34
Button B: X+22, Y+67

Then we have our prize to recover located at a specific coordinate on the grid, like Prize: X=8400, Y=5400. The goal is to find the minimum amount of button presses to move the claw and reach the location of the prize.

... Yes, if you have any memory at all of the maths classes in high school, it's kinda obvious: each claw machine's solution is no more and no less than a system of equations, where the values solving the equations are the number of presses for each of the buttons.

For example a system can be composed as follows:

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

| 94a + 22b = 8400
| 34a + 67b = 5400

Solving it we obtain a = 80 and b = 40, meaning that we need to press Button A 80 times and Button B 40 times in order to reach the prize's exact position. It's also possible that no integer solution exists for the system, in which cases we can't sadly obtain the prize (imagine pressing the buttons exactly 42.63467 times 🤪).

I must say a good 80% of the overall time spent on this problem was wasted parsing the input and then finding a decent JS library to solve the equations - eventually I opted for ml-matrix, the most basic I could find that did the work nicely.

function playAllMachines(clawMachines: ClawMachine[]): number {
    let totalTokens = 0;

    clawMachines.forEach((clawMachine) => {
        const { buttonA, buttonB, prize } = clawMachine;

        const coeffMatrix = new Matrix([
            [buttonA.x, buttonB.x],
            [buttonA.y, buttonB.y],
        ]);

        const resultsVector = Matrix.columnVector([prize.x, prize.y]);

        const solution = solve(coeffMatrix, resultsVector)
            .to1DArray()
            .map((v) => roundCloseToInteger(v));
        if (solution[0] && solution[1]) {
            totalTokens += solution[0] * 3 + solution[1] * 1;
        }
    });

    return totalTokens;
}

For once, part 2 was trivial with the algorithm I had created, since the only difference is the position of the prize got shifted by 10000000000000 (still haven't figured what that number is, but I don't really care) for both X and Y - nothing that my function cannot easily solve 😎

The one hiccup I had is the reason behind that roundCloseToInteger function towards the end: since computers handle numerical calculations using floating-point arithmetic, this introduces small rounding errors. Even though the underlying math is correct, these small errors can lead to results like 39.99999 instead of 40. Therefore, a function like the following helps deal with such cases: if the difference between the result and the rounded number is small enough, we can indeed round it to the nearest integer, at least for the purpose of this challenge.

function roundCloseToInteger(num: number, tolerance = 1e-4) {
    const nearestInt = Math.round(num);
    if (Math.abs(num - nearestInt) <= tolerance) {
        return nearestInt;
    }
    return undefined;
}

So yeah, my problems originated from the tolerance being too low (like 1e-9) at the beginning, which resulted in a "Your number is too low" message when submitting my answer the first time 🤦‍♀️ Making the function a bit more lenient fortunately solved it all.

You know what? With this 26th star we're already past the 50% mark! 🤩