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

[John Posner]

On 8/12/2010 9:22 AM, Dave Angel wrote:
>>
>> Now you have to find the largest number below 120, which you can
>> easily do with brute force

Dept of overkill, iterators/generators division ...

-John

#------------------
from itertools import imap, product, ifilter
from operator import mul

box_sizes = (6, 9, 20)

def sum_product(s1, s2):
     """
     return "scalar product" of two sequences
     """
     return sum(imap(mul, s1, s2))

def reachables(target):
     """
     return generator of numbers that are <= target
     and are valid linear combos of McNuggets
     """
     candidate_box_counts = product(
         xrange(target/box_sizes[0] + 1),
         xrange(target/box_sizes[1] + 1),
         xrange(target/box_sizes[2] + 1),
     )

     gen = (sum_product(box_sizes, tup)
               for tup in candidate_box_counts)

     return (ifilter(lambda val, tgt=target: val < tgt,
                     gen))

if __name__ == "__main__":
     tgt = 120 # thanks, Dave Angel
     unreachables = set(xrange(tgt)) - set(reachables(tgt))
     print "Max unreachable:", max(unreachables)