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

[News123]

On 08/12/2010 10:51 PM, John Posner wrote:
> 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),
>     )

Couldn't this be rewritten as:
    candidate_box_counts = product(
	 * [ xrange(target/sizes + 1) for size in box_sizes ]
     )

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