McNugget Problem (Knapsack)

nuggets.py

"""
The McNugget Problem

Find the smallest n s.t. there exists a solution to:

n = 6x + 9y + 20z

for n, n+1, n+2, ... , n+5

Result is:

Found 44
Found solution 44 in 121 steps
44 = (20,9,6) * (1, 2, 1)
45 = (20,9,6) * (0, 5, 0)
46 = (20,9,6) * (2, 0, 1)
47 = (20,9,6) * (1, 3, 0)
48 = (20,9,6) * (0, 4, 2)
49 = (20,9,6) * (2, 1, 0)
"""

from tuple_iter import diagonal

solves = {}
counts = {}

Found = None
i = 0
for x,y,z in diagonal(3):
    i += 1
    s = x + y + z
    if Found is not None and 6 * s > Found:
        break
    n = 20*x + 9*y + 6*z
    if n not in solves:
        solves[n] = (x,y,z)
        for n1 in range(n-5,n+1):
            if n1 not in counts:
                counts[n1] = 0
            counts[n1] += 1
            if counts[n1] == 6 and (not Found or Found > n1):
                print "Found %d" % n1
                Found = n1

print "Found solution %d in %d steps" % (Found, i) 

for n in range(Found, Found+6):
    print "%d = (20,9,6) * %r" % (n, solves[n])