Question

Question about PSET2, Problem 3:

I've been stuck on this for a while: I think the underlying logic may be wrong.

The intention was keep count for numbers (intN) that do not have a solution.

When the count reaches 6, it would tell give the associated number of nuggets.

The problem is that this does not identify consecutive FALSE results.

Technically, the range function (1, x) with (x+1) doesn't work. Putting in an arbitrary range feels wrong, and also having to call x as a global value seems wrong too.

http://pastebin.com/zLnBTwr7

All help = Muchos Gracias!

Answer 1

You are on the right track, but it seems like you didn't understand when you should exit the while loop. Look for the mathematical relation in the problem set pdf and read it carefully; it should help you more :-)

Answer 2

@BMP, Thanks for the encouragement. To be honest, I don't really understand why the theorem is true to begin with -

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.

Does anyone have some explanation/idea?

In anycase, this is an updated code... abstractly, it seems to work now, but it may be wrong because im not sure what the theorem is about to begin with... le sigh!

http://codepad.org/4yoYeeTm

Answer 3

What the theorem is stating is that if there exists a sequence of 6 consecutive sizes such that each size is solvable, then any size bigger than the first size in the sequence is solvable (suppose, for simplicity, that 10, 11, 12, 13, 14, 15 are solvable. Then, as the theorem implies, every size bigger than 10 is solvable, no need to check those). Again, you are on the right track, you got the idea behind the solution, but you need to tweak your solution a bit still. Why not all solutions are output? Solve this issue, and you will likely have a working solution

Answer 4

If n is buyable, then n+6, n+9, and n+20 are buyable, because you just add another 6-, 9-, or 20-piece package. If n through n+5 are buyable, then n+6 through n+11 are buyable, because you just add another 6-piece package to each of them. So, once you find a group of 6 consecutive buyable numbers, you know the next set of six are buyable, and the last unbuyable number you found will be the last possible unbuyable number.

Answer 5

Wakarimapelleta! ok, the problem I had was understanding that X was an absolute value in relation to the set (6, 9 and 20). *slaps forehead* thanks everyone!

Anyway, massaged the code with this new understanding... answer is 61. Oui/non? And. Was thinking, wouldn't it be possible to do this with lists instead? Anyone tried that before? That way, the values are stored after each iteration so one can reuse it.

http://codepad.org/ekp9Tngl

Answer 6

At least my code's output is 43, rather than 61. At least, 61 is still solvable for (6,9,20) [2 * 20 + 1 * 9 + 2 * 6]. And using lists is pretty good, I implemented this way (and I think most of the answers I saw around here also use lists).
Your code's idea is fine, there are two subtle errors. See if you can find them :-), but they should be easy fix.