Just across the hall, you find a large factory. Fortunately, the Elves here have plenty of time to decorate. Unfortunately, it’s because the factory machines are all offline, and none of the Elves can figure out the initialization procedure.
The Elves do have the manual for the machines, but the section detailing the initialization procedure was eaten by a requirements for each machine.
Visit the website for the full story and the full puzzle description.
The first half of the problem was totally fine: we just had to find the combination with the minimal number of button presses. However, Part 2 was, in my view, against the spirit of Advent of Code.
It’s clearly a linear algebra problem as follows:
- The buttons form the matrix
A. - Each button gets a column in
Awith zeros and ones corresponding to the bits of the button. - The desired joltage becomes the vector
b. - Solve
Ax = bsuch that the components ofxare non-negative integers andΣ xᵢis minimal.
This is a textbook integer linear programming problem, trivially solved by an ILP solver, or in my case z3. But this is not how Advent of Code has worked in the last 10+ years, so I was hoping for some shortcut, maybe a special structure of the input... But no luck, ILP really seems to be the intended way.
The Gaussian way
I'm a purist in the sense that I don't use external dependencies in my C# solutions, so something like OR-tools is out of scope. I did find another path, though, which is not that good-looking, but workable....
One can notice that A is almost always full (column) rank, and the kernel space has at most 2–3 dimensions. This means we can solve the equation using Gaussian elimination, which will give us a solution with the columns in the kernel set to 0. There is no guarantee that the solution is integer, or that all xᵢ are non-negative, though.
But once the columns in the base and the kernel are identified, we can form a square matrix B and move the remaining columns to K, then deal with Bx = b − Ky.
Say that K has 3 columns. Now we can start brute-forcing by setting the values in y to some low integers: [1,0,0], [0,1,0], [0,0,1], then [1,1,0], [1,0,1], [0,1,1], [2,0,0], [0,2,0], [0,0,2], slowly increasing the sum of the values and solving for each combination.
This way we eventually get a feasible solution for the original problem, say with the total button-press count equal to 100 or so. Then it’s enough to continue the above iteration while the sum of yᵢ is ≤ 100. That gives us a termination condition. During the search we might run into better solutions, which further lowers the upper bound.
I prototyped this idea in Python with ChatGPT. I think, if anything, this could be ported to C#, but I don’t feel the urge. Although it uses first principles that one could potentially implement, it’s a much slower solution than the one using z3.
A recursive solution
Based on the ingenious idea of tenthmascot, I could create a plain C# implementation for the problem.
As she says: find all possible sets of buttons you can push so that the remaining voltages are even, and divide by 2 and recurse.
All credits goes to her, but I'll give an extra ⭐ to myself for learning something new again!
namespace AdventOfCode.Y2025.Day10;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
record Problem(int[] target, int[] buttons, int[] joltage);
record SinglePress(int buttonCount, int[] joltageChange);
[ProblemName("Factory")]
class Solution : Solver {
public object PartOne(string input) {
var res = 0;
foreach (var p in Parse(input)) {
var minPressCount = SinglePresses(p)
.Where(press => Enumerable.SequenceEqual(p.target, press.joltageChange.Select(i => i % 2)))
.Min(press => press.buttonCount);
res += minPressCount;
}
return res;
}
// Implements the idea presented by tenthmascot
// https://www.reddit.com/r/adventofcode/comments/1pk87hl/
public object PartTwo(string input) {
var res = 0;
foreach (var p in Parse(input)) {
res += Solve(p.joltage, SinglePresses(p), new Dictionary<string, int>());
}
return res;
}
// Collect changes in joltages when each button is pressed at most once
List<SinglePress> SinglePresses(Problem p) {
var presses = new List<SinglePress>();
foreach (var buttonMask in Enumerable.Range(0, 1 << p.buttons.Length)) {
var joltageChange = new int[p.joltage.Length];
var buttonCount = 0;
for (int ibutton = 0; ibutton < p.buttons.Length; ibutton++) {
if ((buttonMask >> ibutton) % 2 == 1) {
buttonCount++;
var button = p.buttons[ibutton];
for (int ijoltage = 0; ijoltage < p.joltage.Length; ijoltage++) {
if ((button >> ijoltage) % 2 == 1) {
joltageChange[ijoltage]++;
}
}
}
}
presses.Add(new SinglePress(buttonCount, joltageChange));
}
return presses;
}
int Solve(int[] joltages, List<SinglePress> singlePresses, Dictionary<string, int> cache) {
if (joltages.All(jolt => jolt == 0)) {
return 0;
}
var key = string.Join("-", joltages);
if (!cache.ContainsKey(key)) {
var best = 10_000_000;
foreach (var singlePress in singlePresses) {
var buttonCount = singlePress.buttonCount;
var joltageChange = singlePress.joltageChange;
var evens =
Enumerable.Range(0, joltages.Length)
.All(i => joltages[i] >= joltageChange[i] && (joltages[i] - joltageChange[i]) % 2 == 0);
if (evens) {
var subProblem =
Enumerable.Range(0, joltages.Length)
.Select(i => (joltages[i] - joltageChange[i]) / 2)
.ToArray();
best = Math.Min(best, buttonCount + 2 * Solve(subProblem, singlePresses, cache));
}
}
cache[key] = best;
}
return cache[key];
}
IEnumerable<Problem> Parse(string input) {
var lines = input.Split("\n");
// [.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}
foreach (var line in lines) {
var parts = line.Split(" ").ToArray();
var target =
from ch in parts[0].Trim("[]".ToCharArray())
select ch == '#' ? 1 : 0;
var buttons =
from part in parts[1..^1]
let digits = Regex.Matches(part, @"\d+").Select(m => int.Parse(m.Value))
let mask = digits.Aggregate(0, (acc, d) => acc | (1 << d))
select mask;
var joltage =
from m in Regex.Matches(parts[^1], @"\d+")
select int.Parse(m.Value);
yield return new Problem([.. target], [.. buttons], [.. joltage]);
}
}
}
Please ☆ my repo if you like it!