looping through possible combinations of McNuggets packs of 6,9 and 20
in [Python]
|
Prev: looping through possible combinations of McNuggets packs of 6,9 and 20
Next: cx_Oracle 5.0.4 + Python 3.1.2 + Oracle Instant Client10.2.04; DLL Load failed on import (Win/NT)
From: Paul Rubin on 12 Aug 2010 05:33 Baba <raoulbia(a)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.
From: Roald de Vries on 12 Aug 2010 07:04 On Aug 12, 2010, at 11:33 AM, Paul Rubin wrote: > Baba <raoulbia(a)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
From: Dave Angel on 12 Aug 2010 09:22 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(a)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
From: John Posner on 12 Aug 2010 16:51 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)
From: News123 on 12 Aug 2010 18:31
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) |