Algorithms Question 5

import sys
import random

# My solution from the exam
def calc(coins, total):
    c = [1] + [0] * total
    for coin in coins:
        for j in range(total-coin+1):
            c[j+coin]+=c[j]
    return c[total]


# Solution from Extended Intro to Computer Science
# http://nbviewer.jupyter.org/github/taucsrec/recitations/blob/master/2018a/Michal/rec7/rec7_new.ipynb
def change_fast(amount, coins):
    d = {}
    return change_mem(amount, coins, d)

def change_mem(amount, coins, d):
    if amount == 0:
        return 1
    elif amount < 0 or coins == []:
        return 0
    #if (amount, tuple(coins)) not in d:
    if (amount, len(coins)) not in d:
        #d[(amount, tuple(coins))] = \
        d[(amount, len(coins))] = \
            change_mem(amount, coins[:-1], d) +\
            change_mem(amount - coins[-1], coins, d)
    #return d[(amount, tuple(coins))]
    return d[(amount, len(coins))]


# Comparison function
def compare(amt, coins):
    return calc(coins, amt) == change_fast(amt, coins)

sys.setrecursionlimit(20000)

# Samples
for k in range(25):
    test = (random.randint(1,20000), sorted(random.sample(range(1, 100), random.randint(1,10))))
    print("Running test: " + str(test))
    r = compare(test[0], test[1])
    print("\tResult: " + str(r))
    if (not r):
        break