{-
Program : make_change.hs
Author : David Tran
Date : 2008-10-25
On the SOE exercise 5.9 (http://davidtran.doublegifts.com/blog/?p=37)
I said that I will find a solution for it. Here it is.
The make change question could be considered as partitions of integers
problem. (http://davidtran.doublegifts.com/blog/?p=152)
The amount money is the interger to be partition.
The coins are the generating functions; only select functions matchs coins' value.
Examples:
makeChange 99 [5, 1] ==> [19,4]
makeChange 18 [10, 9, 3, 1] ==> [0,2,0,0]
-}
import Data.List
import Data.Maybe
type Constant = (Int, Int) -- "Constant" at "Position"
type Coefficient = [ Constant ] -- "Sum" of Constant
type Exponent = Int
type Term = (Coefficient, Exponent)
type Polynomial = [ Term ] -- "Sum" of Term
term :: Int -> Int -> Polynomial
term max n = ([],0) : [ ([(n,i)], n * i) | i <- [1.. max `div` n ] ]
mult :: Int -> Polynomial -> Polynomial -> Polynomial
mult max p1 p2 = [ (c1++c2, e1+e2) | (c1,e1) <- p1, (c2,e2) <- p2, e1+e2 <= max ]
makeChange :: Int -> [Int] -> [Int]
makeChange n cs = to_solution $ min_change $ only_coeff $ filter_terms $ generate_terms
where
generate_terms = foldr1 (mult n) (map (term n) cs)
filter_terms = filter (\(c, e) -> e == n)
only_coeff = map (\(c, e) -> c)
min_change = minimumBy (\x y -> compare (countCoin x) (countCoin y))
countCoin = foldr (\(c,t) sum -> sum + t) 0
to_solution xs = map (\c -> fromMaybe 0 (lookup c xs)) cs
This entry was posted
on Saturday, November 21st, 2009 at 9:23 pm and is filed under Haskell - SOE.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.