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

John Posner jjposner at optimum.net
Thu Aug 12 22:51:05 CEST 2010

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

```