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: John Posner on 12 Aug 2010 22:26 On 8/12/2010 6:31 PM, News123 wrote: >> 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 ] > ) > Sure (except for the typo: "sizes" should be "size"). You could even use a generator expression instead of a list comprehension: candidate_box_counts = product( * ( xrange(target/size + 1) for size in box_sizes ) ) -John
From: Peter Otten on 13 Aug 2010 05:46 Martin P. Hellwig wrote: > SPOILER ALTER: THIS POST CONTAINS A POSSIBLE SOLUTION > > On 08/12/10 21:41, News123 wrote: > >> On 08/12/2010 09:56 PM, Martin P. Hellwig wrote: >>> On 08/11/10 21:14, Baba wrote: >>> <cut> >>> >>> How about rephrasing that question in your mind first, i.e.: >>> >>> For every number that is one higher then the previous one*: >>> If this number is dividable by: >>> 6 or 9 or 20 or any combination of 6, 9, 20 >>> than this number _can_ be bought in an exact number >>> else >>> print this number >>> >> >> you are allowed to mix. >> 15 is neither divisable by 6 nor by nine, but 9 + 6 = 15 > > I was aware of that, thats whhy I wrote: > "or any combination of 6, 9, 20" > >> >> I guess, trying to find the result with divisions and remainders is >> overly complicated. > > Python 2.6.4 (r264:75706, Jul 1 2010, 12:52:41) > [GCC 4.2.1 20070719 [FreeBSD]] on freebsd8 > Type "help", "copyright", "credits" or "license" for more information. > >>> MODULO_COMBINATIONS = [[20], [9], [6], > ... [20, 9], [20, 6], [9, 20], > ... [9, 6], [6, 20], [6, 9], > ... [20, 9, 6], [20, 6, 9], [9, 20, 6], > ... [9, 6, 20], [6, 20, 9], [6, 9, 20]] > >>> > >>> def apply_combinations_on(number): > ... tmp = list() > ... for combination in MODULO_COMBINATIONS: > ... remainder = number > ... for modulo_value in combination: > ... if remainder == 0: > ... remainder = None > ... break > ... > ... result = remainder % modulo_value > ... > ... if result == remainder : > ... remainder = None > ... break > ... > ... remainder = result > ... > ... if remainder == 0: > ... tmp.append(str(combination)) > ... return(tmp) > ... > >>> print(apply_combinations_on(15)) > ['[9, 6]'] > >>> > > What is so over complicated about it? > Well, it was hard enough for me to run the code rather than just read it. I get >>> apply_combinations_on(21) [] which should be 1*9 + 2*6 What am I missing? Peter
From: Roald de Vries on 13 Aug 2010 06:25 On Aug 12, 2010, at 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 > tgt = 120 # thanks, Dave Angel Anytime, but I'm not Dave Angel. My previous algorithm was more efficient, but for those who like one- liners: [x for x in range(120) if any(20*a+9*b+6*c == x for a in range(x/20) for b in range(x/9) for c in range(x/6))][-1] Cheers, Roald
From: Roald de Vries on 13 Aug 2010 06:38 On Aug 13, 2010, at 12:25 PM, Roald de Vries wrote: > My previous algorithm was more efficient, but for those who like one- > liners: > > [x for x in range(120) if any(20*a+9*b+6*c == x for a in range(x/20) > for b in range(x/9) for c in range(x/6))][-1] OK, I did some real testing now, and there's some small error in the above. All solutions for all x's are given by: [(x, a, b, c) for x in range(120) for a in range(x/20+1) for b in range(x/9+1) for c in range(x/6+1) if x == a*20+b*9+c*6] .... and all non-solutions by: [x for x in range(120) if not any(x == a*20+b*9+c*6 for a in range(x/20+1) for b in range(x/9+1) for c in range(x/6+1))] Cheers, Roald
From: News123 on 13 Aug 2010 16:22
Roald, What would your solution be if you weren't allowed to 'know' that 120 is an upper limit. Assume you were only allowed to 'know', that you won't find any other amount, which can't be bought A AOON A you found six solutions in a row? I have a rather straightforward solution trying from 0 nuggets on until I found six 'hits' in a row, but would be interested about other idioms. On 08/13/2010 12:38 PM, Roald de Vries wrote: > On Aug 13, 2010, at 12:25 PM, Roald de Vries wrote: >> My previous algorithm was more efficient, but for those who like >> one-liners: >> >> [x for x in range(120) if any(20*a+9*b+6*c == x for a in range(x/20) >> for b in range(x/9) for c in range(x/6))][-1] > > OK, I did some real testing now, and there's some small error in the > above. All solutions for all x's are given by: > > [(x, a, b, c) for x in range(120) for a in range(x/20+1) for b in > range(x/9+1) for c in range(x/6+1) if x == a*20+b*9+c*6] > > ... and all non-solutions by: > > [x for x in range(120) if not any(x == a*20+b*9+c*6 for a in > range(x/20+1) for b in range(x/9+1) for c in range(x/6+1))] > > Cheers, Roald |