Question

Hey guyz,

I'm working on the 2nd problem set and think I found a general solution for problem 4.

http://codepad.org/uoQPkTvN

I used lists instead of tuples and ignored the template the profs gave. Got one question though:

The code goes produces a blank response when I think it shouldn't. For example: if x = 7, y = 33, and z = 57, nothing prints out, but, when I increase the xrange from 150 to 200, I get an answer that is under 150 (116 to be specific). Since 7 + 116 < 150, I'm not sure why this is breaking. Thoughts?

Answer 1

Here is the output of my version for the same problem:
Given package sizes < 7 >, < 33 >, and < 57 >, the largest number of McNuggets that cannot be bought in exact quantity is < 116 >
So it confirms the second output of your program (it's always a relief!)

I tried your code, modifying it just a little bit to make it more easy to change the top number tested.
http://codepad.org/mOhOQNFq

Just to show how I found the solution, I'll give you the different tries I made.

First, after the line #reset mc nuggets, I inserted the following:
print n, n_count
Running the program with the values 150 and 200, I noted that with top_number = 150, n_count was reseted to 0 for n == 121, ie the program didn't find a solution for 121 although 121 = 2 * 57 + 7...
But with top_number = 200, it did find the solution for 121

So the next step is: why doesn't it find the answer for 121 with top_number = 150 ?
I inserted the following code:
if n == 121: print a,b,c
after the line mcnugz = mcnugz + [x*a + y*b + z*c]
The goal is to make the program print all the tries it does. I tried again with top_number = 150 and top_number = 200. I noted that with_top_number = 150, it does not try with c = 2 and thus doesn't find the answer. And it's easy to understand since c is in the range 0 to 150 / 57 = 2, with 2 not included ! But 200 / 57 = 3 so 2 is tested.
Now it's easy to see that the bug is xrange(0,top_number/z) that should be changed into xrange(0,top_number/z + 1). Obviously, the same is true for x and y.

Hope it wasn't too long !

Answer 2

GAH, brilliant. i thiiink i just got pwnd, but appreciatively pwnd. Thanks for your time with this.

Answer 3

I don't think anybody sees this as competitive. You are doing very well. I am kind of struggling, but I hope to be able to code this well soon.