Advent of Code 2025; Day 10: Factory

Part 1: Activating the Machines

I’ve come across an underground factory but all the machines are offline. The elves need them running, but the initialisation manual has been eaten by a dog, leaving only indicator light diagrams, button schematics, and some joltage requirements.

Each machine’s specification looks something like this:

1
2
3
4
5
6
7

[.##.]  (3)  (1,3)  (2)  {3,5,4,7}
  │      │     │     │      │
  │      │     │     │      └─ Joltage requirements
  │      │     │     └─ Button: toggles light 2
  │      │     └─ Button: toggles lights 1 and 3
  │      └─ Button: toggles light 3
  └─ Desired state: off, on, on, off

All lights start in the off position. Each button, when pressed, toggles specific lights (0-indexed). The goal is to reach the desired state shown in the indicator diagram using the fewest total button presses across all machines.

Data Structure

A little more elaborate this time, I created a Machine class to house the state, button schematics and joltage of each machine:

1
2
3
4
5
6
7
8

class Machine:
    def __init__(self, lights: list[bool], buttons: list[list[int]], joltage: list[int]) -> None:
        self.on_state = tuple(lights)  # Desired end state
        self.buttons = buttons
        self.joltage = joltage

    def __repr__(self) -> str:
        return f"[{''.join(['#' if x else '.' for x in self.on_state])}]"

The on_state stores the desired configuration as a tuple of booleans - True for on (#), False for off (.). Using a tuple rather than a list means it’s hashable, which becomes more important later.

Thinking in Paths

My first thought was once again fairly naive (I often do this on purpose to think of the problem in simple terms): try every possible combination of buttons and check the state after each press. If it matches the desired state, record the number of presses. Finally, sort to find the minimum.

But there’s a couple of key points to consider; it’s effectively a shortest path algorithm, finding the least number of steps to reach the goal - that hints at how to design this algorithm. In addition to that, toggling a button twice effectively achieves net zero. Pressing the same button an even number of times is pointless - I either press it once or not at all. This limits our search space significantly.

How best to explore this? As it’s effectively a path the obvious choices are a recursive DFS (Depth First Search) which could find all paths, but BFS (Breadth First Search) is probably a better fit to find the shortest path.

Using Python’s heapq module, I can maintain a priority queue sorted by number of presses. This ensures I always explore states reachable in fewer presses first - the moment I hit the target state, I know it’s the minimum.

Parsing the Input

The parsing involves some list comprehension gymnastics to split apart the machine specifications:

1
2
3
4
5
6
7
8
9

def load_machines(input_data: str) -> list[Machine]:
    machines = []
    for line in input_data.strip().splitlines():
        parts = line.split()
        lights = [x == "#" for x in parts[0][1:-1]]
        buttons = [[int(x) for x in buttons[1:-1].split(",")] for buttons in parts[1:-1]]
        joltage = [int(x) for x in parts[-1][1:-1].split(",")]
        machines.append(Machine(lights, buttons, joltage))
    return machines

Not the prettiest code I’ve written - lots of slicing and splitting - but it gets the job done. The [1:-1] slices strip off the brackets from each component.

The Solution

In my Machine class I’ve added an activate method that finds the minimum presses for a single machine, this implements the core BFS algorithm:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

def activate(self) -> int:
    initial = tuple([False] * len(self.on_state))

    # (press_count, state) - heapq sorts by first element
    queue = [(0, initial)]
    heapq.heapify(queue)

    # Track which states we've already tried
    tried = {initial}

    while queue:
        presses, state = heapq.heappop(queue)

        # From this state, try each button
        for button in self.buttons:
            # Apply button to get new state
            new_state = list(state)
            for b in button:
                new_state[b] = not new_state[b]
            new_state = tuple(new_state)

            # Did this button activate the machine?
            if new_state == self.on_state:
                return presses + 1

            # Haven't seen this state before - queue it
            if new_state not in tried:
                tried.add(new_state)
                heapq.heappush(queue, (presses + 1, new_state))

    return 0  # No solution found

The tried set is an important optimisation - without it I’d revisit the same states endlessly - this instead becomes a simple check to see if I have already explored a given path for a number of presses. There’s a bit of back and forth due to tuples being immutable, so switching to a list allows to set the value by the button index easily. I then switch back to a tuple as that is then hashable for the cache key.

Putting it all together:

1
2
3

def part1(input_data: str) -> int:
    machines = load_machines(input_data)
    return sum(machine.activate() for machine in machines)

This works fast, even with the real input. The factory machines are coming back online!

Part 2: Joltage Calibration

Surprise; those joltage requirements I ignored earlier now matter. As the machines come back online, I need to calibrate them to an exact joltage configuration. Each indicator light has a target joltage value, and the joltage increments by 1 every time that light is toggled. I need to match both the indicator state AND the joltage values.

So let’s just try adapting the same BFS approach, adding joltage state to the mix:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

def calibrate(self) -> int:
    initial = tuple([False] * len(self.on_state))
    initial_jolt = tuple([0] * len(self.joltage))

    queue = [(0, initial_jolt, initial)]
    heapq.heapify(queue)

    tried = {(initial_jolt, initial)}

    while queue:
        presses, jolts, state = heapq.heappop(queue)

        for button in self.buttons:
            new_state = list(state)
            new_jolts = list(jolts)
            for b in button:
                new_state[b] = not new_state[b]
                new_jolts[b] += 1
            new_state = tuple(new_state)
            new_jolts = tuple(new_jolts)

            # Now we need BOTH conditions to match
            if new_state == self.on_state and new_jolts == tuple(self.joltage):
                return presses + 1

            if (new_jolts, new_state) not in tried:
                tried.add((new_jolts, new_state))
                # Prune paths where any joltage already exceeds target
                if not any(j > self.joltage[i] for i, j in enumerate(new_jolts)):
                    heapq.heappush(queue, (presses + 1, new_jolts, new_state))
    return 0

The state space is now much larger - I’m tracking both indicator states and joltage values. I’ve added pruning to skip paths where any joltage exceeds its target (since it can only increment, never decrement).

Unfortunately, this doesn’t complete in reasonable time on the real input. The sheer number of possible states has exploded and is too severe, and I suspect there’s a smarter mathematical approach needed here.

To be continued when I have more time to think this through…

As always, code is available at github.com/lordmoocow/aoc25.

Part 1 fell nicely to BFS with a priority queue - I’m quite familiar with this from previous AoC events but also other projects involving pathing algorithms. Part 2’s joltage requirements blow this out of the water though, and brute force isn’t cutting it. I’ll need to come back to this one with fresh eyes. 2 days left.