Project Euler Problem 31, solution by Indi

# Project Euler Problem 31, solution by Indi

TOTAL = 200 # can't go above this, but can go below (and pad with 1s)
DENOMS = [200, 100, 50, 20, 10, 5, 2] # amount of 1s fixed once we allocate the rest

dot = lambda a,b:sum([a[i]*b[i] for i in range(len(a))]) # dot product (truncates second param)

prevConfig = [[]]   # each config is a list of amounts of denominations
config = []         # we're basically making a tree here
for d in DENOMS:
    for c in prevConfig:
        for q in range((TOTAL - dot(c, DENOMS))//d + 1):
            config.append(c+[q,]) # add each possible thing; could use list comprehension
    prevConfig = list(config) # make sure we copy!
    config = [] # reset config for next "depth"

print(len(prevConfig)) #73682
# Rachel has a far cleverer solution than this