looping through possible combinations of McNuggets packs of 6,9 and20

[Baba]

level: beginner

exercise: given that packs of McNuggets can only be bought in 6, 9 or
20 packs, write an exhaustive search to find the largest number of
McNuggets that cannot be bought in exact quantity.

exercise source:
http://ocw.mit.edu/courses/electric...d-programming-fall-2008/assignments/pset2.pdf

please help me write this code

i believe it's something along the lines of this:

c=0
sol=[]
for n in range (0,10):
for a in range (0,10):
for b in range (0,10):
for c in range (0,10):
sol=6*a+9*b+20*c
if sol!=n:
c+=1
if c==6:
print sol

 

[News123]

As said in the instructions.

if you find six consecutive numbers, that can be bough in exact
quantity, then you know, that all bigger numbers can also be bought in
exact quantity.


I would do a brute force approach


first I would create one function, which will try to find out, whether
one can buy an exact quantity of n nuggets.


example function prototype


def can_buy(n_nuggets):
# here you have to write your code


the function should return True or if you're curious a list of packages
and quantities if quantity n_nuggets can be bought

otherwise it should return False or an empty list.



then you can create another function which will start with 6 nuggets (or
if you like to with 1 nugget)
and which will count how many times in sequence it managed to return a
result. (by using the function can_buy() and managibng a counter)

If it found 6 results in sequence, then you know, that all bigger
numbers can also be bought and that the biggest number, which could not
be bought was 6 numbers before.

I think nobody here will write the soultion for you.

If you write some more code and if you tell us what it's supposed to to
and with what exectly you're having trouble with I can give you more hints.

level: beginner

exercise: given that packs of McNuggets can only be bought in 6, 9 or
20 packs, write an exhaustive search to find the largest number of
McNuggets that cannot be bought in exact quantity.

exercise source:
http://ocw.mit.edu/courses/electric...d-programming-fall-2008/assignments/pset2.pdf

please help me write this code

i believe it's something along the lines of this:

c=0
sol=[]
for n in range (0,10):
for a in range (0,10):
for b in range (0,10):
for c in range (0,10):
sol=6*a+9*b+20*c
if sol!=n:
c+=1
if c==6:
print sol

Not very modular.

c=0 # c could have a meaningful name and probably a different one
# it seems, that you reuse c also in a for statement
sol=[]
for n in range (0,10): # n should not only go from 0 to 10
# but from 0 until c is 6

# i'd put this in a separate function it makes it also easier for
# you to understand and test

 

[Thomas Jollans]

level: beginner

exercise: given that packs of McNuggets can only be bought in 6, 9 or
20 packs, write an exhaustive search to find the largest number of
McNuggets that cannot be bought in exact quantity.

The MacDonald's at Nuremberg central station once sold me 25 in a 20-pack. So
this won't work.

exercise source:
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00
-introduction-to-computer-science-and-programming-fall-2008/assignments/pse
t2.pdf

please help me write this code

i believe it's something along the lines of this:

c=0
sol=[]
for n in range (0,10):
for a in range (0,10):
for b in range (0,10):
for c in range (0,10):
sol=6*a+9*b+20*c
if sol!=n:
c+=1
if c==6:
print sol

 

