aoc2025-10p2.py

from fractions import Fraction
from math import inf

INPUT = open("10.in")

zero = Fraction(0)
one = Fraction(1)

"""
Example input line

[.#.###] (0,1,2) (0,2,4,5) (3,5) (2,4,5) (0,1,3,4) (0,2,4) (5) {21,18,30,14,34,40}
"""

ans = 0

for line in INPUT:
    parts = line.split()

    """
    1. process input
    """

    m = parts[-1].count(",") + 1  # number of joltages
    n = len(parts) - 2  # number of buttons

    buttons = []
    for i in range(n):
        button = list(map(int, parts[i + 1][1:-1].split(",")))
        buttons.append(button)

    joltages = list(map(int, parts[-1][1:-1].split(",")))

    """
    2. initialize augmented matrix
    """

    M = [[zero] * (n + 1) for _ in range(m)]

    for c, button in enumerate(buttons):
        for r in button:
            M[r][c] = one

    for r, joltage in enumerate(joltages):
        M[r][n] = Fraction(joltage)

    """
    3. transform to reduced row echelon form
    """

    pivots = []
    free_cols = []
    current_row = 0

    for current_col in range(n):
        # find pivot row and swap it up
        for r in range(current_row, m):
            if M[r][current_col] != zero:
                pivot_row = r
                M[current_row], M[r] = M[r], M[current_row]
                break
        else:
            free_cols.append(current_col)
            continue

        # rescale pivot row
        for c in reversed(range(current_col, n + 1)):
            M[current_row][c] /= M[current_row][current_col]

        # zero out pivot column on other rows
        for r in range(m):
            if r != current_row:
                for c in reversed(range(current_col, n + 1)):
                    M[r][c] -= M[r][current_col] * M[current_row][c]

        pivots.append((current_row, current_col))

        current_row += 1

    """
    4. exhaustive search on free variables
    """

    free_count = len(free_cols)
    free_presses = [0] * free_count

    # max presses per button without exceeding some joltage
    # this provides an upper bound for both free and pivot variables
    max_presses = [min(joltages[i] for i in button) for button in buttons]

    min_total_presses = inf

    def rec(free_index, total_presses):
        global min_total_presses

        if free_index == free_count:
            for pivot_row, pivot_col in pivots:
                # compute derived number of presses for this pivot var
                pivot_presses = M[pivot_row][n]
                for i in range(free_count):
                    pivot_presses -= M[pivot_row][free_cols[i]] * free_presses[i]

                # pivot_presses has to be a non-negative integer within bounds
                # otherwise, abandon this assignment of free vars
                if pivot_presses.denominator == 1 and 0 <= pivot_presses.numerator <= max_presses[pivot_col]:
                    total_presses += pivot_presses.numerator
                else:
                    return

            if min_total_presses > total_presses:
                min_total_presses = total_presses

            return

        free_col = free_cols[free_index]

        for pivot_presses in range(max_presses[free_col] + 1):
            # choose number of presses for this free var
            free_presses[free_index] = pivot_presses
            rec(free_index + 1, total_presses + pivot_presses)

    rec(0, 0)

    ans += min_total_presses

print(ans)