Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On 08/17/2010 11:44 PM, Baba wrote: On Aug 16, 6:28 pm, cbr...@cbrownsystems.com cbr...@cbrownsystems.com wrote: First, suppose d = gcd(x, y, z); then for some x', y', z' we have that x = d*x', y = d*y', z = d*z'; and so for any a, b, c: could you explain the notation? what is the difference btw x and x' ? what is x = d*x', y supposed to say? gcd(x,y,z) determines the greates number by which all three numbers can be devided. 2,4,6 for example are all divided by 2 thus d=2 now you dived x,y,z by d and call them x' , y' , z' The point is if x,y,z have a gcd grater than one, then you know for sure, that you will never be able to find the a finit greates amount, which cannot be bought if xmymz are all divisible by d, then any combination will also be dividible by d thas any number not dividible by d ( for d 1) for example n*d + 1 can not be bought -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On Aug 17, 2:44 pm, Baba raoul...@gmail.com wrote: On Aug 16, 6:28 pm, cbr...@cbrownsystems.com cbr...@cbrownsystems.com wrote: First, suppose d = gcd(x, y, z); then for some x', y', z' we have that x = d*x', y = d*y', z = d*z'; and so for any a, b, c: could you explain the notation? what is the difference btw x and x' ? what is x = d*x', y supposed to say? x', y', z' are names for three natural numbers; I could have chosen r, s, t. x=d*x' above simply notes that since x is divisible by d, it can be written as the product of d and some other natural number, and the same is true for both y and z. therefore sums of multiples of x, y and z are always divisible by d. To go the other way, if d = 1, then there exists integers (not neccessarily positive) such that a*x + b*y + c*z = 1 what's the link with 6*a+9*b+20*c=n except the similarity? The link is that it shows that if we have some u, v, and w with 6*u + 9*v + 20*w = n, and we can find some a, b, and c which satisfy 6*a + 9*b + 20*c = 1 then if we let r = u + a, s = v + b, and t = w + c, we get that 6*r + 9*s + 20*t = n+1 although r, s, and t are not neccessarily positive numbers (as they must be to solve your original problem). However, if u, v, and w are sufficiently large compared to a, b, and c, then r, s and t WILL all be positive. But we can only find such an a,b, and c because the gcd of 6, 9, and 20 is equal to 1; that is why you can't solve this problem for nugget pack sizes 6, 12, and 21. Note that if there is one solution (a,b,c) to the gcd equation, there infinitely many tuples (a,b,c) which satisfy the gcd equation, for example: 6*0+ 9*9+ 20*(-4) = 1 6*(-5) + 9*(-1) + 20*2= 1 6*2+ 9*1+ 20*(-1) = 1 So the proof I gave regarded the /existence/ of a largest unobtainable, not an algorithm for obtaining one. However from the last of those three examples, we can see (details are in my original proof) that the largest unobtainable must be less than 6*0+ 9*0+ 20*(1*5) = 100 so it is potentially helpful for finding an upper bound to the problem. furthermore i came across this: For k = 3, efficient algorithms have been given by Greenberg and Davison ; if x1 x2 x3, these algorithms run in time bounded by a polynomial in log x3. Kannan gave a very complicated algorithm that runs in polynomial time in log xk if k is fixed, but is wildly exponential in k. However, Ram´ırez Alfons´ın proved that the general problem is NP-hard, under Turing reductions, by reducing from the integer knapsack problem. So it seems very likely that there is no simple formula for computing g(x1, x2, . . . , xk) for arbitrary k. source:http://arxiv.org/PS_cache/arxiv/pdf/0708/0708.3224v1.pdf i would be interested in the answer to problem 3: explain in English why the theorem is true I haven't looked at the link; but to be honest it's unlikely you would understand it if you are having trouble with the much simpler question regarding solutions in the case of 6, 12, and 21. Cheers - Chas -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
Hi Chas Thanks for that and i agree on your last remark :) re the number of required consecutive passes required: The number of required consecutive passes is equal to the smallest number because after that you can get any amount of nuggets by just adding the smallest nugget pack to some other number. This is only true if gcd(a,b,c)=1. Thanks to all for the help in getting to the bottom of the exercise. I have truly enjoyed this and most importantly i have learned some new things. Hadn't really done any mathematics in a long time and only starting programming so this was good to get up to speed. kind regards to everyone! Baba -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On Aug 18, 10:52 am, Baba raoul...@gmail.com wrote: Hi Chas Thanks for that and i agree on your last remark :) re the number of required consecutive passes required: The number of required consecutive passes is equal to the smallest number because after that you can get any amount of nuggets by just adding the smallest nugget pack to some other number. This is only true if gcd(a,b,c)=1. Thanks to all for the help in getting to the bottom of the exercise. I have truly enjoyed this and most importantly i have learned some new things. Hadn't really done any mathematics in a long time and only starting programming so this was good to get up to speed. kind regards to everyone! Baba Happy to be of service! Cheers - Chas -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On 8/18/2010 1:38 PM, cbr...@cbrownsystems.com wrote: To go the other way, if d = 1, then there exists integers (not neccessarily positive) such that a*x + b*y + c*z = 1 That fact is non-trivial, although the proof isn't *too* hard [1]. I found it interesting to demonstrate the simpler case (a*x + b*y = 1) by instrumenting the classic Python implementation of Euclid's Algorithm: def show_gcd(a,b): find GCD of two integers, showing intermediate steps in both remainder and linear-combination forms while b: if a%b 0: rem_form = %d == %d*(%d), rem %d % (a, b, a/b, a%b) equ_form = %d == %d*(1) + %d*(-%d) % (a%b, a, b, a/b) print %3d %3d %-30s %s % (a,b, rem_form, equ_form) a,b = b, a%b print \nGCD is, a show_gcd(124, 39) 124 39 124 == 39*(3), rem 7 7 == 124*(1) + 39*(-3) 39 7 39 == 7*(5), rem 4 4 == 39*(1) + 7*(-5) 7 4 7 == 4*(1), rem 3 3 == 7*(1) + 4*(-1) 4 3 4 == 3*(1), rem 1 1 == 4*(1) + 3*(-1) Performing successive substitutions, bottom to top, using the equations in the right-hand column: 1 == 4*(1) + 3*(-1) == 4*(1) + (7*(1) + 4*(-1))*(-1) == 4*(2) + 7*(-1) == (39*(1) + 7*(-5))*(2) + 7*(-1) == 39*(2) + 7*(-11) == 39*(2) + (124*(1) + 39*(-3))*(-11) == 39*(35) + 124*(-11) What could be simpler! :-) -John [1] http://math453fall2008.wikidot.com/lecture-3 (GCD as a linear combonation [sic]) -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On Aug 18, 11:50 am, John Posner jjpos...@optimum.net wrote: On 8/18/2010 1:38 PM, cbr...@cbrownsystems.com wrote: To go the other way, if d = 1, then there exists integers (not neccessarily positive) such that a*x + b*y + c*z = 1 That fact is non-trivial, although the proof isn't *too* hard [1]. I found it interesting to demonstrate the simpler case (a*x + b*y = 1)... And to get the more general case, if we write (a,b) for gcd of and b, we can think of the , as a binary operator that you can show is associative: ((a,b), c) = (a, (b,c)) = (a, b, c) and so a proof that exists x,y with a*x + b*y = (a,b) can then be extended to a proof for an arbitrary number of elements. (Oddly, , is also distributive over itself: ((a,b), c) = ((a,c), (b,c))...) Cheers - Chas -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
Paul Rubin no.em...@nospam.invalid writes: Baba raoul...@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? yes, and no it was a homework problem, assigned in 2008, as clearly stated by the OP most of what was discussed on the ng was clearly stated in the introduction to the actual problem, so that we can thank Baba for NOT having read the text of the assignment, leavin' us a couple of days of amusing and interesting posts -- Mangiate pure le vostre carote, noi mangeremo le nostre salsicce! -- Claud, in IHC -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On Aug 16, 6:28 pm, cbr...@cbrownsystems.com cbr...@cbrownsystems.com wrote: First, suppose d = gcd(x, y, z); then for some x', y', z' we have that x = d*x', y = d*y', z = d*z'; and so for any a, b, c: could you explain the notation? what is the difference btw x and x' ? what is x = d*x', y supposed to say? To go the other way, if d = 1, then there exists integers (not neccessarily positive) such that a*x + b*y + c*z = 1 what's the link with 6*a+9*b+20*c=n except the similarity? furthermore i came across this: For k = 3, efficient algorithms have been given by Greenberg and Davison ; if x1 x2 x3, these algorithms run in time bounded by a polynomial in log x3. Kannan gave a very complicated algorithm that runs in polynomial time in log xk if k is fixed, but is wildly exponential in k. However, Ram´ırez Alfons´ın proved that the general problem is NP-hard, under Turing reductions, by reducing from the integer knapsack problem. So it seems very likely that there is no simple formula for computing g(x1, x2, . . . , xk) for arbitrary k. source: http://arxiv.org/PS_cache/arxiv/pdf/0708/0708.3224v1.pdf i would be interested in the answer to problem 3: explain in English why the theorem is true @Giacomo: when you say that i have not read the text of the assignment i tend to disagree. Therefore could you point out what it is i overlooked that should help me prove my assumption for the generalisation? Enjoy the sausages btw :) tnx Baba -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On Aug 15, 2010, at 11:51 PM, Ian Kelly wrote: On Sun, Aug 15, 2010 at 4:36 PM, Baba raoul...@gmail.com wrote: Hi Mel, indeed i thought of generalising the theorem as follows: If it is possible to buy n, n+1,…, n+(x-1) sets of McNuggets, for some x, then it is possible to buy any number of McNuggets = x, given that McNuggets come in x, y and z packs. so with diophantine_nuggets(7,10,21) i would need 7 passes result:53 but with (10,20,30) and 10 passes i get no result You're on the right track. In the case of (10,20,30) there is no largest exactly purchasable quantity. Any quantity that does not end with a 0 will not be exactly purchasable. I suspect that there exists a largest unpurchasable quantity iff at least two of the pack quantities are relatively prime, but I have made no attempt to prove this. That for sure is not correct; packs of 2, 4 and 7 do have a largest unpurchasable quantity. I'm pretty sure that if there's no common divisor for all three (or more) packages (except one), there is a largest unpurchasable quantity. That is: ∀ i1: ¬(i|a) ∨ ¬(i|b) ∨ ¬(i|c), where ¬(x| y) means x is no divider of y Cheers, Roald -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On Mon, Aug 16, 2010 at 4:23 AM, Roald de Vries downa...@gmail.com wrote: I suspect that there exists a largest unpurchasable quantity iff at least two of the pack quantities are relatively prime, but I have made no attempt to prove this. That for sure is not correct; packs of 2, 4 and 7 do have a largest unpurchasable quantity. 2 and 7 are relatively prime, so this example fits my hypothesis. I'm pretty sure that if there's no common divisor for all three (or more) packages (except one), there is a largest unpurchasable quantity. That is: ∀ i1: ¬(i|a) ∨ ¬(i|b) ∨ ¬(i|c), where ¬(x|y) means x is no divider of y No. If you take the (2,4,7) example and add another pack size of 14, it does not cause quantities that were previously purchasable to become unpurchasable. Ian -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On Mon, Aug 16, 2010 at 11:04 AM, Ian Kelly ian.g.ke...@gmail.com wrote: On Mon, Aug 16, 2010 at 4:23 AM, Roald de Vries downa...@gmail.com wrote: I suspect that there exists a largest unpurchasable quantity iff at least two of the pack quantities are relatively prime, but I have made no attempt to prove this. That for sure is not correct; packs of 2, 4 and 7 do have a largest unpurchasable quantity. 2 and 7 are relatively prime, so this example fits my hypothesis. Although now that I think about it some more, there are counter-examples. For example, the pack sizes (6, 10, 15) have a largest unpurchasable quantity of 29, but no two of those are relatively prime. I'm going to revise my hypothesis to state that a largest unpurchasable quantity exists iff some there exists some relatively prime subset of the pack sizes of cardinality 2 or greater. Cheers, Ian -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On Aug 16, 2010, at 5:04 PM, Ian Kelly wrote: On Mon, Aug 16, 2010 at 4:23 AM, Roald de Vries downa...@gmail.com wrote: I suspect that there exists a largest unpurchasable quantity iff at least two of the pack quantities are relatively prime, but I have made no attempt to prove this. That for sure is not correct; packs of 2, 4 and 7 do have a largest unpurchasable quantity. 2 and 7 are relatively prime, so this example fits my hypothesis. I now notice I misread your post (as 'iff the least two pack quantities are relatively prime') I'm pretty sure that if there's no common divisor for all three (or more) packages (except one), there is a largest unpurchasable quantity. That is: ∀ i1: ¬(i|a) ∨ ¬(i|b) ∨ ¬(i|c), where ¬(x|y) means x is no divider of y No. If you take the (2,4,7) example and add another pack size of 14, it does not cause quantities that were previously purchasable to become unpurchasable. Then what is the common divisor of 2, 4, 7 and 14? Not 2 because ¬(2| 7), not anything higher than 2 because that's no divisor of 2. Cheers, Roald -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On Aug 16, 1:23 am, Roald de Vries downa...@gmail.com wrote: On Aug 15, 2010, at 11:51 PM, Ian Kelly wrote: On Sun, Aug 15, 2010 at 4:36 PM, Baba raoul...@gmail.com wrote: Hi Mel, indeed i thought of generalising the theorem as follows: If it is possible to buy n, n+1,…, n+(x-1) sets of McNuggets, for some x, then it is possible to buy any number of McNuggets = x, given that McNuggets come in x, y and z packs. so with diophantine_nuggets(7,10,21) i would need 7 passes result:53 but with (10,20,30) and 10 passes i get no result You're on the right track. In the case of (10,20,30) there is no largest exactly purchasable quantity. Any quantity that does not end with a 0 will not be exactly purchasable. I suspect that there exists a largest unpurchasable quantity iff at least two of the pack quantities are relatively prime, but I have made no attempt to prove this. That for sure is not correct; packs of 2, 4 and 7 do have a largest unpurchasable quantity. But 2 is coprime to 7. I think a better counterexample is 6, 10, 15; no two are coprime, but there is a largest unpurchasable quantity. I'm pretty sure that if there's no common divisor for all three (or more) packages (except one), there is a largest unpurchasable quantity. That is: ∀ i1: ¬(i|a) ∨ ¬(i|b) ∨ ¬(i|c), where ¬(x| y) means x is no divider of y It's easy to prove that there is a largest unpurchasble quantity iff gcd(x,y,z) = 1. First, suppose d = gcd(x, y, z); then for some x', y', z' we have that x = d*x', y = d*y', z = d*z'; and so for any a, b, c: a*x + b*y + c*z = a*d*x' + b*d*y' + c*d*z' = d*(a*x' + b*y' + c*z') which means that d must always divide the total number of nuggets purchasable; thus if d 1, there is no largest unpurchasable quantity (you cannot purchase n*d + 1 nuggets for any n). To go the other way, if d = 1, then there exists integers (not neccessarily positive) such that a*x + b*y + c*z = 1 so therefore (a*x)*x + (b*x)*y + (c*x)*z = x Choose A, B, and C to be positive integers with A + a*x = 0 B + b*x = 0 C + c*x = 0 Then we get a sequence of x consecutive numbers, all purchasable, via (A + i*a)*x + (B + i*b)*x + (C + i*c)*z = (Ax + By + Cz) + i*(ax + by cz) = (Ax + By + Cz) + i with i in range(x). The next consecutive number is then achieved via (Ax + By + Cz) + x = (A+1)x + By + Cz and so on. Cheers - Chas -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On Mon, Aug 16, 2010 at 12:43 PM, Roald de Vries downa...@gmail.com wrote: I'm pretty sure that if there's no common divisor for all three (or more) packages (except one), there is a largest unpurchasable quantity. That is: ∀ i1: ¬(i|a) ∨ ¬(i|b) ∨ ¬(i|c), where ¬(x|y) means x is no divider of y No. If you take the (2,4,7) example and add another pack size of 14, it does not cause quantities that were previously purchasable to become unpurchasable. Then what is the common divisor of 2, 4, 7 and 14? Not 2 because ¬(2|7), not anything higher than 2 because that's no divisor of 2. Ah, I misread what you meant as well. -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
Hi Chas, Roald, These are all complicated formula that i believe are not expected at this level. If you look at the source (see my first submission) you will see that this exercise is only the second in a series called Introduction to Programming. Therefore i am convinced that there is a much simpler solution. Now, i believe that the number of consecutive passes required to make this work is equal to the smallest number of pack sizes. So if we have packs of (9,12,21) the number of passes needed would be 9 and the theorem would read If it is possible to buy n,n+1,n+2,...n+8 nuggets it is possible to buy any number of nuggets = 9 given that they come in packs of 9,12,21 However i turn in circles because i don't seem to get any results for some random pack combinations like (9,12,21) or (10,20,30). The must always be a solution i'm thinking, be it the smallest pack - 1 Thoughts? tnx Raoul -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
Baba wrote: [ ... ] Now, i believe that the number of consecutive passes required to make this work is equal to the smallest number of pack sizes. So if we have packs of (9,12,21) the number of passes needed would be 9 and the theorem would read If it is possible to buy n,n+1,n+2,...n+8 nuggets it is possible to buy any number of nuggets = 9 given that they come in packs of 9,12,21 That's the proper statement. However i turn in circles because i don't seem to get any results for some random pack combinations like (9,12,21) or (10,20,30). That if it is possible is the big if. If every package you can buy has a multiple of 3, then every possible purchase will be a multiple of 3. Nothing that leaves a remainder of 1 or 2 will ever show up. The must always be a solution i'm thinking, be it the smallest pack - 1 The set (9/3, 12/3, 21/3) settles down pretty quickly: s = nuggets.buyable_set ((3, 4, 7)) nuggets.print_from (s, xrange(20)) 0 set([]) 3 set([0]) 4 set([0]) 6 set([3]) 7 set([0, 3, 4]) 8 set([4]) 9 set([6]) 10 set([3, 6, 7]) 11 set([8, 4, 7]) 12 set([8, 9]) 13 set([9, 10, 6]) 14 set([10, 11, 7]) 15 set([8, 11, 12]) 16 set([9, 12, 13]) 17 set([10, 13, 14]) 18 set([11, 14, 15]) 19 set([16, 12, 15]) The printout here is the 'genaeology' of each purchase -- the set of smaller purchases from which you can reach each one. After ...,6,7,8,... every larger number can be reached. Mel. -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
Baba raoul...@gmail.com writes: Hi Mel, indeed i thought of generalising the theorem as follows: If it is possible to buy n, n+1,~, n+(x-1) sets of McNuggets, for some x, then it is possible to buy any number of McNuggets = x, given that McNuggets come in x, y and z packs. so with diophantine_nuggets(7,10,21) i would need 7 passes result:53 but with (10,20,30) and 10 passes i get no result you need at least an odd number in your set, because summing even numbers only you'll never get an odd result -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
well i still believe that the key is the smallest sized pack and there's no need to go into higher mathematics to solve this problem. I think below code works within the limits of the exercise which states to look at a maximum range of 200 in order not to search forever. packages=[2,103,105] min_size=min(packages[0],packages[1],packages[2]) cbc=0 #cbc=can_buy counter for n_nuggets in range(1,200): if cbc=min_size: break can_buy=False for a in range (n_nuggets/packages[0]+1): for b in range (n_nuggets/packages[1]+1): for c in range (n_nuggets/packages[2]+1): #print trying for %d: %d %d %d % (n_nuggets,a,b,c) if packages[0]*a+packages[1]*b+packages[2]*c==n_nuggets: can_buy=True break if can_buy==True: cbc+=1 else: cbc=0 sol=n_nuggets print sol Baba -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On 8/16/2010 4:18 PM, Baba wrote: packages=[2,103,105] min_size=min(packages[0],packages[1],packages[2]) or: min_size = min(packages) -John -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On Aug 16, 11:04 am, Baba raoul...@gmail.com wrote: Hi Chas, Roald, These are all complicated formula that i believe are not expected at this level. If you look at the source (see my first submission) you will see that this exercise is only the second in a series called Introduction to Programming. Therefore i am convinced that there is a much simpler solution. The question I was responding to (a different one than your original question) was whether there was a proof of Baba's conjecture that a largest unobtainable quantity was possible if, and only if, the three numbers in question had a gcd of 1. Roald had something like a gut feeling that it was true, but such things are generally much more clear cut than gut feelings - they can often easily be /proven/ to be true or false, given the right mental tools. In this case, that proof I gave doesn't immediately yield a concrete answer to your /original/ question - assuming that a largest obtainable solution is possible, /how/ do we find the largest unobtainable solution? But it certainly identifies the conditions whereby we can easily and quickly say that there is no such solution, or conversely that such a solution must exist; and that is often extremely helpful to finding an algorithm that /does/ answer your original question. (One thing it does provide is an upper bound to the space of solutions that you should be looking at - and finding upper bounds and lower bounds is a common programming task. Again, this isn't something that you might be expected to know about at your level of study, but it doesn't hurt you to be aware of it either :)!) Now, i believe that the number of consecutive passes required to make this work is equal to the smallest number of pack sizes. That is your belief, your intuition; and developing good intuitions is good... BUT... So if we have packs of (9,12,21) the number of passes needed would be 9 and... ... and now whatever you might go on to add is simply going off into the weeds, because I have just proven that there can be /no/ such solution in that case: all three of those numbers are divisible by 3, so you are not on the trail when trying to figure out a general solution by considering examples of the type you mention. At your level of study, such things may seem overly complicated (and are certainly /not/ required to simply answer the question as originally stated). But consider the thread in this group called python interview questions: http://groups.google.com/group/comp.lang.python/browse_frm/thread/bb4d3514e9842f9e# The FizzBuzz question involves a similar very basic grasp of the type of mathematical reasoning and thinking that is most valued in programmers in the job market. Of course, your Python class is not the right place to be focusing exclusively on this sort of mathematics, but I would encourage you to simultaneously educate yourself both in the /language/ learning of Python (which is what your class is largely about), along with the more universally applicable skill set that comes from understanding the mathematical justifications of a good algorithm That additional knowledge will serve you equally well whether you are programming in Python, Perl, Ruby, Java, C++, D, F, R, and so on (surely someone will claim Z as a language soon, if they haven't already...). ... the theorem would read If it is possible to buy n,n+1,n+2,...n+8 nuggets it is possible to buy any number of nuggets = 9 given that they come in packs of 9,12,21 So I would ask as a simple exercise: how would you go about /proving/ that your assertion is actually a /theorem/, and not just a pretty solid hunch that your statement is true because for small enough numbers you can easily do it in your head? Yes, it's clearly true, but that is not a proof! That is the muscle which is exercised by mathematical reasoning. However i turn in circles because i don't seem to get any results for some random pack combinations like (9,12,21) or (10,20,30). Well, your intuitions are certainly close to the mark. But if you added to your study a course on discrete mathematics, then you would also immediately see why such turning in circles obviously can bear no fruit, and that would give you a great advantage in solving far more difficult and yet common problems of this type. Cheers - Chas -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
Hi John, Thanks for your submission! I've improved a lot and everone's help so far has been thrilling amd is very good for my self-study motivation :) ok so i think i'm clear on how to approach this problem and on how to write basic but clean Python code to solve it. The next step is to generalise this code so that other pack quantities could be tested: generalize this idea to work with any size packages of McNuggets, not just 6, 9, and 20. For simplicity, however, we will assume that nuggets are provided in three different sized packages I thought this should be relatively straightforward and it does work if i test it for the values 6,920 but if i test for 2,3,4 i would expect the result to be 1 but it returns nothing def can_buy(n_nuggets,packages): for a in range (0,n_nuggets/6+1): for b in range (0,n_nuggets/9+1): for c in range (0,n_nuggets/20+1): #print trying for %d: %d %d %d % (n_nuggets,a,b,c) if packages[0]*a+packages[1]*b +packages[2]*c==n_nuggets: return True return False def diophantine_nuggets(x,y,z): cbc=0 #cbc=can_buy counter packages =[x,y,z] for n_nuggets in range(50): result=can_buy(n_nuggets,packages) if result: cbc+=1 else: cbc=0 if cbc==6: solution=n_nuggets-6 print Largest number of McNuggets that cannot be bought in exact quantity: %d %(solution) diophantine_nuggets(2,3,4) -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
Hi John, Thanks for your submission! I've improved a lot and everone's help so far has been thrilling and is very good for my self-study motivation :) ok so i think i'm clear on how to approach this problem and on how to write basic but clean Python code to solve it. The next step is to generalise this code so that other pack quantities could be tested: generalize this idea to work with any size packages of McNuggets, not just 6, 9, and 20. For simplicity, however, we will assume that nuggets are provided in three different sized packages I thought this should be relatively straightforward and it does work if i test it for the values 6,920 but if i test for 2,3,4 i would expect the result to be 1 but it returns nothing def can_buy(n_nuggets,packages): for a in range (0,n_nuggets/6+1): for b in range (0,n_nuggets/9+1): for c in range (0,n_nuggets/20+1): #print trying for %d: %d %d %d % (n_nuggets,a,b,c) if packages[0]*a+packages[1]*b +packages[2]*c==n_nuggets: return True return False def diophantine_nuggets(x,y,z): cbc=0 #cbc=can_buy counter packages =[x,y,z] for n_nuggets in range(50): result=can_buy(n_nuggets,packages) if result: cbc+=1 else: cbc=0 if cbc==6: solution=n_nuggets-6 print Largest number of McNuggets that cannot be bought in exact quantity: %d %(solution) diophantine_nuggets(2,3,4) -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On 8/15/2010 8:44 AM Baba said... Hi John, Thanks for your submission! I've improved a lot and everone's help so far has been thrilling and is very good for my self-study motivation :) ok so i think i'm clear on how to approach this problem and on how to write basic but clean Python code to solve it. The next step is to generalise this code so that other pack quantities could be tested: generalize this idea to work with any size packages of McNuggets, not just 6, 9, and 20. For simplicity, however, we will assume that nuggets are provided in three different sized packages I thought this should be relatively straightforward and it does work if i test it for the values 6,920 but if i test for 2,3,4 i would expect the result to be 1 but it returns nothing Because can_buy still uses denominators 6,920 - try packages[0],[1][2] Emile def can_buy(n_nuggets,packages): for a in range (0,n_nuggets/6+1): for b in range (0,n_nuggets/9+1): for c in range (0,n_nuggets/20+1): #print trying for %d: %d %d %d % (n_nuggets,a,b,c) if packages[0]*a+packages[1]*b +packages[2]*c==n_nuggets: return True return False def diophantine_nuggets(x,y,z): cbc=0 #cbc=can_buy counter packages =[x,y,z] for n_nuggets in range(50): result=can_buy(n_nuggets,packages) if result: cbc+=1 else: cbc=0 if cbc==6: solution=n_nuggets-6 print Largest number of McNuggets that cannot be bought in exact quantity: %d %(solution) diophantine_nuggets(2,3,4) -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On Sun, Aug 15, 2010 at 9:58 AM, Emile van Sebille em...@fenx.com wrote: On 8/15/2010 8:44 AM Baba said... Hi John, Thanks for your submission! I've improved a lot and everone's help so far has been thrilling and is very good for my self-study motivation :) ok so i think i'm clear on how to approach this problem and on how to write basic but clean Python code to solve it. The next step is to generalise this code so that other pack quantities could be tested: generalize this idea to work with any size packages of McNuggets, not just 6, 9, and 20. For simplicity, however, we will assume that nuggets are provided in three different sized packages I thought this should be relatively straightforward and it does work if i test it for the values 6,920 but if i test for 2,3,4 i would expect the result to be 1 but it returns nothing Because can_buy still uses denominators 6,920 - try packages[0],[1][2] Also, note that testing for 6 buyable quantities in a row is correct for 6, 9, 20 but is not necessarily correct for other denominations. You should think about how many you need to find in sequence for any given input of x, y, and z. Cheers, Ian -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On 8/15/2010 11:38 AM, Baba wrote: In addition to the points that Emile and Ian made ... def diophantine_nuggets(x,y,z): cbc=0 #cbc=can_buy counter packages =[x,y,z] You can take advantage of a nifty syntax convenience feature here. Instead of loading all of the function's arguments into a list manually, you can make it happen automatically: def diophantine_nuggets(x,y,z): cbc = 0 packages =[x,y,z] ... becomes ... def diophantine_nuggets(*packages): cbc = 0 The asterisk (*) in the function's signature does the trick. for n_nuggets in range(50): Careful -- in the general case, you might need to search beyond 50 for your answer! Best, John -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
Hi All, @Emile tnx for spotting the mistake. Should have seen it myself. @John Ian i had a look around but couldn't find a general version of below theorem If it is possible to buy x, x+1,…, x+5 sets of McNuggets, for some x, then it is possible to buy any number of McNuggets = x, given that McNuggets come in 6, 9 and 20 packs. I must admit that i'm not keen on spending too much time on purely mathematical questions. It seems that this has to do with Frobenius Number? re range the exercise seems to suggest to limit it to 200 so feel free to enlighten me on this last part. In the meantime the almost complete code is: def can_buy(n_nuggets,packages): for a in range (0,n_nuggets/packages[0]+1): for b in range (0,n_nuggets/packages[1]+1): for c in range (0,n_nuggets/packages[2]+1): #print trying for %d: %d %d %d % (n_nuggets,a,b,c) if packages[0]*a+packages[1]*b +packages[2]*c==n_nuggets: return True return False def diophantine_nuggets(*packages): cbc=0 #cbc=can_buy counter #packages =[x,y,z] for n_nuggets in range(200): result=can_buy(n_nuggets,packages) if result: cbc+=1 else: cbc=0 if cbc==6: solution=n_nuggets-6 print Largest number of McNuggets that cannot be bought in exact quantity: %d %(solution) break diophantine_nuggets(2,3,4) -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
Baba wrote: Hi All, @Emile tnx for spotting the mistake. Should have seen it myself. @John Ian i had a look around but couldn't find a general version of below theorem If it is possible to buy x, x+1,…, x+5 sets of McNuggets, for some x, then it is possible to buy any number of McNuggets = x, given that McNuggets come in 6, 9 and 20 packs. Not that hard. When you can buy nuggets `n` to a pack (6 for example) then if you have schemes for buying k,k+1,k+2,...,k+n-1 nuggets, you can create a scheme for buying any number of nuggets = k . At worst just buy packs of `n` until the number left to buy is between k and k+n-1 inclusive, then follow the scheme for that number. Mel. -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
Hi Mel, indeed i thought of generalising the theorem as follows: If it is possible to buy n, n+1,…, n+(x-1) sets of McNuggets, for some x, then it is possible to buy any number of McNuggets = x, given that McNuggets come in x, y and z packs. so with diophantine_nuggets(7,10,21) i would need 7 passes result:53 but with (10,20,30) and 10 passes i get no result so i'm not sure i'm on the right path... -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On Sun, Aug 15, 2010 at 4:36 PM, Baba raoul...@gmail.com wrote: Hi Mel, indeed i thought of generalising the theorem as follows: If it is possible to buy n, n+1,…, n+(x-1) sets of McNuggets, for some x, then it is possible to buy any number of McNuggets = x, given that McNuggets come in x, y and z packs. so with diophantine_nuggets(7,10,21) i would need 7 passes result:53 but with (10,20,30) and 10 passes i get no result You're on the right track. In the case of (10,20,30) there is no largest exactly purchasable quantity. Any quantity that does not end with a 0 will not be exactly purchasable. I suspect that there exists a largest unpurchasable quantity iff at least two of the pack quantities are relatively prime, but I have made no attempt to prove this. Cheers, Ian -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On Aug 13, 8:25 pm, Ian Kelly ian.g.ke...@gmail.com wrote: It's not. You're not just trying to find the sixth value that can be bought in exact quantity, but a sequence of six values that can all be bought in exact quantity. The integers [6, 9, 12, 15, 18, 20] are not sequential. Hi Ian, Thanks for stating the obvious. I obviously hadn't understood a fundamental part of the theorem which states that 6 SEQUENTIAL passes must be found! That's a good lesson learned and will help me in future exercises to make sure i understand the theory first. Thanks again! Ok so with your and News123's help (no offence to all others but i need to keep it simple at this stage)i was able to find the solution: 43 my code is probably not elegant but a huge step forward from where i started: def can_buy(n_nuggets): for a in range (0,n_nuggets): for b in range (0,n_nuggets): for c in range (0,n_nuggets): #print trying for %d: %d %d %d % (n_nuggets,a,b,c) if 6*a+9*b+20*c==n_nuggets: return [a,b,c] return [] for n_nuggets in range(50): result1 = can_buy(n_nuggets) result2 = can_buy(n_nuggets+1) result3 = can_buy(n_nuggets+2) result4 = can_buy(n_nuggets+3) result5 = can_buy(n_nuggets+4) result6 = can_buy(n_nuggets+5) if result1!=[] and result2!=[] and result3!=[] and result4!=[] and result5!=[] and result6!=[]: if (n_nuggets+5)-n_nuggets==5: print n_nuggets-1 break i suppose this can be tweaked to make it shorter? For instance i wonder if i can do the same with less variable to be defined? tnx Baba -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
Baba wrote: def can_buy(n_nuggets): for a in range (0,n_nuggets): for b in range (0,n_nuggets): for c in range (0,n_nuggets): #print trying for %d: %d %d %d % (n_nuggets,a,b,c) if 6*a+9*b+20*c==n_nuggets: return [a,b,c] return [] for n_nuggets in range(50): result1 = can_buy(n_nuggets) result2 = can_buy(n_nuggets+1) result3 = can_buy(n_nuggets+2) result4 = can_buy(n_nuggets+3) result5 = can_buy(n_nuggets+4) result6 = can_buy(n_nuggets+5) if result1!=[] and result2!=[] and result3!=[] and result4!=[] and result5!=[] and result6!=[]: if (n_nuggets+5)-n_nuggets==5: print n_nuggets-1 break i suppose this can be tweaked to make it shorter? For instance i wonder if i can do the same with less variable to be defined? That can_buy function is a computational heavyweight -- very repetitive when called inside a loop. It could be cheaper to compute a list of quantities that can be purchased, then check to see what's in the list -- or the set, if you optimize a bit more. Mel. -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On 8/14/10, Baba raoul...@gmail.com wrote: On Aug 13, 8:25 pm, Ian Kelly ian.g.ke...@gmail.com wrote: It's not. You're not just trying to find the sixth value that can be bought in exact quantity, but a sequence of six values that can all be bought in exact quantity. The integers [6, 9, 12, 15, 18, 20] are not sequential. Hi Ian, Thanks for stating the obvious. I obviously hadn't understood a fundamental part of the theorem which states that 6 SEQUENTIAL passes must be found! That's a good lesson learned and will help me in future exercises to make sure i understand the theory first. Thanks again! Ok so with your and News123's help (no offence to all others but i need to keep it simple at this stage)i was able to find the solution: 43 my code is probably not elegant but a huge step forward from where i started: def can_buy(n_nuggets): for a in range (0,n_nuggets): for b in range (0,n_nuggets): for c in range (0,n_nuggets): #print trying for %d: %d %d %d % (n_nuggets,a,b,c) if 6*a+9*b+20*c==n_nuggets: return [a,b,c] return [] for n_nuggets in range(50): result1 = can_buy(n_nuggets) result2 = can_buy(n_nuggets+1) result3 = can_buy(n_nuggets+2) result4 = can_buy(n_nuggets+3) result5 = can_buy(n_nuggets+4) result6 = can_buy(n_nuggets+5) if result1!=[] and result2!=[] and result3!=[] and result4!=[] and result5!=[] and result6!=[]: if (n_nuggets+5)-n_nuggets==5: print n_nuggets-1 break i suppose this can be tweaked to make it shorter? For instance i wonder if i can do the same with less variable to be defined? tnx Baba One tweak: def can_buy(n_nuggets): for a in range (0,n_nuggets): for b in range (0,n_nuggets): for c in range (0,n_nuggets): #print trying for %d: %d %d %d % (n_nuggets,a,b,c) if 6*a+9*b+20*c==n_nuggets: return [a,b,c] return [] for n_nuggets in range(50): if (can_buy(n_nuggets) and can_buy(n_nuggets+1) and can_buy(n_nuggets+2) and can_buy(n_nuggets+3) and can_buy(n_nuggets+4) and can_buy(n_nuggets+5)): print n_nuggets - 1 break -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On Sat, Aug 14, 2010 at 8:52 AM, Baba raoul...@gmail.com wrote: my code is probably not elegant but a huge step forward from where i started: def can_buy(n_nuggets): for a in range (0,n_nuggets): for b in range (0,n_nuggets): for c in range (0,n_nuggets): #print trying for %d: %d %d %d % (n_nuggets,a,b,c) if 6*a+9*b+20*c==n_nuggets: return [a,b,c] return [] for n_nuggets in range(50): result1 = can_buy(n_nuggets) result2 = can_buy(n_nuggets+1) result3 = can_buy(n_nuggets+2) result4 = can_buy(n_nuggets+3) result5 = can_buy(n_nuggets+4) result6 = can_buy(n_nuggets+5) if result1!=[] and result2!=[] and result3!=[] and result4!=[] and result5!=[] and result6!=[]: if (n_nuggets+5)-n_nuggets==5: print n_nuggets-1 break i suppose this can be tweaked to make it shorter? For instance i wonder if i can do the same with less variable to be defined? Instead of calling can_buy() 6 times on every iteration of the main loop, I would suggest maintaining a list of the sequential results. Just call it once on each number of nuggets in order. If the number of nuggets is purchasable, and the list is empty or the last item in the list is the number of nuggets - 1, then append the number of nuggets to the list. If the last item in the list is not the number of nuggets - 1, then they're not sequential and you start a new list. When the length of the list reaches 6, you're done, and the answer is equal to the first item in the list - 1. You can also improve the can_buy() function by tightening up the loop limits. You don't need to go all the way up to n_nuggets on each loop. -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
Baba wrote: On Aug 13, 8:25 pm, Ian Kelly ian.g.ke...@gmail.com wrote: It's not. You're not just trying to find the sixth value that can be bought in exact quantity, but a sequence of six values that can all be bought in exact quantity. The integers [6, 9, 12, 15, 18, 20] are not sequential. Hi Ian, Thanks for stating the obvious. I obviously hadn't understood a fundamental part of the theorem which states that 6 SEQUENTIAL passes must be found! That's a good lesson learned and will help me in future exercises to make sure i understand the theory first. Thanks again! Ok so with your and News123's help (no offence to all others but i need to keep it simple at this stage)i was able to find the solution: 43 my code is probably not elegant but a huge step forward from where i started: def can_buy(n_nuggets): for a in range (0,n_nuggets): for b in range (0,n_nuggets): for c in range (0,n_nuggets): #print trying for %d: %d %d %d % (n_nuggets,a,b,c) if 6*a+9*b+20*c==n_nuggets: return [a,b,c] return [] for n_nuggets in range(50): result1 = can_buy(n_nuggets) result2 = can_buy(n_nuggets+1) result3 = can_buy(n_nuggets+2) result4 = can_buy(n_nuggets+3) result5 = can_buy(n_nuggets+4) result6 = can_buy(n_nuggets+5) if result1!=[] and result2!=[] and result3!=[] and result4!=[] and result5!=[] and result6!=[]: if (n_nuggets+5)-n_nuggets==5: print n_nuggets-1 break i suppose this can be tweaked to make it shorter? For instance i wonder if i can do the same with less variable to be defined? Increase the number of nuggets one by one and keep a count of the number of consecutive successes. If you can buy a number of nuggets exactly, increment the count, otherwise reset the count. When the count reaches 6 you know that you're at the end of a sequence of consecutive successes. -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On 8/14/2010 10:52 AM, Baba wrote: for n_nuggets in range(50): result1 = can_buy(n_nuggets) result2 = can_buy(n_nuggets+1) result3 = can_buy(n_nuggets+2) result4 = can_buy(n_nuggets+3) result5 = can_buy(n_nuggets+4) result6 = can_buy(n_nuggets+5) if result1!=[] and result2!=[] and result3!=[] and result4!=[] and result5!=[] and result6!=[]: if (n_nuggets+5)-n_nuggets==5: print n_nuggets-1 break i suppose this can be tweaked to make it shorter? For instance i wonder if i can do the same with less variable to be defined? [Other responders have covered a lots of the points I make below. I guess I need to be quicker!] First, congratulations on getting to a solution! Code can very often be made shorter, although it's not always worth your while to do so. And often, shorter code is less understandable code -- which makes a big difference if you need to revisit the code later on. Here are some things that can be done with your for-loop: 1. You don't need this if test, because it's always true: if (n_nuggets+5)-n_nuggets==5: 2. Whenever you find yourself inventing a series of variables like result1, result2, result3, etc., think about using a list instead. results = [] for i in range(6): results.append(can_buy(n_nuggets + i)) And to get really fancy, you can use a single list comprehension statement to do it all results = [can_buy(n_nuggets + i) for i in range(6)] 3. Your if statement tests whether all the lists are non-empty. In Python, expressions (a) and (b) are equivalent: (a) if result[0] != [] (b) if result[0] So your if test can be expressed as: if (result[0] and result[1] and result[2] and result[3] and result[4] and result[5]) (The parentheses are not required by if, but they *do* enable you to split the expression across two or more lines.) And you can use the all function to rescue this cumbersome statement; if all(results) After all this work, the code is getting pretty short: for n_nuggets in range(50): results = [can_buy(n_nuggets + i) for i in range(6)] if all(results): print n_nuggets-1 break 4. The variable results is defined in one statement, and then is used just once, in the very next statement. There's no harm in that, and I think it makes the mode easier to understand, but you can get rid of it: for n_nuggets in range(50): if all([can_buy(n_nuggets + i) for i in range(6)]): print n_nuggets-1 break But wait, there's more ... :-) So far, we've just refined the *implementation* of your algorithm. But the algorithm itself could use some work. * When n_nuggets==0, we compute can_buy(0), can_buy(1), can_buy(2), can_buy(3), can_buy(4), and can_buy(5). * When n_nuggets==1, we compute can_buy(1), can_buy(2), can_buy(3), can_buy(4), can_buy(5), and can_buy(6). ... and so on. We can use an algorithm in which can_buy(i) is computed just once for each value of i: can_buy_count = 0 n_nuggets = 0 while n_nuggets 50: if can_buy(n_nuggets): can_buy_count += 1 else: can_buy_count = 0 if can_buy_count == 6: print n_nuggets - 6 break else: n_nuggets += 1 And here's how you could shorten *this* code: ### cbc = can buy count cbc = 0 n_nuggets = -1 while n_nuggets 50: n_nuggets += 1 cbc = cbc+1 if can_buy(n_nuggets) else 0 if cbc == 6: print n_nuggets - 6 break HTH, John -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
Hi News 123, Ok i'm getting closer. I am able to write code that will output values that can be bought in exact quantity (truelist) and values that cannot be bought in exact quantities. For a range up to 29 i get this: true [6, 9, 12, 15, 18, 20, 21, 24, 26, 27, 29] false [0, 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28] the sixth value that passes the test of having an exact solution is 20 so that would mean that the last number i got that cannot be bought in exact quantity is 19 that doesn't seem quite right, does it? def can_buy(n_nuggets): for a in range (0,n_nuggets): for b in range (0,n_nuggets): for c in range (0,n_nuggets): #print trying for %d: %d %d %d % (n_nuggets,a,b,c) if 6*a+9*b+20*c==n_nuggets: return True return False truelist=[] falselist=[] for n_nuggets in range(30): result = can_buy(n_nuggets) if result==True: truelist=truelist+[n_nuggets,] else: falselist=falselist+[n_nuggets,] print 'true',truelist print 'false',falselist tnx Baba -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
Hi News 123, Ok i'm getting closer. I am able to write code that will output values that can be bought in exact quantity (truelist) and values that cannot be bought in exact quantities. For a range up to 29 i get this: true [6, 9, 12, 15, 18, 20, 21, 24, 26, 27, 29] false [0, 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28] the sixth value that passes the test of having an exact solution is 20 so that would mean that the last number i got that cannot be bought in exact quantity is 19 that doesn't seem quite right, does it? def can_buy(n_nuggets): for a in range (0,n_nuggets): for b in range (0,n_nuggets): for c in range (0,n_nuggets): #print trying for %d: %d %d %d % (n_nuggets,a,b,c) if 6*a+9*b+20*c==n_nuggets: return True return False truelist=[] falselist=[] for n_nuggets in range(30): result = can_buy(n_nuggets) if result==True: truelist=truelist+[n_nuggets,] else: falselist=falselist+[n_nuggets,] print 'true',truelist print 'false',falselist tnx Baba -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On Fri, Aug 13, 2010 at 12:25 PM, Baba raoul...@gmail.com wrote: Hi News 123, Ok i'm getting closer. I am able to write code that will output values that can be bought in exact quantity (truelist) and values that cannot be bought in exact quantities. For a range up to 29 i get this: true [6, 9, 12, 15, 18, 20, 21, 24, 26, 27, 29] false [0, 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28] the sixth value that passes the test of having an exact solution is 20 so that would mean that the last number i got that cannot be bought in exact quantity is 19 that doesn't seem quite right, does it? It's not. You're not just trying to find the sixth value that can be bought in exact quantity, but a sequence of six values that can all be bought in exact quantity. The integers [6, 9, 12, 15, 18, 20] are not sequential. -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On 8/13/2010 6:25 AM, Roald de Vries wrote: 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. Oops -- sorry for the erroneous attribution, Roald. -John -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
Hi BAba, On 08/13/2010 09:25 PM, Ian Kelly wrote: On Fri, Aug 13, 2010 at 12:25 PM, Baba raoul...@gmail.com wrote: Hi News 123, Ok i'm getting closer. I am able to write code that will output values that can be bought in exact quantity (truelist) and values that cannot be bought in exact quantities. For a range up to 29 i get this: true [6, 9, 12, 15, 18, 20, 21, 24, 26, 27, 29] false [0, 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28] the sixth value that passes the test of having an exact solution is 20 so that would mean that the last number i got that cannot be bought in exact quantity is 19 that doesn't seem quite right, does it? As Thomas says: It's not. You're not just trying to find the sixth value that can be bought in exact quantity, but a sequence of six values that can all be bought in exact quantity. The integers [6, 9, 12, 15, 18, 20] are not sequential. Six True values in a row without a False value n between tells you, that you can stop searching. So you that's what you have to write A piece of code, which fetches true fals values for 0 to e.g. 200 nuggets and stops if you had 6 True values in a row. Think how you do it manually: you can try this even without the can_buy function and plug in th can_buy() function only if you ahve your detection of 6 True values in a row working. test_sequence = 0010011011101110011101 # below I use the enumerate function. # rather useful for going through a list AND having a counter value. # when plugging in your function you can switch back to # for n_nuggets in xramge(200): # perhaps here some initialisation for your searching for i, a_char in enumerat(test_suequence): print entry %2d (%s) is %s % (i,a_char,result) result = a_char == '1' # result is now true for a '1' # and false for a '0' # here some code to determine the length of the sequence if sequence_length == 6: print I found a sequence of 6 and can stop searching print my solution is -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
Baba wrote: 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 for mcNugget in range(0,10): sendTo(trashbin) You're welcome :p JM -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
Baba raoul...@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. -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
On Aug 12, 2010, at 11:33 AM, Paul Rubin wrote: Baba raoul...@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 -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
Roald de Vries wrote: div class=moz-text-flowed style=font-family: -moz-fixedOn Aug 12, 2010, at 11:33 AM, Paul Rubin wrote: Baba raoul...@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 -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
One more small tip to verify whether your code is working: On 08/12/2010 10:28 PM, News123 wrote: Hi Baba, Your code, but returning the result as suggested in my preious post: 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 [a,b,c] else: return [] # show the results for the first 50 numbers. # and verify whether it's true for n in xrange(50): result = can_buy(n) # get the result (see Brian's commen print(result of can_buy(%2d) is %s % (n,result)) if result: a,b,c = result if a*6+b*9+c*12 != n: print ERROR: can_buy() gives wrong result Alternatively you can use a nice python feature called asserts assert statements can be used to vrify whether your code works as expected. Nothing will be printed if the assertion is correct otherwise your program will abort and print the assertion error: Example: for n in xrange(50): result = can_buy(n) # get the result (see Brian's commen print(result of can_buy(%2d) is %s % (n,result)) if result: a,b,c = result assert a*6+b*9+c*12 == n 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
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) -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
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) -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
In message mailman.1996.1281605023.1673.python-l...@python.org, Jean- Michel Pichavant wrote: for mcNugget in range(0,10): sendTo(trashbin) Ah, but should that be mcNugget.sendTo(trashbin) or trashbin.insert(mcNugget) ? -- http://mail.python.org/mailman/listinfo/python-list
Re: looping through possible combinations of McNuggets packs of 6, 9 and 20
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 -- http://mail.python.org/mailman/listinfo/python-list
