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

### Like this:

Like Loading...

*Related*

Tags: bonsai, code, coins, denominations, floupia, Haskell, kata, praxis, programming

This entry was posted on February 22, 2013 at 11:04 am and is filed under Programming Praxis. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

February 23, 2013 at 1:14 am |

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?

February 23, 2013 at 1:29 am |

@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.

February 23, 2013 at 4:19 am |

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.

February 23, 2013 at 12:01 pm |

@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.

February 23, 2013 at 1:51 pm |

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