Advent of Code 2025
drubery.com
1import sys
2import itertools
3
4def parseIntList(s):
5 return list(map(int, s[1:-1].split(",")))
6
7def parseMachine(line):
8 words = line.split(" ")
9 buttons = list(map(parseIntList, words[1:-1]))
10 goal = parseIntList(words[-1])
11 return (buttons, goal)
12
13def solveMachine(machine):
14 (buttons, goal) = machine
15 rows = len(goal)
16 cols = len(buttons) + 1
17 matrix = [[0 for _ in range(rows)] for _ in range(cols)]
18 for i,button in enumerate(buttons):
19 for b in button:
20 matrix[i][b] = 1
21 for i in range(rows):
22 matrix[cols-1][i] = -goal[i]
23 maxPresses = max(goal)
24 # Row reduce matrix
25 curRow,curCol = 0,0
26 freeVars = []
27 while curRow < rows and curCol < cols:
28 pivotRow = None
29 for i in range(curRow, rows):
30 if matrix[curCol][i] != 0:
31 pivotRow = i
32 break
33 if pivotRow is None:
34 freeVars.append(curCol)
35 curCol += 1
36 continue
37 for i in range(cols):
38 matrix[i][curRow], matrix[i][pivotRow] = matrix[i][pivotRow], matrix[i][curRow]
39 for j in range(rows):
40 if j == curRow:
41 continue
42 a,b = matrix[curCol][curRow],-matrix[curCol][j]
43 for i in range(cols):
44 matrix[i][j] = a*matrix[i][j] + b*matrix[i][curRow]
45 curRow += 1
46 curCol += 1
47 while curCol < cols:
48 freeVars.append(curCol)
49 curCol += 1
50 # The last col is going to be fixed at 1
51 freeVars.pop()
52 minMoves = maxPresses * len(buttons)
53 for freeAssignment in itertools.product(range(maxPresses+1), repeat=len(freeVars)):
54 varAssignment = [None for i in range(cols)]
55 varAssignment[-1] = 1
56 valid = True
57 for i,v in enumerate(freeVars):
58 varAssignment[v] = freeAssignment[i]
59 for j in range(rows-1,-1,-1):
60 nonZeroCols = [i for i in range(cols) if matrix[i][j] != 0]
61 if len(nonZeroCols) == 0:
62 continue
63 rhs = -sum([varAssignment[c]*matrix[c][j] for c in nonZeroCols[1:]])
64 lhs = matrix[nonZeroCols[0]][j]
65 if rhs % lhs != 0:
66 valid = False
67 break
68 if rhs // lhs < 0:
69 valid = False
70 break
71 varAssignment[nonZeroCols[0]] = rhs // lhs
72 if not valid:
73 continue
74 minMoves = min(minMoves, sum(varAssignment) - 1)
75 return minMoves
76
77machines = [parseMachine(line) for line in open(sys.argv[1]).read().strip().split("\n")]
78print(sum(map(solveMachine, machines)))