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

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

[…] 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 then‘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`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, 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 chosenwith replacement. The binomial coefficient defines the number of waysmitems 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):

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)

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