module Problem114 where

import Data.Array

main :: IO ()
-- a(n) → row of length n ending in red block
-- b(n) → same, but ending in black block
-- f(n) = a(n) + b(n) → total rows of length n
-- we can add red block to a(n-1) or add a new block of length 3 to b(n-3)
-- a(n) = a(n-1) + b(n-3)
-- we can add black block to b(n-1) or to a(n-1)
-- b(n) = a(n-1) + b(n-1) = f(n-1)
-- solving
-- ⇒ a(n) = b(n) - b(n-1) + b(n-3)
-- ⇒ b(n) = 2*b(n-1) - b(n-2) + b(n-4)
-- ⇒ f(n) = 2*f(n-1) - f(n-2) + f(n-4)
-- n 1 2 3 4
-- a 0 0 1 2
-- b 1 1 1 2
-- f 1 1 2 4
main = print $ f ! 50
  where
    f = array (1, 50) [ (i, f' i) | i <- [1 .. 50] ] :: Array Int Integer
    f' 1 = 1
    f' 2 = 1
    f' 3 = 2
    f' 4 = 4
    f' x = 2 * f ! (x - 1) - f ! (x - 2) + f ! (x - 4)
