Advent of Code Day 13 was by far the most fun day for me as, as you might guess, I was able to figure out what the puzzle was hinting at from the get go. Let’s dive in!

---

The below is a guest post by the amazing Shraddha Agrawal.

---

Part 1

The puzzle is posed as solving a claw machine but programmatically. We are given the target coordinates, and how far the claw would move on X and Y axis when Button A and B are pressed.

Each configuration input looks like this:

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

In the above example, the target coordinates are (8400, 5400). Pressing button A we increment X by 94 and Y by 34. Pressing button B we increment X by 22 and Y by 67.

We need to:

1. Figure out if there are possible values of button pushes to A and B to reach the target.
2. If yes, we need to find the least value possible for the respective button pushes to reach the target.

Pressing button A costs 3 token and pressing button B costs 1 token. Answer for part 1 is the total number of tokens to win the prizes for all possible input configurations.

Solution

For the above example, the problem statement states that if Button A is pressed 80 times and Button B is pressed 40 times, we can arrive at the target. It was displayed like this:

• 80*94 + 40*22 = 8400
• 80*34 + 40*67 = 5400

Looking at the above, ringed a bell! Do you notice something?

Let’s supposed the number of button pushed for Button A is A and for Button B is B. Then the above can be written as:

• 94A + 22B = 8400
• 34A + 67B = 5400

Above is simply a pair of linear equations with 2 variables! Solving this we can find the values of button pushed needed for each button. The prize is only reachable if:

• Values of A and B are both whole number. (We can’t press a button in fractions)
• Values of A and B are positive.

Using Crammer’s Rule we can find values for A and B. Writing a function for it:

// solveLinearEquation accepts the coeffecients of two linear equations:
//
//	a1x + b1y = c1
//	a2x + b2y = c2
//
// the function retruns two values:
//
// boolen - to indicate if the value of X and Y are whole numbers or not.
// coordinates - actual values for X and Y
func SolveLinearEquation(a, b, c Coordinates) (bool, Coordinates) {
	x := ((b.X * (-c.Y)) - (b.Y * (-c.X))) / ((a.X * b.Y) - (a.Y * b.X))
	y := (((-c.X) * a.Y) - ((-c.Y) * a.X)) / ((a.X * b.Y) - (a.Y * b.X))
	if (((b.X*(-c.Y))-(b.Y*(-c.X)))%((a.X*b.Y)-(a.Y*b.X)) == 0) &&
		((((-c.X)*a.Y)-((-c.Y)*a.X))%((a.X*b.Y)-(a.Y*b.X)) == 0) {
		return true, Coordinates{x, y}
	}
	return false, Coordinates{x, y}
}

Now we just need to call the above function for each input configuration, and get the number of tokens required. Note: a single button press for Button A takes 3 tokens and for Button B a single token.

func getTokenCount(input [][]aoc.Coordinates) (int, int) {
	count1 := 0
	for _, prize := range input {
		isValid1, tokens1 := aoc.SolveLinearEquation(prize[0], prize[1], prize[2])
		if isValid1 {
			count1 += tokens1.X*3 + tokens1.Y
		}
	}
	return count1
}

And the above count is the final answer for part 1.

Part 2

Now, each target coordinates should be incremented by 10000000000000, essentially to make brute force not reasonable.

So the above example where initially the target coordinates were (8400, 5400) now becomes (10000000008400,10000000005400).

Again, we need to find if the configuration is valid, and if so get the count of tokens needed for all.

Solution

Since we are solving a pair of linear equations, all we need to do is change the constants in each equation. We can do so by simply modifying the constants before calling the function to solve the linear equations:

func getButtonPressesIfValid(a, b, final aoc.Coordinates, add int) (bool, aoc.Coordinates) {
	final.X += add
	final.Y += add
	return aoc.SolveLinearEquation(a, b, final)
}

And using the same function above, we can calculate the total number of tokens needed, for both part 1 and 2:

func getTokenCount(input [][]aoc.Coordinates) (int, int) {
	count1, count2 := 0, 0
	for _, prize := range input {
		isValid1, tokens1 := getButtonPressesIfValid(prize[0], prize[1], prize[2], 0)
		if isValid1 {
			count1 += tokens1.X*3 + tokens1.Y
		}

		isValid2, tokens2 := getButtonPressesIfValid(prize[0], prize[1], prize[2], 10000000000000)
		if isValid2 {
			count2 += tokens2.X*3 + tokens2.Y

		}
	}
	return count1, count2
}

And that’s it! You can find my final code here.

I absolutely loved this high school math refresher! What a nice simple puzzle making use of math.

How did you approach Day 13? I would love to compare notes and checkout your solution. Reach out to me on Twitter, Bluesky or on e-mail at contact[at]shraddhaag[dot]dev.