[Haskell-beginners] Dynamic programming (memoization) w/ string keys.

[Stefan Höck]

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/FunctionalProgramming/AdHoc/gameOfKyles_functionallyCorrect.hs
> 
> 
> 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/FunctionalProgramming/AdHoc/gameOfKyles_mapMemoized.hs
> 
> 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 at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners