<div dir="ltr">Hello all!<div><br></div><div>I am trying to solve the following problem on HackerRank. It asks us to compute a cellular automata based on a binary tree:</div><div><a href="https://www.hackerrank.com/challenges/the-tree-of-life">https://www.hackerrank.com/challenges/the-tree-of-life</a> <br></div><div><br></div><div>I have got 9/10 test cases passing. The last test case times out on the server. But I was able to download the input and expected output, and verify that it is functionally correct. The problem is that the big input is supposed to run within 5 sec, and mine is taking 145 seconds, LOL!</div><div><br></div><div>Here was my first implementation:</div><div><a href="https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalProgramming/Recursion/cellular_automata_functionally_correct.hs">https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalProgramming/Recursion/cellular_automata_functionally_correct.hs</a><br></div><div><br></div><div>I figured out that I am constantly re-computing the trees, and decided to try and memoize the results. Here is my memoization attempt:</div><div><a href="https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalProgramming/Recursion/cellular_automata_memoize_attempt.hs">https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalProgramming/Recursion/cellular_automata_memoize_attempt.hs</a><br></div><div><br></div><div>Basically I have changed the simulateCellularAutomata function, which computed the new trees, into a list (automataTrees - line 60).  I was expecting the results to be memoized, but the runtime is unchanged. </div><div><br></div><div>I was wondering if someone can help me figure out what I'm doing wrong with the memoization. Or suggest other ways to memoize this perhaps?</div><div>--</div><div>Thanks much!</div><div>SSJ</div></div>