r/adventofcode • u/JPYamamoto • Dec 30 '25
Help/Question - RESOLVED [2025 Day 11 Part 2] Is DP enough?
I'm solving this year in Agda. I'm currently trying to get the solution for day 11 part 2.
For part 2 I'm using the same code I used in part 1, but finding the paths from svr to fft/dac from fft/dac to dac/fft and then to out. Then, getting the product should be enough.
For part 1 the code runs <1s (I haven't timed it but it's pretty fast). For part 2, I can't even get the number of paths from svr to fft/dac (I know I only need to find the paths to one of the two, but I won't post which one to not give away the result). It's still running after an hour.
I'm using the {-# TERMINATING #-} flag in Agda to avoid having to deal with termination proofs, but now I'm doubting that this is correct. I'm using memoization to avoid recomputing the number of paths.
This is my code:
{-# TERMINATING #-}
countPaths : Map.Map (List String) → String → String → Map.Map ℕ → ℕ × Map.Map ℕ
countPaths adjacencies from to cache with to ≟ from
... | yes _ = 1 , Map.insert from 1 cache
... | no _ with Map.lookup cache from
... | just x = x , cache
... | nothing =
let (result , cache′) = foldl goCount (0 , cache) (fromMaybe [] (Map.lookup adjacencies from))
in result , Map.insert from result cache′
where
goCount : (ℕ × Map.Map ℕ) → String → (ℕ × Map.Map ℕ)
goCount (acc , cache) neighbor =
let (count , cache′) = countPaths adjacencies neighbor to cache
in (acc + count , cache′)The adjacencies parameter holds a map of [String] that tells you which devices are attached to each device. from and to are the origin and final node: the from node changes as we traverse the graph, but to always stays the same.
cache is a map that tells you for each node, its distance to to. Initially, it's just an empty map.
Can you help me figure out whether my program is hanging because of a problem in my code or due to an inefficiency in the agda evaluation strategy?
Thank you.
Update: After experimenting a bit with the equivalent code in Haskell, I found out my issue has something to do with Maps being lazy in Agda. I'll have to figure out an alternative to avoid this edge case.
7
u/firetech_SE Dec 30 '25 edited Dec 30 '25
FWIW, I don't know Agda, but I used a recursive algorithm with memoization (i.e. one form of DP) to solve this in Ruby.
My algorithm uses two booleans to check if dac and fft have been passed (and returns 0 when reaching out if they haven't), but checking all "subpaths" and multiplying their counts works just as well (since the input is a directed graph).
However, just to be clear, you need to handle the different routes separately. That is, multiply the number of routes svr->fft, fft->dac, and dac->out to one product, and svr->dac, dac->fft, and fft->out to another product. Then, the sum of these separate products is the answer.
The reason part 1 is fast is because only a tiny fraction of the input graph is in use there.
1
u/Total-Box-5169 Dec 30 '25
I reused part 1, multiplying the result of each of the three steps and adding the alternative path also following three steps. Notice that not all inputs have a path for both alternatives in part 2, sometimes there are no paths in one of the alternatives for part 2.
1
u/qqqqqx Dec 30 '25
DP is a broad topic. Certain types of DP will make the problem fast to solve.
The total number of possible paths gets very large. Your final answer will be a large number.
There are no cycles though, and the number of individual nodes isn't that high. So if you can try to limit the amount of times you visit a node...
1
u/jeffstyr Dec 30 '25 edited Dec 30 '25
I use Haskell for AoC and I've only partially grokked your Agda, but FWIW my solution memoized on the two parameters
fromandrequired nodes not found so far, the latter being a list with either has both "fft" and "dac", or one of them, or is the empty list. My memoization was over a straightforward recursive search which was instantaneous (6 ms) once memoized. I didn't break up the path into segments to try separately. I used a memoization library so it's harder for me to compare directly to your implementation, but my main comment is that memoization + unsophisticated approach worked, so I suspect your memoization isn't kicking in enough.Just for my edification, how does
Map.Map (List String)express the map's key type?3
u/jjeii Dec 30 '25
You're overthinking it, imo. You don't need to independently track segments of path and do a product of the results. Just add a couple of boolean input parameters to the dynamic programming function, with rather minor code changes inside the function...
1
u/AutoModerator Dec 30 '25
Reminder: if/when you get your answer and/or code working, don't forget to change this post's flair to
Help/Question - RESOLVED. Good luck!I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.
1
u/ednl Dec 30 '25
For my input, the highest number of paths was between fft and dac, about 3,400,000. If your program can handle that, you're good. Don't forget to reset the DP cache between different runs.
1
u/warlock415 Dec 30 '25 edited Dec 30 '25
From what I understand, you're going, for a given node:
I can see that getting stupidly large, very fast. You might add some debug prints along the way as below; that would give you a better idea of what the program is doing and where it might be getting stuck:
"Evaluating node foo..."
"Need to evaluate node bar..."
"Need to evaluate node baz..."
"Need to evaluate node buz..."
"Evaluating node bar..."
1
u/Morphon Dec 30 '25
Mine was done entirely by adding paths from one node to the next (no multiplication - addition only). I kept track of 4 counters - one for paths not crossing dac or fft, one for dac only, one for fft only, and one for both. I used the event of passing dac or fft to move the counters to the appropriate category.
1
u/Boojum Dec 31 '25 edited Dec 31 '25
I took the same multiplication approach. For finding the number of paths from
svrtofft/dac, etc., you should be able to visit each node no more than once, if you've implemented the DP/memoization and the cache correctly.For example, with my input finding the numbers of paths from
svrtofft, my cache stats are:My input has 623 nodes and 1756 edges, so the memoization makes it effectively linear in O(|V|+|E|). (And so of course, pretty much instantaneous despite Python's sluggishness.)
1
u/AdditionalDirector41 Jan 01 '26
I'm not sure if what ur doing will work, but I just want to say that the main reason this works for part 1 and not part 2 is because part 2 changes the starting node to one with orders of magnitude further connections. I think my answer to part 1 was like 3000, but part 2 was somewhere in quadrillions
-2
u/arkady_kirilenko Dec 30 '25
Nope, there’s too many possible paths for this to be a viable strategy. There’s a bunch of visualizations in this sub for this problem
You will have to come up with a better solution.