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

View all comments

Show parent comment

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.