Dicas#

O programa tem um entrada em várias linhas
Você pode usar expressões regulares para extrair os valores de cada linha.
Cada grupo de 4 linhas, trás 4 valores, a entrada para o programa.
Você pode observar o problema como uma sistema de equações lineares.
O sistema não tem solução quando a resposta do sistema de equações não é inteira.
Ache os valores de a e b que satisfaçam a equação. Neste caso, calcule o custo como sendo 3*a + b.
Se você utilizar um otimizador como scipy.optimize.linprog ou Pulp você poderá ter problemas com os grandes números da parte 2.
Modelo no Pulp:

def psolve(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)

Com 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

Quanto de Python você precisa saber?#

Os capítulos se referem ao meu livro Introdução à Programação com Python.

Listas - Capítulo 6
Strings - Capítulo 7
Expressões regulares - Capítulo 12
Álgebra linear, sistemas de equações

Resposta#

Esta resposta foi desenvolvida, com a observação que a otimização de 3*a + b não é necessária, bastando achar os coeficientes para a e b que satisfaçam a equação.

import re
from auxiliares import le_arquivo_sem_linhas_em_branco


ENTRADA = """
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 extraia(entrada):
    estado = 0
    EXPS = [BA, BB, PR]
    valores = []
    v = []
    for linha in entrada.splitlines():
        if not linha:
            continue
        v.extend([int(z) for z in EXPS[estado].match(linha).groups()])
        estado += 1
        if estado == 3:
            valores.append(v)
            v = []
            estado = 0
    return valores


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 calcula_custo(valores):
    custo = 0
    for valor in valores:
        p = [valor[0], valor[2], valor[1], valor[3], valor[4], valor[5]]
        a, b = s(*p)

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


valores = extraia(ENTRADA)


custo = calcula_custo(valores)
print("Parte 1 - Teste:", custo)
assert custo == 480

entrada_parte_1 = le_arquivo_sem_linhas_em_branco("13/input.txt")

valores = extraia(entrada_parte_1)
custo = calcula_custo(valores)
print("Parte 1:", custo)
assert custo == 36758

# Parte 2
print()

valores = extraia(entrada_parte_1)
for valor in valores:
    valor[4] += 10000000000000
    valor[5] += 10000000000000
custo = calcula_custo(valores)
print("Parte 2:", custo)
assert custo == 76358113886726

Advent of code 2024 - Dia 13 de 25

Conteúdo

Dicas#

Quanto de Python você precisa saber?#

Resposta#