current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 4 down vote favorite

Recently, I wrote a simple program to solve the change-making problem. Rather than the tabular dynamic programming solution (described in the link), I tried to write a solution that uses memoization. 

usd = [25, 10, 5, 1]

def make_change(W, denoms=usd):
    """
    Solves the change-making problem where W is
    a given amount of money and denoms 
    is a list of the denominations available

    >>> make_change(6,[3,1])
    (3, 3)
    """

    d = {}

    def inner(W, sol): 
        if W == 0:
            return sol

        if W in d:
            return d[W]

        tmp = []
        for coin in denoms:
            w = W - coin

            if w >= 0:
                tmp.append(inner(w, sol + (coin,)))

        d[W] = min(tmp, key=lambda x : len(x))
        return d[W]
    return inner(W, tuple())

if __name__ == "__main__":
    import doctest
    doctest.testmod()

I'm wondering if there's a better way I should be doing the memoization (i.e. a decorator):

def memoize(f):
    d = {}
    def inner(args):
        if args not in d:
            d[args] = f(*args)
        return d[args]
    return inner

The above code caches the arguments so they don't get recomputed in future computations. Here, however, I think we only want to cache the solution for a given W, and I'm not sure a general purpose decorator like the one above is necessarily correct.

share|improve this question
up vote 5 down vote accepted

I'd say the main issue with your code is that you're confusing what the inner function is supposed to do:

def inner(W, sol): 
    if W == 0:
        return sol   ## return result so far?

    if W in d:
        return d[W]  ## return best result for W?

Those are two different kinds of values. If you're just returning "smallest tuple for weight W", then W == 0 should yield tuple(). And your recursive step should just be:

tmp.append(inner(w) + (coin,))

With that, I would rename tmp. It's not really a temporary variable, we're actually building up our next possible step. So really something like:

next_iteration = (inner(W - coin) + (coin,)
                  for coin in denoms
                  if coin <= W)

And for your key argument to min, you need a function taking one argument and returning a value. You had:

key = lambda x: len(x)

But lambda x: len(x) is the same as len. So I'd reduce the whole thing to:

d = {0: tuple()} # to avoid the special case of 0
def inner(W):
    if W in d:
        return d[W]

    next_iteration = (inner(W - coin) + (coin,)
                      for coin in denoms
                      if coin <= W)
    d[W] = min(next_iteration, key=len)
    return d[W]

return inner(W)

For memoize, sure, with one minor modification:

def memoize(f):
    cache = {}                 # why d?
    def inner(*args):          # <== *args, not args
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return inner

And then just:

@memoize
def inner(W):
    if W == 0:
        return tuple()

    next_iteration = (inner(W - coin) + (coin,)
                      for coin in denoms
                      if coin <= W)
    return min(next_iteration, key = len)

return inner(W)

That does seem nicer. I like it.

share|improve this answer
1  
I like this too, just replace the [ with ( for lazyness and efficiency. (see: python.org/dev/peps/pep-0289 ) – Caridorc Sep 16 '15 at 18:40
up vote 1 down vote

Be careful with using lists as default values for functions. In your case you don't modify denoms, but when default value lists or dictionaries are modified it's actually preserved from one function call to another. For example:

nums = [2, 5]

def f(vals=nums):
    vals.append(12)
    print vals

Calling f repeatedly will produce this:

>>> f()
[2, 5, 12]
>>> f()
[2, 5, 12, 12]
>>> f()
[2, 5, 12, 12, 12]

Even though your current code doesn't run into that trouble you can easily avoid accidentally creating these issues by making usd a tuple. Tuples can't be modified so if you just set usd as one you couldn't even accidentally modify it.

usd = (25, 10, 5, 1)

Also don't use W just because the algorithm does. total, total_change or total_money are all better candidates to choose and clearer to understand. Likewise with d and sol.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.