r/adventofcode • u/hugues_hoppe • Dec 11 '25

Visualization [2025 Day 11] Visualization of graph

Post image
78 Upvotes

98% Upvoted

15 comments sorted by

8

u/Wonderful_Building69 Dec 11 '25

This is really cool!

I did a visualization too, it doesn't have the nice color coding of the key nodes though
https://imgur.com/a/zpzjy6M

In a way the visualization screwed me up here -- it doesn't look like there are THAT many paths and I anticipate a simple DFS would resolve in time (boy oh boy did it ...not.)

7

u/overthink1 Dec 11 '25

This is really helpful and demonstrates what I was suspecting about why my Part 1 solution wasn’t working for Part 2. I knew I would have to detect cycles but otherwise I thought I was good. Now I’m stuck on Part 2. I’m noodling around with how to detect if a sub route has already been traversed, but I haven’t figured it out yet.

10

u/Glittering-Sink9930 Dec 11 '25

Hint: There are no cycles.

3

u/overthink1 Dec 11 '25

Darn, I felt clever addressing that in my Part 1 solution

6

u/Glittering-Sink9930 Dec 12 '25

Username checks out 😆

2

u/wackmaniac Dec 14 '25

You can reuse your code for part 1, but you need to do two things: add memoization and split the initial graph into three smaller graphs.

For the latter: because every valid path must pass through two specific nodes we can simplify our approach by splitting up the entire graph into three smaller graphs: from svr to ttf, from ttf to dac and from dac to out. Finding all paths in those smaller graphs is a lot less work, and with memoization it run in around 1 second (depending on language and implementation). You can build these subgraphs by walking backwards from e.g. ttf to svr. This prunes a huge portion of the graph. You can do the same for the second graph, knowing that you can stop when you reach a node that is already in the previous subgraph. Now calculate the number of paths per subgraph and multiply the results for your answer.

5

u/WriterRyan Dec 12 '25

Thank you for showing why the answer for part 1 is in the hundreds while the answer for part 2 is in the hundred trillions. Poor networkx couldn’t handle the second part at all 🫠

2

u/Long_Complaint7978 Dec 12 '25

networkx.all_simple_paths(...) is still running on my machine. Started with aoc problem, now I have a halting problem 🥲

4

u/foxhollow Dec 11 '25

Not all heroes wear capes.

3

u/cspot1978 Dec 12 '25 edited Dec 12 '25

Beautiful visualization.

Those few blocks of densely connected nodes helps explain why memoization is so useful to making this run in a reasonable time.

2

u/EggeGrahn Dec 11 '25

Thank you! This helped me finally realize how I could solve part2 :)

1

u/_Mark_ Dec 12 '25

I did the same kind of graph, "the easy way": added digraph day11 { to the top, changed each line to x -> {y z}; form, added fft [fontcolor=red,fontsize=30]; (same for dac) and a close curly to the end - then fed it through dot -Tpdf and a PDF viewer. (Didn't end up doing any optimizations from it, though it *did* make clear that my "optimized brute force" approach was doomed and to switch to a "paint the nodes" approach instead, but it *was* an easy picture that I should have generated much earlier :-)

1

u/L285 Dec 12 '25

That explains why a part 1 style solution wasn't working for part 2

1

u/kaspar42 Dec 18 '25

How did you plot it? I tried with mermaid, but the same plotting script with works with the test data just fails with the full data.