Question

Help with PS2 nuggets code?

Answer 1

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)

Answer 2

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.

Answer 3

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

Answer 4

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!

Answer 5

Hi~
I am also having problems with pset2. I have no idea why the theorem in Problem 2 is true. Is it mathematics?

Answer 6

@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?

Answer 7

Okay, I get it now. Thanks very much!