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
I've noticed recently on OnLamp that assumptions are made that the reader already knows what the writer is writing about, and simply wants more details. I've never heard of the "Greedy Coin Change" computer science problem. I've been dabbling in programming for almost thirty years, so perhaps it isn't as well-known as you think. Maybe next time a link to a page that describes the problem being solved just in case the reader isn't aware of it?
Keith/You raise a good point. If I make a regular habit out of doing this I need a summary of the problem I am trying to solve along with references. I have attached both at the bottom of this post.
An alternate version, that requires no conditional logic.
#--start code
#!/usr/bin/env python
"""implement a greedy coin changer, returning the fewest
coins to make the change requested."""
#coin_list can be expanded to include silver dollars and 50 cent
#pieces by just expanding the coin list to [100,50,25,10,5,1]
#the reulting answer structure will modify itself to reflect
coin_list = [25,10,5,1]
change_requested = .71
remaining = change_requested * 100
change_returned = [] #result structure
for coin in coin_list:
num_coins,remaining = divmod(remaining,coin)
change_returned.append(int(num_coins))
#--end loop - comments don't show it properly
print change_returned
print remaining
#--end code
I got this problem as a pre interview assignment for my job (junior web developer). Using c#, I solved it using recursion, however there was a limit on how many times I could make the recursive call, something about the limited size of stack maybe. (I didnt do a computer science degree, so I think I may have been doing something really silly)
I just assumed recursion was a bad way of solving this problem and never got round to working out how to do it with loops/conditionals. In fact I assumed I just wasn't smart enough to figure out a better non recursive way.
Anyway I got the job :)
Any thoughts on the best approach to this problem? Why is recursion better / worse.
Functional version
def functional_change(self)
def change(seq,coin):
return seq[:-1]+divmod(seq[-1],coin)
return reduce(change,reversed(self.coins),(self.convert,))[:-1]
What about the standard dynamic programming solution? This is the knapsack problem... Maybe it was one of the above and I was too lazy to read this in detail. So, sorry in advance.
Hi, good post :)
If you make this into a regular series, would you consider presenting the summary of the problem at the top of the article so the readers can get a chance to think through how they'd solve the problem before reading your suggested solutions?
The loop in the while version can be shortened to:
rem = self.convert
while rem > 0:
coin = self.coins.pop()
num, rem = divmod(rem, coin)
self.printer(num,coin)
The recursive code will give results comparable to this while loop by changing the "if" to:
if len(self.coins) == 0 or rem == 0 :
return []
to mimic the terminating condition of the factorial algorithm.