Applying Cramer’s Rule for Advent of Code 2024, day 13

Day 13 is relatively easy, especially if you’re comfortable with math. I originally started with a purely brute-force approach, but it quickly became clear that it would be inefficient as the difficulty increased. When I attempted the puzzle, I was already a few days behind. After a hint from a friend who was keeping up with the daily challenges, I looked into Cramer’s rule to find a solution.

A cute claw machine generated by Microsoft Copilot

As this is an Advent of Code puzzle, it’s no surprise that we’re not dealing with an ordinary claw machine. Instead, we have two buttons, labelled A and B, that move the claw in specific directions. The cost to press each button also varies.

Overall, this puzzle isn’t too challenging, provided you use the correct mathematical approach. We’ll begin by parsing the puzzle input:

COST_A = 3
COST_B = 1

type Point = tuple[int, int]
type Vector = tuple[int, int]


def extract_vector(input: str) -> Vector:
    return tuple(int(item.strip().lstrip("X").lstrip("Y")) for item in input.split(","))  # type: ignore


def extract_point(input: str) -> Point:
    return tuple(
        int(item.strip().lstrip("X=").lstrip("Y=")) for item in input.split(",")
    )  # type: ignore


def parse(
    input: str, cost_a: int = COST_A, cost_b: int = COST_B
) -> tuple[tuple[dict[Vector, int], Point], ...]:
    result = ()
    button, goal = {}, ()

    for line in input.strip().splitlines():
        if line.startswith("Button A:"):
            button[extract_vector(line.partition(":")[-1])] = cost_a
        elif line.startswith("Button B:"):
            button[extract_vector(line.partition(":")[-1])] = cost_b
        elif line.startswith("Prize:"):
            goal = extract_point(line.partition(":")[-1])
        else:
            result += ((button, goal),)

            button, goal = {}, ()

    return result + ((button, goal),)  # type: ignore

I’ve recently started adding type annotations to my code. While these don’t improve runtime performance, they’re incredibly helpful, especially when using an editor with good type hinting. It can be tedious to repeatedly type complex types like tuple[int, int] (used here for points and vectors) and dict[tuple[int, int], int] (which maps vectors to costs). Fortunately, Python 3.12 introduced the ability to declare type aliases, like this:

type Point = tuple[int, int]
type Vector = tuple[int, int]

This greatly improves the readability of the parsing functions. The parse function returns a tuple of tuples, where each inner tuple contains a button-cost mapping and the goal point.

Cramer’s Rule

To solve this problem efficiently, Cramer’s rule, a method well-suited for solving systems of two linear equations, is a great choice. In our case, we have two equations representing the X and Y movements of the claw:

The variables represent:

• a_1: X movement caused by pressing button A (and a_2 for button B).
• b_1: Y movement caused by pressing button A (and b_2 for button B).
• c_i: Target X and Y coordinates of the prize (combined with button movements in our specific case).
• x: Number of times button A is pressed.
• y: Number of times button B is pressed.

The puzzle provides an example where button A is pressed 80 times and button B is pressed 40 times for the first test input. We can use this information to verify that the movements translate into valid linear equations. The calculation of the resulting X and Y coordinates yields:

Now that we’ve verified that our problem can be represented with linear equations, we can rearrange them into a form suitable for applying Cramer’s rule to solve for the number of times to press each button. This involves expressing the equations in matrix form, Ax = B:

Where:

• A is the coefficient matrix.
• x is the column matrix containing the unknown number of times to press each button (A and B).
• B is the column matrix containing the target X and Y coordinates (or positions).

To apply Cramer’s rule, we first need to calculate the determinant of matrix A, which we’ll denote as D. The determinant of A, denoted using vertical bars around the matrix:

Applying the test values, we get

Next, we calculate the determinants D_x and D_y. To find D_x, we replace the first column of matrix A (the coefficients of x) with the constant matrix B. Similarly, to find D_y, we replace the second column of A (the coefficients of y) with B:

Applying the test case yields

Now that we have all the necessary determinants, we can determine the number of times to press buttons A (x) and B (y) using Cramer’s rule:

Now, we can calculate the number of times to press each button using Cramer’s rule:

Implementation

In our implementation, we’ll need a function to calculate the determinant of a 2x2 matrix. We’ll represent the matrix as a dictionary where keys are tuples representing (row, column) indices, starting from (0,0), and values are the corresponding matrix elements. Here’s the function:

def determinant(matrix: dict[Point, int]) -> int:
    return matrix[(0, 0)] * matrix[(1, 1)] - matrix[(0, 1)] * matrix[(1, 0)]

This function takes the matrix represented as a dictionary and calculates the determinant using the standard formula for a 2x2 matrix. We use a dictionary for the matrix representation to allow for efficient lookup of elements by their row and column indices.

Now, let’s implement the core logic for solving the puzzle using Cramer’s rule. The find function takes the button movements and the target coordinates as input and returns the number of times each button needs to be pressed.

def find(
    buttons: dict[Vector, int],
    goal: Point,
) -> dict[tuple[int, int], int]:
    # apply cramer's rule
    # https://byjus.com/maths/cramers-rule/
    button_a, button_b = tuple(buttons.keys())
    result = {button_a: 0, button_b: 0}

    D = determinant(
        {
            (0, 0): button_a[0],
            (1, 0): button_a[1],
            (0, 1): button_b[0],
            (1, 1): button_b[1],
        }
    )
    Dx = determinant(
        {
            (0, 0): goal[0],
            (1, 0): goal[1],
            (0, 1): button_b[0],
            (1, 1): button_b[1],
        }
    )
    Dy = determinant(
        {
            (0, 0): button_a[0],
            (1, 0): button_a[1],
            (0, 1): goal[0],
            (1, 1): goal[1],
        }
    )

    if Dx % D == 0 and Dy % D == 0:
        result = {button_a: Dx // D, button_b: Dy // D}

    return result

The function first extracts the button movement vectors. Then, it calculates the determinants D, D_x, and D_y, as described in the previous section on Cramer’s rule. The key step here is constructing the matrices for these determinants using the button movements and the target coordinates. The function then checks if integer solutions exist (by checking divisibility by D) and calculates the number of button presses using integer division if they do. The result, a dictionary mapping button vectors to the number of presses, is then returned.

Now that we have most pieces implemented, it’s time to assemble the solution for Part 1, which calculates the total cost (tokens) to win across all claw machine configurations. It parses the input, uses find to determine button presses for each configuration, and sums the product of button costs and press counts:

def part1(input: str) -> int:
    return sum(
        buttons[button] * count
        for buttons, goal in parse(input)
        for button, count in find(buttons, goal).items()
    )

Part 2 adds 10 ** 13 to both the desired x and y coordinates. Because we’re using Cramer’s rule, this change is handled trivially by simply modifying the goal coordinates passed to the find function:

def part2(input: str) -> int:
    return sum(
        buttons[button] * count
        for buttons, goal in parse(input)
        for button, count in find(
            buttons,
            tuple(item + 10000000000000 for item in goal)
        ).items()
    )

While this puzzle wasn’t as challenging as some of the later Advent of Code problems, preparing this article proved to be considerably more demanding. I had to meticulously double-check the formulas to ensure accurate representation and frequently consult my notes to avoid errors. I definitely invested more time in writing this article than in solving the puzzle itself.

So, that’s it for this week’s coding adventure. If you’re searching for a software engineer to join your team, feel free to connect! For now, thanks for reading, and I shall write again, next week.