Posts Tagged ‘denominations’

Programming Praxis – Floupia

February 22, 2013

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] == ([31], [7,7])
          print $ pay 18 [1,10]         == ([10,10],[1,1])