7
\$\begingroup\$

When I'm at a store and I pay for something in cash, I always try to give as exact change as possible in order to minimize the number of coins I have left in my wallet afterwards.

Your task is to build a program that will automate this process for me.

Your program will accept as input:

  • a line containing a single decimal number representing the price of an item.

  • a line consisting of a list of pairs of numbers, each pair representing the value of a denomination of coin or bill, and then the current amount of that denomination that I have in my wallet.

  • a line consisting of a list of denominations that the cashier has (you may assume they have an unlimited amount of each).

For example, the following input:

21.36
0.01 6 0.05 2 0.10 3 0.25 4 1.00 1 2.00 2 5.00 1 20.00 5
0.01 0.05 0.10 0.25 1.00 2.00 5.00 10.00 20.00 50.00 100.00

represents that I'm buying an item costing $21.36, and I have six pennies, two nickels, three dimes, four quarters, one loonie, two toonies, one five-dollar bill, and five 20-dollar bills.

Your program will then output the following:

  • the change that I should give to the cashier.

  • the change that the cashier will give me in return. You must optimize this as well in order to have a good solution.

  • the list of coins and bills still left in my wallet.

  • the total number of coins and bills left in my wallet after the transaction.

In this case, the optimal output is:

0.01 6 0.05 2 0.10 2 0.25 4 20.00 1

0.10 1 1.00 1 2.00 2 5.00 1 20.00 4
12

because I have exact change and this configuration uses the most coins to give that change. The second line is blank because no change was given in return.

Note that your program must support unconventional denominations such as 0.04 or 15.32, if they are part of the input. You are not guaranteed that every denomination will be a multiple or factor of another, except that every denomination will be a multiple of the lowest one, so that there is always a valid solution. You may assume that I will always have enough money to pay for the item whose price is listed.

In a few days, I will be posting a suite of 1,000 test cases for this program. Your program will be scored by the sum of the total number of coins and bills left in my wallet for each test case, with shorter code being a tie-breaker.

\$\endgroup\$

closed as unclear what you're asking by Joe Z., Justin, ProgramFOX, Johannes Kuhn, John Dvorak Dec 24 '13 at 8:01

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ "Note that your program must support unconventional denominations". Guess that means I can't use the Greedy Algorithm \$\endgroup\$ – Justin Dec 14 '13 at 1:32
  • \$\begingroup\$ What is the largest number you want us to make? Must we use arbitrary precision or is long precision or int precision enough? \$\endgroup\$ – Justin Dec 14 '13 at 1:38
  • 1
    \$\begingroup\$ You can assume that the transactions in question will not exceed 1 million dollars. \$\endgroup\$ – Joe Z. Dec 14 '13 at 1:53
  • 1
    \$\begingroup\$ I always try to give as exact change as possible in order to minimize the number of coins I have left in my wallet afterwards. Then the best solution is to give the cashier all of you cash. They will(should) then return to you the most efficient way to represent what's left \$\endgroup\$ – Cruncher Dec 20 '13 at 15:42
  • 1
    \$\begingroup\$ My god, you're right. Maybe we should close this question and post a new one, since I think this question has gone through too many rule changes and discussion for the work of people who were going by the old rules to still be salvageable. \$\endgroup\$ – Joe Z. Dec 21 '13 at 22:28
2
\$\begingroup\$

I think I have a Python 3 solution that should work for any test case. It took me quite a few tries to get something that wouldn't explode for certain degenerate inputs. It's still pretty slow for some large inputs where you have thousands of coins in your wallet to start, but I don't think it's possible to do much better in those cases (you must search a very large set of possible combinations of payment and change).

I've made two version of my solution, one that minimizes the number of coins you end up with in your wallet at the end (as per the current scoring rule), and another that minimizes the number of coins you are given in change (which is equivalent to minimizing the number of coins in your wallet at the end plus the number of coins you paid with, which Joe Z. has been considering changing the scoring rule to). You can switch which version is run by moving the leading # for the comment in the if __name__ == "__main__" block to the previous line. Both versions are based on of the same recursive change making algorithm (in the make_change function), they just run it with slightly different inputs.

The code exploits the effect that Cruncher noted in the question's comments, that the best overall algorithm is to give all your money to the cashier and then get ideal change for your final balance back. What my code does is give all the money to the cashier, then charge a "cost" to the solution for each coin or bill returned to the customer. The best solution is the one with the combined cost for its bills and coins. Later I do some cleaning up, and eliminate any payments that get directly returned using the same bills or coins.

For the version optimized for the original scoring rule, the cost is 1 for every coin or bill. For the alternative scoring rule, the cost is 0 for bills and coins that were originally in the customer's wallet (and are being returned), and 1 for anything that needs to come from the cashier's drawer.

The core algorithm is a depth-first search for combinations of coins that yield exact change. Larger coins are tried first, and more of them before fewer. This means the first result we find will be the "greedy" one (though we keep searching and may find a better result later).

The interesting part of the algorithm is that it keeps track of the cost of the best result found so far, and stops searching for more results down any branch that costs more than that that result. This lets it avoid considering a lot of possible combinations that require too much from the cashier (like thousands of pennies).

I do get a different optimal result for the example case given in the question, but it is in fact better for the current scoring rule (I pay several extra small bills and get a single $50 in change). My output is:

0.01 6 0.05 2 0.10 2 0.25 4 1.00 1 2.00 2 5.00 1 20.00 3
50.00 1
0.10 1 20.00 2 50.00 1

