Floupia
February 22, 2013
Here is the complete solution, written in the VB.net programming language:
Imports System
Public Class Coins
Public Shared Sub Main()
Dim AmountToBePaid, ValueOfChoice, i, j, NrOfCoins, NrOfDenominations, NextChange, Subtotal As Integer
Dim Solved, ValidInput As Boolean
Dim Line, Payline, Returnline As String
Dim Denominations(100), Choices(100) As Integer
Dim Units() As String
For i = 1 To 99
Choices(i) = 0
Next
Line = Console.ReadLine()
If Line = "" Then
Console.WriteLine("Enter amount to be paid, followed by the various denominations of coins and banknotes. All integer numbers, comma separated. Then rerun")
End If
Units = Line.Split(",")
ValidInput = True
If Units.Length > 1 Then
For i = 0 To Units.Length - 1
Denominations(i) = Int(Units(i))
Denominations(i + Units.Length - 1) = -Denominations(i)
Next
End If
If Units.Length < 2 Or ValidInput = False Then
Console.WriteLine("Input not valid")
Exit Sub
End If
AmountToBePaid = Denominations(0)
NrOfDenominations = 2 * Units.Length - 2
Solved = False
NrOfCoins = 1
While Solved = False
If Choices(1) = NrOfCoins Then
NrOfCoins = NrOfCoins + 1
For i = 1 To NrOfDenominations
Choices(i) = 0
Next
End If
Subtotal = 0
For i = 1 To NrOfDenominations
If i = NrOfDenominations Then Choices(i) = NrOfCoins - Subtotal
If i = NextChange Then
Choices(i) = Choices(i) + 1
For j = i + 1 To NrOfDenominations
Choices(j) = 0
Next
End If
Subtotal = Subtotal + Choices(i)
If Subtotal = NrOfCoins And Choices(i) <> 0 Then
NextChange = i - 1
End If
Next
ValueOfChoice = 0
For i = 1 To NrOfDenominations
ValueOfChoice = ValueOfChoice + Choices(i) * Denominations(i)
Next
If ValueOfChoice = AmountToBePaid Then Solved = True
End While
Payline = "Pay: "
Returnline = "Return: "
For i = 1 To NrOfDenominations
If Choices(i) > 0 Then
If Denominations(i) > 0 Then
Payline = Payline & Str(Choices(i)) & " x " & Str(Denominations(i)) & " ; "
Else
Returnline = Returnline & Str(Choices(i)) & " x " & Str(-Denominations(i)) & " ; "
End If
End If
Next
Console.WriteLine(Payline)
Console.WriteLine(Returnline)
End Sub
End Class
Most of the code is straight forward, involved with getting the input and writing the output. The Denominations array is a list of all available coins, augmented with the negatives of all the coins; a positive coin is paid by the customer to the merchant, and a negative coin is change given by the merchant to the customer.
The magic happens in the Choice array, which contains the count of each denomination of coin that is currently chosen. Each time through the main loop the Choices array is updated until all possibilities with the current number of coins have been considered; when those possibilities are exhausted, the current number of coins is incremented by one and the main loop continues, finally stopping when the current Choices equal the target price. With two coins, each paired with its negative, and the current number of coins set at three, the Choices array will take on the following configurations:
| Choice(1) | Choice(2) | Choice(3) | Choice(4) |
| Denomination(1) | Denomination(2) | Denomination(3) | Denomination(4) |
| 0 | 0 | 0 | 2 |
| 0 | 0 | 1 | 1 |
| 0 | 0 | 2 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 0 | 2 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 2 | 0 | 0 | 0 |
This program runs forever without result if given infeasible input; for instance, with a target of 13 and coins of 2, 4, and 10, there is no possible solution.
You can run the program at http://ideone.com/NzKNOC.
Programming Praxis 
[…] today’s Programming Praxis exercise, our goal is to calculate the minimum total amount of coins involved in […]
My Haskell solution (see http://bonsaicode.wordpress.com/2013/02/22/programming-praxis-floupia/ for a version with comments):
import Data.List import Math.Combinat 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][…] Pages: 1 2 […]
This was a lot of fun. I like problems that make you take something you do everyday and think about it sideways. Here’s my take: Making Floupian Change
I played a bit with having higher order functions so that there’s a function which makes the coin system and in turn returns the function that makes change. Here’s an example:
It turns out that the inner function is horribly inefficient. I know I check multiple identical permutations, but for the most part the solutions use only a few coins so it doesn’t matter anyways. So it goes.
Before we look at today’s exercise, let’s review some facts from high-school mathematics. The binomial coefficient
is the number in the m‘th position of the n‘th row of Pascal’s Triangle, and is computed as (n * (n−1) * … * (n−k+1)) / (k * (k−1) … * 1). Thus 
. We compute the binomial coefficient with this function, which is the same as the
choosefunction of a previous exercise:(define (binom n m)(let loop ((n n) (m m) (b 1))
(if (zero? m) b
(loop (- n 1) (- m 1) (* b n (/ m))))))
In the study of probability and statistics,
is the number of ways m items can be chosen from a set of n items, so there are 10 different ways to select 3 items from a set of 5 items; if the items are a, b, c, d and e, the ten ways are (a b c), (a b d), (a b e), (a c d), (a c e), (a d e), (b c d), (b c e), (b d e), and (c d e). The list can be generated with a recursive function:
(define (combinations-without-replacement n xs)(if (= n 0) (list (list))
(if (null? xs) (list)
(append (map (lambda (xss) (cons (car xs) xss))
(combinations-without-replacement (- n 1) (cdr xs)))
(combinations-without-replacement n (cdr xs))))))
> (binom 5 3)10
> (combinations-without-replacement 3 '(a b c d e))
((a b c) (a b d) (a b e) (a c d) (a c e) (a d e) (b c d)
(b c e) (b d e) (c d e))
This definition of combinations doesn’t allow duplicates; the items are chosen without replacement, in the jargon of probability and statistics. But sometimes it is useful to allow duplicates, in which case the items are said to be chosen with replacement. The binomial coefficient
defines the number of ways m items can be chosen from a set of n items with replacement, and the list can be generated with a recursive function similar to the previous one:
(define (combinations-with-replacement n xs)(if (= n 0) (list (list))
(if (null? xs) (list)
(append (map (lambda (xss) (cons (car xs) xss))
(combinations-with-replacement (- n 1) xs))
(combinations-with-replacement n (cdr xs))))))
> (binom (+ 5 3 -1) 3)35
> (combinations-with-replacement 3 '(a b c d e))
((a a a) (a a b) (a a c) (a a d) (a a e) (a b b) (a b c)
(a b d) (a b e) (a c c) (a c d) (a c e) (a d d) (a d e)
(a e e) (b b b) (b b c) (b b d) (b b e) (b c c) (b c d)
(b c e) (b d d) (b d e) (b e e) (c c c) (c c d) (c c e)
(c d d) (c d e) (c e e) (d d d) (d d e) (d e e) (e e e))
With that done, we are ready to look at today’s exercise. We augment the list of coins with the negatives of all the coins, so that a positive coin is given to the merchant by the customer and a negative coin is the change given back to the customer by the merchant; a transaction like (10 10 -2) indicates that the customer paid two 10-floupia coins and received a single 2-floupia coin in change, for a net payment of 18 floupia. Our solution generates all possible combinations with replacement (since there may be more than one instance of a particular denomination of coin) of 1 coin, then 2 coins, then 3 coins, and so on until the desired payment is found:
(define (floupia price coins)(if (positive? (modulo price (apply gcd coins)))
(error 'floupia "infeasible")
(let ((coins (append coins (map negate coins))))
(let loop ((n 1))
(let ((xs (filter (lambda (xs) (= (sum xs) price))
(combinations-with-replacement n coins))))
(if (null? xs) (loop (+ n 1)) xs))))))
Note the test for feasibility. A particular input has a feasible solution only if the greatest common divisor of the set of coins evenly divides the price; for example, there is no way to make a price of 11 floupia if only 3-floupia and 6-floupia coins are available.
Here are some examples:
> (floupia 13 '(2 5 10))((5 10 -2))
>((10 10 -2))
> (floupia 17 '(1 3 7 31 153))
((3 7 7) (31 -7 -7))
> (floupia 11 '(3 6))
floupia: infeasible
We used filter, sum and negate from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/XQuQhu5C.
An attempt in Python (which seems to have a similarly inefficient inner algorithm):
def combinations(coins, size): if size == 1: for coin in coins: yield [coin] else: for coin in coins: for comb in combinations(coins, size-1): yield [coin] + comb def mostEfficientPayment(coins, balance): coins.extend([-coin for coin in coins]) numberofcoins = 1 while True: for comb in combinations(coins, numberofcoins): if sum(comb) == balance: return comb numberofcoins += 1 coins = map(lambda x: int(x), raw_input("Coins: ").split()) balance = int(raw_input("Balance: ")) comb = mostEfficientPayment(coins, balance) print "You give: ", " ".join([str(coin) for coin in comb if coin > 0]) print "Merchant gives: ", " ".join([str(-coin) for coin in comb if coin < 0])My Python solution. In essence it is a breadth-first search of coin combinations. A queue keeps track of the search space. A dictionary is used to keep track of the minimum number of coins needed to produce a value. The search stops when the difference between ‘new_value’ and the target price is known (i.e., already in the dictionary)
from collections import deque def floupian(price, coinage): coins = [sign*coin for sign in (1,-1) for coin in coinage] seen = {0:[]} queue = deque([0]) while True: value = queue.popleft() for coin in coins: new_value = value + coin if new_value not in seen: seen[new_value] = seen[value] + [coin] queue.append(new_value) rest = price - new_value if rest in seen: return seen[new_value] + seen[rest]An inefficient, but terse implementation in python. Catches infeasible inputs.