Re: looping through possible combinations of McNuggets packs of 6,9 and 20
On Aug 12, 4:33 am, Paul Rubin no.em...@nospam.invalid wrote: Baba raoul...@gmail.com writes: 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. If I recall, this was a puzzler on the NPR radio show Car Talk. Still might be homework, though. -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6,9 and 20
SPOILER ALTER: THIS POST CONTAINS A POSSIBLE SOLUTION On 08/12/10 21:41, News123 wrote: 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 was aware of that, thats whhy I wrote: or any combination of 6, 9, 20 I guess, trying to find the result with divisions and remainders is overly complicated. Python 2.6.4 (r264:75706, Jul 1 2010, 12:52:41) [GCC 4.2.1 20070719 [FreeBSD]] on freebsd8 Type help, copyright, credits or license for more information. MODULO_COMBINATIONS = [[20], [9], [6], ...[20, 9], [20, 6], [9, 20], ...[9, 6], [6, 20], [6, 9], ...[20, 9, 6], [20, 6, 9], [9, 20, 6], ...[9, 6, 20], [6, 20, 9], [6, 9, 20]] def apply_combinations_on(number): ... tmp = list() ... for combination in MODULO_COMBINATIONS: ... remainder = number ... for modulo_value in combination: ... if remainder == 0: ... remainder = None ... break ... ... result = remainder % modulo_value ... ... if result == remainder : ... remainder = None ... break ... ... remainder = result ... ... if remainder == 0: ... tmp.append(str(combination)) ... return(tmp) ... print(apply_combinations_on(15)) ['[9, 6]'] What is so over complicated about it? -- mph -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6,9 and 20
On 08/13/10 10:46, Peter Otten wrote: Martin P. Hellwig wrote: SPOILER ALTER: THIS POST CONTAINS A POSSIBLE SOLUTION No it wasn't :-) which should be 1*9 + 2*6 What am I missing? Aah interesting, 21 % 9 returns 3 instead of 12, which makes sense of course. I guess the algorithm has to be adapted in a way that if the value is bigger or equal twice the size of the modulo value you need to iterate over it, something like: for minus_multiplier in range(1, int(number, modulo_value)+2): number = number - (modulo_value * minus_multiplier) do the rest of the loop Probably another ten lines or so to make it working as it should -- mph -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6,9 and 20
Martin P. Hellwig wrote: On 08/13/10 10:46, Peter Otten wrote: Martin P. Hellwig wrote: SPOILER ALTER: THIS POST CONTAINS A POSSIBLE SOLUTION No it wasn't :-) which should be 1*9 + 2*6 What am I missing? Aah interesting, 21 % 9 returns 3 instead of 12, which makes sense of course. I guess the algorithm has to be adapted in a way that if the value is bigger or equal twice the size of the modulo value you need to iterate over it, something like: for minus_multiplier in range(1, int(number, modulo_value)+2): number = number - (modulo_value * minus_multiplier) do the rest of the loop Probably another ten lines or so to make it working as it should I don't understand what you're trying to do. My solution would be: def can_buy(nuggets): for packs_20 in range(nuggets // 20, -1, -1): remaining_20 = nuggets - 20 * packs_20 for packs_9 in range(remaining_20 // 9, -1, -1): remaining_9 = remaining_20 - 9 * packs_9 if remaining_9 % 6 == 0: packs_6 = remaining_9 // 6 return [packs_6, packs_9, packs_20] return [] -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6,9 and 20
On 08/13/2010 10:57 AM, Martin P. Hellwig wrote: SPOILER ALTER: THIS POST CONTAINS A POSSIBLE SOLUTION On 08/12/10 21:41, News123 wrote: 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 was aware of that, thats whhy I wrote: or any combination of 6, 9, 20 I guess, trying to find the result with divisions and remainders is overly complicated. Python 2.6.4 (r264:75706, Jul 1 2010, 12:52:41) [GCC 4.2.1 20070719 [FreeBSD]] on freebsd8 Type help, copyright, credits or license for more information. MODULO_COMBINATIONS = [[20], [9], [6], ...[20, 9], [20, 6], [9, 20], ...[9, 6], [6, 20], [6, 9], ...[20, 9, 6], [20, 6, 9], [9, 20, 6], ...[9, 6, 20], [6, 20, 9], [6, 9, 20]] def apply_combinations_on(number): ... tmp = list() ... for combination in MODULO_COMBINATIONS: ... remainder = number ... for modulo_value in combination: ... if remainder == 0: ... remainder = None ... break ... ... result = remainder % modulo_value ... ... if result == remainder : ... remainder = None ... break ... ... remainder = result ... ... if remainder == 0: ... tmp.append(str(combination)) ... return(tmp) ... print(apply_combinations_on(15)) ['[9, 6]'] What is so over complicated about it? What I meant with complicated is your mathematical assumption about modulos, which are probably not obvious to everybody on the first glance. Saying, that you can find out, whether for integers a,b.c,n the equation n = a*6 + b*9 + c*20 is true by verifying whether n mod 6 == 0 or n mod 9 == 0 or (n mod 6) mod 9 == 0 or (n mod 9) mod 6 == 0 Trial error is not so smart, but much easier to explain to beginners. One can even return a,b,c for verification. Being a little (and incrementally) smart, the search space can then be reduced by some degrees with rather easy to explain and incremental assumptions, For given example the run times are so short, that it's not really an issue. Another advantage of brute force is, that you can return a,b,c and not only say, whether a,b,c exist. This allows simple verification or assertions during debugging and learning. # plain brute force. # def can_buy(n_nuggets): for a in range (n_nuggets): for b in range (n_nuggets): for c in range (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) return () # brute force but reduce the upper limit for each loop by saying, # that one can stop if one a*6 n or b*9 n or c*20 n #-- def can_buy(n_nuggets): for a in range (n_nuggets / 6 + 1): for b in range (n_nuggets / 9 + 1): for c in range (n_nuggets / 20 + 1): print trying for %2d: %2d %2d %2d % (n,a,b,c) if 6*a + 9*b + 20*c == n_nuggets: return (a,b,c) return () # as above code, but try even less in inner loops by # removing what has been taken in outer loop # def can_buy(n_nuggets): for a in range (1, n_nuggets / 6 + 1): left_6 = n)nuggets - a * 6 for b in range (1, left_6 / 9 + 1): left_9 = left_6 - b * 9 for c in range (1, left_9/ 20 + 1): print trying for %2d: %2d %2d %2d % (n,a,b,c) if 6*a+9*b+20*c==n_nuggets: return (a,b,c) return () # as above code, but do less multiplications # in inner loop #--- def can_buy(n_nuggets): for a in range (1, n_nuggets / 6 + 1): left_6 = n)nuggets - a * 6 for b in range (1, left_6 / 9 + 1): left_9 = left_6 - b * 9 for c in range (1, left_9/ 20 + 1): print trying for %2d: %2d %2d %2d % (n,a,b,c) if 20*c == left_9: return (a,b,c) return () # as above code, but use modulo in inner loop # -- def can_buy(n_nuggets): for a in range (1, n_nuggets / 6 + 1): left_6 = n)nuggets - a * 6 for b in range (1, left_6 / 9 + 1): left_9 = left_6 - b * 9 print trying for %2d: %2d %2d c % (n,a,b) if left_9
Re: looping through possible combinations of McNuggets packs of 6,9 and 20
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. -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6,9 and 20
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. 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! :-) -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6,9 and 20
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6,9 and 20
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6,9 and 20
Baba wrote: 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. -- Brian -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6,9 and 20
Baba wrote: 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6,9 and 20
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6,9 and 20
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. -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6,9 and 20
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6,9 and 20
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. Unhelpfully yours, -- Steven -- http://mail.python.org/mailman/listinfo/python-list
