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

[Sourabh]

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...
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150607/eb94ddd6/attachment.html>