Hackbright Code Challenges

Coins: Solution

Coins: Solution

Problem

Coins

Whiteboard

Harder

Challenge

Medium

Concepts

Recursion

Download

coins-solution.zip


We have a recursive function, add_coins, which has the number of free slots left for new coins, the total amount of change for this path, and the set, results, which holds the total change amounts found so far:

coins.py
def add_coins(left, total, results):
    """Add combos coins to total.

    If this is the last time we can add coins, return change.

    Otherwise, recursively call until that condition.

        >>> results = set()
        >>> add_coins(left=1, total=0, results=results)
        >>> results == set([1, 10])
        True
    """

    DIME = 10
    PENNY = 1

    if left == 0:
        # Base Case
        # We've added all the coins we're supposed to, so keep
        # track of this total of change and stop recursing
        results.add(total)
        return

    # Fork into two recursions, one adding a dime and another a penny
    # For each, we'll have 1 fewer coin to add afterwards, so left -= 1
    add_coins(left - 1, total + DIME, results)
    add_coins(left - 1, total + PENNY, results)

This is called by coins:

coins.py
def coins(num_coins):
    """Find change from combinations of `num_coins` of dimes and pennies.

    This should return a set of the unique amounts of change possible.
    """

    # START SOLUTION

    results = set()

    add_coins(left=num_coins, total=0, results=results)

    return results

Non-Recursive Solution

There’s an easier way, though.

Imagine that you have 5 coins to spend. If you use three of them as dimes, you know that you’ll have exactly two left for use as pennies. So you can simply calculate 3 × 10 + 2 × 1 = 32.

coins.py
def coins_simpler(num_coins):
    """Find change from combinations of `num_coins` of dimes and pennies.

    This should return a set of the unique amounts of change possible.
    
        >>> coins_simpler(0) == {0}
        True

        >>> coins_simpler(1) == {1, 10}
        True

        >>> coins_simpler(2) == {2, 11, 20}
        True

        >>> coins_simpler(3) == {3, 12, 21, 30}
        True

        >>> coins_simpler(4) == {4, 13, 22, 31, 40}
        True

    Let's make sure it works when we can spend over 10 pennies::

        >>> coins_simpler(11) == {65, 101, 38, 74, 11, 110, 47, 83, 20, 56, 92, 29}
        True
    """

    results = set()

    for ndimes in range(num_coins + 1):
        npennies = num_coins - ndimes
        results.add(ndimes * 10 + npennies)

    return results