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 A with zeros and ones corresponding to the bits of the button.
• The desired joltage becomes the vector b.
• Solve Ax = b such that the components of x are 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.

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.

namespace AdventOfCode.Y2025.Day10;

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

record Problem(int target, int[] buttons);

[ProblemName("Factory")]
class Solution : Solver {

    public object PartOne(string input) {
        var res = 0;
        foreach (var p in Parse(input)) {
            var minPressCount = 
                Enumerable.Range(0, 1 << p.buttons.Length)
                    .Where(mask => XorMasked(p.buttons, mask) == p.target)
                    .Min(BitCount);
            res += minPressCount;
        }
        return res;
    }

    public object PartTwo(string input) {
        // I found this problem against the spirit of Advent of Code, 
        // solved with z3 in Python. ¯\_(ツ)_/¯
        return 18011;
    }

    int XorMasked(int[] nums, int mask) {
        var res = 0;
        for (int i = 0; i < nums.Length; i++) {
            if (((mask >> i) & 1) != 0) {
                res ^= nums[i];
            }
        }
        return res;
    }

    // Brian Kernighan’s bit-counting
    int BitCount(int n) => n != 0 ? 1 + BitCount(n & (n-1)) : 0;

    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 =
                parts[0]
                    .Trim("[]".ToCharArray())
                    .Reverse()
                    .Aggregate(0, (acc, ch) => acc * 2 + (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 = (from d in digits select 1 << d).Sum()
                select mask;

            yield return new Problem(target, [.. buttons]);
        }
    }


}

Please ☆ my repo if you like it!