Blog :: Ask an Expert - I'm wising up
3 November 2012
After discovering that I was answering somebody else's test questions for them yesterday I'm less likely to answer questions like:
McDonald’s sells Chicken McNuggets in packages of 6, 9 or 20 McNuggets. Thus, it is possible, for example, to buy exactly 15 McNuggets (with one package of 6 and a second package of 9), but it is not possible to buy exactly 16 McNuggets, since no non- negative integer combination of 6's, 9's and 20's add up to 16. To determine if it is possible to buy exactly n McNuggets, one has to find non-negative integer values of a, b, and c such that 6a + 9b + 20c = n
Write a function, called McNuggets that takes one argument, n, and returns True if it is possible to buy a combination of 6, 9 and 20 pack units such that the total number of McNuggets equals n, and otherwise returns False. Hint: use a guess and check approach.
Do your own work, people! I'll give you a hint myself - the time spent figuring out how to figure out the problem is the point! And just jumping to the solution doesn't actually do you any favors... But I'll give you one more clue by discussing how I might approach the problem.
I'm tempted to just brute-force it. An answer is going to end up having an 'a', 'b', and 'c' variable that each ranges from 0 to ... well to what number? Given an answer n we can just say the top range for any variable will be n/associated_constant. To take a for instance - the maximum value a can have is going to be n/6 - otherwise we'd be exceeding the number n even if b and c are both zero.
And if I can easily calculate max_a, max_b , and max_c I can use the itertools.product to make a list of all the combinations of a, b, and c that could possibly be valid. For intance if our number n was 20 then max_a is 3, max_b is 2, and max_c is 1. And
>>> list(itertools.product(range(3+1), range(2+1), range(1+1))) [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (0, 2, 0), (0, 2, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1), (1, 2, 0), (1, 2, 1), (2, 0, 0), (2, 0, 1), (2, 1, 0), (2, 1, 1), (2, 2, 0), (2, 2, 1), (3, 0, 0), (3, 0, 1), (3, 1, 0), (3, 1, 1), (3, 2, 0), (3, 2, 1)]
Hmm. Then if only I knew some way to transform an input list of three-tuples of the form of (a, b, c) into an output list of numbers I could just check and see if n was in the list! Hint again - try a list comprehension or map. Ok - that's all the help I'm giving!
Related tags: python
blog comments powered by Disqus