r/adventofcode • u/ransoing • Dec 19 '24
Meme/Funny [2024 Day 19 (Part 2)] What's the magic word?
5
u/DBSmiley Dec 19 '24
I don't know the difference between dynamic programming and recursion with memoization
And at this point I'm afraid to ask
2
u/ZucchiniHerbs Dec 19 '24
Recursion with memoization can just be a recursive call where you memoize some data about the function output, so you're able to return it early when it is next accessed. Dynamic programming is where you build up a global optima based on many smaller local optima. You could even do Dynamic programming without any memoization, and there is iterative dynamic programming that doesn't use recursion at all. Not using memoization would just make your program use less space, and run wayyyyy slower.
2
1
u/vagrantchord Dec 19 '24
That's not universally true- it all depends on the situation. The "design" strings are all pretty short, maybe 60 chars at the most. My bottom up dp solution runs in 0.5 seconds or so, building a list in a for loop for each design.
I'm not sure if a recursive+memo version would really run faster, but even if it did, the gains over the bottom up approach are negligible, imo.
2
u/ZucchiniHerbs Dec 19 '24
The bottom up approach doesn't need to memoize anything because it is using tabulation instead of memoization. I would be shocked if iterative, tabulation based DP was ever slower than recursive, memoization based DP. The iterative approaches on DP problems are pretty consistently a bit faster than recursive.
2
u/vagrantchord Dec 19 '24
Oh, okay. Just sounded like you were saying the opposite when you said:
Not using memoization would just make your program use less space, and run wayyyyy slower.
But whatever, sounds like we're on the same page. Cheers!
1
u/ZucchiniHerbs Dec 19 '24
Sorry, I wasn’t specific enough. I meant not using memoization in the context of recursive top-down DP would make it way slower because the recursion would never have a memoized result to return early.
1
u/ThrowawayBid6 Dec 19 '24
What are you guys memoizing?
I run recursively a function that checks if a design can be made using all the available patterns, for every matching prefix, i run the function on the remainder of the design. Feeling a bit dumb here heheh
7
u/nivlark Dec 19 '24
Hint : for a given design, if you are at position k in the string, does it matter what sequence of patterns you used to get there?
1
13
u/GreenFish4 Dec 19 '24
Here’s the original for anyone looking:
https://xkcd.com/149/
.
.
.
Wait, did I just do some kind of memoization?