Greedy Algorithms: Making Change

In this week's installment of my Coursera class on Algorithms, we've been introduced to "greedy" algorithms. One of the homework requires us to solve a tried and tested greedy problem: determining the least number of coins needed to change money.

My first answer to this question wasn't actually a greedy algorithm…but it was only one line:

def get_change(num):
    return (num % 5 + ((num - (num % 5)) % 10 // 5) + ((num - (num % 10)) // 10))

Which adds up the constituent ones, fives, and tens of the number. Here's the code on PythonTutor. While this code passed all the tests, it is neither readable nor greedy. So, back to the drawing board.

Next, I wrote a function that took two variables: the amount (num) and number of coins (coins):

def get_change(m, coins):

    while m:
        if m - 10 >= 0:
            m -= 10
            coins += 1
            return get_change(m, coins)
        if m - 5 >= 0:
            m -= 5
            coins += 1
            return get_change(m, coins)
        if m - 1 >= 0:
            m -= 1
            coins += 1
            return get_change(m, coins)

    return coins

Ho there, recursion! The program keeps calling itself, stating the amount of money (m) remaining and the number of coins each time. This also wound up being about twice as fast as my first version of the code: in the online grader, the first version of the code took .04 seconds, while the second iteration took just .02 seconds. Pretty good! Here's the code on PythonTutor; it takes 26 steps to find how many coins are needed to change six cents.

That's fine, but I wanted to see if I could do it without that second variable. And whaddayaknow, I could.

def get_change(m):

    coins = 0

    while m:
        while m - 10 >= 0:
            m -= 10
            coins += 1
        while m - 5 >= 0:
            m -= 5
            coins += 1
        while m - 1 >= 0:
            m -= 1
            coins += 1

    return coins

That just seems much cleaner and more readable, doesn't it? Looking at it on PythonTutor, it only takes 17 steps to solve get_change(6) – much more efficient than my second attempt! In the online grader this third iteration ran slightly more efficiently, using 4 MB less memory than the second iteration taking the same amount of time.

What I Would Do Next

Next steps for the above? If I were to come back to this assignment, I'd work to make the code reusable. Right now it is built to work with pennies, nickels, and dimes. It would be an idea to allow the user to enter an amount and a list of coin values that could be used to determine how many coins are needed to make change.