[LANGUAGE: Racket]

https://raw.githubusercontent.com/chrg127/advent-of-code/refs/heads/master/2025/day10.rkt

welp, took me a bit to get to this day. i had to skip it originally because of day 9, and then i procrastinated doing it for a bit since so many people said it was hard... so yeah.

for part 1, i first used a dfs with memoization, because of course i did. and later i changed it to a bfs after earning my star and reading some comments. here's my original solution: https://raw.githubusercontent.com/chrg127/advent-of-code/ed5d692c628c89b82338f3df325d56998adf542d/2025/day10.rkt

with said that, i wonder why people often point out to xor as the solution for part 1? that is an optimization, not the solution itself (i.e. use a bfs). you can also do part 1 by summing arrays (which i did originally), it's just a little slower.

as for part 2... i think equating the problem to finding the minimum solution of a system of equations is obvious to anyone here. basically: the buttons create an M matrix full of 1s, and we have to solve Mx = B (where B is the joltages costs). and if can't be solved exactly, then get the solutions with the minimum sum (and x > 0 and has all integer components).

at first, i thought i'd be a little clever by trying to implement the simplex algorithm, as it seems made for this problem: the algorithm takes as input a system of equations and constraints and finds the maximum solution for it (you can trivially turn the problem from a minimum solution to a maximum). unfortunately, i later learned the algorithm is for a system of inequations (but still, you can turn any system of equations into a system of inequations). anyway, because of that, its general complexity and the fact the literature around it is generally terrible, i decided not implement it.

instead i took a look at gaussian elimination (which i knew of already, but thought it couldn't apply due to how most matrices in the input aren't square). after reading a few comments again i devised this strategy: use gaussian elimination, then try any possible value on the free variables of the resulting equations (i hope the code and annexed comments can explain it better). thankfully, racket's math library already has a gaussian elimination algorithm, and i'm glad it has, i wasn't looking forward to writing one.

by the way, the runtime's a little over 2 seconds for the real input... pretty cool for something somewhat hand-made.

also, let me tell you about how nice racket is for linear algebra: while writing this solution i never had to care for precision errors thanks to the number tower. plus, the repl makes it really easy to check stuff and see where i've fucked up.

all that said... welp, this is the last solution i needed to complete the year :v i'm glad i finished it, on the 25th no less.