module Problem76 where

import Data.Array

lim :: Int
lim = 100

main :: IO ()
main = print $ partitionsWith [1 .. lim] lim - 1

partitions :: Array (Int, Int) Integer
partitions = array
    ((0, 0), (lim, lim))
    [ ((i, j), partitionsWith [1 .. i] j) | j <- [1 .. lim], i <- [1 .. lim] ]

partitionsWith :: [Int] -> Int -> Integer
partitionsWith [] n'
    | n' < 0    = 0
    | otherwise = partitions ! (n', n')
partitionsWith xs n' = eq + (sum . map (\x -> partitions ! (x, n' - x)) $ xs')
  where
    eq  = fromIntegral . length . filter (== n') $ xs
    xs' = filter (< n') xs
{-
1 -> (1) -> 0
2 -> 1+1, (2)-> 1
3 -> 1+1+1, 1+2, (3) -> 2
4 -> 1+1+1+1, 1+1+2, 2+2, 1+3, (4) -> 4
5 -> 1+1+1+1+1, 1+1+1+2, 1+2+2, 1+1+3, 2+3, 1+4, (5) -> 6
6 -> 1+1+1+1+1+1, 1+1+1+1+2, 1+1+2+2, 2+2+2, 1+1+1+3, 1+2+3, 3+3, 1+1+4, 2+4, 1+5, (6) -> 10
7 -> 1+1+1+1+1+1+1, 1+1+1+1+1+2, 1+1+1+2+2, 1+2+2+2, 1+1+1+1+3, 1+1+2+3, 2+2+3, 1+3+3, 1+1+1+4, 1+2+4, 3+4, 1+1+5, 2+5, 1+6, (7) -> 14
-}
