Memoizing countingStairs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
--Haskell doesn't magically/automatically memoize results, but it is an easy thing to add:

-- The original (working) counting stairs code is:

countStairs n | n <= 0 = 1
countStairs n = countStairs(n-1) + countStairs(n-2) + countStairs(n-3)

main = print (countStairs 35)

{- And takes a long time:

   $ time ./so
   2698569577

   real    0m23.242s
-}

-- Memoizing the result requires a single import (from the MemoTrie package) and a simple change:

import Data.MemoTrie

countStairs :: Int -> Int
countStairs n | n <= 0 = 1
countStairs n = memoStairs(n-1) + memoStairs(n-2) + memoStairs(n-3)
 where
 memoStairs = memo countStairs

main = print (countStairs 35)

{- The operation is now just an O(n) and with n = 35 it's very fast:

   $ time ./so
   2698569577

   real    0m0.005s
-}


-- I'm no Python expert, but the trivial implementation is something like:
def countStairs(n):
  if (n <= 0):
        return 1;
  else:
        return (countStairs(n-1) + countStairs(n-2) + countStairs(n-3));

print(countStairs(35));
-- This runs for many a minute without a result.

-- The memoized python is also plenty easy:

memo_cs = {}
def countStairs(n):
  if not memo_cs.has_key(n):
    if (n <= 0):
        return 1;
    else:
        memo_cs[n] = (countStairs(n-1) + countStairs(n-2) + countStairs(n-3));
  return memo_cs[n];

print(countStairs(35));

{- And is also very fast:

   $ time python so.py
   2698569577

   real    0m0.019s
-}