AoC 2025 Day 10

Introduction

Every year I do Advent of Code (AoC), and there are always one or two problems that stick with me. These are problems that I usually struggle with initially, and as such spend a long time ruminating on. I like to focus on such problems since these usually represent either a blind spot in my problem solving toolkit, or they are at my personal sweet spot of difficulty, i.e. not too difficult such that they are discouraging, but difficult enough to push me out of my comfort zone. To cement my insights from these problems further I am going to start writing up such problems when I encounter them.

Importantly, these write-ups will focus on the core logic of the solution. This is important to distinguish, since deciphering and breaking down the problem descriptions of AoC problems is usually a problem within its self. These write-ups will simply present these simplified problem statements, that you would usually have to decipher yourself. Additionally, these write-ups will not be focusing on how to parse the line-by-line input for these problems. Again this can often represent a significant part of the problem, usually involving complex regex expressions. For a full implementation of the solutions I discuss you can consult my GitHub.

To start these write-ups I will be discussing 2025 Day 10, in particular part 2. This problem was challenging for many reasons. However, one of the main reasons I liked this problem, is that it forces you to consider an out of the box way of utilising your solution to part 1, and punishes you if you try to directly adapt your solution to part 1 in the most obvious fashion. This is a useful reminder to not only consider how changes in requirements can affect your future code, but also how they can cause you to re-evaluate how your existing code is being used.

Part 1

Problem

You are presented with lightbulbs and buttons. The lightbulbs can either be on or off and they all start in the off state. Each button wires into different subset of lightbulbs, such that pressing a button will flip the state (on or off) of all lightbulbs wired to that button. You must write an algorithm to determine the minimum number of button presses required to achieve some specified final state of the lightbulbs.

Example

buttons = [(3), (1,3), (2), (2,3), (0,2), (0,1)]
target_state = "0110"

The solution to the above is 2, the final state can be achieved by pressing button (0,2) and (0, 1).

Solution - BFS

Exposition

We can treat the above as a finite state machine, with a state space equal to and a action space equal to set of buttons . At each timestamp we are able to choose one action, which will then cause a transition to a different state. As with any finite state machine, we can associate a directed graph with this state machine, whereby the states are the vertices of this graph and the actions for a given state represent the directed edges between these vertices.

Under this framework, we can reframe our problem as a shortest path algorithm between our starting state 0...0 and some target state. Given that the edges associated with our graph are of equal weight, i.e. each edge is associated with 1 button press, it follows that the most efficient shortest path algorithm will be a Breadth First Search (BFS). Additionally, the first time a state is visited will always produce the shortest path going through that state, therefore we should also make use of a “seen” set, meaning that vertices are only ever added to the BFS queue once.

One way to implement the state tracking logic would be to use some light state vector and button vectors , such that the result of some button press would be:

However, we can achieve a isomorphic algebra by using 32 bit integers under the exclusive or (^ ) operation. Under this framework the parity of the i’th bit of our state integer takes the place of the parity of the i’th component of our vector. This leads to a much more space efficient implementation, i.e. 32 bits versus bits, and such bitwise operations can be performed with much fewer CPU cycles. The only constraint this imposes is that our state space dimension must be less than 32, i.e. .

Implementation

def find_minimum_clicks_for_target_state(buttons: list[int], target_state: int) -> int:
    n_buttons = len(buttons)

    q = deque([0])
    seen = set()

    clicks = 0
    while q:
        for _ in range(len(q)):
            cur_state = q.popleft()

            if cur_state == target_state:
                return clicks

            for i in range(n_buttons):
                next_state = cur_state ^ buttons[i]
                if next_state not in seen:
                    q.append(next_state)
                    seen.add(next_state)

        clicks += 1

    raise RuntimeError("No solution found")

Asymptotic Analysis

Solution - Combinations

Exposition

Lets now strive to find a more efficient way of exploring our state space. To motivate this lets start with the observation that a double button press is a “no-op”, i.e. doesn’t do anything. Lets see if we can formulate this mathematically.

Suppose we unravel our iterative light vector equation and we keep track of the button we pressed at timestamp via the function . Then the state of our light vector can be written

Now suppose we collect all similar button pushes and note that is the zero vector. Then we would end up with an equation:

But, this is a linear combination of button vectors. Therefore we can collect our button vectors into a button matrix and our button press counts into a vector . This then gives:

Where we will now drop the for brevity. Therefore we can restate our problem as:

Where is equal to the component sum of the button press combination vector , i.e. the number of button presses.

However, by the division theorem we can write our vector as:

By the rules of modular arithmetic, it follows that the even portion of the vector does not contribute to the final state:

This means that the vector part of vector does not contribute anything to us achieving our target state, the only part that matters is the vector. Therefore, button presses should not be wasted on this component if we are to minimise the the total number of button presses to achieve the desired state, i.e. . This means we can restate our problem as:

We can now change our state space exploration algorithm to simply explore the vector space . However, this is equivalent to simply exploring all button press combinations, where a 0 indicates not including a button and 1 indicates including a button. We can systematically do this by simply modifying our BFS such that only buttons after the current button’s index are included as possible presses. For a given button press trajectory this means that buttons are only allowed to be included at most once, meaning that all combinations will be explored exactly once.

Implementation

def find_minimum_clicks_for_target_state(buttons: list[int], target_state: int) -> int:
    n_buttons = len(buttons)

    q = deque([(0, 0)])

    clicks = 0
    while q:
        for _ in range(len(q)):
            cur_state, next_button_idx = q.popleft()

            if cur_state == target_state:
                return clicks

            for i in range(next_button_idx, n_buttons):
                button = buttons[i]
                q.append((cur_state ^ button, i + 1))

        clicks += 1

    raise runtimeerror("No solution found")

Asymptotic Analysis

Part 2

Problem

Write an algorithm to determine the minimum number of button presses to achieve some specified total number of on-off transitions for each individual lightbulb.

Example

buttons = [(3), (1,3), (2), (2,3), (0,2), (0,1)]
target_counts = [3,5,4,7]

This requires a minimum of 10 button presses. One way of doing this is as follows:

• (3) - press 1 time
• (1, 3) - press 3 times
• (2, 3) - press 3 times
• (0, 2) - press 1 time
• (0, 1) - press 2 times

Solution - BFS (Failed)

Exposition

The most straightforward way of solving this problem is to directly adapt our first BFS solution. Previously we could encode our state with integers, which was possible since we only had to store a zero or one per component of our state. However, now our state represents counts, which can take on any value in . Therefore, we now need to use a tuple to encode our state. We can now progress as before, updating our state based on the available button presses in a BFS manner, returning the minimum number of presses required to get to the desired state.

An integer will still be used to encode the button vector since this is still a space efficient solution for the button and the code for parsing the buttons in this format already exists. However, now that a mixture of representations are being used, we will now need a way to access elements of this integer vector. This can be achieved using the trick button & (1 << i), which will retrieve the i’th bit of our button vector.

Implementation

def find_minimum_clicks_for_target_state(
    buttons: list[int], target_counts: list[int]
) -> int:
    n_lights = len(target_counts)

    cur_state = tuple(target_counts)
    q = deque([cur_state])

    zero_state = (0,) * n_lights

    seen = set()
    clicks = 0
    while q:
        for _ in range(len(q)):
            cur_state = q.popleft()

            if cur_state == zero_state:
                return clicks

            for button in buttons:
                new_state_list = list(cur_state)

                valid = True
                for i in range(n_lights):
                    if button & (1 << i):
                        new_state_list[i] -= 1
                        if new_state_list[i] < 0:
                            valid = False
                            break

                if valid and (new_state := tuple(new_state_list)) not in seen:
                    q.append(new_state)
                    seen.add(new_state)

        clicks += 1

    raise RuntimeError("No solution found")

Asymptotic Analysis

Discussion

Unfortunately, this solution was not computationally tractable. This is because the state space is now , where is the max count in the target counts vector. This is problematic since , meaning that the number of states that we have to explore has exploded.

Solution - A* (Failed)

Exposition

One way we might try to overcome the short comings of the previous approach is by using a different shortest path algorithm. As previously stated the edges of our graph all have the same weight, i.e. the cost of an action is one button press. However, we might find salvation in the A* algorithm, which modifies Dijkstra’s to use an optimistic total cost/distance heuristic to act as the order in the priority queue. Previously it was not feasible to come up with such a heuristic. However, with this new approach we notice that a button press can only increment each component of the current state at most once. This means that optimistic heuristic for the remaining number of button presses would be the maximum component wise difference between the current counts and target counts.

Implementation

def find_minimum_clicks_for_target_state(
    buttons: list[int], target_counts: list[int]
) -> int:
    n_lights = len(target_counts)

    cur_state = tuple(target_counts)
    q = [(max(cur_state), 0, cur_state)]

    zero_state = (0,) * n_lights

    seen = set()
    clicks = 0
    while q:
        for _ in range(len(q)):
            _, dist, cur_state = heapq.heappop(q)

            if cur_state == zero_state:
                return dist

            dist += 1
            for button in buttons:
                new_state_list = list(cur_state)

                valid = True
                for i in range(n_lights):
                    if button & (1 << i):
                        new_state_list[i] -= 1
                        if new_state_list[i] < 0:
                            valid = False
                            break

                if valid and (new_state := tuple(new_state_list)) not in seen:
                    heapq.heappush(q, (dist + max(new_state), dist, new_state))
                    seen.add(new_state)

        clicks += 1

    raise RuntimeError("No solution found")

Asymptotic Analysis

Discussion

Again, unfortunately the state space that has to be explored is simply too large for this to be computationally tractable.

Solution - Dynamic Programming

Exposition

After failing to solve part 2 using graph based approach, lets take inspiration from our alternative approach to part 1, where progress was made when we mathematically formalised the problem.

Previously we were trying to solve a “parity” problem of the form:

We previously saw from the division theorem that our button press count vector could be split into . This was useful since it let us transform our problem into:

This meant we could focus on finding the combination vector , which transformed our problem into a simpler combinatorics problem that could be solved in time.

Lets now see if we can use our previous solution to aid us in solving our current problem. We can formalise our current problem as:

Where, is some desired count vector.

Lets, now break this down using the division theorem:

With the motivation of using our previous solution lets now take the modulo 2 of everything

This is a parity problem, the type that we are able to solve using our solution to part 1. However, the major caveat is that our previous solution was used to find the with the fewest presses that solved the parity problem. However, it is now possible that this might have an associated large number of presses associated with its quotient , i.e. we cannot generally assume that this will be the optimal for part 2 of our problem.

Instead, we now must consider the set of all combination vectors that are consistent with our parity condition. Modifying our previous solution to achieve this goal is simple, we just need to continue the combination search beyond the point of the first combination being found that satisfies the solution. We can then append combinations which meet the criteria to a list such that they can be returned by the function. After performing such an exhaustive search we will be left with every possible combination vector that satisfies the parity problem. One of these combination vectors must be associated with the optimal solution, since the parity equation represents a necessary condition that any optimal solution must obey.

Let us now investigate how we can determine the quotient for a given combination vector . We can rearrange one of the equations above to give:

But this is of the same form as our original problem, which means we can express our problem recursively as:

Notice that components of our target counts vector have at least halved. Additionally, we can prune branches from our recursion tree by noticing that any subproblem count vector that contains fractional or negative values will have no associated positive integral button press solution, and therefore is invalid. Furthermore, we note that the base case for this procedure is , i.e. the number of presses required to achieve the zero count vector state is zero. Combining this information leads to the conclusion that the depth of the recursion tree associated with this procedure will be .

