### Solution to ps2

Jan. 24th, 2010 08:13 pm**jetamors**posting in

**intro_to_cs**

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

~~(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 :)

# 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)+"."

## no subject

Date: 2010-01-27 03:09 pm (UTC)arantheUmm...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

to a larger number, so that it continues long enough to find the next value that doesn't have a solution.trueiter== 6I could be wrong—I can only prove this to myself by showing it—but I

thinkthe smallest number of consecutive solutions required to find the last non-solution is bound to the smallest coefficient.## no subject

Date: 2010-01-27 03:49 pm (UTC)arantheTo expand on that last paragraph: If

xis the smallest coefficient, it makes sense that once you findxnumber of consecutive solutions, you will have ability to create all solutions after that, since doing so merely requires that you addxto each of the previous solutions. Whether you needat leastxnumber 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.## no subject

Date: 2010-01-27 07:24 pm (UTC)jetamorsOr... is there a way to select the smallest value in a tuple? I'm sure there is.

## no subject

Date: 2010-01-28 04:55 pm (UTC)arantheYes, you can use the

`sorted`

function on a tuple: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.