I am going to make an effort to solve classic computer science problems in Python on a regular basis, and blog about them. It seems like a good way to have some fun. This may be a regular blog series.
Because I am going to implement a Coin Changing Restful Web Service using Google App Engine for a presentation I am doing for PyAtl next month, I thought I would show three approaches that I could think of. In doing a google search for “Python Greedy Coin Change”, I didn’t find anyone that had written one and posted the code, so I figured I would make one easily googable. The full source code is here, along with unittests:
Python Greedy Coin Algorithm Source
Approach one was to just use conditional statements, which was pretty tedious to write. Approach two used a while loop and was much shorter. Approach three used recursion, which was also quite a bit shorter. My friend Toby beat me to the recursion solution, so I have to thank him for that one. It would be interesting to see how many other ways I could solve the problem, I think trying to use only functional programming could be a fun twist for example.
I put all three in a commandline tool which make it easier to run and test things out. A couple interesting things to point out about Greedy Coin Changer.
1. You need to get rid of decimals and only work with whole numbers. int(amount*100)
2. Divmod is a wonderful built in function that divides and returns the number and a remainder as a tuple.
Method 1: Conditional Statements
def make_change_conditional(self):
"""Greedy Coin Match with Conditional Statements
Return both number of coins and remainder
>>> c = Change(.71)
>>> c.make_change_conditional()
(2, 21, 2, 1, 0, 0, 1)
>>>
"""
quarter, qrem = divmod(self.convert,25)
#initialize values
dime, drem = 0,0
nickel, nrem = 0,0
penny = 0
#if remainder is dime or higher
if qrem >= 10:
dime, drem = divmod(qrem,10)
if drem >= 5:
nickel, nrem = divmod(drem,5)
if nrem >= 1:
penny = nrem
elif drem < 5:
penny = drem
#if remainder is nickel or higher
elif qrem >= 5:
nickel, nrem = divmod(qrem,5)
if nrem >= 1:
penny = nrem
#if remainder is penny or higher
elif qrem > 0:
penny = qrem
return quarter, qrem, dime, drem, nickel, nrem, penny
Method 2: While Loop
def while_loop_change(self):
"""Greedy Coin Match with While Loop
>>> c = Change(.71)
>>> c.while_loop_change()
2 quarters
2 dimes
1 pennies
"""
coin = self.coins.pop()
num, rem = divmod(self.convert, coin)
self.printer(num,coin)
while rem > 0:
coin = self.coins.pop()
num, rem = divmod(rem, coin)
self.printer(num,coin)
Method 3: Recursion
def recursive_change(self, rem):
"""Greedy Coin Match with Recursion
>>> c = Change(.71)
>>> c.recursive_change(c.convert)
2 quarters
2 dimes
1 pennies
[1, 0, 2, 2]
"""
if len(self.coins) == 0:
return []
coin = self.coins.pop()
num, new_rem = divmod(rem, coin)
self.printer(num,coin)
return self.recursive_change(new_rem) + [num]
Feel free to point out corrections, or alternate solutions
Summary of Problem
Given an arbitrary amount of change, say 1.34, determine the correct amount of change to give using a greedy match, which uses the highest coins first. With US coins, 25,10, 5,1, greedy match will lead to the lowest coins possible.
References:
Google App Engine Version
Greedy Algorithm
Coin Changing Algorithm
Greedy Coins
