4
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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