commit b52eef5b9399ab3888fcfe1bc9ca23c7a9f7b026
parent 4dc2097b38697614dba7a58bf2ec53e1e54e52fe
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Wed, 10 Dec 2025 18:15:14 +0100
Day 10 2025
Diffstat:
6 files changed, 364 insertions(+), 3 deletions(-)
diff --git a/2025/10/a.py b/2025/10/a.py
@@ -1,6 +1,37 @@
import fileinput
+def readline(line):
+ m = 0
+ for i in range(1, line.index(']')):
+ if line[i] == '#':
+ m |= 1 << (i-1)
+
+ b = []
+ j = line.index(']')
+ while '(' in line[j:]:
+ i = line[j:].index('(') + j + 1
+ j = line[i:].index(')') + i
+ x = 0
+ for y in line[i:j].split(','):
+ x |= 1 << int(y)
+ b.append(x)
+
+ return m, b
+
+def works(m, b, s):
+ x = 0
+ for j in range(len(s)):
+ if s[j] == '1':
+ x ^= b[j]
+ return x == m
+
+def sol(m, b):
+ s = 99999999
+ for i in range(2**len(b)):
+ if works(m, b, bin(i)[2:].rjust(len(b), '0')):
+ s = min(s, i.bit_count())
+ return s
+
with fileinput.input() as lines:
- for line in lines:
- ...
+ print(sum(sol(*readline(line)) for line in lines))
diff --git a/2025/10/b-debug.py b/2025/10/b-debug.py
@@ -0,0 +1,133 @@
+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))
diff --git a/2025/10/b-recursive-slow.py b/2025/10/b-recursive-slow.py
@@ -0,0 +1,66 @@
+import fileinput
+from functools import cache
+
+def readline(line):
+ b = []
+ j = line.index(']')
+ while '(' in line[j:]:
+ i = line[j:].index('(') + j + 1
+ j = line[i:].index(')') + i
+ x = 0
+ for y in line[i:j].split(','):
+ x |= 1 << int(y)
+ b.append(x)
+
+ begin = line.index('{')+1
+ end = line.index('}')
+ j = tuple(int(x) for x in line[begin:end].split(','))
+
+ return tuple(b), j
+
+def newj(j, b, n):
+ return tuple(j[i]-n if b & (1<<i) else j[i] for i in range(len(j)))
+
+def can(b, i):
+ return b & (1 << i) != 0
+
+inf = 99999999999
+@cache
+def sol(b, j, best):
+ print(f"{b} {j} {best}")
+ if all(x == 0 for x in j):
+ return 0
+ if any(x < 0 for x in j):
+ return inf
+ if len(b) == 0:
+ return inf
+ for i in range(len(j)):
+ if j[i] > 0 and not any(can(bb, i) for bb in b):
+ return inf
+
+ # Optimization: if any of the buttons is the last one available that
+ # toggles a certain jolt, we press it as much as needed.
+ for i in range(len(j)):
+ for k in range(len(b)):
+ bb = b[:k] + b[k+1:]
+ if can(b[k], i) and not any(can(x, i) for x in bb):
+ return j[i] + sol(bb, newj(j, b[k], j[i]), best)
+
+ c = 0
+ while all(x >= 0 for x in j) and c <= best:
+ best = min(best, c + sol(b[1:], j, best))
+ j = newj(j, b[0], 1)
+ c += 1
+
+ return best
+
+with fileinput.input() as lines:
+ sols = []
+ c = 1
+ for line in lines:
+ print(f"doing line {c}: {line}")
+ c += 1
+ sols.append(sol(*readline(line), inf))
+ print(sols)
+ print(sum(sols))
+
diff --git a/2025/10/b.py b/2025/10/b.py
@@ -0,0 +1,125 @@
+import fileinput
+from math import gcd
+
+inf = 999999999
+
+# Read an input line and return a triple A, b, c where:
+# A is the matrix of coefficient (A[i][j] is 1 if pressing the j-th button
+# increases the i-th counter, 0 otherwise).
+# b is the list of required final values of each counter.
+# c is a list of bounds for the number of times each button can be pressed:
+# c[i] is the minimum required value of a counter increased by button i.
+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
+
+# swaprow, swapcol and reducerow are utility functions for the matrix
+# row reduction procedure.
+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
+
+# Reduce the matrix A by row, including back subsitution. Returns a triple
+# A, b, c where:
+# A is the reduced matrix in the form [D|p] with D diagonal and p a matrix
+# whose number of columns is the number of free parameters for Ax = b.
+# b and c are the adjusted versions of the input paramters with the same
+# names. In particular, b is adjusted every time a row is reduced and
+# when rows are swapped, while c (the list of bounds) is adjusted when
+# two columns are swapped (which is equivalent to changing the order of
+# two buttons).
+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])]
+ A = [A[i] for i in I]
+ b = [b[i] for i in I]
+
+ # Back substitution
+ for i in range(len(A)-1, -1, -1):
+ for j in range(i):
+ reducerow(A, b, i, j)
+
+ return A, b, c
+
+# Find all combinations of parameters respecting the bounds in c. The
+# free parameters are always the last n-rank(A) columns of the matrix A
+# (where n is the total number of columns).
+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
+
+# Solve the integer linear system Ax = b, minimizing the sum of the
+# coordinates of x.
+def solve_system_min_sum(A, b, c):
+ k = len(A[0]) - len(A)
+ mins = inf
+ for c in paramcomb(k, c):
+ sol = sum(c)
+ for i in range(len(A)):
+ cc = (c[j]*A[i][len(A[0])-k+j] for j in range(len(c)))
+ s = b[i]-sum(cc)
+ a = s // A[i][i]
+ # If a is negative or not integer, we skip this solution
+ if a < 0 or s % A[i][i] != 0:
+ sol = inf
+ break
+ sol += a
+ mins = min(mins, sol)
+ return mins
+
+with fileinput.input() as lines:
+ print(sum(solve_system_min_sum(*reduce(*readline(l))) for l in lines))
diff --git a/2025/README.md b/2025/README.md
@@ -11,6 +11,7 @@ Example
```
Day -Part 1- -Part 2-
+ 10 00:27:43 11:51:51
9 00:05:05 02:11:41
8 00:29:14 00:33:02
7 00:05:27 00:20:40
@@ -173,3 +174,8 @@ For example with this input:
The first version of my program return 4851 instead of 202. I added a
check for this case in `b-fixed.py`, hopefully it works in 100% of the
cases now.
+
+### Day 10: Factory
+
+Phew, this was a hard one!
+(More details coming soon, for now read the code and the comments)
diff --git a/README.md b/README.md
@@ -14,4 +14,4 @@ See `year/README.md` for instructions on how to run my code.
|2022| 50 | Rust | Done in 2025 to learn Rust |
|2023| 50 | C | All solved by December 25, 2023 |
|2024| 50 | C++ | Each solved within 24h |
-|2025| 18 | Python | Work in progress... |
+|2025| 20 | Python | Work in progress... |
