Coin sum dynamic programming in Python

Question

I am preparing for an interview, and here's a popular problem on the dynamic programming. And I want to see if there's any feedback or code review for my solution at dynamic programming question.

# Problem: Coin Sum
#
# Given an array of coins and a target total, return how many
# unique ways there are to use the coins to make up that total.
#
# Input: coins {Integer Array}, total {Integer}
# Output: {Integer}
#
#
# Example:
# Input: [1,2,3], 4
# Output: 4
#
# 1+1+1+1
# 1+3
# 1+1+2
# 2+2
#
#
# Input: [2,5,3,6], 10
# Output: 5
#
# 2+3+5
# 5+5
# 2+3+2+3
# 2+2+6
# 2+2+3+3
#
# Note: You have an unlimited number of each coin type. All coins in the
# coin array will be unique
# Order does not matter. Ex: One penny and one nickel to create six
# cents is equivalent to one nickel and one penny
#
#

def coin_sum(coins, total):
 # tabulation way
 arr = [1] + [0] * total
 for coin in coins:
 for i in range(coin, total + 1):
 arr[i] += arr[i - coin]
 return 0 if total == 0 else arr[total]
# Time Complexity: O(N*M), let the number of coins be m.
# We iterate from arr[coin] -> arr[n], or ~ n operations on each coin, hence n*m.
# Auxiliary Space Complexity: O(N)

It passes all of the following 5 tests for my Coin sum tests:

def expect(count, name, test):
 if (count == None or not isinstance(count, list) or len(count) != 2):
 count = [0, 0]
 else:
 count[1] += 1
 result = 'false'
 errMsg = None
 try:
 if test():
 result = ' true'
 count[0] += 1
 except Exception as err:
 errMsg = str(err)
 print(' ' + (str(count[1]) + ') ') + result + ' : ' + name)
 if errMsg != None:
 print(' ' + errMsg + '\n')
def lists_equal(lst1, lst2):
 if len(lst1) != len(lst2):
 return False
 for i in range(0, len(lst1)):
 if lst1[i] != lst2[i]:
 return False
 return True
print("\nCoin Sum Tests")
test_count = [0, 0]
def test():
 example = coin_sum([1, 2, 3], 4)
 return example == 4
expect(test_count, 'should work for first example case', test)
def test():
 example = coin_sum([2, 5, 3, 6], 10)
 return example == 5
expect(test_count, 'should work for second example case', test)
def test():
 example = coin_sum([2], 10)
 return example == 1
expect(test_count, 'should work for a single coin', test)
def test():
 example = coin_sum([7, 15], 20)
 return example == 0
expect(test_count, 'should work when there is no solution', test)
def test():
 example = coin_sum(
 [78, 10, 4, 22, 44, 31, 60, 62, 95, 37, 28, 11, 17, 67, 33, 3, 65, 9, 26, 52, 25, 69, 41, 57, 93, 70, 96, 5,
 97, 48, 50, 27, 6, 77, 1, 55, 45, 14, 72, 87, 8, 71, 15, 59], 100)
 return example == 3850949
expect(test_count, 'should work for variety of coins and large total', test)
print(('\nPASSED: ' + str(test_count[0]) + ' / ' + str(test_count[1])))

• hjpotter92: python 3.? Please mention the version you might be using
• NinjaG: yes. this is python3
• hjpotter92: Your solution looks a lot like the one here: geeksforgeeks.org/dynamic-programming-set-7-coin-change
• bobah: It instantly runs out of memory if you try with total = (1 << 256) and the same value in the coin array.

Answer 1

Some tips:

• Know your PEP8, format your code appropriately.
• Learn string formatting - and know the differences between 3.6 and earlier.
• Your errMsg and Exception process seem like you expect an error but what error are you expecting? Might want to specify which error you're expecting from your edge cases. ValueError? AttributeError? Also, you shouldn't perform equality statements against None.
• if (count == None or not isinstance(count, list) or len(count) != 2) has redundant brackets

And use a proper test harness instead of writing your own. Here is your code with your expect function removed and using pytest:

import pytest
def coin_sum(coins, total):
 # tabulation way
 arr = [1] + [0] * total
 for coin in coins:
 for i in range(coin, total + 1):
 arr[i] += arr[i - coin]
 return 0 if total == 0 else arr[total]
def test01():
 example = coin_sum([1, 2, 3], 4)
 assert example == 4
def test02():
 example = coin_sum([2, 5, 3, 6], 10)
 assert example == 5
def test03():
 example = coin_sum([2], 10)
 assert example == 1
def test04():
 example = coin_sum([7, 15], 20)
 assert example == 0
def test05():
 example = coin_sum(
 [78, 10, 4, 22, 44, 31, 60, 62, 95, 37, 28, 11, 17, 67, 33, 3, 65, 9, 26, 52, 25, 69, 41, 57, 93, 70, 96, 5,
 97, 48, 50, 27, 6, 77, 1, 55, 45, 14, 72, 87, 8, 71, 15, 59], 100)
 assert example == 3850949

And here are the results:

C:\PycharmProjects\codereview\tests>pytest test_tt.py
======================== test session starts ========================
platform win32 -- Python 3.7.0, pytest-3.6.2, py-1.5.4, pluggy-0.6.0
rootdir: C:\PycharmProjects\codereview\tests, inifile:
plugins: cov-2.5.1, celery-4.2.0
collected 5 items
test_tt.py ..... [100%]
===================== 5 passed in 0.13 seconds ======================

Hope this helps!