Advent of Code 2024, Day 13

At first I thought I would need some kind of two-dimensional dynamic-programming array, but it turns out you just need to solve two equations with two unknowns and then check if the solutions are integers. This runs in constant time for each prize.

In part 1, I solved the equations halfway and let the loop do the rest. In part 2, I solved the second equation as well. I lost time there because I made a mistake on paper and because I needed to find the right tolerance for the integer checks.

Part 1

import sys

def cost(prize):
    ax, ay, bx, by, px, py = prize
    for b in range(100):
        a = (px - b*bx) / ax
        if py != a*ay + b*by: continue
        return round(3*a + b)
    return 0

prizes = []

with open(sys.argv[1]) as f:
    prize = [0, 0, 0, 0, 0, 0]
    for i, line in enumerate(f):
        if i % 4 == 3: continue
        line = line.split()
        x, y = line[-2], line[-1]
        x, y = int(x[2:-1]), int(y[2:])
        prize[(i%4)*2], prize[(i%4)*2+1] = x, y
        if i % 4 == 2:
            prizes.append(tuple(prize))

print(sum([cost(prize) for prize in prizes]))

Part 2

import sys
import math

def is_int(x):
    return math.isclose(x, round(x), rel_tol=0, abs_tol=0.01)

def cost(prize):
    ax, ay, bx, by, px, py = prize
    b = (py - px*ay/ax) / (by - bx*ay/ax)
    a = (px - b*bx) / ax
    if is_int(a) and is_int(b):
        return 3*round(a) + round(b)
    else:
        return 0

prizes = []
offset = int(sys.argv[2]) if len(sys.argv) > 2 else 10000000000000

with open(sys.argv[1]) as f:
    prize = [0, 0, 0, 0, 0, 0]
    for i, line in enumerate(f):
        if i % 4 == 3: continue
        line = line.split()
        x, y = line[-2], line[-1]
        x, y = int(x[2:-1]), int(y[2:])
        if i % 4 == 2:
            x, y = x+offset, y+offset
        prize[(i%4)*2], prize[(i%4)*2+1] = x, y
        if i % 4 == 2:
            prizes.append(tuple(prize))

print(sum([cost(prize) for prize in prizes]))

2024-12-13