MIT OCW 6.00's Chicken McNugget program... again

Question

I have spent a little while reading previous questions/answers about MIT OpenCourseWare 6.00's problem set regarding a program for determining the maximum unattainable number of chicken McNuggets in packs of 6, 9, and 20. Unfortunately, I'm having trouble integrating those answers into the code I've tried to make on my own.

First, here is the actual phrasing of the problem set that I'm trying to write code for:

... we can write an exhaustive search to find the largest number of McNuggets that cannot be bought in exact quantity. The format of the search should probably follow this outline:
• Hypothesize possible instances of numbers of McNuggets that cannot be purchased exactly, starting with 1
• For each possible instance, called n, test if there exists non-negative integers a, b, and c, such that 6a+9b+20c = n. (This can be done by looking at all feasible combinations of a, b, and c)
• If not, n cannot be bought in exact quantity, save n
• When you have found six consecutive values of n that in fact pass the test of having an exact solution, the last answer that was saved (not the last value of n that had a solution) is the correct answer, since you know by the theorem that any amount larger can also be bought in exact quantity. Write an iterative program that finds the largest number of McNuggets that cannot be bought in exact quantity. Your program should print the answer in the following format (where the correct number is provided in place of (n)): “Largest number of McNuggets that cannot be bought in exact quantity: (n)”
Hint: your program should follow the outline above.

(The theorem referenced basically says that once you have six permissible values for n in a row, you can add six on to them indefinitely and there will be no more impermissible values for n.)

This is my code:

n = 1                                  #set first value for trying to solve the equation
savedn = []                            #list for holding values of n w/ no integer solution
consecutivecount = 0
while consecutivecount < 6:
    for a in range(0,n):
        for b in range(0,n):
            for c in range(0,n):
                if 6*a + 9*b + 20*c == n:
                    consecutivecount += 1
                else:
                    #NOW A MIRACLE HAPPENS!!!
                    consecutivecount = 0      #resets consecutivecount value to zero
                    savedn += [n]             #adds current value of n to list
                n += 1                        #increases value of n to continue test loop
print 'Largest amount of McNuggets that cannot be bought in exact quantity:',str(savedn[-1])+'.'

My difficulties:

1. As you can see, I am stuck in the very middle of this, where indicated. I see other questions/answers for this problem using bools, but I'm not sure why anyone is going about it that way. Do I actually have to use bools, though? And why? Basically I would appreciate help figuring out an efficient operation to perform for the "else."

2. I'm not sure if I am really using the savedn list correctly. When I have run test segments of this code, I know I am clearly adding values to the list, but some confirmation that this is the correct way to use "savedn += [n]" would be nice.

I still know VERY few commands and I have very rusty math skills, so as with my last question from this course, please assume I'm an idiot in responding. On the other hand, if what I'm attempting above is just hopelessly off the mark, feel free to clearly suggest how I should start from scratch.

Thanks and apologies for length— the other discussions of this question just didn't seem thorough enough to be useful. (And apologies also that this requires Python 2.5.)

Answer 1

You're almost there. Suppose the question was "find a solution of what to order to get 'n' McNuggets"? You have the core of that, and could solve that question with something like:

solution = (0,0,0)
for a in range(0,n):
    for b in range(0,n):
        for c in range(0,n):
            if 6*a + 9*b + 20*c == n:
                solution = (a,b,c)

Now, all you need to do is surround this with bookkeeping like you have:

while consecutivecount < 6:
    solution = (0,0,0)
    # ** find a solution like above
    if solution == (0,0,0):
        consecutivecount = 0      #resets consecutivecount value to zero
        savedn += [n]             #adds current value of n to list
    else:
        consecutivecount += 1
    n += 1                        #increases value of n to continue test loop

So you look for a solution for n and if you found one, you count up the consecutivecount, and if you didn't find one, you save off another unattainable number (and reset consecutivecount). In either case, time to go on to another n.

Answer 2

I've used itertools.product to avoid the 3 deep nesting of for loops. This means I can easily break out of the loop

from itertools import product, count

v = [6,9,20]
min_v = min(v)
miss = 0

for n in count(1):
    for w in product(range(n), repeat=len(v)):
        if sum(i * j for i, j in zip(v, w)) == n:
            break
    else:
        miss = n
    if n == miss + min_v:
        break

print miss

This does test a bunch of cases that aren't necessary as noticed by @Joran in the comments on the question. The following way avoids those cases by setting up the product slightly differently

from itertools import product, count

v = [6,9,20]
min_v = min(v)
miss = 0

for n in count(1):
    for w in product(*(range(1 + n // i) for i in v)):
        if sum(i * j for i, j in zip(v, w)) == n:
            break
    else:
        miss = n
    if n == miss + min_v:
        break

print miss

If we use the step parameter to range, it can be further simplified to this

from itertools import product, count

v = [6,9,20]
min_v = min(v)
miss = 0

for n in count(1):
    for w in product(*(range(0, n + 1, i) for i in v)):
        if sum(w) == n:
            break
    else:
        miss = n
    if n == miss + min_v:
        break

print miss

Answer 3

Here is a generalized version, which will work for any number of pieces:

def solution_exists(amt, pieces, i=None):
    """
    Return True if any whole multiples of pieces[:i+1] sum to amt, else False
    """
    if i is None:
        i = len(pieces) - 1   # start with last item
    p = pieces[i]
    if i:
        return any(solution_exists(amt - p*k, pieces, i-1) for k in range(amt // p + 1))
    else:
        return amt % p == 0

def find_max_unbuyable(pieces):
    least = min(pieces)
    n = 0
    last_unsolved = None
    consecutive = 0
    while consecutive < least:
        n += 1
        if solution_exists(n, pieces):
            consecutive += 1
        else:
            last_unsolved = n
            consecutive = 0
    return last_unsolved

def main():
    pieces = [6, 9, 20]
    max_unbuyable = find_max_unbuyable(pieces)
    print("Largest number of McNuggets that cannot be bought in exact quantity: {n}".format(n=max_unbuyable))

if __name__=="__main__":
    main()

find_max_unbuyable is pretty straight-forward; it's pretty much step-for-step from the description of the problem.

solution_exists is more involved; it is a recursive satisfiability test. For each pack, starting with the last one and working to the first, it figures out the maximum possible number which can be bought (amt // p) and the remaining number of pieces to buy (amt - p*k). It then calls itself against the reduced sub-problem. If the sub-problem is solved, then the problem is solved, and any short-cuts the evaluation and returns True. For the base case (i == 0, we are looking at the last pack) we return True iff the remaining amount is evenly divisible by p (amt % p == 0).

There are two benefits to writing solution_exists in this way: first, it is a more efficient solution (iterating as few times as possible, doing the last piece as modulo divison instead of another iteration, short-circuiting as soon as a solution is found); second, because it is recursive, it will happily operate on arbitrarily large numbers of packages.