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

[Dave Angel]

Roald de Vries wrote:
> <div class="moz-text-flowed" style="font-family: -moz-fixed">On Aug 
> 12, 2010, at 11:33 AM, Paul Rubin wrote:
>> Baba <raoulbia at 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.
>
> Good point. There is actually an upper bound. Let's take 6 packs of 
> 20, that's 120 nuggets.
> Now 121 nuggets can be reached by substituting 1 pack of 20 with 2 
> packs of 6 and 1 pack of 9.
> 122 = 4*20 + 2*(2*6+9)
> 123 = 3*20 + 3*(2*6+9)
> ...
> 126 = 6*20 + 6
> 127 = 121 + 6 = 5*20 + (2*6 + 9) + 6
> ... etcetera.
>
> Now you have to find the largest number below 120, which you can 
> easily do with brute force (untested):
>
> can_be_bought = [False for i in range(120)]
> for twenties in range(6):
>     for nines in range(14):
>         for sixes in range(20):
>             can_be_bought[twenties*20+nines*9+sixes*6] = True
> for i in reverse(range(120)):
>     if not can_be_bought[i]: return i
>
> Cheers, Roald
>
for i in reverse(range(120)):
    if not can_be_bought[i]: return i

can probably be replaced by (untested):

return len(can_be_bought) - reverse(can_be_bought).index(False) - 1

DaveA