2025 Day 10: Factory

Advent of Code
1

I was beginning to think I wasn’t going to solve the second part. This is usually around the time that the AoC problems are huge headaches. I have it in my head that around days 21-23 were usually the worst.

For the first part:

I used a simple depth-first search with an array of booleans to indicate whether or not I had visited a particular light position. I used a binary heap to track pending visits.

For the second part:

It was a little while before I realized that I no longer had to worry about all the lights being turned off, and then many, many hours before I got to a solution that runs in 5 minutes. I do a depth first search, based around working on fulfilling the joltage requirement for a specific light. I look for the light that has the fewest buttons (among the buttons I haven’t pushed yet) that set it, and I break ties by the number of joltage units that still need to be added to the light, the fewer the better.So at each step, then, I have N buttons that manipulate some light that needs J more units for the joltage. If N=1, I press it J times (if possible). If N > 2 then I start at the maximum J value and count down to 0 for the first button, and then repeat that for the next button, starting with whatever J is left, and so forth. If I get to the last button, I don’t need to count down, it’s just however many J units are left after pressing the previous buttons some number of times. I keep track of which lights I have analyzed and which buttons I have pressed so I don’t repeat them (until I back up to a previous configuration).

2 Likes
2

Wow, very impressive solution for part 2. I did not think it was possible to solve it without writing some kind of equation solver.

As I mentioned in the solutions thread I didn’t solve part 2 in Ada but here’s the theory:

Given some input:

[.##.##] (4,5) (0,5) (2,3) (1,3,5) (0,3,5) (0,2,3,5) (0,1,4) (0,2,4,5) {198,181,22,50,173,65}

We can rewrite each button as a vector (1 if it increments a joltage, or 0 if not) times some scalar (the number of presses). In this example the vectors are:

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

When we multiply each vector by a scalar it starts to look like a linear combination:

k0*v0 + k1*v1 + k2*v2 + ... + kN*vN = [198,181,22,50,173,65]

where kN is the number of presses and vN is the vector transformation mentioned above for button N.

Expanded, you end up with this system of equations (note the vectors from above are transposed):

k0*0 + k1*1 + k2*0 + k3*0 + k4*1 + k5*1 + k6*1 + k7*1 == 198
k0*0 + k1*0 + k2*0 + k3*1 + k4*0 + k5*0 + k6*1 + k7*0 == 181
k0*0 + k1*0 + k2*1 + k3*0 + k4*0 + k5*1 + k6*0 + k7*1 == 22
k0*0 + k1*0 + k2*1 + k3*1 + k4*1 + k5*1 + k6*0 + k7*0 == 50
k0*1 + k1*0 + k2*0 + k3*0 + k4*0 + k5*0 + k6*1 + k7*1 == 173
k0*1 + k1*1 + k2*0 + k3*1 + k4*1 + k5*1 + k6*0 + k7*1 == 65

or as a matrix:

   0      1      0      0      1      1      1      1  |  198
   0      0      0      1      0      0      1      0  |  181
   0      0      1      0      0      1      0      1  |  22
   0      0      1      1      1      1      0      0  |  50
   1      0      0      0      0      0      1      1  |  173
   1      1      0      1      1      1      0      1  |  65

I believe the key to solving this without z3 is to write a solver that reduces the matrix to RREF, which will let you find a solution but it won’t necessarily be optimal. You will still need to do a bit of searching to find the minimum number of button presses.

For the above example one set of optimal values would be:

k0 = 2
k1 = 0
k2 = 0
k3 = 23
k4 = 18
k5 = 9
k6 = 158
k7 = 13
2 Likes
3

Today’s bad omen was that I had trouble merely parsing the data. I knew that was a bad sign.

(Don’t ask why I struggled with that. I don’t quite understand why myself.)

At least Part 1 worked out great. For I ran a counter from 1 to 2**11, converted it to an array of booleans to indicate which buttons to turn on, and converted that to an array of booleans indicating which indicators were turned on. Very, very fast, though I took longer to write the last part than I should have. (Possibly related to my parsing issues.)

For Part 2 I spent 2-3 hours looking at it and thought of something like @wutka’s approach, but didn’t want to wait an eternity to find out either that (a) it was infeasible due to combinatorial complexity, or (b) feasible but wrong because… well, see what I wrote above about parsing and Part 1.

So I looked at the Reddit solutions & sighed even harder because I used to teach linear programming, so you’d think I’d have recognized that this is a linear programming problem. I came up with the mathematical description fine, but how to solve it? Some years ago I used gnat to generate a thin binding to glpk, so it seemed it should be a snap to use that.

Nope.

It took me another 2-3 hours to find the right incantation that would convince glpk to solve even the first example problem. I think the problem was that (a) I first forgot to set the objective function’s coefficients, then (b) when I realized the problem, I mysteriously set the coefficients to 0 instead of 1, so of course the objective value was always 0.

The final kick in the teeth came when I finally got it all working and forgot to turn one of the levers back to the correct position: while twiddling to try and make it work, I had set the row constraint to be a lower bound rather than a fixed bound, so I ended up getting the wrong answer.

I should probably get some sleep, but we’re still 3 days away from that.

2 Likes
4

Had to brush up on my linear algebra, but here’s the continuation of my idea from before:

I will use the same example matrix as above.

The matrix above has 6 equations (rows) and 8 variables (columns k0 up to k7). We first need to reduce the matrix as much as possible and write it in row echelon form. This will not actually be in reduced row echelon form because there are some nasty ratios in the equations. For this purpose I used scipy.linalg.lu, but in Ada we’d need to do this ourselves or find a library. This gives us:

1      0      0      0      0      0      1      1  |  173
0      1      0      0      1      1      1      1  |  198
0      0      1      0      0      1      0      1  |   22
0      0      0      1      1      0      0     -1  |   28
0      0      0      0      1      0     -1     -1  | -153
0      0      0      0      0      0      3      1  |  487

We can see that columns for k5 and k7 do not have a row with a leading integer, so they can take any value. Conceptually, we can insert those equations manually to state k5 = x and k7 = y:

1      0      0      0      0      0      1      1  |  173
0      1      0      0      1      1      1      1  |  198
0      0      1      0      0      1      0      1  |   22
0      0      0      1      1      0      0     -1  |   28
0      0      0      0      1      0     -1     -1  | -153
0      0      0      0      0      1      0      0  |    x   <-- new row
0      0      0      0      0      0      3      1  |  487
0      0      0      0      0      0      0      1  |    y   <-- new row

Now we just need to find values for x and y such that A * presses = b where A is the non-augmented matrix and b is the augmented column. presses is the vector [k0, k1, k2 ... k7] and is given by back substitution using the values we pick for x and y.

matrix form equation              simplified equation
k7 = y                            k7 = y
3*k6 + k7 = 487                   k6 = (487 - y) / 3
k5 = x                            k5 = x
k4 - k6 - k7 = -153               k4 = k6 + y - 153
k3 + k4 - k7 = 28                 k3 = 28 - k4 + y
k2 + k5 + k7 = 22                 k2 = 22 - x - y
k1 + k4 + k5 + k6 + k7 = 198      k1 = 198 - k4 - x - k6 - y
k0 + k6 + k7 = 173                k0 = 173 - k6 - y

After back substitution, we can produce solutions by varying only two values instead of eight. This greatly reduces the search space.

There are two constraints that make this even easier: all values of k must be integers (no 0.5 button presses) and they must be >= 0 (no unpressing of buttons). Now we can generate a bunch of solutions trivially.

Here’s a direct translation of these equations to python:

import itertools
best = 1e9
for x, y in itertools.product(range(100), range(100)):
    k = [0] * 8
    k[7] = y
    k[6] = (487 - y) / 3
    k[5] = x
    k[4] = k[6] + y - 153
    k[3] = 28 - k[4] + y
    k[2] = 22 - x - y
    k[1] = 198 - k[4] - x - k[6] - y
    k[0] = 173 - k[6] - y
    if all(val.is_integer() and val >= 0 for val in k):
        if sum(k) < best:
            best = int(sum(k))
            print(x,y,[int(val) for val in k],best)

Sure enough this generates an optimal solution:

x y  presses                          sum(presses)
0 1  [10, 25, 21, 19, 10, 0, 162, 1]  248
0 4  [8, 21, 18, 20, 12, 0, 161, 4]   244
0 7  [6, 17, 15, 21, 14, 0, 160, 7]   240
0 10 [4, 13, 12, 22, 16, 0, 159, 10]  236
0 13 [2, 9, 9, 23, 18, 0, 158, 13]    232
0 16 [0, 5, 6, 24, 20, 0, 157, 16]    228
1 16 [0, 4, 5, 24, 20, 1, 157, 16]    227
2 16 [0, 3, 4, 24, 20, 2, 157, 16]    226
3 16 [0, 2, 3, 24, 20, 3, 157, 16]    225
4 16 [0, 1, 2, 24, 20, 4, 157, 16]    224
5 16 [0, 0, 1, 24, 20, 5, 157, 16]    223   <------ correct answer

There’s one last piece of the puzzle missing: how do we determine the upper bound on x and y? There’s probably a better way to do this, but one method is to look at the joltages that each button increments and pick the minimum of them. Pressing the button more times than that would go beyond the target joltage which makes the solution invalid. In practice the actual upper bound may be lower because pressing a second button can reduce the number of times you can press the first one. Maybe we can come up with another system of equations for that later. :slight_smile:

For reference here’s our input again:

(4,5) (0,5) (2,3) (1,3,5) (0,3,5) (0,2,3,5) (0,1,4) (0,2,4,5) {198,181,22,50,173,65}
                                  ^~~ k5 ~~         ^~~ k7 ~~

k5 (x) upper bound is min(198,22,50,65) = 22
k7 (y) upper bound is min(198,22,173,65) = 22

Add 1 to each bound to get the number of states we need to consider since we can leave a button at zero presses. Thus we can solve this specific example in (1+22)*(1+22) = 529 iterations.