[ create a new paste ] login | about

Link: http://codepad.org/BHYqzQG8    [ raw code | output | fork ]

morgkl6 - Python, pasted on Jan 17:
#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)


Output:
1
The Largest number of McNuggets that cannot be bought in exact quantity is: 43


Create a new paste based on this one


Comments: