Yesterday, I did a writeup on Advent of Code Day 9. Today, it’s day 10’s turn.

Day 10

For day 10 (part 2), you’re given a list of “machines” that need fixing. Each machine has several “joltage meters” and buttons that increment one or more joltage meters. The joltage meters start at all zero, and each has a target number to hit.

For example, a machine might have joltage targets {7,5,12,7,2}, and buttons (0,1,4), (1,2,3), and (4,5). Pressing the button (0,1,4) would take the joltage meters from 0,0,0,0,0 to 1,1,0,0,1. Eventually, we want to press the buttons so that the joltage meters read 7,5,12,7,2.

To “fix” the machine, you need to press the buttons such that the joltage meters are set to the right numbers. Your task is to find the smallest number of button presses needed.

A simple example machine:

buttons:
(0,2,3,4) (2,3) (0,4) (0,1,2) (1,2,3,4)

joltage target:
{7,5,12,7,2}

1. Dynamic Programming

At first, this seems like a classic dynamic programming problem. So, I whipped together a memoized recursion algorithm and ran the program until… why is it taking so long? I took a look at the input file and that’s when I realized–the inputs were really really big. Joltage targets could be 100+ with 7+ buttons to choose from.

The problem with dynamic programming is… it’s really just brute force. In the worst case, dynamic programming needs to go through every valid input. And for this problem, there can be a lot of valid inputs. The number of valid inputs for a problem with n buttons and minimum target joltage of m has O(m^n) different valid inputs (since a button can be pressed at most m times before crossing the minimum). That’s exponential runtime complexity. No bueno.

2. Linear Algebra

Thus, dynamic programming is not good enough. Something I’ve learned from doing these Advent of Code puzzles is: whenever you’re stuck, start with taking a closer look at the input. So, I took out pen and paper and started working out some simple examples. Almost immediately, a sense of familiarity hit me as I realized: this looks like linear algebra!

Let’s take a look at the example from above:

buttons:
(0,2,3,4) (2,3) (0,4) (0,1,2) (1,2,3,4)

joltage target:
{7,5,12,7,2}

We can convert the button representation from its current set representation to an indicator representation:

buttons:
(0,2,3,4)   ->  [1,0,1,1,1]
(2,3)       ->  [0,0,1,1,0]
(0,4)       ->  [0,0,0,0,1]
(0,1,2)     ->  [0,1,1,0,0]
(1,2,3,4)   ->  [0,1,1,1,1]

joltage target:
{7,5,12,7,2}

Suddenly, this is looking a lot like a matrix! Maybe if we create a variable vector representing the number of times we press each button… and convert the joltage target into a vector too…

buttons:
1,0,1,1,1
0,0,1,1,0
0,0,0,0,1
0,1,1,0,0
0,1,1,1,1

button press counts:
n_0
n_1
n_2
n_3
n_4
n_5

joltage target:
7
5
12
7
2

And then a bit of rearranging…

1 0 1 1 1     n_0     7
0 0 1 1 0     n_1     5
0 0 0 0 1  *  n_2  =  12
0 1 1 0 0     n_3     7
1 1 1 1 1     n_4     2

We can represent these with variables to be less verbose:

Ax = b

Aha! It’s a linear system of equations! So we can just solve the system by finding the inverse of A and easy game!

But no… alas life is not this simple. There are two problems with this approach. First, it’s not a guarantee that every matrix is invertible. Many of the inputs in fact had too many or too few buttons to make a square matrix. Second, more fundamentally, solving a system of equations gives you an answer, but does not guarantee the best answer. In this case, we want the smallest number of button presses, so linear algebra won’t do.

3. Linear Programming

Upon this realization, my mind jumped back to EECS127, the class I took in college on optimization. I realized that this problem could very simply be modeled as a linear programming problem!

4. Integer Linear Programming

Except for one problem. Linear programming doesn’t work with integer constraints. For that, we need integer linear programming, which is NP-hard. Uh oh.

However, just because something is NP-hard in theory, doesn’t mean it’s slow in practice. So I imported scipy’s ILP function just to see if it would work. And it did!

5. Brute Force Again (Constrained by Linear Algebra)

I was done, but this solution didn’t satisfy me. I really wanted to solve the puzzle without importing any libraries outside of python’s standard library. That means no scipy, no numpy. I looked at some of people’s solutions on the reddit thread for approaches that didn’t use any sort of ILP or theorem solver. I saw that pretty much every solution fell into one of two classes:

  1. Use an ILP or theorem solver (ILP, Z3, etc.)
  2. Do brute force “intelligently”.

By “intelligently”, I mean: constrain the problem some way. Earlier, I mentioned that there are O(m^n) inputs to brute force. If you can find a way to constrain the problem so that there are less inputs to sort through, then maybe the problem becomes tractable.

