Whenever someone makes a purchase at a shop or restaurant and pays with cash, the person taking their payment may have to return change to them. This presents that person with a simple algorithmic problem. Given the amount of change to return, they will have to determine an optimal combination of coins to return to the customer. Fortunately, the algorithm for doing this optimally is pretty simple.
Suppose you need to return 87 cents to a customer. The algorithm consists of handing the customer the largest possible number of the largest denomination coins first. The largest denomination of coin in common use in the United States is the quarter, so we start by trying to give the customer as many quarters as we can without exceeding the amount due. The simplest way to figure out how many quarters to give is to ask how many times 25 will divide evenly into 87.
This is something we can compute in Python via some simple code:
amount = 87 quarters = amount//25
Here we have to be careful to use the integer version of division, //, which will answer the question "how many times does 25 divide into 87?"
After determining how many quarters to give out, we have to reduce the amount due and repeat the process for the other available denominations:
amount = amount - quarters*25 dimes = amount//10 amount = amount - dimes*10 nickels = amount//5 pennies = amount - nickels*5
Finally, we would have to set up print statements to print the number of each coin to give out. If we are being careful, we might want to use some if-else statements to make sure that print the denominations in their proper singular or plural forms. For example, this is the logic to print how many quarters to give the customer.
if quarters > 1:
print(str(quarters)+ " quarters")
elif quarters == 1
print("1 quarter")
The simple algorithm I showed above is somewhat redundant, in that you will find yourself doing similar steps on each round with small variants. The main variant is the number of cents each coin is worth. To automate this algorithm, we can start by putting the cent values of the various denominations in a list:
values = [25,10,5,1]
We could then write a loop that iterates over this list of coin values doing the repetitive steps with each new coin type. To facilitate doing this all in a loop, the results would also have to go into a list. We can do this easily by starting with an empty list of results and appending a new entry to that list for each denomination we process. Finally, we could also automate the process of printing the results by using a loop that iterates over the names of the various coin denominations.
Here is a program, change.py, that uses a pair of loops to automate the key steps in the algorithm:
amount = 87
denominations = [25,10,5,1]
names = [('quarter','quarters'),('dime','dimes'),('nickel','nickels'),('penny','pennies')]
counts = []
for d in denominations:
counts.append(amount//d)
amount = amount % d
result = "I owe you "
for n in range(0,len(names)):
if counts[n] == 1:
result = result + "1 " + names[n][0] + " "
elif counts[n] > 1:
result = result + str(counts[n]) + " " + names[n][1] + " "
print(result)
If you look closely at the code above, you will see that the second loop has to iterate over both the counts of each coin and the corresponding names of the coins. We handle this by noting that since both lists have the same length, we can use a common index variable, n, to iterate over the list positions in both lists at the same time. Since we are using an index variable we also have to use the list index notations counts[n] and names[n] with the two lists we are iterating over.
An alternative technique used to iterate over multiple lists at the same time is to start by forming a zip list from the individual lists. For example, suppose we had to iterate over a list of fruit names and prices per pound. Using a loop index we would do this:
fruits = ['orange','banana','apple']
prices = [1.45,0.45,1.15]
for n in range(0,len(fruits)):
print(fruits[n]+"s are $"+str(prices[n])+" per pound.")
The alternative is to form a zip list that combines the information from both lists into a list of tuples. To form the zip list we do
both = zip(fruits,prices)
This results in a new list whose structure is
[('orange',1.45),('banana',0.45),('apple',1.15)]
We can then set up an iteration over this zipped list:
fruits = ['orange','banana','apple']
prices = [1.45,0.45,1.15]
for fruit, price in zip(fruits,prices):
print(fruit+"s are $"+str(price)+" per pound.")
One special trick in this iteration is the structure of the loop. Since we are iterating over a list of tuples, each element in the list is a tuple. The special trick here is to assign each tuple to an implicit tuple consisting of the variables fruit and price. This will automatically assign the first element of each tuple in the iteration to fruit and the second element to price. The net effect of forming the zip list and then using the special iteration trick is that we have now managed to iterate over two lists at the same time.
Here is the change making program rewritten to use a zip list where appropriate:
amount = 87
denominations = [25,10,5,1]
names = [('quarter','quarters'),('dime','dimes'),('nickel','nickels'),('penny','pennies')]
counts = []
for d in denominations:
counts.append(amount//d)
amount = amount % d
result = "I owe you "
for count, name in zip(counts,names):
if count == 1:
result = result + "1 " + name[0] + " "
elif count > 1:
result = result + str(count) + " " + name[1] + " "
print(result)
Here is one last improvement to make in the program. When we run either of the two solutions above the program will print
I owe you 3 quarters 1 dime 2 pennies
This is almost what we want, but it would be nice to have some additional punctuation. Specifically, we would like to have commas between the various results and also a period at the end.
One way to handle this is to simply print a comma after each result. This is not quite right, since it will leave us with an extra comma at the end. A better approach is to print a comma before each result except for the first one. To handle this, we need to make use of a flag variable. We introduce a new variable, didOne, that we can use to track whether or not we have printed a first result. We set that flag to true after printing our first result, and then use the flag subsequently to determine whether or not we need to print a comma before the next result. Putting the period at the end is also easy to do.
For this version I revert back to using an index variable instead of a zip list.
amount = 87
denominations = [25,10,5,1]
names = [('quarter','quarters'),('dime','dimes'),('nickel','nickels'),('penny','pennies')]
counts = []
for d in denominations:
counts.append(amount//d)
amount = amount % d
result = "I owe you "
didOne = False
for count,name in zip(counts,names):
if count == 1:
if didOne == True:
result = result + ", "
else:
didOne = True;
result = result + "1 " + name[0]
elif count > 1:
if didOne == True:
result = result + ", "
else:
didOne = True;
result = result + str(count) + " " + name[1]
print(result+".")
Here is the output of the final version:
I owe you 3 quarters, 1 dime, 2 pennies.