1
\$\begingroup\$

Given an infinite number of different coin types (such as pennies, nickels, dimes, quarters) find out how many ways n cents can be represented.

My code appears to work (although I am curious to know if it has any correctness issue). But I feel like the memoization I am doing is a bit inelegant. Can we do without dictionaries/maps, perhaps a dynamic programming based approach using 2d arrays? Or is that even worse in terms of time and space complexity?

Also is my code to update the memoized_sol good in terms of coding technique?

'''
Parameters:
    cents: amount to get change for.
    coin_vals: list of coin denominations in no particular order.

Returns: 
    number of ways <cents> can be changes using any number of coins from the given list
'''
def get_coin_change_count (cents, coin_vals):
    memoized_sol = {}
    return compute_coin_change_count(cents, coin_vals, 0, memoized_sol )

def compute_coin_change_count (rem_cents, coin_vals, coin_index, memoized_sol ):

    if coin_index in memoized_sol:
        if rem_cents in memoized_sol[coin_index]:
            return memoized_sol[coin_index][rem_cents]
    else:
        memoized_sol[coin_index] = {}

    if rem_cents == 0:
        return 1

    if coin_index >= len(coin_vals):
        return 0

    coin_val = coin_vals[coin_index]

    i = 0
    count = 0
    while i*coin_val <= rem_cents:
        count = count + compute_coin_change_count\
            ( rem_cents - i*coin_val, coin_vals, coin_index+1, memoized_sol )
        i = i + 1

    memoized_sol[coin_index][rem_cents] = count
    return count


w = get_coin_change_count ( 37, [10, 1, 5, 25])
print (w)
\$\endgroup\$
1
\$\begingroup\$

I don't see any correctness issues, but it could be more idiomatic.

    if coin_index in memoized_sol:
        if rem_cents in memoized_sol[coin_index]:
            return memoized_sol[coin_index][rem_cents]
    else:
        memoized_sol[coin_index] = {}

Check out first defaultdict, and then functools.lru_cache for ways to simplify the memoisation - although note that lru_cache has a subtlety in that it doesn't like list as an argument type.


    if rem_cents == 0:
        return 1

    if coin_index >= len(coin_vals):
        return 0

IMO these should have gone before the memoisation code, because they are non-memoised special cases. But I freely admit that this is mainly a matter of opinion. The only real difference effected would be to avoid initialising memoized_sol[len(coin_vals)].


    i = 0
    count = 0
    while i*coin_val <= rem_cents:
        count = count + compute_coin_change_count\
            ( rem_cents - i*coin_val, coin_vals, coin_index+1, memoized_sol )
        i = i + 1

Using sum and range this could be simplified to

count = sum(compute_coin_change_count(
        surplus, coin_vals, coin_index + 1, memoized_sol)
    for surplus in range(rem_cents, -1, -coin_vals[coin_index]))

(I'm not quite sure what the most Pythonesque indentation would be - I wouldn't normally follow PEP8 on maximum line lengths).


I would also be tempted to use sublists and eliminate the need for coin_index, but that depends on how you're handling memoisation.


Putting it all together, I get

from functools import lru_cache


def get_coin_change_count(cents, coin_vals):
    @lru_cache(None)
    def inner(remaining, idx):
        if remaining == 0:
            return 1

        if idx == len(coin_vals):
            return 0

        return sum(inner(surplus, idx + 1)
                   for surplus in range(remaining, -1, -coin_vals[idx]))
    return inner(cents, 0)


print(get_coin_change_count(37, [10, 1, 5, 25]))

and here the indentation does pass PEP8, in part because of shorter names. Note that using an inner function allows memoisation with lru_cache and allows the short name inner because its scope is restricted enough that this is sufficiently expressive.

\$\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.