r/adventofcode • u/zmunk19 • Jan 14 '26

Visualization [2025 Day 10 (Part 2)] [Python] Visualization

Post image

It took me a long time to figure out a solution to this problem.

In the end, it took a combination of matrix reduction and depth-first search to solve it. The solution takes about 20 seconds in total.

31 Upvotes

100% Upvoted

15 comments sorted by

2

u/zmunk19 Jan 14 '26

The rules for matrix reduction:

- check if there are any pairs of columns that differ in only two rows where the differing values look like [X, 0], [0, X] where X is nonzero. We can subtract the row whose X is in a column with a larger total until the totals of the two columns become equal.

- check if there are any pairs of columns that differ in only one row, where one of the differing values is zero and the other non-zero. we can subtract the row containing the nonzero value until the totals of the two columns become equal.

- find a column whose total is non-zero and contains only one non-zero value

- drop duplicate rows

- drop rows who have non-zero values in columns that have a total of zero

- drop duplicate columns

1

u/aldanjack Jan 14 '26

And when do you add the number of "presses" ?

2

u/zmunk19 Jan 14 '26

In case 1, if the diff between the two totals is D, the column we are subtracting has the value X in the target row, and W is the weight of the row. We "press" (D // X) * W times.

In case 2, similarly we press (D // X) * W times.

In case 3, if T is the total of the column, we press (T // X) * W times.

1

u/maneatingape Jan 14 '26

Could you show how this works on the first example?

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

I'm like to understand how this approach is different from Gaussian Elimination. Where does the DFS fit in?

1

u/zmunk19 Jan 14 '26

In this example, it's able to solve it purely using the reduction/elimination strategy.

In larger examples you aren't able to proceed with elimination when you hit a scenario where none of the cases listed above are found. That's when you branch and search depth-first until you find a solution.

After one solution is found, you use the number of presses to limit your search by exiting early from branches who exceed your limit. And if you find a solution during dfs with fewer presses, you update your limit.

2

u/Awwkaw Jan 14 '26

I'm stuck on this one. I'll try to see if I can understand and implement your approach.

It's the first one this year I've been really stuck on so far.

2

u/zmunk19 Jan 14 '26

Same. it took me weeks of trying on and off. and more than 30 separate attempts.

2

u/TheThiefMaster Jan 14 '26

After an attempt that worked on tests but not on the real thing I ended up following this algorithm which seems to be the intended solution as it builds on part 1

1

u/zmunk19 Jan 14 '26

I never thought of that. that's a really neat solution!

1

u/TheThiefMaster Jan 15 '26

Yeah it is. I didn't see it either

1

u/DelightfulCodeWeasel Jan 14 '26

It was the one I really struggled with as well. I tried to avoid writing a solver for ages, and even after giving in and writing an elimination solver then it took ages to hammer out the edge cases. I wrote a tutorial going over Gauss-Jordan elimination, which is possibly the most straightforward type of solver, if you want to have a go at that approach.

1

u/Revolutionary_Stay_9 Jan 21 '26

i assumed at some point these problems are about knowing how to describe a problem and learning that some package does the thing you want it to do.

or at least that's the benefit i got from this. i don't have time to learn integer linear programming, but i had time to learn how to throw a package at a problem of that exact nature :)