brainwagon

As part of my daily puzzling in December, I’ve been engaged in the Advent of Code 2024 challenge. This is the kind of thing that sane people only do when prepping for job interviews (which I suppose I could be) but I do more for fun, in some hope that I’ll buoy up my ego a bit as well by proving that “I still got it.”

For the first few days, I didn’t even realize that there was a competitive element to this challenge, but it turns out that they keep a kind of leaderboard, and award points for first 100 people who solve a particular 2 part problem. Given that a few tens of thousands of people seem to be engaged in this activity, I have suspected that my chance of scoring even a single point is vanishingly small, but for the last couple of days, I decided to give it a whirl with my best efforts right at 9:00PM when the next days puzzle is released.

You can read the puzzle description for day 13 on their website.

Here is where I went awry, right from the very start. I read this:

The cheapest way to win the prize is by pushing the A button 80 times and the B button 40 times. This would line up the claw along the X axis (because 80*94 + 40*22 – 8400) and along the Y axis (because 80*34 + 40*67 = 5400). Doing this would cost 80*3 tokens for the A presses and 40*1 for the B presses, a total of 280 tokens.

This sent me down a complete rabbit hole, which took me the better part of an embarrassing four hours (and a night’s sleep) to rectify. I had convinced myself that there were potentially multiple solutions to this, and therefore I needed to treat it as a Diophantine equation. And, because I’m that kind of guy, I resorted to playing around with it on that basis using Python’s sympy.solvers.diophantine module.

I eventually solved it using that library, but because it is kind of a complicated module, it took me a lot of time, and had a lot of false starts and rabbit holes.

It’s simpler, way simpler than that. And I’m positively idiotic for considering otherwise.

Each potential move of the crane game arm moves the arm to the right and up. If we call the amounts that the Button A moves a_x, a_y, and for Button B b_x, b_y, then we can think of each button push as a vector. If you think of these as independent vectors, you will realize that it doesn’t matter what order you press the buttons. Let’s say we do all the A buttons first, and all the B buttons. If we end up at the target t_x, t_y after all that, then we win.

All the A steps occur along a line starting at the origin. We can reverse the direction of all the B steps, but begin at the target location. These are lines. The “A” line has slope a_y / a_x, and the B line has slope b_y / b_x. The A line passes through the origin and the B line passes through the target.

Clearly, unless they are coincident, they can only cross at a single point. There is no “optimization” because there can only be a single solution. If they intersect at a point on the integer lattice, then the game has a solution. Doh.

It’s still convenient to use sympy to avoid having to do algebra by hand, and cancel out stuff on paper and transcript it into code, but it’s not rocket science even if you had to do it by hand.

Spoiler: here’s my revised code to do it.

#!/usr/bin/env python

import re

data = """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""".split("\n\n")

data = open("input.txt").read().rstrip().split("\n\n")

def parse_data(d):
    d = d.split("\n")
    m = re.match(r"Button A: X\+(\d+), Y\+(\d+)", d[0])
    ax, ay = m.group(1), m.group(2)
    m = re.match(r"Button B: X\+(\d+), Y\+(\d+)", d[1])
    bx, by = m.group(1), m.group(2)
    m = re.match(r"Prize: X\=(\d+), Y\=(\d+)", d[2])
    tx, ty = m.group(1), m.group(2)
    return int(ax), int(ay), int(bx), int(by), int(tx), int(ty)

coins = 0

from sympy import solve, symbols, Eq

def mysolve(d):
    global coins
    ax, ay, bx, by, tx, ty = parse_data(d)
    tx += 10000000000000
    ty += 10000000000000

    # let sympy do all the heavy lifting

    a, b = symbols("a, b", integer=True)
    eq1 = Eq(a * ax + b * bx, tx)
    eq2 = Eq(a * ay + b * by, ty)
    sol = solve((eq1, eq2))

    if sol != []:
        coins += 3 * sol[a] + sol[b]

for d in data:
    mysolve(d)

print(coins)

If nothing else, it did make me dust off my knowledge of the simple bits of sympy, but I feel like an idiot. Note to self: don’t read too much into the wording of puzzles like this, they may be designed to mislead as much to illuminate.

Happy Holidays to all.