Problem Set 2

[elz]

Post and discuss your answers in the comments! (And yay for everybody who posted problem set 1 answers!)

Comments

Problem 3

[yhlee]

I'm pretty sure this is ugly and I know it's inefficient, but they asked for exhaustive search...

# Solving a Diophantine Equation.

# Helper function
def consecutiveValues(n1, n2, n3, n4, n5, n6):
	value = (n1 + 1 == n2) and (n2 + 1 == n3) and (n3 + 1 == n4) and (n4 + 1 == n5) and (n5 + 1 == n6)
	return value

# Helper function
def nuggetsTest(n):
	answer = False
	for a in range(0,11):
		for b in range(0,11):
			for c in range(0,11):
				if (a*6 + b*9 + c*20) == n:
					return True
	return answer

def mcnuggets():
	# Possible instance of number of McNuggets that cannot be purchased
	# exactly.
	n = 1

	# Stores successful values of n.
	successful_n = [0,0,0,0,0,0]

	# Stores failed values of n.
	failed_n = [0]

	# We already know from Problem 1 that 50, 51, ..., 55 (and all
	# instances thereafter) have exact solutions.  So let's set an
	# upper bound for a, b, and c as 10, which should catch all
	# feasible possibilities for each variable (6*10 = 60).

	while consecutiveValues(successful_n[-6], successful_n[-5], successful_n[-4], successful_n[-3], successful_n[-2], successful_n[-1]) == False:
		if nuggetsTest(n) == True:
			successful_n = successful_n + [n]
			print n
		else:
			failed_n = failed_n + [n]
		n = n + 1

	print "Largest number of McNuggets that cannot be bought in exact quantity: " + str(failed_n[-1])