Problem Set 2

#Function Purpose: To test if the number of nuggets is evenly divisible by any
#                  of the packs sold

#Function Operations:  iterates through the tuple containing the nugget packs,
#                      each time checking to see if the number of nuggets is
#                      divisible by the pack, if it is, then it returns True,
#                      otherwise, it returns False
def divisibilityTester(factorsTuple, integer_test):
  for n in factorsTuple:
    if integer_test%n == 0:
      return True
  return False

#Function Purpose:  To generate a list of all possible results of the purchases
#                   of nuggets  (like how 37 nuggets can be subtracted down,
#                   using a pack of 9, to 28, then to 8 using a pack of 20)
#                   Similar to branching:  (example uses packs of 6, 9, and 20)
#                                                28
#                                       /          |        \
#                                      8           19       22
#                                     /  |  \   /  |  \   /  |  \
#                                   -12  -1  2  -1 10 13  2  13 16
#NC = Not counted (due to negativity)
#                                    NC  NC     NC
#Tree not completed yet, its just an example of the first steps taken

#Function Operations:  Takes the starting list (passed to it by another function
#                      , in this case "chickenTester") and iterates through it.
#                      During each iteration the function iterates through the
#                      packs tuple, each time appending (if the result is
#                      non-negative) the difference between the element,
#                      and each individual pack from the tuple.  Finally, it
#                      returns the list of possible non-negative results from
#                      purchases of nugget packs.
def listMaker(quantityTuple, startingList):
  for element in startingList:
    if element > 0:
      for quantity in quantityTuple:
        if element - quantity > 0:
          startingList.append(element - quantity)
  return startingList
#Function Purpose:  To use the output of the other two functions to judge whether
#                   or not it is possible to purchase any given number of
#                   in an exact quantity

#Function Operations:  Takes the packs tuple and the number of nuggets in
#                      question as input.  Tests whether or not the nuggets in
#                      question are able to be bought using just one type of
#                      pack using the divisibilityTester function.  Returning
#                      True if it is.  If the purchase isn't so simple, it checks
#                      each element of the possibilities list to see if it is
#                      divisible by any of the packs (using divisibilityTester).
#                      If no evenly divisible solutions exist, then it returns
#                      false
def chickenTester(quantityTuple, testQuantity):
  if divisibilityTester(quantityTuple, testQuantity) == True:
    return True
  else:
    for possibility in listMaker(quantityTuple, [testQuantity]):
      if divisibilityTester(quantityTuple, possibility) == True:
        return True
  return False


#Function Purpose:  To collect and provide sufficient information to the other
#                   functions, and to use the other functions to solve the prompt


#Function Operations:  Sets the biggestSoFar counter (as suggested by the template)
#                      and then uses the range (as provided by the template) to
#                      perform a check on every quantity to find the largest
#                      non-purchasable number of nuggets.
def main():
  pack1 = int(raw_input("What is the 1st available pack?"))
  pack2 = int(raw_input("What is the 2nd available pack?"))
  pack3 = int(raw_input("What is the 3rd available pack?"))

  biggestSoFar = 0
  for n in range(1,150):
    if chickenTester((pack1,pack2,pack3), n) == False:
      biggestSoFar = n
  print "Given package sizes", pack1, ",", pack2, ", and", pack3, ", the largest number of McNuggets that cannot be bought in exact quantity is: ", biggestSoFar


#Boilerplate code to initiate main() on startup
if __name__ == '__main__':
  main()
#Largest non-purchasable number of nuggets that this program finds is 43