Contents

module Change (findFewestCoins) where

import Data.List (sortBy)

type Coin = Integer
type Coins = [Coin]
type Amount = Integer

findFewestCoins :: Amount -> Coins -> Maybe Coins
findFewestCoins target coins = minChange target sortedCoins [] Nothing
  where
    sortedCoins = sortBy (flip compare) coins

    minChange target' coins' candidate bestResult
      | target' < 0 || worseResult = bestResult
      | target' == 0 = Just candidate
      | otherwise = dropCoin target' coins' candidate newBestResult
      where
        worseResult = maybe False (\x -> length x <= length candidate) bestResult
        newBestResult = addCoin target' coins' candidate bestResult

    addCoin target' coins'@(coin:_) candidate
      | newTarget >= 0 = minChange newTarget coins' (coin:candidate)
      where newTarget = target' - coin
    addCoin _ _ _ = id

    dropCoin target' (_:restCoins) = minChange target' restCoins
    dropCoin _ _ = flip const

Version data entries

396 entries across 396 versions & 1 rubygems

Version	Path
trackler-2.0.0.5	tracks/haskell/exercises/change/examples/success-standard/src/Change.hs
trackler-2.0.0.4	tracks/haskell/exercises/change/examples/success-standard/src/Change.hs
trackler-2.0.0.3	tracks/haskell/exercises/change/examples/success-standard/src/Change.hs
trackler-2.0.0.2	tracks/haskell/exercises/change/src/Example.hs
trackler-2.0.0.1	tracks/haskell/exercises/change/src/Example.hs
trackler-2.0.0.0	tracks/haskell/exercises/change/src/Example.hs
trackler-1.0.4.1	tracks/haskell/exercises/change/src/Example.hs
trackler-1.0.4.0	tracks/haskell/exercises/change/src/Example.hs
trackler-1.0.3.0	tracks/haskell/exercises/change/src/Example.hs
trackler-1.0.2.1	tracks/haskell/exercises/change/src/Example.hs
trackler-1.0.2.0	tracks/haskell/exercises/change/src/Example.hs
trackler-1.0.1.2	tracks/haskell/exercises/change/src/Example.hs
trackler-1.0.1.1	tracks/haskell/exercises/change/src/Example.hs
trackler-1.0.1.0	tracks/haskell/exercises/change/src/Example.hs
trackler-1.0.0.1	tracks/haskell/exercises/change/src/Example.hs
trackler-1.0.0	tracks/haskell/exercises/change/src/Example.hs