Advent of Code 2024 Day 13

Parsing

Parsing is somewhat complicated for this day. The input is a list of descriptions of claw machines. We create a struct to store the numbers for each machine in a organized and readable manner. We use a lot of string splits to extract the numbers from the input.

#[derive(Clone, Debug, PartialEq, Eq)]
struct Machine {
    a_x: i64,
    a_y: i64,

    b_x: i64,
    b_y: i64,

    prize_x: i64,
    prize_y: i64,
}

fn parse_input(s: String) -> Vec<Machine> {
    s.trim().split("\n\n").map(parse_machine).collect()
}

fn parse_machine(s: &str) -> Machine {
    let mut lines = s.trim().lines();
    let first_line = lines.next().unwrap();
    let second_line = lines.next().unwrap();
    let third_line = lines.next().unwrap();

    let mut first_line = first_line.split_once(':').unwrap().1.split(',').map(|num| {
        num.trim_matches(|ch: char| !ch.is_ascii_digit())
            .parse()
            .unwrap()
    });
    let a_x = first_line.next().unwrap();
    let a_y = first_line.next().unwrap();

    let mut second_line = second_line
        .split_once(':')
        .unwrap()
        .1
        .split(',')
        .map(|num| {
            num.trim_matches(|ch: char| !ch.is_ascii_digit())
                .parse()
                .unwrap()
        });
    let b_x = second_line.next().unwrap();
    let b_y = second_line.next().unwrap();

    let mut third_line = third_line.split_once(':').unwrap().1.split(',').map(|num| {
        num.trim_matches(|ch: char| !ch.is_ascii_digit())
            .parse()
            .unwrap()
    });
    let prize_x = third_line.next().unwrap();
    let prize_y = third_line.next().unwrap();

    return Machine {
        a_x,
        b_x,
        a_y,
        b_y,
        prize_y,
        prize_x,
    };
}

Part One

We control claw machines by pressing buttons where button presses cost us tokens. The two buttons, A and B move the claw a certain number of units in the X and Y directions, each machine having different numbers. Pressing A costs 3 tokens while pressing B costs 1 token. The prize of a claw machine is obtained by moving the claw directly over the prize coordinates. Some of the machines are also unwinnable.

We need to find the number of tokens need to win as many prizes as possible. The problem also restricts us to a maximum of 100 presses of either button, making for a simple brute force solution.

impl Machine {
    fn get_num_tokens(&self) -> i64 {
        for a_count in 0..=100 {
            for b_count in 0..=100 {
                if (a_count * self.a_x + b_count * self.b_x == self.prize_x)
                    && (a_count * self.a_y + b_count * self.b_y == self.prize_y)
                {
                    return a_count * 3 + b_count * 1;
                }
            }
        }
        0
    }
}

fn part1(input: &Vec<Machine>) -> i64 {
    input.iter().map(Machine::get_num_tokens).sum()
}

Part Two

Now, due to a unit conversion error, the actual locations of the prizes are 10 trillion higher in both directions. This means that we are no longer limited to 100 button presses and need many more presses, making our original brute force solution ineffective.

The key to solving this is to realize that each claw machine description represents a system of two linear equations in two variables. If we take x₁, x₂, and x₃ to be the A button X delta, the B button X delta and the prize X respectively, let y₁, y₂ and y₃ be defined similarily for Y, and n₁ and n₂ to be the number of A presses and B presses respectively, we get the following system of equations.

Plugging this into Wolfram-Alpha, we get the following solution:

We can convert this back to code to get our solution for part two. Note that since we are using integers and because integer division has no fractional part that would indicate a unwinnable machine we verify that our calculated answer is correct before returning the number of tokens.

impl Machine {
    fn get_num_tokens_p2(&self) -> i64 {
        const OFFSET: i64 = 10000000000000;
        let prize_x = self.prize_x + OFFSET;
        let prize_y = self.prize_y + OFFSET;
        let Machine {
            a_x, a_y, b_x, b_y, ..
        } = self.clone();

        // Taken from https://www.wolframalpha.com/input?i=x_1*n_1%20%2B%20x_2*n_2%20%3D%20x_3%3B%20y_1*n_1%2By_2*n_2%20%3D%20y_3find%20n_1%20and%20n_2
        let a_count = (prize_x * b_y - b_x * prize_y) / (a_x * b_y - b_x * a_y);
        let b_count = (prize_x * a_y - a_x * prize_y) / (b_x * a_y - a_x * b_y);

        if (a_count * a_x + b_count * b_x == prize_x)
            && (a_count * a_y + b_count * b_y == prize_y)
        {
            a_count as i64 * 3 + b_count as i64 * 1
        } else {
            0
        }
    }
}

fn part2(input: &Vec<Machine>) -> i64 {
    input.iter().map(Machine::get_num_tokens_p2).sum()
}