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

Pages: 1 2

### 8 Responses to “Floupia”

1. […] today’s Programming Praxis exercise, our goal is to calculate the minimum total amount of coins involved in […]

```import Data.List
import Math.Combinat

pay :: (Eq a, Num a) => a -> [a] -> ([a], [a])
[(p,c) | n <- [1..], pc <- [1..n], p <- combine pc coins
, c <- combine (n - pc) (coins \\ p), sum p - total == sum c]
```
3. […] Pages: 1 2 […]

4. jpverkamp said

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:

```> (define floupia (make-coinage '(1 3 7 31 153)))
> (floupia 17)
'((31) (7 7))
> (floupia 100)
'((1 1 7 153) (31 31))
> (floupia 57)
'((1 1 31 31) (7))
```

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.

5. programmingpraxis said

Before we look at today’s exercise, let’s review some facts from high-school mathematics. The binomial coefficient $\binom {n} {m}$ is the number in the m‘th position of the n‘th row of Pascal’s Triangle, and is computed as (n * (n−1) * … * (nk+1)) / (k * (k−1) … * 1). Thus $\binom {5} {3} = 10$. We compute the binomial coefficient with this function, which is the same as the `choose` function 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, $\binom {n} {m}$ 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 $\binom {n+m-1} {m}$ 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.

6. Simon Wo said

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])
```
7. Mike said

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

```
8. An inefficient, but terse implementation in python. Catches infeasible inputs.

```from fractions import gcd
def coin_fun(coins, n):
if n % reduce(gcd, coins) > 0:
return "infeasible"

q = []
cur = []
coins.extend([c * -1 for c in coins])

while True:
for coin in coins:
newcur = list(cur)
newcur.append(coin)
q.append(newcur)

cur = q.pop(0)
if sum(cur) == n:
return cur
```