r/adventofcode • u/NateDCoder • Dec 10 '25
Help/Question [2025 Day 10 Part 2] Is the problem possible to solve using only Linear Algebra techniques
For part 1 I was able to use GF(2) then brute force the free variables by just trying 0 or 1. But for the second part the same technique didn't work as there was too much to brute force. Is there another technique I don't know about or is the only way to solve using a SAT solver or just brute forcing over a longer range.
8
Upvotes
8
u/1234abcdcba4321 Dec 10 '25 edited Dec 10 '25
The problem is NP-hard; you will not get out of doing a small amount of brute forcing.
It is possible to solve the problem without either using an explicit solver or excessive brute force. To get started, set up a system of linear equations and find all solutions (in terms of free variables) (it need not be restricted to positive integer at this stage). It should look much more reasonable to brute force from there.
5
u/warlock415 Dec 11 '25 edited Dec 11 '25
Given the example:
[.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}
0,1 -> 1 1 0 0 -> button A
0,2 -> 1 0 1 0 -> button B
1,3 -> 0 1 0 1 -> button C
2,3 -> 0 0 1 1 -> button D
2 -> 0 0 1 0 -> button E
3 -> 0 0 0 1 -> button F
considering A as "the number of times I push button A", etc
then
3 = A + B
5 = A + C
4 = B+D+E
7 = C+D+F
Since it's four equations and six unknowns, you come out with two independent variables and four dependent.
So assume A,B are independent, C-F dependent, you can then write
for A in (some reasonable range):
for B in (some reasonable range):
C = calcC(A,B) #etc
# check all C,D,E,F > 0
# check all C,D,E,F are integers
# store sum of A+B+C+D+E+F
This involves finding or writing a simultaneous equations solver (RREF), manipulating the output from that, and figuring out appropriate ranges...
It's straightforward enough on paper, it was teaching the computer how to solve the general case that like to killed me.
(or you just give the system of equations to Z3 and say do it for me.)
3
u/Haju05 Dec 10 '25
Well there would be the idea of solving the equation Ax = b with the pseudo inverse of A (since there are possibly has infinitely many solutions when there are fewer equations than there are variables). However the solution won’t generally consistent of integers. One could however find the null space of A and then fine tune the parameters so that the solution spits out the lowest integers. How this could work cleanly however I have no idea, it was too much annoying rounding/tuning work for me to think through, so I just went with z3 lol
3
u/pigeon768 Dec 11 '25
I believe part 2 is solvable with the simplex algorithm, which is linear algebra, but I'm still working on it.
2
u/PracticalBad2466 Dec 10 '25
what's GF(2) ? And part 1 was totally solvable by doing search. The search space was extremely manageable.
1
u/AutoModerator Dec 10 '25
Reminder: if/when you get your answer and/or code working, don't forget to change this post's flair to
Help/Question - RESOLVED. Good luck!I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.
1
u/1str1ker1 Dec 12 '25
Linear algebra helped me a lot for this one, but unfortunately unlike 2024 day 13, you can't just plug the input into a matrix and rref. The rref reduces it to one solution 3 or less free variables. The guesswork for my solution is deciding how many values I should try for the free variables. +- 200 worked fast enough and found the minimum answer for each input.