For the alternate scoring rule I get the same result shown in the question.

I've not made much effort at minimizing the number of characters in this code, though some parts were written in terse, code-golf style before I got more distracted by performance issues and correctness. I think I've factored out the all the repeated code into separate functions, but let me know if you see any obvious improvements.

def make_change(value, coins, best_cost=float("inf")):
    if value == 0:
        return [], 0

    best_solution=None
    for i, (coin, count, cost) in enumerate(coins):
        max_num = min(count, value//coin, best_cost//cost if cost else float("inf"))
        for num in range(max_num, 0, -1):
            coin_value = num*coin
            coin_cost = num*cost
            if coin_cost < best_cost: # this is always true the first iteration, but may not be later
                solution, solution_cost = make_change(value-coin_value, coins[i+1:],
                                                      best_cost-coin_cost)
                if solution is not None:
                    best_solution = [(coin, num)] + solution
                    best_cost = coin_cost + solution_cost
    return best_solution, best_cost

def parse():
    value = int(input().replace(".",""))
    wallet = dict(zip(*[iter(map(int,input().replace(".","").split()))]*2))
    cashier = list(map(int,input().replace(".","").split()))
    return value,wallet,cashier

def print_output(pay, change, final_wallet):
    print(" ".join("{:.2f} {}".format(coin/100, count) for coin, count in pay if count != 0))
    print(" ".join("{:.2f} {}".format(coin/100, count) for coin, count in change if count != 0))
    print(" ".join("{:.2f} {}".format(coin/100, count) for coin, count in final_wallet if count != 0))

def solve(value, wallet, coins):
    result, cost = make_change(value, coins)
    pay=[]
    change=[]
    for coin, count in result:
        if coin in wallet:
            if wallet[coin] > count:
                pay.append((coin, wallet[coin] - count))
            elif wallet[coin] < count:
                change.append((coin, count - wallet[coin]))
            del wallet[coin]
        else:
            change.append((coin, count))
    pay.extend(wallet.items())
    pay.sort()
    change.sort()
    result.sort()
    return pay, change, result

def minimize_wallet(value, wallet, cashier):
    wallet_value = sum(coin*count for coin,count in wallet.items())
    coin_dict = wallet.copy()
    coin_dict.update((coin, wallet_value//coin) for coin in cashier)
    coin_list = [(coin, count, 1) for coin, count in sorted(coin_dict.items(), reverse=True)]
    return solve(wallet_value-value, wallet, coin_list)

def minimize_change(value, wallet, cashier):
    wallet_value = sum(coin*count for coin,count in wallet.items())
    coin_list = [(coin, count, 0) for coin, count in wallet.items()]
    coin_list.extend((coin, wallet_value//coin, 1) for coin in cashier)
    coin_list.sort(key=lambda x: (-x[0], x[2]))
    return solve(wallet_value-value, wallet, coin_list)

if __name__ == "__main__":
    print_output(*minimize_wallet(*parse()))
    #print_output(*minimize_change(*parse())) # use this if the scoring rules are changed

I'd also like to suggest a testcase that is likely to break many implementations:

1.00
100.00 10000
0.01 0.05 0.10 0.25 1.00 2.00 5.00 10.00 20.00 50.00 100.00 999999.00

This testcase comes with a story I like to call "The bank robber and the debt limit":

One day, Alice robbed a bank. She made a clean getaway with exactly one million dollars in $100 bills. On her way home from the bank, she stopped off at a convenience store to buy a candy bar, but realized that she had not brought her wallet with her, so the only money she had was her bag of stolen money (ten thousand $100 bills will fit snugly in a decent sized backpack if they're shrink wrapped). She hoped the clerk would be willing to break a $100 bill.

Unbeknownst to Alice, Bob the convenience store clerk had been recently laid off as a worker at the US Mint. He had worked for several months this past spring and summer preparing high-denomination platinum coins in case they would be the only way for the US Government to make its interest payments without Congress increasing the debt limit. It turned out the coins were not needed, so their existence was never acknowledged. When he was told his job was being cut, Bob decided he would keep on of the coins he had worked so hard on. He smuggled out a single $1,000,000-denominated coin in his box of personal effects.

Sadly for everyone involved, Bob was showing off his million dollar coin to a coworker when Alice came to his register to see if he'd give her $99 in change for her $1 candy bar. Alas, seeing the coin, Alice's compulsion to receive the smallest amount of change possible got the better of her. She misinterpreted the text on the coin saying it was "0.999999 pure Platinum" to mean it was worth that fraction of its face value. If that was the case, it would be exact change for her candy bar if she paid Bob with her backpack full of money. She'd go from having 10,000 bills to having just one coin!

Can your code satisfy Alice? Expected output:

100.00 10000
999999.00 1
999999.00 1
\$\endgroup\$
  • \$\begingroup\$ I'm sorry I put you through all those rule changes. \$\endgroup\$ – Joe Z. Dec 21 '13 at 22:25
  • \$\begingroup\$ @JoeZ. No problem. The same basic algorithm works for either version, with just minor tweaks. And minimizing the change you get back (the newer scoring method) is probably a bit more interesting, since it's not just a pure change-making problem. \$\endgroup\$ – Blckknght Dec 22 '13 at 17:34

Not the answer you're looking for? Browse other questions tagged or ask your own question.