Sha256: addef340a27f7d447bad669bd07fac46ae330a90add5cea2c11f38178831c1c5
Contents?: true
Size: 946 Bytes
Versions: 396
Compression:
Stored size: 946 Bytes
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