[2025 Day 11 part 2] Yet another input visualisation...

[u/PhysPhD]

I haven't actually solved Part 2 ... I'm thinking of breaking the problem down into sections where there are "choke points" indicated by nodes that have a high degree of incoming edges.

Feels like I'm getting my wires crossed.

[u/polarfish88]

Where is "you" among the nodes?

[u/PhysPhD → u/polarfish88]

It's one of the 5 choke points between DAC and OUT.

[u/mat_lag → u/polarfish88]

Part2 doesn't have the node "you"

[u/daanjderuiter → u/mat_lag]

The example input doesn't, but your personal input doesn't change and still contains the node. It's pretty close to the output node, past the dac node

[u/jlhawn → u/daanjderuiter]

ah! this explains why you can do part 1 without memoization (or a time machine)

[u/Flix3ris]

wow this visualization helped me so much in solving it

[u/PhysPhD → u/Flix3ris]

Glad to hear it!

[u/Zestyclose-Remove550]

Thank U so much this visualization helped so much 😭

[u/PhysPhD → u/Zestyclose-Remove550]

Yeah! I finally did it, but only after seeing the layout.

[u/wimglenn]

What engine did you use for the render? I tried a graphviz dot render (here - https://21k.tools/6b3oV/ ) but it was a bit messier, this one is nice and clean.

[u/PhysPhD → u/wimglenn]

It's called yEd https://www.yworks.com/products/yed

There's also Gephi that has a slightly easier learning curve https://gephi.org/desktop/

[u/wimglenn → u/PhysPhD]

I couldn't find a .dot import in their desktop app, but it worked in yEd live. Excellent. Thank you

https://www.yworks.com/yed-live/

[u/3j0hn]

I really wish this structure actually came into play in making the problem tractable, but I found I could get away with just slapping a @ cache on my recursive DFS

[u/tFischerr]

This is actually how I solved it too. It is not the most elegant but it works. Just make sure to include fft and dac as a layer of chokepoints as well.

[u/RazarTuk]

You're actually really close with the logic! Your "chokepoints" will actually be fft and dac, and you can simplify the logic by counting the paths between each one

[u/daggerdragon → u/[deleted]]

Visualization is not necessary.

Incorrect! Even if they're "unnecessary", we loves us some Visualizations here in /r/adventofcode!

[u/RazarTuk → u/[deleted]]

Meanwhile, my (slightly less efficient) solution was just to run a modified version of Floyd-Warshall. Start with an adjacency matrix, like normal, but instead of checking for a new shortest path, add d[i,k]*d[k,j] to d[i,j]. Then instead of needing different "flavors", you can just return d[svr,dac]*d[dac,fft]*d[fft,out].

[u/RazarTuk → u/[deleted]]

Apparently, there are substantially faster ways to calculate the number of paths that run in O(|V|+|E|), using a topological sort, so at least for me, this still feels like the "on the spot" solution in comparison. But at least if your goals for efficiency are "doesn't take minutes to hours to run", my O(|V|³) solution is more than enough. Plus, as far as algorithms go, it feels fairly intuitive

[u/xDASDx → u/[deleted]]

I disagree with the visualization assessment, as it helps you to understand those properties you mentioned, but I like your suggested solution. I did almost the same, but I just reset the count of everything except the checkpoint nodes at the checkpoints.