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:
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.