Skip to content

Instantly share code, notes, and snippets.

@wavebeem
Last active Aug 29, 2015
Embed
What would you like to do?
import Data.List
data Coin = Coin Integer String
instance Show Coin where
show (Coin _ name) = name
currency =
[ Coin 25 "quarter"
, Coin 10 "dime"
, Coin 5 "nickel"
, Coin 1 "penny"
]
opt1 n = (remainder, reverse change) where
(remainder, change) = opt (n, []) currency
opt (n, coins) [] = (n, coins)
opt (n, coins) (c@(Coin v _):cs) = case divMod n v of
(0, _) -> opt (n, coins) cs
(a, b) -> opt (b, (a, c) : coins) cs
opt2 n = (remainder, reverse change) where
(remainder, change) = foldl' opt (n, []) currency
opt (n, coins) c@(Coin v _) = case divMod n v of
(0, _) -> (n, coins)
(a, b) -> (b, (a, c) : coins)
optimal = opt2
main = do
let f (n, c) = "\t" ++ show n ++ "\t" ++ show c
let change = 57
let (n, coins) = optimal change
let lines = map f coins
putStrLn ("The optimal change for " ++ show change ++ " is:\n")
putStrLn (intercalate "\n" lines)
putStrLn ("\n...with " ++ show n ++ " cents left over")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment