Dynamic programming (memoization) w/ string keys.
Hello again! I'm hoping to get some more insight into another memoization issue I'm facing. This time, I was solving the following problem, which seems like a dynamic programming problem. https://www.hackerrank.com/challenges/game-of-kyles I coded up a straightforward recurrence equation (without any memoization): https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalPr... The function playGameOfKyles shows the recurrence. (playGameOfKyles :: String -> Bool) I tried to perform top-down dynamic programming, by caching the results in a Data.Map, in between calls to the function. This is because the input is a string. Here is the new version: https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalPr... Basically I am passing a map around, and returning one as well. ( playGameOfKyles :: CacheMap -> String -> (Bool, CacheMap)) The naive version (without memoization) is extremely slow of course, and probably won't finish running until the sun cools down (so far, even one test case of a string with length 74 hasn't finished running after many minutes). The memoized version is... improving something... and for example the entire test case 2, which contains 100 test cases of size 50 to 100 each, runs in about 8 minutes. Is there something I can improve with the memoization, to make it faster? Use something other than Data.Map? Or could the bottleneck be someplace else in the algorithm? I know those are kinda broad questions, but I've run out of ideas...
Do you have a dynamic programming solution which runs reasonably fast in another language? Because this game of kyles looks like an example from combinatoric game theory to me and as such it might be much more efficient to solve it using nim-sums (if possible; I haven't given this too much thought). Also note that, since your strings only consist of X and I, you could also use Integers and bit-operations instead of lists in your algorithms. You'd still need a Map for memoization, but other operations might be much faster. Cheers Stefan On Sun, Jun 07, 2015 at 03:15:16PM -0700, Sourabh wrote:
Hello again! I'm hoping to get some more insight into another memoization issue I'm facing.
This time, I was solving the following problem, which seems like a dynamic programming problem. https://www.hackerrank.com/challenges/game-of-kyles
I coded up a straightforward recurrence equation (without any memoization): https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalPr...
The function playGameOfKyles shows the recurrence. (playGameOfKyles :: String -> Bool)
I tried to perform top-down dynamic programming, by caching the results in a Data.Map, in between calls to the function. This is because the input is a string.
Here is the new version: https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalPr...
Basically I am passing a map around, and returning one as well. ( playGameOfKyles :: CacheMap -> String -> (Bool, CacheMap))
The naive version (without memoization) is extremely slow of course, and probably won't finish running until the sun cools down (so far, even one test case of a string with length 74 hasn't finished running after many minutes).
The memoized version is... improving something... and for example the entire test case 2, which contains 100 test cases of size 50 to 100 each, runs in about 8 minutes.
Is there something I can improve with the memoization, to make it faster? Use something other than Data.Map? Or could the bottleneck be someplace else in the algorithm? I know those are kinda broad questions, but I've run out of ideas...
_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
participants (2)
-
Sourabh -
Stefan Höck