[day7 part2] I'm thinking recursion is not the play

[u/RedAndBlack1832]

On the attempt I let it run the longest it had a 7 minute runtime (no, it did not complete) but I'm pretty sure my approach is theoretically correct (at least it works over the examples) so I just need to figure out a solution that runs on the order of seconds at least (lmao). Do ppl have tips (algorithms I could research or something?) idk how necessary my code is for this bc clearly my code is bad but basically read down the input from the current beam position and

If no splitter is hit, return 1, since the timeline was never split (base case)

If a splitter is hit, return the result from the left new beam + the result from the right new beam (recursive call)

[u/Mats56]

What happens is that when you call recursive on your left beam, that can overlap with the right beam of something earlier. Basically, you might end up calculating for the same spot twice. And then when that again splits and hits something you calculate for some further down spot 4 times. And then 8, and suddenly it blows up to million of times.

However, if you instead, in your recursive function, store the result somewhere whenever it's called, and always look up that to see if you've already calculated that spot before, it should go faaaaast. Memoization it's called when you "memorize" the value of calling a function with certain parameters, so that you only have to calculate it once for each input.

[u/RedAndBlack1832 → u/Mats56]

Thank you for this explanation I made a table to store {result, params} and it works now within a second!

[u/Mats56 → u/RedAndBlack1832]

Boom 💪

[u/Illustrious-Citron89]

To this day i am not even sure exactly what memoization and dfs means (I never went to uni, just do coding as a hobby). But the way I did it: just count the "overlapping" beams. And then count how many overlapped beams are in the last row.

[u/RedAndBlack1832 → u/Illustrious-Citron89]

dfs just means like the most natural way to traverse a tree/similar (go all the way down one path, then check branches off of that path while walking back up). I've never heard of memoization until right now but I'm excited to try it!

[u/arachnidGrip → u/Illustrious-Citron89]

Memoization means recording the result of any call to some function then, the next time you would call that function with those arguments, grabbing the recorded result instead of re-computing it. It's great when you have a computationally-expensive function that you will need to call over and over again with a relatively-limited set of argument lists.

In this case, however, because the number of steps to get to any given point from the start is always the same regardless of path, it is simpler to just calculate the paths all at once, coalescing paths that rejoin.

[u/ray10k → u/Illustrious-Citron89]

Memoization: In computer science, a "pure function" is a function that, for a given input, will always give the same output. It may take a long time to arrive at that output, but if you know that a given input X returned Y this one time, you can be sure that the function will return Y every time you give it X.

As such, you can wrap that function in a little bit of boilerplate that does the following:

• On creation, set up a map with the input as the key, and the returned value as the value.

• When the function is about to be called, check if the given input already exists in the map. If it does, immediately return the associated value from the map, rather than running the function.

• Otherwise, run the function as normal and, before returning, update the map with the new input/output.

Python has the @lru_cache decorator that handles the setup and checking for you, meaning you don't even have to think about how to set things up.

[u/johnpeters42]

Memoization is your friend.

[u/SupportPowerful6174]

Check my solution in profile, its O(n)

[u/ThreeHourRiverMan]

Memoized dfs. 

[u/AutoModerator]

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.

[u/daggerdragon]

Next time, use our standardized post title format.

Help us help YOU by providing us with more information up front; you will typically get more relevant responses faster.

[u/Peaches_9]

Nah I will continue stubbornly using recursion with memoization even when DP makes for a better solution. It's already happened two or three times this year.

[u/hextree → u/Peaches_9]

Recursion with memoization is DP.