aoc

b-debug.py (3000B)

---

 import fileinput
 from math import gcd
 
 inf = 999999999
 
 def readline(l):
 	b = [int(x) for x in l[l.index('{')+1:l.index('}')].split(',')]
 
 	A = [[] for j in b]
 	c = []
 
 	end = l.index(']')
 	while '(' in l[end:]:
 		begin = l[end:].index('(') + end + 1
 		end = l[begin:].index(')') + begin
 		bu = [int(x) for x in l[begin:end].split(',')]
 		c.append(min(b[j] for j in bu))
 		for i in range(len(b)):
 			A[i].append(1 if i in bu else 0)
 
 	return A, b, c
 
 def printabc(A, b, c):
 	print("--")
 	for i in range(len(b)):
 		print(A[i], [b[i]])
 	print(f"Parameter bounds: {c}")
 	print("--")
 
 def swaprow(A, b, i, j):
 	if i != j:
 		A[i], A[j] = A[j], A[i]
 		b[i], b[j] = b[j], b[i]
 
 def swapcol(A, c, i, j):
 	if i != j:
 		for k in range(len(A)):
 			A[k][i], A[k][j] = A[k][j], A[k][i]
 		c[i], c[j] = c[j], c[i]
 
 def reducerow(A, b, i, j):
 	if A[i][i] != 0:
 		x = A[i][i]
 		y = -A[j][i]
 		d = gcd(x, y)
 		A[j] = [(y*A[i][k]+x*A[j][k])//d for k in range(len(A[i]))]
 		b[j] = (y*b[i]+x*b[j])//d
 
 def reduce(A, b, c):
 	for i in range(len(A[0])):
 		# Swap columns until there is one in position i with at least
 		# one non-zero element.
 		I = []
 		k = i
 		while len(I) == 0 and k < len(A[0]):
 			swapcol(A, c, i, k)
 			I = [j for j in range(i, len(A)) if A[j][i] != 0]
 			k += 1
 
 		# If no such column is found, we are done
 		if len(I) == 0:
 			break
 
 		# Swap rows so that A[i][i] is non-zero
 		swaprow(A, b, i, I[0])
 
 		# Reduce all other rows
 		for j in range(i+1, len(A)):
 			reducerow(A, b, i, j)
 
 	# Remove all rows of zero and check if the system is solvable
 	I = [i for i in range(len(A)) if any(a != 0 for a in A[i])]
 	if any(b[i] != 0 for i in range(len(A)) if i not in I):
 		printabc(A, b, c)
 		print("Unsolvable!")
 		exit(1)
 	A = [A[i] for i in I]
 	b = [b[i] for i in I]
 
 	# TODO continue with back substitution?
 	for i in range(len(A)-1, -1, -1):
 		for j in range(i):
 			reducerow(A, b, i, j)
 
 	# Clean all rows to minimize coefficients (unnecessary, but makes
 	# numbers smaller).
 	for i in range(len(A)):
 		d = gcd(*A[i]) * (-1 if A[i][i] < 0 else 1)
 		A[i] = [A[i][k]//d for k in range(len(A[i]))]
 		b[i] = b[i]//d
 
 	return A, b, c
 
 def paramcomb(nparam, c):
 	if nparam == 0:
 		return [[]]
 
 	ret = []
 	for i in range(c[-nparam]+1):
 		ret += [[i, *l] for l in paramcomb(nparam-1, c)]
 	return ret
 
 def solve_system_min_sum(A, b, c):
 	#nparam = len(A[0])-len(A)
 	#print(f"{nparam}: {paramcomb(nparam, c)}")
 
 	k = len(A[0]) - len(A)
 	mins = inf
 	for c in paramcomb(k, c):
 		sol = sum(c)
 		for i in range(len(A)):
 			p = sum(c[j]*A[i][len(A[0])-k+j] for j in range(len(c)))
 			a = (b[i] - p)//A[i][i]
 			if a < 0 or a*A[i][i] != b[i] - p:
 				sol = inf
 				break
 			sol += a
 		mins = min(mins, sol)
 	return mins
 
 with fileinput.input() as lines:
 	sols = []
 	k = 1
 	for line in lines:
 		print(f"doing line {k}: {line[:-1]}")
 		A, b, c = readline(line)
 		#printabc(A, b, c)
 		A, b, c = reduce(A, b, c)
 		#printabc(A, b, c)
 		sols.append(solve_system_min_sum(A, b, c))
 		k += 1
 	print(sols)
 	print(sum(sols))