Hello all!

I am trying to solve the following problem on HackerRank. It asks us to compute a cellular automata based on a binary tree:

https://www.hackerrank.com/challenges/the-tree-of-life

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!

Here was my first implementation:

https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalProgramming/Recursion/cellular_automata_functionally_correct.hs

I figured out that I am constantly re-computing the trees, and decided to try and memoize the results. Here is my memoization attempt:

https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalProgramming/Recursion/cellular_automata_memoize_attempt.hs

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.

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?

Thanks much!

SSJ