Solution to ps2

[jetamors]

Putting my code for ps2 behind the cut. Please feel free to critique it, ask questions, or post your own code in the comments.

# ps2 for MIT OpenCourse 6.00 Introduction to Computing
# Written by Jetamors, January 2010

# Problems 1,3
# To do this exhaustive search, I'm using what are called nested for loops.
# In this case:
# a = number of 6-packs
# b = number of 9-packs
# c = number of 20-packs
# Then I put for-loops for a, b, and c inside each other. The code will start with
# a = 0, b = 0, c = 0 to see if it can find n (where n = the exact quantity we want).
# If that doesn't work, it'll go to a = 0, b = 0, c = 1, then a = 0, b = 0, c = 2,
# and so on.  The for loop will end when the total is bigger than n, since that means
# we've overshot our goal.
# Once c gets too high, we go on to a = 0, b = 1, c = 0, and go through again.
# Through doing this, the code will look at every possible combination of a, b, and c
# that results in a number of nuggets less than or equal to n.
#
# The exception is if we manage to hit n exactly, which is what we want to do.  In that case,
# we break out of all three for loops, and print the results.
# Below is problem 3, but my answer for problem 1 was very similar.
# For problem 1, I used n in range(50,66) to generate the answers for those values of n.  I
# also did *not* use the trueiter or largest variables for problem 1.

print "Problem 3\n"

nuggets = (6,9,20) # nugget pack sizes

trueiter = 0 # this variable is incremented every time an exact quantity can be purchased,
             # but is reset to zero if an exact quantity cannot be purchased.
for n in range(1,58):   # n is the exact quantity we want to purchase
    found = False # this variable becomes true when we find an exact quantity.
    for a in range (0,n/nuggets[0]+1):          # a = number of 6-packs
        for b in range (0,n/nuggets[1]+1):      # b = number of 9-packs
            for c in range (0,n/nuggets[2]+1):  # c = number of 20-packs
                solution = nuggets[0]*a + nuggets[1]*b + nuggets[2]*c   # solution is the total quantity if we purchase these numbers of packs
                if solution == n:
                    found = True
                    trueiter += 1   # for problem 1, comment this out.
                    break
            if found == True:
                break
        if found == True:
            break
    if found == True:
        print "To get",n,"nuggets, you can buy",a,"6-packs,",b,"9-packs, and",c,"20-packs.\n"
    if found == False:
        trueiter = 0    # for problem 1, comment this out.
        largest = n     # for problem 1, comment this out
        print n,"nuggets cannot be bought in exact quantity.\n"
    if trueiter == 6:  # for problem 1, comment this out.
        break

print "The largest number of nuggets that can't be purchased in exact quantity is "+repr(largest)+".\n"


# Problem 4
# This code is pretty much the same as problem 3. The main difference is that now we want n in range(1,200), and
# the output is of course different.

print "Problem 4\n"

nuggets = (7,9,17) # nugget pack sizes; you can alter this however you like.  (Tuples do NOT take user input though.)

trueiter = 0
for n in range(1,200):
    found = False
    for a in range (0,n/nuggets[0]+1):
        for b in range (0,n/nuggets[1]+1):
            for c in range (0,n/nuggets[2]+1):
                abc = [a,b,c]
                solution = nuggets[0]*a + nuggets[1]*b + nuggets[2]*c
                if solution == n:
                    found = True
                    trueiter += 1
                    break
            if found == True:
                break
        if found == True:
            break
    # if found == True:
        # print "To get",n,"nuggets, you can buy",a,"6-packs,",b,"9-packs, and",c,"20-packs.\n"
    if found == False:
        trueiter = 0
        largest = n
        # print n,"nuggets cannot be bought in exact quantity.\n"
    if trueiter == 6:
        break

print "Given package sizes "+repr(nuggets[0])+", "+repr(nuggets[1])+", and",
print repr(nuggets[2])+", the largest number of nuggets that can't be purchased in exact quantity is "+repr(largest)+"."

(Also a question: when I have a really long print statement like this, how do I break it up so it doesn't stretch the screen? I looked through some of the documentation, but I couldn't find anything on it.) ETA: Figured it out and updated my code :)

Comments

[aranthe]

Umm...I think that last one isn't quite right. It stops at 22, but there's no solution at 29, either. You can prove this on paper with a sieve or by changing the "6" in trueiter == 6 to a larger number, so that it continues long enough to find the next value that doesn't have a solution.

I could be wrong—I can only prove this to myself by showing it—but I think the smallest number of consecutive solutions required to find the last non-solution is bound to the smallest coefficient.

[aranthe]

To expand on that last paragraph: If x is the smallest coefficient, it makes sense that once you find x number of consecutive solutions, you will have ability to create all solutions after that, since doing so merely requires that you add x to each of the previous solutions. Whether you need at least x number is what I haven't formally proven, but using an equation where the smallest coefficient is greater than 6 and the largest one is relatively large by comparison shows that it requires more than 6 consecutive solutions to find the last number that doesn't have one.

[jetamors]

Oh, you're probably right! I hadn't even really thought about that part. I'm at work so I can't field-test, but I guess you could rewrite that statement as

if trueiter == nuggets[0]:

Or... is there a way to select the smallest value in a tuple? I'm sure there is.

[aranthe]

Or... is there a way to select the smallest value in a tuple? I'm sure there is.

Yes, you can use the sorted function on a tuple:

myTuple = 3, 1, 2
sortedList = sorted(myTuple)

When you use sorted on a tuple, it returns a sorted list of the tuple's elements. Then all you have to do us peel off index 0, as you did above.