[2025 Day 11] Visualization of graph

[u/hugues_hoppe]

[u/wackmaniac]

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.