[Steven D'Aprano]

level: beginner

exercise: given that packs of McNuggets can only be bought in 6, 9 or 20
packs, write an exhaustive search to find the largest number of
McNuggets that cannot be bought in exact quantity.

Is this a trick question?

I'd like to see somebody try to buy exactly 10**100**100 (1 googleplex)
McNuggets. And that's not even close to the largest number that you can't
buy.


Unhelpfully yours,

 

[MRAB]

Is this a trick question?

I'd like to see somebody try to buy exactly 10**100**100 (1 googleplex)
McNuggets. And that's not even close to the largest number that you can't
buy.

If you'd looked at the link then you would've seen that it's
mathematically possible.

But then I expect you have a life!

 

[News123]

Hi Steven,

Is this a trick question?

I'd like to see somebody try to buy exactly 10**100**100 (1 googleplex)
McNuggets. And that's not even close to the largest number that you can't
buy.

You CAN buy that many Nuggets.

You just need the money and of course you have to wait a little until
they are ready.

 

[News123]

level: beginner

exercise: given that packs of McNuggets can only be bought in 6, 9 or
20 packs, write an exhaustive search to find the largest number of
McNuggets that cannot be bought in exact quantity.

exercise source:
http://ocw.mit.edu/courses/electric...d-programming-fall-2008/assignments/pset2.pdf

please help me write this code

i believe it's something along the lines of this:

c=0
sol=[]
for n in range (0,10):
for a in range (0,10):
for b in range (0,10):
for c in range (0,10):
sol=6*a+9*b+20*c
if sol!=n:
c+=1
if c==6:
print sol

If you're interested in more, than just finishing the exercise, then you
should post your solution even if you have it already and read about all
the tips how to make it faster or shorter or more readable

 

[Jean-Michel Pichavant]

level: beginner

exercise: given that packs of McNuggets can only be bought in 6, 9 or
20 packs, write an exhaustive search to find the largest number of
McNuggets that cannot be bought in exact quantity.

exercise source:
http://ocw.mit.edu/courses/electric...d-programming-fall-2008/assignments/pset2.pdf

please help me write this code

i believe it's something along the lines of this:

c=0
sol=[]
for n in range (0,10):
for a in range (0,10):
for b in range (0,10):
for c in range (0,10):
sol=6*a+9*b+20*c
if sol!=n:
c+=1
if c==6:
print sol

for mcNugget in range(0,10):
sendTo(trashbin)

You're welcome

JM

 

[Paul Rubin]

exercise: given that packs of McNuggets can only be bought in 6, 9 or
20 packs, write an exhaustive search to find the largest number of
McNuggets that cannot be bought in exact quantity.

Is that a homework problem? Hint: first convince yourself that a
largest number actually exists.

 

[Roald de Vries]

Is that a homework problem? Hint: first convince yourself that a
largest number actually exists.

Good point. There is actually an upper bound. Let's take 6 packs of
20, that's 120 nuggets.
Now 121 nuggets can be reached by substituting 1 pack of 20 with 2
packs of 6 and 1 pack of 9.
122 = 4*20 + 2*(2*6+9)
123 = 3*20 + 3*(2*6+9)
....
126 = 6*20 + 6
127 = 121 + 6 = 5*20 + (2*6 + 9) + 6
.... etcetera.

Now you have to find the largest number below 120, which you can
easily do with brute force (untested):

can_be_bought = [False for i in range(120)]
for twenties in range(6):
for nines in range(14):
for sixes in range(20):
can_be_bought[twenties*20+nines*9+sixes*6] = True
for i in reverse(range(120)):
if not can_be_bought: return i

Cheers, Roald

 

[Dave Angel]

<div class="moz-text-flowed" style="font-family: -moz-fixed">On Aug

Is that a homework problem? Hint: first convince yourself that a
largest number actually exists.

Good point. There is actually an upper bound. Let's take 6 packs of
20, that's 120 nuggets.
Now 121 nuggets can be reached by substituting 1 pack of 20 with 2
packs of 6 and 1 pack of 9.
122 = 4*20 + 2*(2*6+9)
123 = 3*20 + 3*(2*6+9)
...
126 = 6*20 + 6
127 = 121 + 6 = 5*20 + (2*6 + 9) + 6
... etcetera.

Now you have to find the largest number below 120, which you can
easily do with brute force (untested):

can_be_bought = [False for i in range(120)]
for twenties in range(6):
for nines in range(14):
for sixes in range(20):
can_be_bought[twenties*20+nines*9+sixes*6] = True
for i in reverse(range(120)):
if not can_be_bought: return i

Cheers, Roald

for i in reverse(range(120)):
if not can_be_bought: return i

can probably be replaced by (untested):

return len(can_be_bought) - reverse(can_be_bought).index(False) - 1

DaveA

 

[Baba]

Hi News123

Thank You for helping me out. Indeed i am not looking for the code but
rather for hints that direct my reasoning as well as hints as to how
to write basic programs like this.

You have broken down the approach into 2 parts. I have tried to solve
part 1 but i'm not quite there yet. Here's my code:

def can_buy(n_nuggets):
for a in range (1,n_nuggets):
for b in range (1,n_nuggets):
for c in range (1,n_nuggets):
if 6*a+9*b+20*c==n_nuggets:
#print a,b,c,'n_nuggets=',n_nuggets
return True
else:
return False


can_buy(55)

as you can see i am trying to loop through all combinations of values
bewtween 1 and n_nuggets and when the equation resolves it should
return True, else it should return False.

I was hoping that when i then call my function and ask it to test a
value nothing happens. What is wrong? My syntax? My semantic? Both?

tnx
Baba

 

[Brian Victor]

def can_buy(n_nuggets): [snip]
can_buy(55)

as you can see i am trying to loop through all combinations of values
bewtween 1 and n_nuggets and when the equation resolves it should
return True, else it should return False.

I was hoping that when i then call my function and ask it to test a
value nothing happens. What is wrong? My syntax? My semantic? Both?

You're calling the function, but you're not doing anything with the
result. If you use "print can_buy(55)" you'll see the result on the
console. Presumably you'll actually want to use it in an if statement.

 

[Peter Otten]

Baba wrote:

Thank You for helping me out. Indeed i am not looking for the code but
rather for hints that direct my reasoning as well as hints as to how
to write basic programs like this.

You have broken down the approach into 2 parts. I have tried to solve
part 1 but i'm not quite there yet. Here's my code:

def can_buy(n_nuggets):
for a in range (1,n_nuggets):
for b in range (1,n_nuggets):
for c in range (1,n_nuggets):
if 6*a+9*b+20*c==n_nuggets:
#print a,b,c,'n_nuggets=',n_nuggets
return True
else:
return False


can_buy(55)

as you can see i am trying to loop through all combinations of values
bewtween 1 and n_nuggets and when the equation resolves it should
return True, else it should return False.

I was hoping that when i then call my function and ask it to test a
value nothing happens. What is wrong? My syntax? My semantic? Both?

First, the function gives up too early; it should only return False when all
combinations of a, b, c (technically: the product of the ranges) have been
tried.

Second, can_buy(0) should return True, but the solution 0*6 + 0*9 + 0*20 is
never tried; fix your ranges accordingly.

Peter

 

[MRAB]

Hi News123

Thank You for helping me out. Indeed i am not looking for the code but
rather for hints that direct my reasoning as well as hints as to how
to write basic programs like this.

You have broken down the approach into 2 parts. I have tried to solve
part 1 but i'm not quite there yet. Here's my code:

def can_buy(n_nuggets):
for a in range (1,n_nuggets):
for b in range (1,n_nuggets):
for c in range (1,n_nuggets):
if 6*a+9*b+20*c==n_nuggets:
#print a,b,c,'n_nuggets=',n_nuggets
return True
else:
return False


can_buy(55)

as you can see i am trying to loop through all combinations of values
bewtween 1 and n_nuggets and when the equation resolves it should
return True, else it should return False.

I was hoping that when i then call my function and ask it to test a
value nothing happens. What is wrong? My syntax? My semantic? Both?

Think about it this way.

How many packs of 20 would you need? You don't want too many, but too
few is OK.

Then, how many packs of 9 for the remaining nuggets? (Again, you don't
want too many.)

Then, how many packs of 6?

If all the nuggets are accounted for, good, otherwise reduce the number
of one of the packs and try again. Repeat as necessary.

A couple of 'for' loops will do it.

 

[Roald de Vries]

Baba wrote:



First, the function gives up too early; it should only return False
when all
combinations of a, b, c (technically: the product of the ranges)
have been
tried.

Second, can_buy(0) should return True, but the solution 0*6 + 0*9 +
0*20 is
never tried; fix your ranges accordingly.

Moreover: a, b and c can range over n_nuggets/6, n_nuggets/9 and
n_nuggets/20 respectively. This will work, but does too much work.

Cheers, Roald

 

[Martin P. Hellwig]

On 08/11/10 21:14, Baba wrote:
<cut>

How about rephrasing that question in your mind first, i.e.:

For every number that is one higher then the previous one*:
If this number is dividable by:
6 or 9 or 20 or any combination of 6, 9, 20
than this number _can_ be bought in an exact number
else
print this number

* There are an infinite amount of numbers, just imagine the biggest
number you can think of and I say plus 1


Next thing you have to do is figure out how to write this in python,
particularly getting all the combinations of divisions can be tricky.
Hint; you are not really interested in the division result but rather if
a division would be complete or give a remainder (modulo operator).
If you get an remainder this could be okay if that can divided by one of
the other numbers, and so forth till you ran out of combinations.

 

[News123]

Hi Baba,

The last tips should really help you getting started:

for testing your function you could do:

Below your uncorrected code and a test for it

def can_buy(n_nuggets):
for a in range (1,n_nuggets):
for b in range (1,n_nuggets):
for c in range (1,n_nuggets):
print "trying for %2d: %2d %2d %2d" % (n,a,b,c)
if 6*a+9*b+20*c==n_nuggets:
return True
else:
return False

# show the results for the first 50 numbers.
for n in xrange(50):
result = can_buy(n) # get the result (see Brian's comment)
print("result of can_buy(%2d) is %s" % (n,result))


with the print statement in can_buy() you should immediately see some
issues.
as soon as can_buy seems to work, you could comment the print statement.


Additionally:
I would return [a,b,c] if you got a result
and [] if you got no result.

So you don't only seem whether you can buy n nuggets, but you can also
see how (AND even verify the solution)


the print statement should show you what Peter said.
You just make one test and return immediately in the else statement

Instead you should continue until you found a solution or until you
tried all possibilities.

After having fixed the fact, that you don't try all options, you'll see
that your first success would be with 6+9+12 = 27 nuggets es you never
try with 0 boxes of a kind. (as Peter mentioned)

Finally as Roald says.

if you can reduce the upper limit of your search ranges.
if you have for example 13 nuggets you do not have to try 3 boxes of 6
as this is already 18, so trying only 0,1 or two boxes is enough







You will now also see, what

 

[News123]

One more small tip to verify whether your code is working:

Hi Baba,

Your code, but returning the result as suggested in my preious post:

def can_buy(n_nuggets):
for a in range (1,n_nuggets):
for b in range (1,n_nuggets):
for c in range (1,n_nuggets):
print "trying for %2d: %2d %2d %2d" % (n,a,b,c)
if 6*a+9*b+20*c==n_nuggets:
return [a,b,c]
else:
return []

# show the results for the first 50 numbers.
# and verify whether it's true

for n in xrange(50):
result = can_buy(n) # get the result (see Brian's commen
print("result of can_buy(%2d) is %s" % (n,result))
if result:
a,b,c = result
if a*6+b*9+c*12 != n:
print "ERROR: can_buy() gives wrong result"

Alternatively you can use a nice python feature called asserts

assert statements can be used to vrify whether your code works as expected.
Nothing will be printed if the assertion is correct otherwise your
program will abort and print the assertion error:


Example:
for n in xrange(50):
result = can_buy(n) # get the result (see Brian's commen
print("result of can_buy(%2d) is %s" % (n,result))
if result:
a,b,c = result
assert a*6+b*9+c*12 == n

with the print statement in can_buy() you should immediately see some
issues.
as soon as can_buy seems to work, you could comment the print statement.


Additionally:
I would return [a,b,c] if you got a result
and [] if you got no result.

So you don't only seem whether you can buy n nuggets, but you can also
see how (AND even verify the solution)


the print statement should show you what Peter said.
You just make one test and return immediately in the else statement

Instead you should continue until you found a solution or until you
tried all possibilities.

After having fixed the fact, that you don't try all options, you'll see
that your first success would be with 6+9+12 = 27 nuggets es you never
try with 0 boxes of a kind. (as Peter mentioned)

Finally as Roald says.

if you can reduce the upper limit of your search ranges.
if you have for example 13 nuggets you do not have to try 3 boxes of 6
as this is already 18, so trying only 0,1 or two boxes is enough







You will now also see, what

Moreover: a, b and c can range over n_nuggets/6, n_nuggets/9 and
n_nuggets/20 respectively. This will work, but does too much work.

Cheers, Roald

 

[News123]

On 08/11/10 21:14, Baba wrote:
<cut>

How about rephrasing that question in your mind first, i.e.:

For every number that is one higher then the previous one*:
If this number is dividable by:
6 or 9 or 20 or any combination of 6, 9, 20
than this number _can_ be bought in an exact number
else
print this number

you are allowed to mix.
15 is neither divisable by 6 nor by nine, but 9 + 6 = 15

I guess, trying to find the result with divisions and remainders is
overly complicated.

Simple brute force trial to find a combination shall be enough.

Also:


if you know for example,
that you can buy 101,102,103,104,105 and 106 nuggets,
then you know, that you can buy any other larger amout of nuggets.

107 = 101 + one box of six
108 = 102 + one box of six
.. . .

As soon as you found 6 sequential solutions you can stop searching.