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.

About these ads

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 [...]

  2. 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]
    
  3. 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.

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

  5. 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])
    
  6. 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):
        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]
    
    
  7. 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 
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 616 other followers

%d bloggers like this: