<div dir="ltr">Hello again! I'm hoping to get some more insight into another memoization issue I'm facing. <br><br>This time, I was solving the following problem, which seems like a dynamic programming problem.<div><a href="https://www.hackerrank.com/challenges/game-of-kyles">https://www.hackerrank.com/challenges/game-of-kyles</a><br><br>I coded up a straightforward recurrence equation (without any memoization):<br><a href="https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalProgramming/AdHoc/gameOfKyles_functionallyCorrect.hs">https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalProgramming/AdHoc/gameOfKyles_functionallyCorrect.hs</a> <br><br>The function playGameOfKyles shows the recurrence. (<span class="" style="color:rgb(121,93,163);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre">playGameOfKyles</span><span style="color:rgb(51,51,51);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre"> </span><span class="" style="color:rgb(167,29,93);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre">::</span><span style="color:rgb(51,51,51);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre"> </span><span class="" style="color:rgb(0,134,179);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre">String</span><span style="color:rgb(51,51,51);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre"> </span><span class="" style="color:rgb(167,29,93);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre">-></span><span style="color:rgb(51,51,51);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre"> </span><span class="" style="color:rgb(0,134,179);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre">Bool)</span><br><br>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.<br><br>Here is the new version:<br><a href="https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalProgramming/AdHoc/gameOfKyles_mapMemoized.hs">https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalProgramming/AdHoc/gameOfKyles_mapMemoized.hs</a><br><br>Basically I am passing a map around, and returning one as well. (<span class="" style="color:rgb(121,93,163);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre">playGameOfKyles</span><span style="color:rgb(51,51,51);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre"> </span><span class="" style="color:rgb(167,29,93);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre">::</span><span style="color:rgb(51,51,51);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre"> </span><span class="" style="color:rgb(167,29,93);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre">CacheMap</span><span style="color:rgb(51,51,51);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre"> </span><span class="" style="color:rgb(167,29,93);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre">-></span><span style="color:rgb(51,51,51);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre"> </span><span class="" style="color:rgb(0,134,179);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre">String</span><span style="color:rgb(51,51,51);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre"> </span><span class="" style="color:rgb(167,29,93);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre">-></span><span style="color:rgb(51,51,51);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre"> (</span><span class="" style="color:rgb(0,134,179);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre">Bool</span><span style="color:rgb(51,51,51);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre">, </span><span class="" style="color:rgb(167,29,93);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre">CacheMap</span><span style="color:rgb(51,51,51);font-family:Consolas,'Liberation Mono',Menlo,Courier,monospace;font-size:12px;line-height:16.7999992370605px;white-space:pre">)</span>)</div><div><br>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).<br><br>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.<br><br>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...</div></div>