{- |

In England the currency is made up of pound, £, and pence, p.
There are eight coins in general circulation:
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p).

-}
module Euler.Problems.Problem31 (answer, ways) where

import Euler.Prelude

import qualified Data.Foldable as Foldable
import qualified Data.List as List

{- |

The number of ways to make £2 using any number of coins.

-}
answer :: Natural
answer = ways 200 [200, 100, 50, 20, 10, 5, 2, 1]

ways
  :: Natural   -- ^ Target amount
  -> [Natural] -- ^ Denominations (in descending order for best performance)
  -> Natural   -- ^ Number of ways to make the target amount using the
               --   denominations

ways 0 _  = 1  -- There's exactly one way to make no money
ways _ [] = 0  -- You can't anything with no denominations

ways target (x:xs) =
  Foldable.sum $
  -- r: How much to make with the first denomination
  List.takeWhile (<= target) $ List.iterate (+ x) 0 <&> \r ->
  -- How many ways to make the rest without that denomination
  ways (target - r) xs