# looping through possible combinations of McNuggets packs of 6,9 and 20

News123 news1234 at free.fr
Fri Aug 13 23:02:52 CEST 2010

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

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.
#------------------------------------
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
#------------------------------------------
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
#--------------------------------------------
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
#-------------------------------------------
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
# ------------------------------------------
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 ()

```