Help with PS2 nuggets code?
Any constructive comments welcome! Here's what I'm working with: ## PS2: 'Can't buy me nuggets' def solve (nuggets): """ Find the largest number of nuggets that cannot be purchased in some combination of 6-, 9-, or 20-packs. """ solutionFound = False maxImpossible =  #List to hold the 'impossible' numbers of nuggets. for numSixes in range (0, (nuggets/6) + 1): #Iterate over 6-packs for numNines in range (0, (nuggets/9) + 1): #Iterate over 9-packs #Calculate 20-packs numTwenties = (nuggets - 6*numSixes - 9*numNines)/20 #Calculate total nuggets with this combination totNuggets = 6*numSixes + 9*numNines + 20*numTwenties #Test against the given number of nuggets if totNuggets == nuggets: solutionFound = True elif not solutionFound: #Add this value of nuggets to the list, sort, #and print the largest value in the list. maxImpossible.append (nuggets) sort (maxImpossible) print maxImpossible [-1] for nuggets in range (1, 151): solve (nuggets)
I'm leaving for work in a few minutes, so this isn't as comprehensive as I'd like, but I might be around later today to help. For now, take a look at this section elif not solutionFound: #Add this value of nuggets to the list, sort, #and print the largest value in the list. maxImpossible.append (nuggets) print maxImpossible [-1] There are two things to notice about it. First, it's going to test every single combination of sizes when it's looking for a specific number of nuggets. For instance, I know I can get 35 nuggets (20 + 6 + 9). But what happens when I'm testing 35 in this section of the program in the first iteration, when numSixes = 0, numNines = 0, and numTwenties = 1? I also think you're going to want to move the 'first' statements for nuggets in range (1, 151): solve (nuggets) into the solve function. As it's written, those lines feed numbers of nuggets into the 'solve' function one at a time, and because the definition of maxImpossible is local to the solve function, it gets reset to the empty list every time the funtion is called. Also, a list is indexed, so the sort is unnecessary, I think. It was causing an error when I tried to run it, so I took it out. And as it is, there can only ever be one number in maxImpossible, even if it's repeated in that list.
def solve(a,b,c,n): total=6*a + 9*b + 20*c if total==n: return 1 else: return 0 def brute(n): q=0 for a in range (0,n+1): for b in range (0,n+1): for c in range (0,n+1): hyp=solve(a,b,c,n) q=q+hyp if q>=1: return 1 else: return 0 n=0 counter=0 while not counter==6: n=n+1 coun=brute(n) if coun==0: counter = 0 m=n else: counter=counter+coun print "Largest number of McNuggets that cannot be bought in exact quantity: ",m
Thank you both! All comments were helpful, especially with the structure issues (what goes where - my usual trouble) and seeing that I needed a second function as well as this little gem to make it stop in the right place: while not counter == 6:. Cheers!
Hi~ I am also having problems with pset2. I have no idea why the theorem in Problem 2 is true. Is it mathematics?
@de_void: If you have the solution to 50 just add a 6-pack to get 56. If you have it for 51 just add a 6-pack to get 57. So if you have a 'run' of purchasable combinations the length of the smallest pack, (in this case, 50-55) then from then on you can buy anything. Does that make any sense?
Okay, I get it now. Thanks very much!