Tips#

The program has a multi-line input
You can use regular expressions to extract values from each line
Each group of 4 lines brings 4 values, the input for the program
You can view the problem as a system of linear equations
The system has no solution when the equation system’s answer is not an integer
Find the values of a and b that satisfy the equation. In this case, calculate the cost as 3*a + b
If you use an optimizer like scipy.optimize.linprog or Pulp you might have problems with the large numbers in part 2
Model in Pulp:

def solve(ax, ay, bx, by, rx, ry):

    model = LpProblem("Minimize Tokens", LpMinimize)
    A = LpVariable("A", lowBound=0, cat=LpInteger)
    B = LpVariable("B", lowBound=0, cat=LpInteger)

    model += 3 * A + B
    model += ax * A + bx * B == rx
    model += ay * A + by * B == ry
    model.solve()    

    return model, value(A), value(B)

With scipy:

from scipy.optimize import linprog

def minimize_cost(x, y, r, c, max_tokens=100):    
    A_eq = [x, y]  # Coefficient matrix for equality constraints
    b_eq = r  # Right-hand side of the equations
    
    result = linprog(
        c,
        A_eq=A_eq,
        b_eq=b_eq,
        method="highs",
        bounds=[(0, max_tokens), (0, max_tokens)],
        integrality=[1, 1],
    )

    # Check if the optimization was successful
    if result.success:
        a, b = result.x
        print(
            f"The optimized solution is: a = {a}, b = {b}, with a cost of {3*a + b} {result.fun}"
        )
        return a, b, 3 * a + b

    else:
        print("No valid solution (could not optimize).", result)
        return None

How much Python do you need to know?#

The chapters refer to my book Introduction to Programming with Python.

Lists - Chapter 6
Strings - Chapter 7
Regular Expressions - Chapter 12
Linear Algebra, Systems of Equations

Answer#

This answer was developed with the observation that optimizing 3*a + b is not necessary, just finding the coefficients for a and b that satisfy the equation is enough.

import re
from helpers import read_file_without_blank_lines


INPUT = """
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
"""

BA = re.compile(r"Button A: X\+(\d+), Y\+(\d+)")
BB = re.compile(r"Button B: X\+(\d+), Y\+(\d+)")
PR = re.compile(r"Prize: X=(\d+), Y=(\d+)")


def extract(input):
    state = 0
    EXPS = [BA, BB, PR]
    values = []
    v = []
    for line in input.splitlines():
        if not line:
            continue
        v.extend([int(z) for z in EXPS[state].match(line).groups()])
        state += 1
        if state == 3:
            values.append(v)
            v = []
            state = 0
    return values


def s(ax, bx, ay, by, rx, ry):
    b = (ay * rx - ax * ry) / (-ax * by + ay * bx)
    a = (ry - by * b) / ay
    return a, b


def calculate_cost(values):
    cost = 0
    for value in values:
        p = [value[0], value[2], value[1], value[3], value[4], value[5]]
        a, b = s(*p)

        if int(a) == a and int(b) == b:
            cost += 3 * int(a) + int(b)
    return cost


values = extract(INPUT)


cost = calculate_cost(values)
print("Part 1 - Test:", cost)
assert cost == 480

input_part_1 = read_file_without_blank_lines("13/input.txt")

values = extract(input_part_1)
cost = calculate_cost(values)
print("Part 1:", cost)
assert cost == 36758

# Part 2
print()

values = extract(input_part_1)
for value in values:
    value[4] += 10000000000000
    value[5] += 10000000000000
cost = calculate_cost(values)
print("Part 2:", cost)
assert cost == 76358113886726

Advent of Code 2024 - Day 13 of 25

Table of Contents

Tips#

How much Python do you need to know?#

Answer#