Advent of Code 2024 Day 13

Day 13: Claw Contraption

https://adventofcode.com/2024/day/13

Another day, another familiar location.

Today’s input is the behaviour of a bunch of arcade claw machines.

An example input looks like this:

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

Each block of input represents one machine. Their grippers all move on a 2D-plane directly above the prize.

Each machine has 2 buttons, which each move the gripper some direction in the x and y axis.

The 3 lines per machine tell you:

1. What pressing A does to the gripper coordinates
2. What pressing B does to the gripper coordinates
3. The coordinates of the prize

The goal is to place the gripper directly over the prize. You do this by pressing the A and B button a number of times.

Parsing

If you’ve been following along, you know what I do when I see a puzzle with coordinates by now, Point!

Point

#[derive(PartialEq, Eq)]
struct Point {
    x: i64,
    y: i64,
}

impl Point {
    fn new(x: i64, y: i64) -> Self {
        Self { x, y }
    }
}

I stored each machine as a 3-item array of Points.

use itertools::Itertools;

fn parse(input: &str) -> Vec<[Point; 3]> {
    let mut machines = Vec::new();
    for block in input.split("\n\n") {
        let (adx, ady, bdx, bdy, x, y) = block
            .split(|c: char| !c.is_ascii_digit())
            .filter(|s| !s.is_empty())
            .map(|s| s.parse().unwrap())
            .collect_tuple()
            .unwrap();
        let a = Point::new(adx, ady);
        let b = Point::new(bdx, bdy);
        let prize = Point::new(x, y);
        machines.push([a, b, prize]);
    }
    machines
}

Part 1

• Pressing the A button costs 3 tokens.
• Pressing the B button costs 1 token.

Don’t overthink why, the answer is ✨reasons✨.

The question asks for sum of the lowest cost for all winnable machines.

This is a system of 2 linear equations.

Variable definitions:

• $a_n$ The amount of times button A is pressed
• $b_n$ The amount of times button B is pressed
• $a_x$ The change in x coordinate pressing A causes
• $a_y$ The change in y coordinate pressing A causes
• $b_x$ The change in x coordinate pressing B causes
• $b_y$ The change in y coordinate pressing B causes
• $p_x$ The x coordinate of the prize
• $p_y$ The y coordinate of the prize

The 2 equations describe which x and y coordinate the gripper has after n presses. This location should be equal to the location of the prize to win:

1. $a_n * a_x + b_n * b_x = p_x$
2. $a_n * a_y + b_n * b_y = p_y$

Solving for $a_n$ first. By multiplying both sides of each equation so the $b_n$ term cancels out when I subtract the 2 equations from eachother:

1. the top is multiplied by $b_y$
2. the bottom is multiplied by $b_x$

Isolating $a_n$ as that is the only unknown, all other variables can be replaced by numbers.

After calculating the amount of times A should be pressed, calculate the amount of times B should be pressed. I did this by replacing $a_n$ by its value in one of the original functions.

Now that we have the amount of times to press the A button and the amount of times to press the B button, we need to check if those numbers make sense. After all, when dealing with 2 linear equations there are 3 possibilities:

1. They intersect once
2. They are parallel and never intersect
3. They represent the same line, overlap, so intersect infinitely many times

Luckily, this question never runs in to option 2 or 3. Because the puzzlemaster decided to be kind today.

But there is still an extra option I have to handle, I’m not magic and can not press a button a fractional amount of times. (bummer, I know)

So in the code, I check if the position the gripper reaches after $a_n$ A presses and $b_n$ B presses is the same as the position of the prize.

If it is, I return a successful result with a price of $3 * a_n + 1 * b_n$.

Helpers

Coding that math into a function.

It returns something when the found intersection of the 2 lines is the same as the location of the prize.
If the intersection exists, but is not reachable in whole button presses, the function returns nothing.

fn solve(a: Point, b: Point, prize: Point) -> Option<i64> {
    // lines are never parallel in this question
    assert!(((a.y as f64 / a.x as f64) - (b.y as f64 / b.x as f64)).abs() > f64::EPSILON);

    let na = ((prize.x * b.y) - (prize.y * b.x)) / ((a.x * b.y) - (a.y * b.x));
    let nb = (prize.x - na * a.x) / b.x;
    let solution = Point::new(na * a.x + nb * b.x, na * a.y + nb * b.y);
    (solution == prize).then_some(3 * na + nb)
}

Code

A short function because of the helper functions again.

• Parse the input into a list of [A, B, Prize] points.
• Solve using that combination of Points
• If solveable: add the solution cost to the sum

fn part_1(input: &str) -> i64 {
    parse(input)
        .into_iter()
        .filter_map(|[a, b, prize]| solve(a, b, prize))
        .sum()
}

Part 2

Woopsie, small mistake. The prize coordinates are both (x and y) 10 trillion less than what they should have been.

const TEN_TRILLY: i64 = 10_000_000_000_000;
pub fn part_2(input: &str) -> i64 {
    parse(input)
        .into_iter()
        .filter_map(|[a, b, mut prize]| {
            prize.x += TEN_TRILLY;
            prize.y += TEN_TRILLY;
            solve(a, b, prize)
        })
        .sum()
}

Final code

1
use itertools::Itertools;
2

3
#[derive(PartialEq, Eq)]
4
struct Point {
5
    x: i64,
6
    y: i64,
7
}
8

9
impl Point {
10
    fn new(x: i64, y: i64) -> Self {
11
        Self { x, y }
12
    }
13
}
14

15
fn parse(input: &str) -> Vec<[Point; 3]> {
16
    let mut machines = Vec::new();
17
    for block in input.split("\n\n") {
18
        let (adx, ady, bdx, bdy, x, y) = block
19
            .split(|c: char| !c.is_ascii_digit())
20
            .filter(|s| !s.is_empty())
21
            .map(|s| s.parse().unwrap())
22
            .collect_tuple()
23
            .unwrap();
24
        let a = Point::new(adx, ady);
25
        let b = Point::new(bdx, bdy);
26
        let prize = Point::new(x, y);
27
        machines.push([a, b, prize]);
28
    }
29
    machines
30
}
31

32
fn solve(a: Point, b: Point, prize: Point) -> Option<i64> {
33
    // lines are never parallel in this question
34
    assert!((a.y as f64 / a.x as f64) != (b.y as f64 / b.x as f64));
35

36
    let na = ((prize.x * b.y) - (prize.y * b.x)) / ((a.x * b.y) - (a.y * b.x));
37
    let nb = (prize.x - na * a.x) / b.x;
38
    let solution = Point::new(na * a.x + nb * b.x, na * a.y + nb * b.y);
39
    (solution == prize).then_some(3 * na + nb)
40
}
41

42
pub fn part_1(input: &str) -> i64 {
43
    parse(input)
44
        .into_iter()
45
        .filter_map(|[a, b, prize]| solve(a, b, prize))
46
        .sum()
47
}
48

49
const TEN_TRILLY: i64 = 10_000_000_000_000;
50
pub fn part_2(input: &str) -> i64 {
51
    parse(input)
52
        .into_iter()
53
        .filter_map(|[a, b, mut prize]| {
54
            prize.x += TEN_TRILLY;
55
            prize.y += TEN_TRILLY;
56
            solve(a, b, prize)
57
        })
58
        .sum()
59
}