import sys import itertools def parseIntList(s): return list(map(int, s[1:-1].split(","))) def parseMachine(line): words = line.split(" ") buttons = list(map(parseIntList, words[1:-1])) goal = parseIntList(words[-1]) return (buttons, goal) def solveMachine(machine): (buttons, goal) = machine rows = len(goal) cols = len(buttons) + 1 matrix = [[0 for _ in range(rows)] for _ in range(cols)] for i,button in enumerate(buttons): for b in button: matrix[i][b] = 1 for i in range(rows): matrix[cols-1][i] = -goal[i] maxPresses = max(goal) # Row reduce matrix curRow,curCol = 0,0 freeVars = [] while curRow < rows and curCol < cols: pivotRow = None for i in range(curRow, rows): if matrix[curCol][i] != 0: pivotRow = i break if pivotRow is None: freeVars.append(curCol) curCol += 1 continue for i in range(cols): matrix[i][curRow], matrix[i][pivotRow] = matrix[i][pivotRow], matrix[i][curRow] for j in range(rows): if j == curRow: continue a,b = matrix[curCol][curRow],-matrix[curCol][j] for i in range(cols): matrix[i][j] = a*matrix[i][j] + b*matrix[i][curRow] curRow += 1 curCol += 1 while curCol < cols: freeVars.append(curCol) curCol += 1 # The last col is going to be fixed at 1 freeVars.pop() minMoves = maxPresses * len(buttons) for freeAssignment in itertools.product(range(maxPresses+1), repeat=len(freeVars)): varAssignment = [None for i in range(cols)] varAssignment[-1] = 1 valid = True for i,v in enumerate(freeVars): varAssignment[v] = freeAssignment[i] for j in range(rows-1,-1,-1): nonZeroCols = [i for i in range(cols) if matrix[i][j] != 0] if len(nonZeroCols) == 0: continue rhs = -sum([varAssignment[c]*matrix[c][j] for c in nonZeroCols[1:]]) lhs = matrix[nonZeroCols[0]][j] if rhs % lhs != 0: valid = False break if rhs // lhs < 0: valid = False break varAssignment[nonZeroCols[0]] = rhs // lhs if not valid: continue minMoves = min(minMoves, sum(varAssignment) - 1) return minMoves machines = [parseMachine(line) for line in open(sys.argv[1]).read().strip().split("\n")] print(sum(map(solveMachine, machines)))