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

[Ian Kelly]

On Sat, Aug 14, 2010 at 8:52 AM, Baba <raoulbia at gmail.com> wrote:
> my code is probably not elegant but a huge step forward from where i
> started:
>
> def can_buy(n_nuggets):
>   for a in range (0,n_nuggets):
>       for b in range (0,n_nuggets):
>           for c in range (0,n_nuggets):
>               #print "trying for %d: %d %d %d" % (n_nuggets,a,b,c)
>               if 6*a+9*b+20*c==n_nuggets:
>                   return [a,b,c]
>   return []
>
> for n_nuggets in range(50):
>    result1 = can_buy(n_nuggets)
>    result2 = can_buy(n_nuggets+1)
>    result3 = can_buy(n_nuggets+2)
>    result4 = can_buy(n_nuggets+3)
>    result5 = can_buy(n_nuggets+4)
>    result6 = can_buy(n_nuggets+5)
>    if result1!=[] and result2!=[] and result3!=[] and result4!=[] and
> result5!=[] and result6!=[]:
>     if (n_nuggets+5)-n_nuggets==5:
>        print n_nuggets-1
>        break
>
> i suppose this can be tweaked to make it shorter? For instance i
> wonder if i can do the same with less variable to be defined?

Instead of calling can_buy() 6 times on every iteration of the main
loop, I would suggest maintaining a list of the sequential results.
Just call it once on each number of nuggets in order.  If the number
of nuggets is purchasable, and the list is empty or the last item in
the list is the number of nuggets - 1, then append the number of
nuggets to the list.  If the last item in the list is not the number
of nuggets - 1, then they're not sequential and you start a new list.
When the length of the list reaches 6, you're done, and the answer is
equal to the first item in the list - 1.

You can also improve the can_buy() function by tightening up the loop
limits.  You don't need to go all the way up to n_nuggets on each
loop.