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: Martin P. Hellwig on 13 Aug 2010 04:57 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
From: Martin P. Hellwig on 13 Aug 2010 06:51 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
From: MRAB on 13 Aug 2010 13:57 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 []
From: News123 on 13 Aug 2010 17:02
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 % 20 == 0: return (a,b,left_9/20) return () |