Problem Set 2

[elz]

Post and discuss your answers in the comments! (And yay for everybody who posted problem set 1 answers!)

Comments

Problem #4

[elz]

This is my answer to #4, which is a lot like my answer to #3:

# Takes a tuple of three package sizes and a number of nuggets    
# Returns True or False depending on whether the exact
# given number of McNuggets can be purchased
def divisible_by_mcnuggets(packages, nuggets):
    # We shouldn't bother trying numbers that are greater than the
    # total number we're looking for. For example, if the total number
    # of nuggets is 50 and one of the packages contains 20 nuggets, we'll
    # never want more than 2 of them      
    maximum_a = nuggets/packages[0] + 1
    maximum_b = nuggets/packages[1] + 1
    maximum_c = nuggets/packages[2] + 1
    # Loop through all possible combinations of the three package sizes
    # from 0 to the maximum
    for a in range(0, maximum_a):
        for b in range(0, maximum_b):
            for c in range(0, maximum_c):
                if (packages[0]*a) + (packages[1]*b) + (packages[2]*c) == nuggets:
                    return True
    return False

# Prints the largest number of McNuggets that can't be bought up to 150
# for a given set of 3 package sizes 
def diophantine_mcnuggets():
    bestSoFar = 0           # variable that keeps track of largest number
                            # of McNuggets that cannot be bought in exact quantity
    packages = (6,9,20)     # variable that contains package sizes
    consecutive_divisibles = []
    while len(consecutive_divisibles) < 6:
        for n in range(1, 150): # only search for solutions up to size 150
            if divisible_by_mcnuggets(packages, n) == True:
                consecutive_divisibles.append(n)
            else:
                consecutive_divisibles = []
                bestSoFar = n         
    print "Given package sizes %i, %i, and %i, the largest number of McNuggets that cannot be bought in exact quantity is: %i" % (packages[0], packages[1], packages[2], bestSoFar)


diophantine_mcnuggets()

Re: Problem #4

[elz]

And to nitpick myself, I should have changed the line from:

while len(consecutive_divisibles) < 6:

to:

while len(consecutive_divisibles) < packages[0]:

Re: Problem #4

[(Anonymous)]

ELZ - My script wound up being very similar to yours. I couldn't figure out how to stop looking after 6 consecutive successful results, so I just put all successful results in a list. I then looked for numbers not in that list and used the highest number that was missing. I'm not sure if I'm happy to find this thread AFTER I finally figured it out (hours), or if I'm glad I didn't because I think I learned more.....

## This program looks for the maximum number that can't be
## created using combinations of package sizes.


# variables - change to manipulate how what numbers to try and max range
# to try within. If the result is close to your max range, you should
# probably increase the range.
packages = [6,9,20] # variable that contains package sizes
n = range(0, 201) # range to test within. Max number must be at least TWO more than expected result.

# tests all possible combinations. Saves numbers that were successfully computed to numworks.
numworks = []
for count in n:
for a in range(0, count/packages[0]+1): #instead of using all combinations, only combinations that
# wouldn't be higher than max range (so max range divided by package size). Adding one because
# of remainders. This cuts WAY down on the time to process the program vs just using "range (0, count)"
for b in range(0, count/packages[1]+1):
for c in range(0, count/packages[2]+1):
if ((a*packages[0] + b*packages[1] + c*packages[2]) == count):
numworks = numworks + [count]

### found that entire section is not needed to get correct results. It makes numworks look nicer, but isn't needed.
### Sort then Remove duplicates from numworks
##cycle = 0
##if numworks:
## numworks.sort()
## last = numworks[-1]
## for i in range(len(numworks)-2, -1, -1):
## if last == numworks[i]:
## del numworks[i]
## else:
## last = numworks[i]

# create numbad which is list of numbers that didn't work. This is based on numbers that are not in numworks.
numbad = [0]
for ii in range (0,numworks[-1]):
if ii not in numworks:
numbad = numbad + [ii]

# prints results. Also accounts for no results.
if numbad == [0]:
print "No numbers were generated. \nYou likely used a 1 (one) or a negitive number as a package size."
else:
print "Given package sizes %i, %i, and %i, the largest number of McNuggets that \ncannot be bought in exact quantity is: %i. \n \n*** Note: the highest number tested was %i ***" % (packages[0], packages[1], packages[2], numbad[-1], n[-1])