07.26.07

Exercise 5.9

Posted in Uncategorized at 11:20 pm by admin

makeChange :: Int -> [Int] -> [Int]
makeChange _ [] = []
makeChange 0 _ = []
makeChange amt (v:vs) = n : (makeChange newamt vs)
    where n = amt `div` v
          newamt = amt `mod` v

This was one tricky to do with higher-order functions, until I discovered scanl.

makeChange' :: Int -> [Int] -> [Int]
makeChange' amt vs = zipWith div modvs vs
    where modvs = scanl mod amt vs

See technical error 12 for a note about this exercise.

2 Comments »

  1. Julian said,

    April 11, 2010 at 4:48 am

    Here’s one way of solving the problem as described in the technical error, which finds the best way of doing it. It uses several functions from the Standard Prelude and a little bit of currying. Hopefully this will be properly formatted – apologies if not!

    type Coin = (Int,[Int])
     
    {-
     This takes a list of coins and produces a list of Coins, where each coin
     denomination is converted into a pair (value,[0,0,...,0,1,0,...]), where
     the value is the value of the coin, and the 0-1 array has length equal to
     the number of coins and has a 1 in only the ith position, where the coin
     is the ith in the list of coins (0-based), so for example, [10,5,1] will
     be converted to [ (10,[1,0,0]), (5,[0,1,0]), (1,[0,0,1]) ].
     In this way, we are easily able to add one coin to a collection, simply
     by adding the corresponding array termwise to the existing array.
    -}
    makeCoins :: [Int] -> [Coin]
    makeCoins coins = aux coins [0..]
                      where n = length coins
                            aux [] _ = []
                            aux (c:cs) (i:is) =
                              (c,replicate i 0 ++ [1] ++ replicate (n-1-i) 0):
                              aux cs is
     
    {- 
     This takes an amount and a set of coins, and recursively finds the best
     way of producing all amounts up to and including the given amount; this
     is the heart of the solution of the problem.
     We do this by finding all possibilities for making the required amount,
     which is easy: with a coin of value 10, say, we take the best way of making
     10 less (if the amount is at least 10), and add the array corresponding to
     the 10 coin to this best way.
     We then take the possibility which uses the fewest coins, using a variation
     on the Standard Prelude definition of minimum.
    -}
    best :: Int -> [Coin] -> [[Int]]
    best n coins
      | n == 0  = [ replicate (length coins) 0 ]
      | n > 0   = let bests = best (n-1) coins
                  in (next n coins bests) : bests
                    where next n coins bests
                            = let possibilities = concat (map aux coins)
                                  aux (den,coinList)
                                    = if den <= n
                                      then [ zipWith (+) (bests!!(den-1)) coinList ]
                                      else []
                              in smallest possibilities
                          smallest = foldr1 aux
                            where aux p1 p2 | (sum p1) <= (sum p2)  = p1
                                            | otherwise             = p2
     
    makeChange :: Int -> [Int] -> [Int]
    makeChange amt coins = let cs = makeCoins coins
                               bests = best amt cs
                           in head bests
  2. Ricky Liu said,

    February 19, 2014 at 5:42 am

    We can do it with what we currently learnt (without scanl):

    makeChange amt cs = zipWith div modList cs
    where modList = amt : map (mod amt) cs

    Without currying:

    makeChange amt cs = zipWith div modList cs
    where modList = amt : map doMod cs
    doMod x = amt `mod` x

Leave a Comment