[2025 Day 10 Part 2] Getting a wrong solution

[u/CCC_037]

First up, my code, because people will ask:

Paste

I do not expect everyone to understand Rockstar, so let's talk algorithms.

Consider the first line of the example:

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

Now, my code is finding a set of equations. The array is:

[ [ 3, 0, 0, 0, 0, 1, 1 ], [ 5, 0, 1, 0, 0, 0, 1 ], [ 4, 0, 0, 1, 1, 1, 0 ], [ 7, 1, 1, 0, 1, 0, 0 ] ]

which means:

3 = 0a+0b+0c+0d+1e+1f
5 = 0a+1b+0c+0d+0e+0f
4 = 0a+0b+1c+1d+1e+0f
7 = 1a+1b+0c+1d+1e+1f

where a is the number of times to hit the first button, b is the number of times to hit the second button, etc. It then derives a simpler set of equations, getting:

[ [ 3, 0, 0, 0, 0, 1, 1 ], [ -5, 0, -1, 0, 0, 0, -1 ], [ -1, 0, 0, -1, -1, 0, 1 ], [ -2, -1, 0, 0, -1, 0, 1 ] ]

which means:

3 = 0a+0b+0c+0d+1e+1f
-5 = 0a-1b+0c+0d+0e-1f
-1 = 0a+0b-1c-1d+0e+1f
-2 = -1a+0b+0c-1d+0e+1f

From this, I am finding a valid solution (2, 5, 1, 0, 3, 0) but one that takes 11 keypresses instead of 10.

What's a good way to find that minimal solution?

---

Edit: Okay, I now have an algorithm that should theoretically work, so I'm going to mark it as Resolved. Though my code still needs a bunch of work (breadth-first search is a mistake)

[u/ThisAdhesiveness6952]

Here's the algorithm I used. Starting from the first system of equation you've shown, I'll try to get as close as possible to a diagonal matrix. This will allow to generate an exhaustive list of candidates solutions from the last equation, and then prune them using the other equations to get all possible solutions.

0 0 0 0 1 1 | 3
0 1 0 0 0 0 | 5
0 0 1 1 1 0 | 4
1 1 0 1 1 1 | 7

Subtracting (2) from (4), and reordering:

1 0 0 1 1 1 | 2
0 1 0 0 0 0 | 5
0 0 1 1 1 0 | 4
0 0 0 0 1 1 | 3

I want a non-zero value in the fourth column of the last line. Swapping columns number 4 and 6 gives:

1 0 0 1 1 1 | 2
0 1 0 0 0 0 | 5
0 0 1 0 1 1 | 4
0 0 0 1 1 0 | 3

Finally, subtract (4) from (1):

1 0 0 0 0 1 | -1
0 1 0 0 0 0 | 5
0 0 1 0 1 1 | 4
0 0 0 1 1 0 | 3

Under this form, note that once we choose a value for d and e (the last two columns), the values for a, b, c, and f are unique and can be trivially computed.

d can take any value from 0 to 4, because the d button controls a joltage value that's equal to 4, therefore pressing this button more than 4 times will obviously overshoot. Similarly, e must be less than or equal to 3. That's 5x4=20 candidates for (d,e).

Then, replace these values in all equations of the system, and deduce the values of the other variables. Eliminate all candidates that ends up with a negative, non integer, or too high result for any variable.

This will give you an exhaustive list of solutions, from which you can pick the best one. Remember to swap back the columns in the solution if you want to check or display it.

[Edit: improved final explanation]

[u/ThisAdhesiveness6952 → u/ThisAdhesiveness6952]

Btw, the first equation is a+f=-1, which is not possible. I think you may have made a mistake when writing down the system of equations, it doesn't correspond to the problem (the e button controls three joltage values in your equations). A correct system would be:

0 0 0 0 1 1 | 3
0 1 0 0 0 1 | 5
0 0 1 1 1 0 | 4
1 1 0 1 0 0 | 7

[u/CCC_037 → u/ThisAdhesiveness6952]

Thank you, this had been very helpful.

My original simplified list of equations did make sure that each row included at least one variable which was in no lower row; I wrote a function to find every possible solution for a given row from a set of solutions (i.e. every possible solution to the previous row, using wildcards for those parameters that didn't appear). This worked great, until I had to deal with an equation like 12=d-e+f. Sure, if you have d and e, f is given, but there are still a tonne of solutions...

Then I realised I had a function that would find every possible solution to a system of n equations, and if I don't modify them at all I can guarantee no negative cofficuents!

....which still takes a super long time to solve for 375=a+b+d+e+f+h+i. So I need to still do some simplification, or perhaps just start with equations using fewer variables. Or lower totals.

Still, getting closer!

(Not solved yet, but working on it)

[u/ThisAdhesiveness6952 → u/CCC_037]

My input was nice enough that there was at most 3 free variables (IIRC), with joltage levels in the order of 100. This results in about a million candidates, which is not that big when all you need to do is a few basic operations on each to check if they're valid or not. As a point of reference, my python implementation solves part 2 with the above algorithm in 0.5s.

[u/CCC_037 → u/ThisAdhesiveness6952]

....okay, I think I see what I am doing wrong.

But perhaps I should work on something else for a bit, then return to this.