[Haskell-cafe] Coin changing algorithm

[Mark Carroll]

On Wed, 13 Jul 2005, Dinh Tien Tuan Anh wrote:

(snip)
> eg: m = 75, k = 5
>      =>   [50, 20, 5]
>              [50, 20, 1,2,2]
(snip)
> Is this problem suitable for functional programming language ?

Oh, what fun. I like this sort of thing. My quick attempt is:

module Coins where
import Data.Maybe

nextChange :: Num a => (Int, [a]) -> [(Int, [a])]

nextChange (n, xs) = [ (n', increment n' xs) | n' <- [ n .. length xs - 1 ] ]
    where
    increment 0 (x:xs) = x+1 : xs
    increment n (x:xs) = x   : increment (n-1) xs

makeChange :: (Num a, Ord a) => [a] -> a -> a -> [[a]]

makeChange coins total number =
    helper (0, replicate (length coins) 0)
    where
    helper state@(_, change)
           | sum change > number = []                       -- too many coins
           | otherwise =
               case compare (sum (zipWith (*) coins change)) total of
                  EQ -> [change]                            -- correct amount
                  LT -> concatMap helper (nextChange state) -- too little
                  GT -> []                                  -- too much

showResults :: Num a => [a] -> [a] -> [String]

showResults coins change =
    mapMaybe showResult (zip coins change)
    where
    showResult (_,0) = Nothing
    showResult (c,n) = Just (show n ++ " x " ++ show c)

test =
    let coins = [1,2,5,10,20,50,100,200]
        printChange change = do mapM_ putStrLn (showResults coins change)
                                putChar '\n'
     in mapM_ printChange (makeChange coins 75 5)


I post it here because, whenever I do, someone else shows a much better
solution that's shorter and clearer! Especially, I don't see myself using
much real functional programming in the above, and I'd love to see a
better approach.

-- Mark