In today’s Programming Praxis exercise, our goal is to calculate the minimum total amount of coins involved in a payment (including change) for a currency with a given set of coin denominations. Let’s get started, shall we?
import Data.List import Math.Combinat
First we search all transactions involving one coin, then all transactions involving two coins, etc. We exclude all options where the payment and the change include the same coin, since that would make both coins useless. We return the first option for which the change equals the difference between the payment and the amount required.
pay :: (Eq a, Num a) => a -> [a] -> ([a], [a]) pay total coins = head [(p,c) | n <- [1..], pc <- [1..n], p <- combine pc coins , c <- combine (n - pc) (coins \\ p), sum p - total == sum c]
Some tests to see if everything is working properly:
main :: IO () main = do print $ pay 17 [1,3,7,31,153] == (, [7,7]) print $ pay 18 [1,10] == ([10,10],[1,1])