Advent of Code 2025 - Day 10

Useful Links

Concepts and Packages Demonstrated

Combinations Bitwise Operations NumPy SymPy Scipy

Problem Intro

We find ourselves in a factory where the machines are offline. The manual is… partially eaten by a Shiba Inu (naturally). All we have are diagrams showing:

Indicator Lights (Start OFF, need to match a pattern).
Buttons (Each toggles a specific set of lights).
Joltage Requirements (Relevant for Part 2).

An example input line looks like this:

[.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}

This means:

Target Lights: .##. (Light 0 Off, 1 On, 2 On, 3 Off). Note: 0-indexed.
Buttons: Button 0 toggles Light 3; Button 1 toggles Lights 1 and 3, etc.
Target Joltages: Light 0 needs 3 jolts, Light 1 needs 5 jolts, etc.

Part 1: Indicator Lights

What is the fewest number of button presses required to configure the lights?

The Concept: Bitwise Operations

Since lights are either ON (1) or OFF (0), and buttons toggle them, this is a textbook case for Bitwise XOR.

0 ^ 1 = 1 (Off -> On)
1 ^ 1 = 0 (On -> Off)
Order doesn’t matter: A ^ B = B ^ A.
Self-inverse: A ^ A = 0 (Pressing twice does nothing).

What is ^=?

This is the “XOR and assign” operator. current_state ^= mask is shorthand for current_state = current_state ^ mask. Imagine current_state is 1010 (Lights 1 and 3 on). If mask is 0010 (Light 1), then 1010 ^ 0010 = 1000. Light 1 vanished! If we do it again: 1000 ^ 0010 = 1010. Light 1 is back! This perfectly models the “toggle” behavior of the buttons.

Because pressing a button twice cancels itself out, each button is either pressed 0 times or 1 time. We never need to press a button more than once which makes this… MUCH EASIER!

Why Brute Force?

At first glance, this looks like a search problem (BFS). However, looking at the data, most machines have only ~6 buttons, with a max of 13.

\[2^{13} = 8192 \text{ combinations}\]

This is tiny! We don’t need a complex algorithm; simple brute force is perfectly fine.

Implementation Details

We use a Machine Dataclass to keep our parsing clean and typesafe.

@dataclass
class Machine:
    num_lights: int 
    target_lights: int 
    button_indices: list[list[int]] 
    # ...

In __post_init__, we convert the lists of button indices (e.g., [1, 3]) into integer bitmasks (e.g., 1010 in binary or 10 decimal) for fast math.

def __post_init__(self):
    # Convert [1, 3] -> (1<<1) | (1<<3) -> 1010 binary
    self.button_masks = [sum(1 << i for i in indices) for indices in self.button_indices]

How does 1 << i work? This is the Left Shift operator.

1 << 0 is 1 (binary 0001) -> First light.
1 << 1 is 2 (binary 0010) -> Second light.
1 << 3 is 8 (binary 1000) -> Fourth light.

By summing them (ORing them), we create a single integer “mask” that represents the entire set of lights a button affects.

To find the solution, we use itertools.combinations to try pressing 0 buttons, then any 1 button, then any 2 buttons… the first one that matches our target is guaranteed to be the minimum.

for k in range(num_buttons + 1):
    for combo in itertools.combinations(self.button_masks, k):
        current_state = 0
        for mask in combo:
            # XOR all buttons in this combination
            current_state ^= mask 
        
        if current_state == self.target_lights:
            return k

Part 2: High Voltage!

What is the fewest number of button presses to match the target joltages?

The rules change completely here:

Buttons ADD generally (not XOR).
We need specific Total Joltages per light.
We can press buttons as many times as we want (Integers >= 0).

Why is this a Linear Equation? Each button contributes a fixed amount to specific lights. If Button A adds 1 to Light 1, and Button B adds 1 to Light 1: Total_Light_1 = (1 * Count_A) + (1 * Count_B) This is the definition of a linear equation: y = mx + c (or here Ax = b). Since we have multiple lights, we have a System of simultaneous linear equations.

Note: the buttons now operate on the joltages, not the lights. So the part of the input that describes the target lights is now irrelevant.

The Solution Evolution

Okay, I confess. This one was hard. It definitely exceeds my existing knowledge of Python tools, and my math skills. So I went on a bit of a journey…

Step 1: “It’s Algebra!”

My maths is good enough to spot that this is clearly a System of Linear Equations. For Light i, if x_j is the number of times we press Button j:

\[A_{i0}x_0 + A_{i1}x_1 + \dots = \text{Target}_i\]

Step 2: “Use SymPy!”

My first instinct was to use sympy, a symbolic math library I used back in 2024 Day 13. (See also my article: Python SymPy to Solve Linear Equations).

solution = sympy.solve(equations, variables)

The Problem: We have 10 lights (equations) but up to 13 buttons (variables). In Algebra, if you have more variables than equations, you have an under-determined system. Imagine a + b = 10. a could be 1 and b 9. Or a 99 and b = -89. There is no single answer! SymPy handles this by giving us a “parametric” solution: it says a = 10 - b. It solves in terms of the extra variables. To find the minimum total presses, we would have to test values for these 3 “free” variables. Since the inputs are large, the search space for these 3 variables could be millions of combinations. Searching this “solution space” effectively devolves back into brute-force, which is what we wanted to avoid!

Step 3: “Minimal Integer Solution

The puzzle gives us a great hint by explicitly saying that we can only have integer numbers of button presses. I mean, why say that when it’s so obvious? Well, saying it helped me with journey of discovery! We need a minimal integer solution. A bit of Internet research that combines “minimal integer” alongside “linear algebra” and “sympy” led me to Integer Linear Programming (ILP). I.e. a method of finding the minimal integer solution to a system of linear equations.

We need to:

Minimize cost vector c = [1, 1, ...] (all button presses cost 1).
Subject to constraints Ax = b.
Where x are Integers >= 0.

Step 4: Scipy to the Rescue

How to do this in Python? Well, scipy is the go-to library for this kind of thing. I decided to use scipy.optimize.milp (Mixed-Integer Linear Programming). This library has high-performance solvers designed exactly for this.

Matrix Construction

We build a binary matrix A where rows are lights and columns are buttons.

# A[i][j] = 1 if Button j affects Light i
A = np.zeros((self.num_lights, num_buttons))
for j, indices in enumerate(self.button_indices):
    for i in indices:
        A[i, j] = 1

We then set up the constraints. Note that milp generally solves for bounds constraints (lb <= Ax <= ub), so for exact equality (Ax = b), we set both bounds to b.

from scipy.optimize import milp, LinearConstraint, Bounds

# Constraints: Ax = b
constraints = LinearConstraint(A, b, b)

# Integrality: 1 = Integer, 0 = Continuous
integrality = np.ones(num_buttons)

# Solve
res = milp(c=np.ones(num_buttons), constraints=constraints, integrality=integrality)

A Final Gotcha: Floating Point

Even “Integer” solvers often work in floating point math internally. The solver might return 4.99999999 for 5 presses. If we just cast this: int(4.99999) becomes 4 (Wrong!). So we must round first:

solution = np.round(res.x).astype(int)

Results

This approach was blindingly fast compared to searching through SymPy’s parametric solutions.

The output looks like this:

Part 1 soln=123
Part 2 soln=45678

‹