looping through possible combinations of McNuggets packs of 6,9 and 20
in [Python]
|
Prev: most popular gui framework for python
Next: looping through possible combinations of McNuggets packs of 6,9and 20
From: Baba on 11 Aug 2010 16:14 level: beginner 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. exercise source: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/assignments/pset2.pdf please help me write this code i believe it's something along the lines of this: c=0 sol=[] for n in range (0,10): for a in range (0,10): for b in range (0,10): for c in range (0,10): sol=6*a+9*b+20*c if sol!=n: c+=1 if c==6: print sol
From: Thomas Jollans on 11 Aug 2010 17:15 On Wednesday 11 August 2010, it occurred to Baba to exclaim: > level: beginner > > 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. The MacDonald's at Nuremberg central station once sold me 25 in a 20-pack. So this won't work. > > exercise source: > http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00 > -introduction-to-computer-science-and-programming-fall-2008/assignments/pse > t2.pdf > > please help me write this code > > i believe it's something along the lines of this: > > c=0 > sol=[] > for n in range (0,10): > for a in range (0,10): > for b in range (0,10): > for c in range (0,10): > sol=6*a+9*b+20*c > if sol!=n: > c+=1 > if c==6: > print sol
From: Peter Otten on 12 Aug 2010 15:02 Baba wrote: > Thank You for helping me out. Indeed i am not looking for the code but > rather for hints that direct my reasoning as well as hints as to how > to write basic programs like this. > > You have broken down the approach into 2 parts. I have tried to solve > part 1 but i'm not quite there yet. Here's my code: > > def can_buy(n_nuggets): > for a in range (1,n_nuggets): > for b in range (1,n_nuggets): > for c in range (1,n_nuggets): > if 6*a+9*b+20*c==n_nuggets: > #print a,b,c,'n_nuggets=',n_nuggets > return True > else: > return False > > > can_buy(55) > > as you can see i am trying to loop through all combinations of values > bewtween 1 and n_nuggets and when the equation resolves it should > return True, else it should return False. > > I was hoping that when i then call my function and ask it to test a > value nothing happens. What is wrong? My syntax? My semantic? Both? First, the function gives up too early; it should only return False when all combinations of a, b, c (technically: the product of the ranges) have been tried. Second, can_buy(0) should return True, but the solution 0*6 + 0*9 + 0*20 is never tried; fix your ranges accordingly. Peter
From: Roald de Vries on 12 Aug 2010 15:42 On Aug 12, 2010, at 9:02 PM, Peter Otten wrote: > Baba wrote: > > >> Thank You for helping me out. Indeed i am not looking for the code >> but >> rather for hints that direct my reasoning as well as hints as to how >> to write basic programs like this. >> >> You have broken down the approach into 2 parts. I have tried to solve >> part 1 but i'm not quite there yet. Here's my code: >> >> def can_buy(n_nuggets): >> for a in range (1,n_nuggets): >> for b in range (1,n_nuggets): >> for c in range (1,n_nuggets): >> if 6*a+9*b+20*c==n_nuggets: >> #print a,b,c,'n_nuggets=',n_nuggets >> return True >> else: >> return False >> >> >> can_buy(55) >> >> as you can see i am trying to loop through all combinations of values >> bewtween 1 and n_nuggets and when the equation resolves it should >> return True, else it should return False. >> >> I was hoping that when i then call my function and ask it to test a >> value nothing happens. What is wrong? My syntax? My semantic? Both? > > First, the function gives up too early; it should only return False > when all > combinations of a, b, c (technically: the product of the ranges) > have been > tried. > > Second, can_buy(0) should return True, but the solution 0*6 + 0*9 + > 0*20 is > never tried; fix your ranges accordingly. Moreover: a, b and c can range over n_nuggets/6, n_nuggets/9 and n_nuggets/20 respectively. This will work, but does too much work. Cheers, Roald
From: News123 on 12 Aug 2010 16:28
Hi Baba, The last tips should really help you getting started: for testing your function you could do: Below your uncorrected code and a test for it def can_buy(n_nuggets): for a in range (1,n_nuggets): for b in range (1,n_nuggets): for c in range (1,n_nuggets): print "trying for %2d: %2d %2d %2d" % (n,a,b,c) if 6*a+9*b+20*c==n_nuggets: return True else: return False # show the results for the first 50 numbers. for n in xrange(50): result = can_buy(n) # get the result (see Brian's comment) print("result of can_buy(%2d) is %s" % (n,result)) with the print statement in can_buy() you should immediately see some issues. as soon as can_buy seems to work, you could comment the print statement. Additionally: I would return [a,b,c] if you got a result and [] if you got no result. So you don't only seem whether you can buy n nuggets, but you can also see how (AND even verify the solution) the print statement should show you what Peter said. You just make one test and return immediately in the else statement Instead you should continue until you found a solution or until you tried all possibilities. After having fixed the fact, that you don't try all options, you'll see that your first success would be with 6+9+12 = 27 nuggets es you never try with 0 boxes of a kind. (as Peter mentioned) Finally as Roald says. if you can reduce the upper limit of your search ranges. if you have for example 13 nuggets you do not have to try 3 boxes of 6 as this is already 18, so trying only 0,1 or two boxes is enough You will now also see, what On 08/12/2010 09:42 PM, Roald de Vries wrote: > > On Aug 12, 2010, at 9:02 PM, Peter Otten wrote: > >> Baba wrote: >> >> >>> Thank You for helping me out. Indeed i am not looking for the code but >>> rather for hints that direct my reasoning as well as hints as to how >>> to write basic programs like this. >>> >>> You have broken down the approach into 2 parts. I have tried to solve >>> part 1 but i'm not quite there yet. Here's my code: >>> >>> def can_buy(n_nuggets): >>> for a in range (1,n_nuggets): >>> for b in range (1,n_nuggets): >>> for c in range (1,n_nuggets): >>> if 6*a+9*b+20*c==n_nuggets: >>> #print a,b,c,'n_nuggets=',n_nuggets >>> return True >>> else: >>> return False >>> >>> >>> can_buy(55) >>> >>> as you can see i am trying to loop through all combinations of values >>> bewtween 1 and n_nuggets and when the equation resolves it should >>> return True, else it should return False. >>> >>> I was hoping that when i then call my function and ask it to test a >>> value nothing happens. What is wrong? My syntax? My semantic? Both? >> >> First, the function gives up too early; it should only return False >> when all >> combinations of a, b, c (technically: the product of the ranges) have >> been >> tried. >> >> Second, can_buy(0) should return True, but the solution 0*6 + 0*9 + >> 0*20 is >> never tried; fix your ranges accordingly. > > Moreover: a, b and c can range over n_nuggets/6, n_nuggets/9 and > n_nuggets/20 respectively. This will work, but does too much work. > > Cheers, Roald > |