Day 10 2025

5 files changed, 363 insertions, 2 deletions

diff --git a/2025/10/a.py b/2025/10/a.py
index 5fdb11b..52fa0b0 100644
--- 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
new file mode 100644
index 0000000..e6f9961
--- /dev/null
+++ 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
new file mode 100644
index 0000000..a52b50e
--- /dev/null
+++ 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
new file mode 100644
index 0000000..57fff46
--- /dev/null
+++ 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
index d75a4d3..dc87240 100644
--- 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)