#PS2, Q4
#iterative function that increases the value of total_mcnuggets tested in the nested "mcnuggets" function (which determine if the number is solvable by the Diophantine equation). The nested "mcnuggets" function is run (with increasing the input by 1 each time) until x numbers have been added to the "solvable" list (where x is equal to the number of mcnuggets in the smallest package). Once x numbers have been added to the "solvable" list, the differences between the last numbers added to the solvable list are. If each difference is 1 (i.e. all the numbers are consecutive), then this is the solution and the last number added to the "unsolvable" list is printed. If not all the differences are one, the input increases by 1 and the function starts over.
solvable = [0]
unsolvable = []
small = 6
medium = 9
large = 20
packages = small, medium, large
def mcnuggets(total_mcnuggets): # function determines if the input number (total_mcnuggets), which comes from the function "Diophantine", is solvable by the diophantine equation and sorts the number into one of two lists (solvable or unsolvable).
solution = False
for small_packs in range(0, total_mcnuggets / packages[0] + 1): #define range for small_packs
for medium_packs in range(0, (total_mcnuggets - packages[0]*small_packs) / packages[1] + 1): #define range for medium_packs
large_packs = (total_mcnuggets - packages[1]*medium_packs - packages[0]*small_packs) / packages[2] #equation for solving for large_packs
if packages[0]*small_packs + packages[1]*medium_packs + packages[2]*large_packs == total_mcnuggets: #test to see if number of mcnuggets is evenly divisible
solution = True
if solvable[-1] != total_mcnuggets: #test if number has already been added to list
solvable.append(total_mcnuggets) #if it hasn't, the number is added
if not solution: unsolvable.append(total_mcnuggets) #if no solution, number is added to unsolvable list
def Diophantine(starting_number): #iterative function. Input is the first number of mcnuggets to be tested (should just be 1).
total_mcnuggets = starting_number #defines the input for mcnuggets function
if total_mcnuggets <= 200: #test if it is already > 200
mcnuggets(total_mcnuggets) #tests if the input number is solvable by the Diophantine equation for three numbers (previously defined as packages = small, medium, large)
if len(solvable) < (packages[0] + 1): #test if "solvable" list has at least x numbers, where x is the number of mcnuggets in the "small package" (previously defined). Solvable list must have at least this number because it must have x consecutive integers for the last unsolvable number to be found.
starting_number += 1 #if not enough numbers added to "solvable" list, input increases by 1 and function runs again
Diophantine(starting_number)
else:
possible_solutions = [] #Enough numbers have been added to "solvable" list, new list (which holds the differences between the last numbers on the "solvable" list) is created.
for x in range(1, packages[0] + 1): #Defines range to be tested
possible_solutions.append(solvable[-x] - solvable[-x-1]) #Differences between last numbers of "solvable" list are added to "possible_solutions" list.
if len(possible_solutions) + 1 == packages[0]: #Test if length of "possible_solutions" list is equal to the number of mcnuggets in "small" package.
if sum(possible_solutions) == len(possible_solutions): #Test if the sum of the numbers equals the length of "possible_solutions" list. If it does, that means it all the differences in the "solvable" list were 1 (i.e. they're consecutive), so from here on all numbers are solvable.
print 'The Largest number of McNuggets that cannot be bought in exact quantity is:', unsolvable[-1] #Solution is printed
break
else:
starting_number += 1 #If not consecutive, add number to number of mcnuggets and run Diophantine function again #If the sum was not equal to the length (i.e. the differences were NOT all 1) the input is increased by 1 and the program repeats.
Diophantine(starting_number)
else: print 'The largest number of Mcnuggets that cannot be bought in exact quanity is > 200, but so far it is: ', unsolvable[-1]
Diophantine(1)