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:
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."
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.)
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.