Python Algorithms: Greedy Coin Changer
by Noah Gift
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
8 Comments
Keith 20080426 06:17:03 
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 wellknown 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? 
Noah Gift 20080426 06:53:21 
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. 
Jeff Hinrichs 20080426 10:27:35 
An alternate version, that requires no conditional logic. #start code

bplus 20080426 10:29:28 
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)

Mike 20080426 13:38:03 
Functional version

Rui Ferreira 20080426 14:24:38 
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. 
Haakon 20080428 00:29:28 
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? 
Eldon 20080429 18:00:12 
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)
