Triple Step

Brute force solution



In [1]:

    
import Numeric.Natural



In [2]:

    
tripleStep :: Natural -> Natural
tripleStep 0 = 1
tripleStep 1 = 1
tripleStep 2 = 2
tripleStep n = sum $ map tripleStep [n - 1, n - 2, n - 3]



In [3]:

    
map tripleStep [3, 4, 5]









    





[4,7,13]

Note how it is taking a very long time to compute the number of possibilities already only for 30 steps:



In [4]:

    
tripleStep 30

53798080



In [5]:

    
tripleStep (-1)









    




arithmetic underflow

Memoization



In [6]:

    
tripleStep' :: Int -> Integer
tripleStep' = (map count [0..] !!)
    where
        count :: Int -> Integer
        count 0 = 1
        count 1 = 1
        count 2 = 2
        count n = sum $ map tripleStep' [n - 1, n - 2, n - 3]



In [7]:

    
tripleStep' 3
tripleStep' 4
tripleStep' 30

Much better! But why memoization does not work with Natural?