Advent of Code 2025 Day 10: Factory
Linear Programming Tutorial
Some years I'm able to solve both parts of all the puzzles without any assistance. This is not one of those years! :) Part 1 was straightforward, but I wasn't able to come up with a fast enough solution for part 2. My part 2 did solve the sample data, so it was accurate; it just wasn't performant enough to handle the real input.
After exhausting my mental resources on the problem, I turned to reddit for some tips. While there are a number of creative solutions, the technique I settled on was linear programming because I think it may be a useful technique for me in the future.
Peter Norvig described linear programming much better than I in his day 10 solution:
"A linear programming solver finds a solution x to the equation A x = b that minimizes c x, where A is a two-dimensional matrix and the other variables are one-dimensional vectors."
Let's consider the sample input for part 2. We're given the following buttons:
and the following joltages:
Recall, that the first joltage, 3, is counter 0, and is incremented by pressing buttons containing a 0.
Similarly, the second joltage, 5, is counter 1, and is incremented by pressing buttons containing a 1, etc.
First, we'll create a matrix, A, relating buttons to counters. We could use True and False for the elements
of A, but I find 1 and 0 better:
The first row is for counter 0, and each element corresponds to a button. It indicates that only the last two
buttons contribute to counter 0, e.g. buttons (0,2) and (0,1), because those buttons each have a zero.
Similarly, the second row is for counter 1, and it indicates that the second and last buttons contribute to
counter 1 e.g. buttons (1,3) and (0,1).
Next, for each of our buttons, we have a variable representing the number of presses. We'll represent that with
a vector x: [ x0, x1, x2, x3, x4, x5 ] So, if we multiply the matrix A with vector x, the resulting vector will
need to equal b i.e. the counters. You may need to refresh yourself on matrix multiplication, as I did :)
[ [ 0, 0, 0, 0, 1, 1 ], [ x0 [ b0 [ 3
[ 0, 1, 0, 0, 0, 1 ], x x1 = b1 = 5
[ 0, 0, 1, 1, 1, 0 ], x2 b2 4
[ 1, 1, 0, 1, 0, 0 ] ] x3 b3 ] 7 ]
x4
x5 ]
The inputs to our linprog linear programming function are the following:
- A vector of coefficients of the linear objective function to be minimized, c
- A coefficient matrix, A
- A requirement vector, b i.e. our
joltagevector
So, what about this c vector? Well, what the linprog function is going to minimize is essentially
the product of multiplying the c vector by our x vector, so it will have the same length as x e.g.:
In our case, we want to sum all the button presses i.e. the presses for button0, e.g. x0, the presses for
button1, e.g. x1, etc., so if we simply use 1 for all the coefficients, the result of c * x will be
the sum of all the x variables !!
c = [ 1, 1, 1, 1, 1, 1 ] x [ x0 = x0 + x1 + x2 + x3 + x4 + x5 = total number of button presses
x1
x2
x3
x4
x5 ]
If you're like me, you may need to read over that a few times to internalize it, but nothing speaks as clearly as code!
Solution
"""Advent of Code 2025: Day 10 - Factory Part 2 (using help from reddit)"""
from advent import parse
from scipy.optimize import linprog
Machine = tuple[list[list[int]], list[int]]
def parse_machine(line) -> Machine:
def parse_buttons(buttons):
return [[int(s) for s in button[1:-1].split(',')] for button in buttons]
def parse_joltage(joltage):
return [int(s) for s in joltage[1:-1].split(',')]
items = line.split()
return (parse_buttons(items[1:-1]), parse_joltage(items[-1]))
machines: list[Machine] = parse(10, parse_machine)
def minimize(buttons, joltage) -> int:
c = [1 for _ in buttons]
A = [[1 if i in b else 0 for b in buttons] for i in range(len(joltage))]
return round(linprog(c, A_eq=A, b_eq=joltage, integrality=1).fun)
def part2():
return sum(minimize(buttons, joltage) for buttons, joltage in machines)
assert part2() == 18273
For completeness, I'll include my original, unaided, code which works for part 1, and works for the sample input for part 2, but is far too slow for the real data:
"""Advent of Code 2025: Day 10 - Factory"""
from advent import parse, heappop, heappush, decimal_to_bool_list
Machine = tuple[int, list[int], list[int]]
def parse_machine(line) -> Machine:
def parse_diagram(s):
return int(''.join(['0' if s == '.' else '1' for s in list(reversed(s[1:-1]))]), 2)
def parse_buttons(buttons):
return [sum([2 ** int(s) for s in button[1:-1].split(',')]) for button in buttons]
def parse_joltage(joltage):
return [int(s) for s in joltage[1:-1].split(',')]
items = line.split()
return (parse_diagram(items[0]), parse_buttons(items[1:-1]), parse_joltage(items[-1]))
machines: list[Machine] = parse(10, parse_machine)
def part1(m: Machine) -> int:
(diagram, buttons, _) = m
h = []
for button in buttons:
heappush(h, (1, button, button))
while True:
(presses, button, lights) = heappop(h)
if lights == diagram:
return presses
for btn in buttons:
heappush(h, (presses + 1, btn, lights ^ btn))
def part2(m: Machine) -> int:
"""This implementation produces the correct answer quickly for the sample input, but
is too slow for the real input. I need to switch to a linear programming solution."""
def step_joltages(counters, btn) -> list[int]:
counters = counters[:] # clone
for i, d in enumerate(reversed(decimal_to_bool_list(btn))):
counters[i] += d
return counters
(_, buttons, joltages) = m
n = len(joltages)
h = []
for btn in buttons:
heappush(h, (1, step_joltages([0] * n, btn)))
seen = set()
while True:
(presses, counters) = heappop(h)
key = tuple(counters)
if key in seen:
continue
else:
seen.add(key)
if any(counters[i] > joltages[i] for i in range(n)):
continue
elif joltages == counters:
return presses
for btn in buttons:
heappush(h, (presses + 1, step_joltages(counters, btn)))
def solve(part):
return sum(part(m) for m in machines)
assert solve(part1) == 475