Floupia
February 22, 2013
[ Today’s exercise was contributed by Tom Rusting, who worked as a programmer until the mid 70’s. Being retired, he has now taken up programming again as a hobby. Suggestions for exercises are always welcome, or you may wish to contribute your own exercise; feel free to contact me if you are interested.
Floup is an island-country in the South Pacific with a currency known as the floupia; coins are denominated in units of 1, 3, 7, 31 and 153 floupias. Merchants and customers engage in a curious transaction when it comes time to pay the bill; they exchange the smallest number of coins necessary to complete the payment. For instance, to pay a bill of 17 floupia, a customer could pay three 7-floupia coins and receive single 1-floupia and 3-floupia coins in exchange, a total of five coins, but it is more efficient for the customer to pay a single 31-floupia coin and receive two 7-floupia coins in exchange.
Your task is to write a program that determines the most efficient set of coins needed to make a payment, generalized for any set of coins, not just the set 1, 3, 7, 31 and 153 described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
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.