One solution I saw was careful about the order in which they tried inputs so that they could prune off impossible branches as early as possible. However, the one that caught my eye was one that used linear algebra to constrain the problem.

Recall the linear system of equations that we want to optimize:

Ax = b

Instead of trying to enumerate every possible x, we can run Gaussian elimination on the augmented matrix A|b to put it into reduced row echelon form (RREF). From the RREF, we can identify the pivot and free variables.

For example,

If we had A and b like:
A  [1 0 1 0]    b  [3]
   [0 1 0 1]       [5]
   [1 1 1 1]       [8]

The augmented matrix A|b would be:
[1 0 1 0 | 3]
[0 1 0 1 | 5]
[1 1 1 1 | 8]

And the RREF would be:
[1 0 1 0 | 3]           ^ = pivot
[0 1 0 1 | 5]           * = free
[0 0 0 0 | 0]
 ^ ^ * *

Columns in the RREF with a "pivot entry", or a leading 1 in some row,
are pivot columns. If not, then they are free columns. In this example,
columns 0 and 1 are pivot columns, while columns 2 and 3 are free 
columns.

This means that in the variable vector x, x_0 and x_1 are pivot 
variables, while x_2 and x_3 are free variables:

x  [x_0]
   [x_1]
   [x_2]
   [x_3]

The neat thing about pivot variables is that they are fully constrained by the free variables. In other words, given values for all the free variables, you can determine the values of the pivot variables.

To see why, we can convert our RREF back into a system of equations.

RREF:
[1 0 1 0 | 3]
[0 1 0 1 | 5]
[0 0 0 0 | 0]

    A      *    x    =   b

[1 0 1 0]     [x_0]     [3]
[0 1 0 1]  *  [x_1]  =  [5]
[0 0 0 0]     [x_2]     [0]
              [x_3]

x_0 + x_2 = 3
x_1 + x_3 = 5

x_0 = 3 - x_2
x_1 = 5 - x_3

We can represent the pivot variables `x_0` and `x_1` in terms of 
the free variables `x_2` and `x_3`!

This is huge because instead of brute forcing over every variable, we can just brute force over the free ones and use them to determine the pivot variables. It turns out that the inputs given always had at most 3 free variables, so suddenly the runtime is reduced from O(m^n) to O(m^3). From exponential to cubic.

Figuring out the theory wasn’t enough for me, so I sat down and painfully implemented the whole thing with vanilla python arrays. My solution ended up crunching all the solutions in a little under a minute.

5.5 Bonus: A Neat Trick

After implementing all the linear algebra with vanilla python, I still needed to implement the brute force algorithm. The most intuitive way to brute force over all the variables would be to write something like:

for free0 in range(max0):
    for free1 in range(max1):
        for free2 in range(max2):
            ...
                for freeN in range(maxN):
                    solve(...)

but this doesn’t work because the number of free variables is variable, so I can’t just write a variable number of for-loops. It happens to be that there were at most 3 free variables for this puzzle, but in the general case there could be arbitrarily many.

The key to resolving this is realizing that all of the different possible free values can be ordered. And if they can be ordered, you can simply use a single loop.

For example, for free variables (free0, free1, free2) with 
maximums (1,2,2), the possible values are:
(0,0,0)
(0,0,1)
(0,0,2)
(0,1,0)
(0,1,1)
(0,1,2)
(0,2,0)
(0,2,1)
(0,2,2)
(1,0,0)
(1,0,1)
(1,0,2)
(1,1,0)
(1,1,1)
(1,1,2)
(1,2,0)
(1,2,1)
(1,2,2)
It's like counting where each digit is in a different base!

In python, a neat way to produce this order is to use a generator. My code ended up looking something like this:

for x in iterate(maximums):
    solve(...)

// ...

def iterate(maximums):
    n = len(maximums)
    current = [0] * n

    while True:
        yield current.copy()

        for i in range(n):
            current[i] += 1
            if current[i] <= maximums[i]:
                break
            current[i] = 0
        else:
            return

6. Conclusion

Overall, I had a lot of fun with this problem. I definitely could have just imported scipy’s ILP solver and called it a day, but I’m so glad I decided to dive deep into this puzzle and explore the constrained brute force approach. By thinking through the linear algebra solution and implementing it in vanilla python, I feel like I got to brush up on my linear algebra and really deepen my understanding.

I’m really grateful for Eric Wastl for creating the puzzles every year and running Advent of Code. I think it’s really fun and a great way to learn some new things. I also really enjoy the sense of community from knowing that programmers all around the world are working on these puzzles at the same time, and seeing all the different strategies (and programming languages) people used to solve the puzzles on reddit afterwards.