counting coins, brute force

changeBrute.hs

module Change () where

import Data.List (sortOn)
import Data.Ord (Down(..))
import Control.Exception.Base (assert)

-- count the number of ways a `tot` can be realized using the given coins
-- any coin can be used any number of times
countChangeOpen :: Int -> [Int] -> Int
countChangeOpen tot coins = consumeOpen tot $ sortOn Down coins 

consumeOpen 
    :: Int -- tot to realize
    -> [Int] -- coin values
    -> Int -- ways
consumeOpen 0 [] = 1
consumeOpen r [c] = error "implement consumeOpen 1"
consumeOpen r (c:cs) = error "implement consumeOpen 2"
consumeOpen _ _ = 0


-- count the number of ways a `tot` can be realized using the given coins in limited number
countChangeClosed 
    :: Int -- tot to realize
    -> [(Int, Int)] -- list of (count, coin value)
    -> Int -- ways
countChangeClosed tot coins = consumeClosed tot $ sortOn (Down . snd) coins 

consumeClosed :: Int -> [(Int, Int)] -> Int
consumeClosed 0 [] = 1
consumeClosed r [(n,c)] = error "implement consumeClosed 1"
consumeClosed r ((n,c):cs) = error "implement consumeClosed 2"
consumeClosed _ _ = 0

main :: IO ()
main = do 
    test $ countChangeOpen 100 [1,2,5,30] == 922
    test $ countChangeClosed 100 [(30,1),(20,2),(10,5),(3,30)] == 241
    where
        test = flip assert mempty