Lets bring all these parts together to define the overall recurrence relation for our minimum counts problem. Let represent the set of all valid combination vectors for a given target count vector, where combination vectors that give rise to invalid quotients have been removed. Then it follows that the solution to our problem can be stated as

Finally, we note that it is possible for our function to receive the same input multiple times, therefore the solution of this problem would also benefit from top-down dynamic programming, i.e. memoization.

Implementation

@lru_cache(None)
def find_all_button_clicks_and_combos_for_target_state(
    buttons: tuple[int], target_state: int
) -> list:
    res = []

    n_buttons = len(buttons)

    # state, button_combo, next_button_idx
    q = deque([(0, 0, 0)])

    clicks = 0
    while q:
        for _ in range(len(q)):
            cur_state, button_combo, next_button_idx = q.popleft()

            if cur_state == target_state:
                res.append((clicks, button_combo))

            for i in range(next_button_idx, n_buttons):
                button = buttons[i]
                next_button_combo = button_combo | (1 << i)
                q.append((cur_state ^ button, next_button_combo, i + 1))

        clicks += 1

    return res


def find_minimum_number_of_button_presses_for_target_counts(
    buttons: tuple[int, ...], target_counts: tuple[int, ...]
) -> int:
    n_lights = len(target_counts)
    n_buttons = len(buttons)

    zero_vector = (0,) * n_lights

    @lru_cache(None)
    def rec(target_counts: tuple[int, ...]) -> int:
        if target_counts == zero_vector:
            return 0

        target_state = 0
        for i, count in enumerate(target_counts):
            if count % 2:
                target_state |= 1 << i

        res = 1_000_000
        button_clicks_and_combos = find_all_button_clicks_and_combos_for_target_state(
            buttons, target_state
        )
        for clicks, button_combo in button_clicks_and_combos:
            next_target_counts = list(target_counts)

            valid = True
            for i in range(n_lights):
                for j in range(n_buttons):
                    if buttons[j] & (1 << i) and button_combo & (1 << j):
                        next_target_counts[i] -= 1

                if next_target_counts[i] % 2 == 1 or next_target_counts[i] < 0:
                    valid = False
                    break
                else:
                    next_target_counts[i] //= 2

            if valid:
                res = min(res, clicks + 2 * rec(tuple(next_target_counts)))

        return res

    return rec(target_counts)

Asymptotic Analysis

Discussion

The recursive nature of this problem and the usage of the division theorem reminded me a lot of the Euclidian algorithm. Obviously it is not the same, since the Euclidian algorithm involves you swapping the current iteration’s remainder for the next iterations divisor. Meanwhile in this problem the divisor stays the same. Nonetheless, intuitions about the Euclidian algorithm helped me greatly when coming up with the solution to this problem. I will be sure to lean on these intuitions again in the future if I am faced with a problem that needs to be broken down into subproblems using the division theorem.

Bonus Solution - Linear Programming

Exposition

During the last solution we reformulated our problem as:

Which can be identified as a integer linear programming problem:

Where we have:

This means we can solve this problem using an integer linear programming library, like the one contained in SciPy.

Implementation

def find_minimum_clicks_for_target_state(
    buttons: np.ndarray, target_counts: np.ndarray
):
    n_lights, n_buttons = buttons.shape

    c = np.ones(n_buttons)

    constraints = LinearConstraint(buttons, target_counts, target_counts)
    bounds = Bounds(0, np.inf)
    integrality = np.ones(n_buttons)

    res = int(
        milp(c, constraints=constraints, bounds=bounds, integrality=integrality).fun
    )

    return res

Discussion

AoC does not mention any rules against using libraries. However, I do not feel this was the intended solution by the problem creator, given that it does not utilise part 1 at all. Nonetheless, I have included it as an extra, since this is likely the best solution if you encountered such a problem in the real world.