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

[News123]

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