I did not solve today’s puzzle on my own, pretty much at all. Let’s talk about that before we go into the solution.
Today’s puzzle involved a toy claw machine and two buttons that move the claw different amounts towards the target. We start from (0, 0) and our goal is to reach (target_x, target_y) by moving along the path with steps of either (A_x, A_y) or (B_x, B_y).
To add to the mix, pressing the button labeled A costs 3 tokens and B costs just 1. The goal is to find the cheapest way to reach the end.
It’s a math puzzle, through and through.
And here lies my issue with it: it’s been a while since I’ve been to a math class and I severe lack the mental knowledge base required to be able to go “Ah, I see this is problem of type Z, therefore the solution calls for K o L”. I do have that for many of the other types of puzzles present at Advent of Code but not with math puzzles.
After a really bad attempt at solving the first part by following every branching path after every button press and the code not reaching a solution in any kind of meaningful time, I decided I approach today differently.
I decided to approach it purely as an opportunity to learn how to solve this kind of puzzle. So while I ended up with two stars today, they are different kinds of stars. They are stars that at best signify a moment of learning, although I’m not sure how much of that I managed to achieve either. A star that was achieved by learning something is definitely no dimmer than a star that was solved all by my own. Today I’m not sure if I gained much new wisdom though.
I tried to ask around and while I got helpful solution ideas, I wasn’t able to find a more in-depth wisdom about how would someone like me who cannot deduce the mathematical concept required from the puzzle description, get towards solving this type of puzzle.
I also tried my hand at adding types to my Python code.
Read input
We have a multi-section input with each claw machine spread to three lines, separated by an empty space.
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=10279I have a multi-section input reader ready in my utility belt for these kinds of puzzles:
re_button = re.compile(r"Button (?P<button>[AB]): X\+(?P<x>\d+), Y\+(?P<y>\d+)")
re_prize = re.compile(r"Prize: X=(?P<x>\d+), Y=(?P<y>\d+)")
Button = namedtuple("Button", ["name", "x", "y", "cost"])
Prize = namedtuple("Prize", ["x", "y"])
Machine = namedtuple("Machine", ["A", "B", "prize"])
def map_fn(section: str) -> Machine:
lines = section.split("\n")
a_button = re.match(re_button, lines[0]).groupdict()
a_button = Button(a_button["button"], int(a_button["x"]), int(a_button["y"]), 3)
b_button = re.match(re_button, lines[1])
b_button = Button(b_button["button"], int(b_button["x"]), int(b_button["y"]), 1)
prize = re.match(re_prize, lines[2].strip()).groups()
prize = Prize(int(prize[0]), int(prize[1]))
return Machine(a_button, b_button, prize)Since the machine descriptions are regular, it’s a prime use case for regular expressions.
Let’s talk about regular expressions a bit more today since I don’t have much to teach in terms of math.
The buttons come in following shape
Button A: X+94, Y+34
Button B: X+22, Y+67There are two types of things in each of these lines:
- static parts that don’t change, here those are
Button,:,X+and, Y+ - dynamic parts that do change from line to line, here those are
A(orB) and the numbers
To match anything static (or literal), we can write it as-is into our regex:
import re
re_button = re.compile(r"Button")
print(re.match(re_button, 'Button A: X+94, Y+34'))
# <re.Match object; span=(0, 6), match='Button'>Here, regex would match the literal string “Button” at the start of the string and tell us it was found between indices 0 and 6.
We know that the buttons are labeled either A or B and with the next part of our pattern we’ll do three things:
- match either
AorB([AB]) - capture the result of that match (
()) - give that capture group a name
?P<button>
re_button = re.compile(r"Button (?P<button>[AB])")
print(re.match(re_button, 'Button A: X+94, Y+34').groupdict())
# prints { 'button': 'A' }
print(re.match(re_button, 'Button B: X+22, Y+67').groupdict())
# prints { 'button': 'B' }When we use named groups, we gain access to groupdict() method that returns a dictionary of all the captured, named groups. Using named groups improves the readability a ton and reduces the likelihood of errors when we don’t have to deal with numerical indices.
Final part of the regular expression we use here is \d+ that we use twice:
re_button = re.compile(r"Button (?P<button>[AB]): X\+(?P<x>\d+), Y\+(?P<y>\d+)")\d is a special meta-character that matches any single digit. It’s the same as writing [0123456789] (using the same method we used with [AB]). When using the [] pattern, we can shortcut ranges with -: [0-9] matches any digit from 0 to 9. We could also say [A-Z] to match every capital letter between A and Z.
Putting these together, we get:
re_button = re.compile(r"Button (?P<button>[AB]): X\+(?P<x>\d+), Y\+(?P<y>\d+)")
print(re.match(re_button, 'Button A: X+94, Y+34').groupdict())
# Prints {'button': 'A', 'x': '94', 'y': '34'}We also take advantage of named tuples to give our data structures names and attributes to make it easier to read through the code:
Button = namedtuple("Button", ["name", "x", "y", "cost"])
Prize = namedtuple("Prize", ["x", "y"])
Machine = namedtuple("Machine", ["A", "B", "prize"])Part 1
In part 1, we have one restriction: each button can be pressed maximum 100 times.
To calculate the cost, we first check if the machine is winnable at all: if we press both buttons 100 times and still cannot reach either the x or y coordinate of the prize, we know it can’t win. Adding this check avoids 10 000 loops for each un-winnable machine, making the code run way faster.
For any winnable machine, we loop over each of the 100*100 combinations of pressing button A and button B, calculate the final position we end up with each combination. If that position is where the prize is, we calculate the total cost and return it:
def calculate_cost(machine: Machine) -> int:
"""Calculates the cost of finding the prize for a machine
or 0 if no solution is found in 100 presses for each button.
:param machine Machine for which to calculate the cost
:returns cost of finding the prize
"""
if 100 * machine.A.x + 100 * machine.B.x < machine.prize.x:
return 0
if 100 * machine.A.y + 100 * machine.B.y < machine.prize.y:
return 0
for a_presses in range(101):
for b_presses in range(101):
x = a_presses * machine.A.x + b_presses * machine.B.x
y = a_presses * machine.A.y + b_presses * machine.B.y
if (x, y) == machine.prize:
return machine.A.cost * a_presses + machine.B.cost * b_presses
return 0To calculate the total cost of winning loads of teddy bears from a bunch of machines, we calculate the cost and of each and sum them up.
def part_1():
machines = read_multisection_input(13, [map_fn])
cost = sum(calculate_cost(machine) for machine in machines)
print(f"Part 1: {cost}")Part 2
Part 2 is a classic Advent of Code second half twist: make the search space so large that looping through won’t cut it.
In part 2, we need to add 10_000_000_000_000 to the x and y position of every prize.
Tip
Did you know that in Python, you can add
_separators inside large integers to make them easier to read. Python ignores them when dealing with the number but it makes it nicer for the reader!
Like I wrote at the beginning, figuring out the math for the second part would have never happened if I had sat down alone at my computer.
Instead, let me show a couple of solutions I adapted from others as I was trying to teach myself something from those solutions.
First, Toni’s solution that simplifies (is that the right mathematical term? I’m not sure) the pair of equations to solve for a_presses and b_presses into a format where we can solve the amount of a_presses based on numbers we already know and then use that result to solve for b_presses.
His solution walks through how he reached that solution so check out the original solution from his GitHub.
def find_cheapest_win(machine: Machine) -> int:
"""Solution by lamperi: https://github.com/lamperi/aoc/blob/main/2024/13/solve.py"""
a_presses = (machine.A.x * machine.prize.y - machine.A.y * machine.prize.x) / (
machine.A.x * machine.B.y - machine.A.y * machine.B.x
)
b_presses = (machine.prize.x - a_presses * machine.B.x) / machine.A.x
if int(a_presses) == a_presses and int(b_presses) == b_presses:
return int(a_presses) + 3 * int(b_presses)
return 0From Wouter, I learned that there’s a library for symbolic mathematics called SymPy that can be used to solve multivariable equations. I generally try to avoid installing external libraries for my Advent of Code solutions but since today is a different day all together, I gave it a go:
import sympy
def find_cheapest_win(machine: Machine) -> int:
""" Solution adapted from Wouter's """
a_presses, b_presses = sympy.symbols('a_presses b_presses', integer=True)
equations = [
a_presses * machine.A.x + b_presses * machine.B.x - machine.prize.x,
a_presses * machine.A.y + b_presses * machine.B.y - machine.prize.y
]
solution = sympy.solve(equations)
if solution:
return machine.A.cost * solution[a_presses] + machine.B.cost * solution[b_presses]
return 0It’s quite a handy library - even though to be able to use it on my own, I’d first have to know what to solve for but at least I know have one more tool in my tool belt if need arises.
The wrapper for second part is similar to first one:
def part_2():
machines = read_multisection_input(13, [map_fn])
cost = 0
for machine in machines:
machine = Machine(
machine.A,
machine.B,
Prize(
machine.prize.x + 10_000_000_000_000,
machine.prize.y + 10_000_000_000_000,
),
)
cost += find_cheapest_win(machine)
print(f"Part 2: {cost}")PS. We had a great Advent of Code jam yesterday
Solving Advent of Code puzzles alone and then chatting about the solutions is quite fun. What’s even more fun is getting together to solve them. With our Python community archipylago we did just that on the 12th.
We had a small group of developers and we booked a space for the evening to get together to write code and solve puzzles. I paired up with a friend who’s new to Advent of Code and we solved the first two days in pair-programming way and I helped pair-debug a bug in another participant’s code and we brainstormed approaches and solutions with a few others.
And I got to teach why named tuples are so fantastic to one developer. Spreading the good word!
I can highly recommend gathering a few friends from your local community and gathering somewhere for an evening to solve puzzles. It’s so much more fun.
If you’re a Python developer in Turku, Finland area, check out our website and join our events! We host monthly events (outside summer season) and it’s a great way to learn more about Python, meet others who share the interest and make new friends.