Programming Praxis – Floupia

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])

Tags: , , , , , , , ,

5 Responses to “Programming Praxis – Floupia”

  1. programmingpraxis Says:

    I tried to run your code, but don’t have the Math.Combinat library.

    What happens if you try to pay 11 floupia with coins of 3 and 6 floupia?

  2. Remco Niemeijer Says:

    @programmingpraxis: My solution uses the same basic idea as yours, so it will likewise go into an infinite loop when there is no solution. Since this wasn’t part of the exercise, I didn’t bother to catch those cases.

    My first thought for solving it would be to do something like:
    – remove all denominations for which a denomination exists that is a divisor (so in your example remove the 6 since 3 is a divisor).
    – if only one number is left, a solution is impossible if the remaining denomination isn’t a divisor of the total amount.
    – I think that if more than one denomination is left a solution should be possible. I might be wrong, though.

  3. programmingpraxis Says:

    I posit, though I am not certain, that a feasible solution exists only if the greatest common divisor of the various denominations of coins evenly divides the target price. Which is pretty much the same as what you said. I’m glad to see we are thinking along the same lines.

  4. Remco Niemeijer Says:

    @programmingpraxis: Not quite the same, since some further thinking reveals that my solution doesn’t work with denominations 6 and 9. I believe your gcd approach does work correctly.

  5. programmingpraxis Says:

    I wasn’t entirely sure. Thanks for the confirmation.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: