I haven't tried in another language yet. I wasn't aware of nim-sum, and looked up the game of nim. And yes, this sounds like a tweak on the nim problem, so I will take a look at game theory. Thank you for the pointers. Coursera has a course on combinatorial game theory, and I've put it on my watch list now! I'll try to tweak my program to use bits instead of strings. I don't think I've ever used bit shifting in Haskell (I've used it plenty in C), so it should be interesting. Thanks for the suggestions Stefan!

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