looping through possible combinations of McNuggets packs of 6,9and 20
in [Python]
|
Prev: looping through possible combinations of McNuggets packs of 6,9 and 20
Next: cx_Oracle 5.0.4 + Python 3.1.2 + Oracle Instant Client 10.2.04; DLL Load failed on import (Win/NT)
From: News123 on 11 Aug 2010 16:48 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. On 08/11/2010 10:14 PM, Baba wrote: > 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/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-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 > for a in range (0,10): > for b in range (0,10): > for c in range (0,10): # c used here and lso as counter > sol=6*a+9*b+20*c > if sol!=n: > c+=1 > if c==6: > print "solution is",sol-6 >
From: News123 on 12 Aug 2010 03:39 Hi Steven, On 08/12/2010 01:37 AM, Steven D'Aprano wrote: > On Wed, 11 Aug 2010 13:14:35 -0700, Baba wrote: > >> 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. You CAN buy that many Nuggets. You just need the money and of course you have to wait a little until they are ready.
From: News123 on 12 Aug 2010 04:24 On 08/11/2010 10:14 PM, Baba wrote: > 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/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-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
From: Martin P. Hellwig on 12 Aug 2010 15:56 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. -- mph
From: News123 on 12 Aug 2010 16:41
On 08/12/2010 09:56 PM, Martin P. Hellwig wrote: > 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. |