Quiz 2

#1)  Is each of the following True or False 
    1.1. A greedy algorithm can be used to solve the 0-1 knapsack optimization problem. 
	FALSE

    1.2. Dynamic programming can be used to solve optimization problems where the size of the space of possible solutions is exponentially large.
	TRUE

    1.3. Dynamic programming can be used to find an approximate solution to an optimization problem, but cannot be used to find a solution that is guaranteed to be optimal.
	FALSE

    1.4. In Python, an instance of a class is an object, but a class itself is not.
	FALSE

    1.5. In Python, a subclass can override a function definition contained in a super class.
	TRUE

    1.6. Decision trees are always binary.
	FALSE

#2) Provide code implementing a Python function that meets the specification below. 

def findMedian(L):
    """
	Finds median of L.
	L: a non-empty list of floats
	Returns: If L has an odd number of elements, returns the median element of L.  For example, if L is the list [15.0, 5.3, 18.2], returns 15.0.

	If L has an even number of elements, returns the average of the two median elements. For example, if L is the list [1.0, 2.0, 3.0, 4.0], returns 2.5.

	If the list is empty, raises a ValueError exception.

	Side effects: none.
	"""
	try:
		if len(L) < 1:
			raise exception 
		L_middle = len(L) / 2
		L_sorted = sorted(L)
		if len(L) % 2 == 0:		#	even case
		    median = (L_sorted[L_middle] + L_sorted[L_middle+1]) / 2
		else:
		    median = L_sorted[L_middle]
		return median
	except ValueError:
		print "L ValueError"

#3) What does the following code print? 

    class Shape(object):
        def __cmp__(s1, s2):
            return cmp(s1.area(), s2.area())
    class Square(Shape):
        def __init__(self, h):
            self.side = float(h)
        def area(self):
            return self.side**2
        def __str__(self):
            return 'Square with side ' + str(self.side)
    class Circle(Shape):
        def __init__(self, radius):
            self.radius = radius
        def area(self):
            return 3.14159*(self.radius**2)
        def __str__(self):
            return 'Circle with radius ' + str(self.radius)

	def f(L):
		if len(L) == 0: return None
		x = L[0]
		for s in L:
			if s >= x:
				x = s
		return x
        
	s = Square(4)						# Create a square, s, with height 4
	print s.area()						# Print area of s = 16
	L = []								# Create list L
	shapes = {0:Circle, 1: Square}		# Create dictionary with two keys.
	for i in range(10):					# loop ten times
		L.append(shapes[i%2](i))		# add objects from shapes dictionary L list
	print L[4]							# "Circle with radius 4"
	print f(L)							# "Circle with radius 8"

16.0
Circle with radius 4
Circle with radius 8


4)  The following two formulas can be used to formalize a 0-1 knapsack problem. 
        1) See handout.         2) See handout. 
    
    4.1) What do each of n, pi, xi, wi, and C represent? 
		Beats me.

    4.2) Use the formulas (refer to them as “formula 1” and “formula 2”) to 
        describe the optimization problem to be solved. 
		No idea.

#5. Write pseudo code describing merge sort.
	def msort(L):
		sorted = []
		La = L[,l/2]
		Lb = L[l/2,]
		La = msort(La)
		Lb = msort(Lb
		
		
		for each in range La:
			if La > Lb:
				sorted.append(La)
			else:
				sorted.append(Lb)
		return sorted
		
	

#6)  Consider the two functions specified below that are used to play a “guess a number game.” 

def cmpGuess(guess): 
    """
    Assumes that guess is an integer in range(maxVal).
    returns -1 if guess is < than the magic number, 0 if it is equal to the    magic number and 1 if it is greater than the magic number.
    """ 

def findNumber(maxVal): 
    """
    Assumes that maxVal is a positive integer.  Returns a number, num, such that 
cmpGuess(num) == 0.
    """
	num = maxVal / 2
	if cmpGuess(num) == 0:
		return num
	elif cmpGuess(num) == -1:
		return num / 2
	else:


    Write a Python implementation of findNumber that guesses the magic number defined by 
cmpGuess.  Your program should have the lowest time complexity possible. (20 points) 

# 6.00 Problem Set 9
#
# Name:  Scott Brenner
# Collaborators: None
# Time:

from string import *

class Shape(object):
    def area(self):
        raise AttributeException("Subclasses should override this method.")
    

class Square(Shape):
    def __init__(self, h):
        """
        h: length of side of the square
        """
        self.side = float(h)
    
    def area(self):
        """
        Returns area of the square
        """
        return round(self.side**2)
    
    def __str__(self):
        return 'Square with side ' + str(self.side)
    
    def __eq__(self, other):
        """
        Two squares are equal if they have the same dimension.
        other: object to check for equality
        """
        return type(other) == Square and self.side == other.side
    

class Circle(Shape):
    def __init__(self, radius):
        """
        radius: radius of the circle
        """
        self.radius = float(radius)
    
    def area(self):
        """
        Returns approximate area of the circle
        """
        return round(3.14159*(self.radius**2))
    
    def __str__(self):
        return 'Circle with radius ' + str(self.radius)
    
    def __eq__(self, other):
        """
        Two circles are equal if they have the same radius.
        other: object to check for equality
        """
        return type(other) == Circle and self.radius == other.radius
    

#
# Problem 1: Create the Triangle class
#
## TO DO: Implement the `Triangle` class, which also extends `Shape`.

class Triangle(Shape):
    def __init__(self, base, height):
        """
        base: length of base.
        height: height of triangle
        """
        self.base = float(base)
        self.height = float(height)
    
    def area(self):
        """
        Returns approximate area of the triangle 
        """
        return round(.5 * self.base * self.height,2)
    
    def __str__(self):
        """
        Describes this intance of Triangle.
        """
        return 'Triangle with a base of %0.2f and height of %0.2f.' % (self.base, self.height)
    
    def __eq__(self, other):
        """
        Two triangles are equal if they have the same base and height.
        other: object to check for equality
        """
        return type(other) == Triangle and self.base == other.base and self.height == other.height
    

#
# Problem 2: Create the ShapeSet class
#
## TO DO: Fill in the following code skeleton according to the
##    specifications.

class ShapeSet:
    def __init__(self):
        """
        Initialize any needed variables
        """
        ## TO DO
        self.members = []
        self.index = 0
    
    def addShape(self, sh):
        """
        Add shape sh to the set; no two shapes in the set may be
        identical
        sh: shape to be added
        """
        ## TO DO
        if sh not in self.members:
            self.members.append(sh)
            # print sh, "added to set."
    
    def __iter__(self):
        """
        Return an iterator that allows you to iterate over the set of
        shapes, one shape at a time
        """
        ## TO DO
        for i in self.members:
            yield i
    
    def __str__(self):
        """
        Return the string representation for a set, which consists of
        the string representation of each shape, categorized by type
        (circles, then squares, then triangles)
        """
        ## TO DO
        my_string = ""
        for each in self.members:
            # print each
            my_string += str(each) + "\n"
        return my_string
    
    


#
# Problem 3: Find the largest shapes in a ShapeSet
#
def findLargest(shapes):
    """
    Returns a tuple containing the elements of ShapeSet with the largest area.
    
    shapes: ShapeSet
    
    This is a sorting problem
    """
    result = (0,)
    for each in shapes:
        try:
            if each.area() > result[-1].area():
                result = (each,)
            elif each.area() == result[-1].area():
                result += (each,)
        except AttributeError:
            result = (each,)
    return result

#
# Problem 4: Read shapes from a file into a ShapeSet
#

SHAPES_FILENAME = "shapes.txt"

def readShapesFromFile(filename):
    """
    Retrieves shape information from the given file. Creates and returns a ShapeSet with the shapes found. 
    
    filename: string
    """
    ## TO DO
    inFile = open(filename, 'r', 0)
    shape_set = ShapeSet()
    for line in inFile:
        obj_para = line.split(",")
        if obj_para[0] == "circle":
            shape = Circle(obj_para[1])
        if obj_para[0] == "square":
            shape = Square(obj_para[1])
        if obj_para[0] == "triangle":
            shape = Triangle(obj_para[1],obj_para[2])
        shape_set.addShape(shape)
    return shape_set

my_ss = readShapesFromFile(SHAPES_FILENAME)
print my_ss

# my_circle = Circle(2)
# my_square = Square(4)
# my_square2 = Square(1)
# my_triangle = Triangle(1,1)
# 
# my_shapeset = ShapeSet()
#print len(my_shapeset.members)
# 
# print my_triangle
# print my_triangle.area()
# print your_triangle == my_triangle
# print your_triangle == her_triangle
# your_triangle.base = 45
# print my_triangle


# my_shapeset.addShape(Circle(2.25676))
# my_shapeset.addShape(Square(4))
# my_shapeset.addShape(Square(1))
# my_shapeset.addShape(Triangle(1,1))
# 
# print my_shapeset
#print my_shapeset.next()
# print my_shapeset.index
# print my_shapeset.next()
# print my_shapeset.index

#print my_shapeset.__str__()

# findLargest(my_shapeset)
#sorted(my_shapeset.members, key=my_shapeset.area())

def testFindLargest():
    ss = ShapeSet() 
    ss.addShape(Triangle(1.2,2.5)) 
    ss.addShape(Circle(4)) 
    ss.addShape(Square(3.6)) 
    ss.addShape(Triangle(1.6,6.4)) 
    ss.addShape(Circle(2.2)) 
    largest = findLargest(ss)
    print largest
    for e in largest: print e
    
    
    ss = ShapeSet()
    ss.addShape(Triangle(3,8)) 
    ss.addShape(Circle(1)) 
    ss.addShape(Triangle(4,6)) 
    largest = findLargest(ss) 
    print largest
    for e in largest:
        print e

def testSamenes():
    t = Triangle(6,6)
    c = Circle(1)
    ss = ShapeSet()
    ss.addShape(t)
    ss.addShape(c)
    largest = findLargest(ss)
    print largest
    print largest[0] is t
    print largest[0] is c

testFindLargest()

# 6.00 Problem Set 8
#
# Intelligent Course Advisor
#
# Name: Scott Brenner
# Collaborators: http://openstudy.com/studypads/Problem-Set-8-4c6bf092e6153a7f05c12e1e
# Time: problem 1: 20 minutes
#

import time
import string
from operator import itemgetter, attrgetter

SUBJECT_FILENAME = "my_subjects.txt"
SUBJECT_FILENAME = "subjects.txt"
VALUE, WORK = 0, 1

#
# Problem 1: Building A Subject Dictionary
#
def loadSubjects(filename):
    """
    Returns a dictionary mapping subject name to (value, work), where the name
    is a string and the value and work are integers. The subject information is
    read from the file named by the string filename. Each line of the file
    contains a string of the form "name,value,work".
    
    returns: dictionary mapping subject name to (value, work)
    """
    result = {}
    inputFile = open(filename)
    
    for line in inputFile:
        line = line.strip()
        line_as_list = line.split(',')
        result[line_as_list[0]] = (int(line_as_list[-2]),int(line_as_list[-1])) 
    return result
            
    # TODO: Instead of printing each line, modify the above to parse the name,
    # value, and work of each subject and create a dictionary mapping the name
    # to the (value, work).

def printSubjects(subjects):
    """
    Prints a string containing name, value, and work of each subject in
    the dictionary of subjects and total value and work of all subjects
    """
    totalVal, totalWork = 0,0
    if len(subjects) == 0:
        return 'Empty SubjectList'
    res = 'Course\tValue\tWork\n======\t====\t=====\n'
    subNames = subjects.keys()
    subNames.sort()
    for s in subNames:
        val = subjects[s][VALUE]
        work = subjects[s][WORK]
        res = res + s + '\t' + str(val) + '\t' + str(work) + '\n'
        totalVal += val
        totalWork += work
    res = res + '\nTotal Value:\t' + str(totalVal) +'\n'
    res = res + 'Total Work:\t' + str(totalWork) + '\n'
    print res

def cmpValue(subInfo1, subInfo2):
    """
    Returns True if value in (value, work) tuple subInfo1 is GREATER than
    value in (value, work) tuple in subInfo2
    """
    val1 = subInfo1[VALUE]
    val2 = subInfo2[VALUE]
    return  val1 > val2

def cmpWork(subInfo1, subInfo2):
    """
    Returns True if work in (value, work) tuple subInfo1 is LESS than than work
    in (value, work) tuple in subInfo2
    """
    work1 = subInfo1[WORK]
    work2 = subInfo2[WORK]
    return  work1 < work2

def cmpRatio(subInfo1, subInfo2):
    """
    Returns True if value/work in (value, work) tuple subInfo1 is 
    GREATER than value/work in (value, work) tuple in subInfo2
    """
    val1 = subInfo1[VALUE]
    val2 = subInfo2[VALUE]
    work1 = subInfo1[WORK]
    work2 = subInfo2[WORK]
    return float(val1) / work1 > float(val2) / work2

#
# Problem 2: Subject Selection By Greedy Optimization
#
def greedyAdvisor(subjects, maxWork, comparator):
    """
    Returns a dictionary mapping subject name to (value, work) which includes
    subjects selected by the algorithm, such that the total work of subjects in
    the dictionary is not greater than maxWork.  The subjects are chosen using
    a greedy algorithm.  The subjects dictionary should not be mutated.
    
    subjects: dictionary mapping subject name to (value, work)
    maxWork: int >= 0
    comparator: function taking two tuples and returning a bool
    returns: dictionary mapping subject name to (value, work)
    """    
    # TODO...
    #
    # Build function that sorts based on comparator returns list of subject names sorted by comparator criteria.
    #
    def sort(l, comparator) :
        """
        Sorts the list of subjects' names in descendig order
        acording to the comparator.
        """
        # print "l, comparator type:", type(l), type(comparator)
        # print 
        
        for i in range(1, len(l)) :
            value = l[i]
            j = i - 1
            done = False
            # print 'i, value, j', i, value, j
            # print
            while not done:
                # print "subjects[value], subjects[l[j]] type:", type(subjects[value]), type(subjects[l[j]])
                # print
                if comparator(subjects[value], subjects[l[j]]):
                    l[j+1] = l[j]
                    j -= 1
                    if j < 0 :
                        done = True
                else :
                    done = True
            l[j+1] = value
    #
    # Pick classes from top of sorted list until maxWork is reached
    #
    schedule_list = subjects.keys()
    #print 'schedule_list unsorted: ', schedule_list
    #print
    sort(schedule_list, comparator)
    # print 'schedule_list sorted: ', schedule_list
    #     print
    recommended_schedule = {}
    courseLoad = 0
    done = False
    for course in schedule_list:
        if subjects[course][1] <= maxWork - courseLoad:
            recommended_schedule[course] = subjects[course]
            courseLoad += subjects[course][1]
    return recommended_schedule


def bruteForceAdvisor(subjects, maxWork):
    """
    Returns a dictionary mapping subject name to (value, work), which
    represents the globally optimal selection of subjects using a brute force
    algorithm.
        
    subjects: dictionary mapping subject name to (value, work)
    maxWork: int >= 0
    returns: dictionary mapping subject name to (value, work) 
    """
    nameList = subjects.keys()
    tupleList = subjects.values()
    bestSubset, bestSubsetValue = \
            bruteForceAdvisorHelper(tupleList, maxWork, 0, None, None, [], 0, 0)
    outputSubjects = {}
    for i in bestSubset:
        outputSubjects[nameList[i]] = tupleList[i]
    return outputSubjects


counter = 0

def bruteForceAdvisorHelper(subjects, maxWork, i, bestSubset, bestSubsetValue, subset, subsetValue, subsetWork):
    # Hit the end of the list.
    if i >= len(subjects):
        if bestSubset == None or subsetValue > bestSubsetValue:
            # Found a new best.
            return subset[:], subsetValue
        else:
            # Keep the current best.
            return bestSubset, bestSubsetValue
    else:
        s = subjects[i]
        # Try including subjects[i] in the current working subset.
        if subsetWork + s[WORK] <= maxWork:
            subset.append(i)
            bestSubset, bestSubsetValue = bruteForceAdvisorHelper(subjects,
                    maxWork, i+1, bestSubset, bestSubsetValue, subset,
                    subsetValue + s[VALUE], subsetWork + s[WORK])
            subset.pop()
        bestSubset, bestSubsetValue = bruteForceAdvisorHelper(subjects,
                maxWork, i+1, bestSubset, bestSubsetValue, subset,
                subsetValue, subsetWork)
        return bestSubset, bestSubsetValue

#
# Problem 3: Subject Selection By Brute Force
#

def bruteForceTime():
    """
    Runs tests on bruteForceAdvisor and measures the time required to compute
    an answer.
    """
    # TODO...
    trial_work = [15]
    total_times = {}
    for each in trial_work:
        start_time = time.time()
        print bruteForceAdvisor(subjects,each)
        end_time = time.time()
        total_times[each] = round(end_time - start_time, 2)
    print total_times

# Problem 3 Observations
# ======================
#
# TODO: write here your observations regarding bruteForceTime's performance
# Th brute force function is very slow for even moderately large course loads.
   # For a maxLoad of  2: 0.01 seconds
                           # 4: 0.22
                           # 6: 1.76
                           # 7: 3.70
                           # 8: 11.42
                           # 9: 27.57
                           # 10: 122.58
                           # 11: 354.55
                           # 12: 778.29
                           # 13: 1714.95
                           # 14: 2907.09
                           # 14: 2850.40
       # Unreasonable depends on a multiple  factors, including the importance of the results and the quality of the results of a faster, less optimal function.  In this case the greedy function probably produces results that nearly as good as the results of the brute force method.
   #  Considering MIT costs ~$200k in tuition and room and board.  Perhaps a few minutes to optimize a semester course load is worth it. 
   


#
# Problem 4: Subject Selection By Dynamic Programming
#
def dpAdvisor(subjects, maxWork):
    """
    Returns a dictionary mapping subject name to (value, work) that contains a
    set of subjects that provides the maximum value without exceeding maxWork.
    
    subjects: dictionary mapping subject name to (value, work)
    maxWork: int >= 0
    returns: dictionary mapping subject name to (value, work)
    
    These are the results for running this full catalog:
    {8: 0.02, 10: 0.01, 45: 0.080000000000000002, 15: 0.02, 120: 0.23000000000000001, 90: 0.23000000000000001, 60: 0.11, 30: 0.050000000000000003}
        
    """
    # TODO...
    
    rec_dict = {}
    m = {}
        
    #   Build the work and value lists.
    work_list = []
    value_list = []
    key_list = []
    for each in subjects:
        work_list.append(subjects[each][1])
        value_list.append(subjects[each][0])
        key_list.append(each)
    
    # Build optimal list of courses to take.
    value, rec_list = dp_decision_tree(work_list,value_list,len(work_list)-1,maxWork,m)
    
    #   Build dictionary from list.
    for each in rec_list:
        rec_dict[key_list[each]] = (value_list[each],work_list[each])
    return rec_dict

def dp_decision_tree(w,v,i,aW,m):
    """
    Creates a course schedule that is optimized the maximum value.
    """
    
    ## check if value is already in the dictionary
    try: return m[(i,aW)]
    except KeyError:
        ##  Leaf/Bottom of the tree case decision
        if i == 0:
            if w[i] < aW:
                m[(i,aW)] = v[i], [i]
                return v[i],[i]
            else:
                m[(i,aW)] = 0, []
                return 0,[]
    
    ## Calculate with and without i branches
    without_i, course_list = dp_decision_tree(w,v,i-1,aW,m)
    if w[i] > aW:
        m[(i,aW)] = without_i, course_list
        return without_i, course_list
    else:
        with_i, course_list_temp = dp_decision_tree(w, v, i-1, aW - w[i], m)
        with_i += v[i]
    
    ## Take the branch with the higher value
    if with_i > without_i:
        i_value = with_i
        course_list = [i] + course_list_temp
    else:
        i_value = without_i
    
    ## Add this value calculation to the memo
    m[(i,aW)] = i_value, course_list
    return i_value, course_list
    


#
# Problem 5: Performance Comparison
#
def dpTime():
    """
    Runs tests on dpAdvisor and measures the time required to compute an
    answer.
    
    Prints total schedule, recommended schedule, time to complete each trial.
    """
    # TODO...
    trial_work = [8,10,15,30,45,60,90,120]
    total_times = {}
    for each in trial_work:
        print "Trial for max workload of %i." % each
        start_time = time.time()
        recommendation = dpAdvisor(subjects, each)
        end_time = time.time()
        total_times[each] = round(end_time - start_time, 2)
        printSubjects(recommendation)
    print total_times
    return
    
    

# Problem 5 Observations
# ======================
#
# TODO: write here your observations regarding dpAdvisor's performance and
# how its performance compares to that of bruteForceAdvisor.

subjects = loadSubjects(SUBJECT_FILENAME)
dpTime()

#print subjects
#print "Course Catalog"
#printSubjects(loadSubjects(SUBJECT_FILENAME))

# print 'greedy(cmpValue):'
# printSubjects(greedyAdvisor(subjects, 15, cmpValue))
# 
# print '\ngreedy(cmpWork):'
# printSubjects(greedyAdvisor(subjects, 15, cmpWork))
# 
# print '\ngreedy(cmpRatio)'
# printSubjects(greedyAdvisor(subjects, 15, cmpRatio))

# printSubjects(bruteForceAdvisor(subjects,15))
# 
#bruteForceTime()

#print dpAdvisor(subjects, 15)

# 6.00 Problem Set 6
#
# The 6.00 Word Game
#
# Scott Brenner
# Problem 1: 25 minutes
# Problem 2: 35 minutes
# Problem 3: ~8 hours  Lots of careless problems along the way.  Problems cause by short periods of time to work on problems and trouble with large sclae organization.


import random
import string
import time

VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
HAND_SIZE = 7
COMPUTER_TIME_FACTOR = 1

SCRABBLE_LETTER_VALUES = {
'a': 1, 'b': 3, 'c': 3, 'd': 2, 'e': 1, 'f': 4, 'g': 2, 'h': 4, 'i': 1, 'j': 8, 'k': 5, 'l': 1, 'm': 3, 'n': 1, 'o': 1, 'p': 3, 'q': 10, 'r': 1, 's': 1, 't': 1, 'u': 1, 'v': 4, 'w': 4, 'x': 8, 'y': 4, 'z': 10
}

WORDLIST_FILENAME = "words.txt"

# -----------------------------------
# PREPROCESSSING FUNCTIONS- These prep the word lists/dictionaries for game play.  They should execute only once--when the app is launched.  They include function used for scoring and for the computer-player.
def load_words():
    """
    Returns a list of valid words. Words are strings of lowercase letters.
    
    Depending on the size of the word list, this function may
    take a while to finish.
    """
    print "Loading word list from file..."
    # inFile: file
    inFile = open(WORDLIST_FILENAME, 'r', 0)
    # wordlist: list of strings
    wordlist = []
    for line in inFile:
        wordlist.append(line.strip().lower())
    print "  ", len(wordlist), "words loaded."
    return wordlist

def sort_word(word_string):
    """
    Takes a string, alphabetizes it and returns it as a string.
    """
    char_list =[]
    sorted_string = ''
    for char in word_string:
        char_list.append(char)
    char_list.sort()
    for char in char_list:
        sorted_string += char
    return sorted_string

def get_word_rearrangements(a_list_of_words):
    """
    This function takes a list of words and returns a dictionary of strings mapped to actual words.
    
    This function is used by the computer-player to find valid words.
    
    Create a dict where, for any set of letters, you can determine if there is some acceptable word that is a rearrangement of those letters.
    Let d = {}
    For every word w in the word list:
        Let d[(string containing the letters of w in sorted order)] = w
    """
    rearrange_dict = {}
    for word in a_list_of_words:
        #   build a list from the char in word: 1) convert word string to list, 2) sort list, 3) convert list back to string.
        char_list =[]
        my_string = ''
        for char in word:
            char_list.append(char)
        char_list.sort()
        for each in range(len(char_list)):
            my_string +=char_list[each]
        rearrange_dict[my_string] = word
    #print "In get_word_rearrangements. Rrearrange_dict:", rearrange_dict
    return rearrange_dict

def get_frequency_dict(sequence):
    """
    Returns a dictionary where the keys are elements of the sequence
    and the values are integer counts, for the number of times that
    an element is repeated in the sequence.
    
    sequence: string or list
    return: dictionary
    """
    # freqs: dictionary (element_type -> int)
    freq = {}
    for x in sequence:
        freq[x] = freq.get(x,0) + 1
    return freq

def get_word_score(word, n):
    """
    Returns the score for a word. Assumes the word is a
    valid word.
    
    The score for a word is the sum of the points for letters
    in the word, plus 50 points if all n letters are used on
    the first go.
    
    Letters are scored as in Scrabble; A is worth 1, B is
    worth 3, C is worth 3, D is worth 2, E is worth 1, and so on.
    
    word: string (lowercase letters)
    returns: int >= 0
    """
    score = 0
    for letter in word:
        score += SCRABBLE_LETTER_VALUES[letter.lower()]
    if len(word) == n:
        score += 50
    return score


# -----------------------------------
# GAME PLAY FUNCTIONS- These functions start and play the game play.  They will execute mulitple times.
def display_hand(hand):
    """
    Displays the letters currently in the hand.
    
    For example:
       display_hand({'a':1, 'x':2, 'l':3, 'e':1})
    Should print out something like:
       a x x l l l e
    The order of the letters is unimportant.
    
    hand: dictionary (string -> int)
    """
    for letter in hand.keys():
        for j in range(hand[letter]):
             print letter,              # print all on the same line
    print                              # print an empty line

def deal_hand(n):
    """
    Returns a random hand containing n lowercase letters.
    At least n/3 the letters in the hand should be VOWELS.
    
    Hands are represented as dictionaries. The keys are
    letters and the values are the number of times the
    particular letter is repeated in that hand.
    
    n: int >= 0
    returns: dictionary (string -> int)
    """
    hand={}
    num_vowels = n / 3
    
    for i in range(num_vowels):
        x = VOWELS[random.randrange(0,len(VOWELS))]
        hand[x] = hand.get(x, 0) + 1
        
    for i in range(num_vowels, n):    
        x = CONSONANTS[random.randrange(0,len(CONSONANTS))]
        hand[x] = hand.get(x, 0) + 1
        
    return hand

def update_hand(hand, word):
    """
    Assumes that 'hand' has all the letters in word.
    In other words, this assumes that however many times
    a letter appears in 'word', 'hand' has at least as
    many of that letter in it. 
    
    Updates the hand: uses up the letters in the given word
    and returns the new hand, without those letters in it.
    
    word: string
    hand: dictionary (string -> int)    
    returns: dictionary (string -> int)
    """
    freq = get_frequency_dict(word)
    newhand = {}
    for char in hand:
        newhand[char] = hand[char]-freq.get(char,0)
    return newhand
    #return dict( ( c, hand[c] - freq.get(c,0) ) for c in hand )

def is_valid_word(word, hand, point_dict):
    """
    Returns True if word is in the word_list and is entirely
    composed of letters in the hand. Otherwise, returns False.
    Does not mutate hand or word_list.
    
    word: string
    hand: dictionary (string -> int)
    word_list: list of lowercase strings
    """
    freq = get_frequency_dict(word)                 # Create dictionary frequency dictionary for word.  E.g., if work is 'hello', freq = {'h': 1, 'e': 1, 'l': 2, 'o': 1}.
    for letter in word:
        if freq[letter] > hand.get(letter, 0):      # Confirm that each letter needed to spell word is in the hand in sufficient quantity.
            return False
    return word in point_dict

def play_hand(hand, word_list):
    """
    Allows the user to play the given hand, as follows:
    * The hand is displayed.
    
    * The user may input a word.
    
    * An invalid word is rejected, and a message is displayed asking the user to choose another word.
    
    * When a valid word is entered, it uses up letters from the hand.
    
    * After every valid word: the score for that word is displayed,
      the remaining letters in the hand are displayed, and the user
      is asked to input another word.
    
    * The sum of the word scores is displayed when the hand finishes.
    
    * The hand finishes when there are no more unused letters.
      The user can also finish playing the hand by inputing a single
      period (the string '.') instead of a word.
      
      hand: dictionary (string -> int)
      word_list: list of lowercase strings
    """    
    
    total_points = 0.0
    initial_handlen = sum(hand.values())
    foo = True
    elapsed_time = 0.0
    chessTime = get_time_limit(point_dict, COMPUTER_TIME_FACTOR)
    print "\nComputer will have %0.2f seconds to play the hand.\n" % chessTime
    # this is commented out because it was replaced by the line above.  The line above sets chessTime based on computer speed.  The commented code aske the user for chessTime.
    # while foo:
    #     chessTime = raw_input('Enter time limit, in seconds, for players:')
    #     if chessTime.isdigit():
    #         chessTime = float(chessTime)
    #         foo = False
    while sum(hand.values()) > 0:
        print
        print 'Current Hand:',
        display_hand(hand)
        startTime = time.time()
        # userWord = raw_input('Enter word, or a . to indicate that you are finished: ')
        userWord = pick_best_word_faster(hand, arranged_words) # 'faster' function
        # userWord = pick_best_word(hand, point_dict) # orignial fuction
        endTime = time.time()
        playTime = endTime - startTime
        print "It took %0.5f seconds to play %s." % (playTime, userWord)
        elapsed_time += playTime
        if userWord == '.':
            break
        elif elapsed_time > chessTime:
            print "It took %0.5f seconds to play %s." % (playTime, userWord)
            # print 'It took %0.2f seconds to enter your word.' % elapsed_time
            print 'Your total time to play the hand exceeded %0.5f seconds. Your final score is %0.2f points.' % (chessTime, total_points)
            break
        else:
            isValid = is_valid_word(userWord, hand, word_list)
            if not isValid:
                print 'Invalid word, please try again.'
            else:
                if playTime < 1: playTime = 1
                points = get_word_score(userWord, initial_handlen) /  playTime
                total_points += points
                print '%s earned %0.5f points. Total: %0.5f points' % (userWord, points, total_points)
                hand = update_hand(hand, userWord)
                #print 'Updated hand:%s' % hand
    print 'Total score: %0.5f points.' % total_points
    return total_points

def play_game(word_list):
    """
    Allow the user to play an arbitrary number of hands.
    * Asks the user to input 'n' or 'r' or 'e'.
    
    * If the user inputs 'n', let the user play a new (random) hand. When done playing the hand, ask the 'n' or 'e' question again.
    
    * If the user inputs 'r', let the user play the last hand again.
    
    * If the user inputs 'e', exit the game.
    
    * If the user inputs anything else, ask them again.
    """
    
    # hand_score = 0.0
    # counter = 0
    # while hand_score < 40 or counter < 5:
    #         hand = deal_hand(HAND_SIZE)
    #         hand_score = play_hand(hand.copy(), word_list)
    #         print "Counter %i." %counter 
    #         counter += 1
    # print "Counter %i." %counter 
    
    hand = deal_hand(HAND_SIZE) # random init
    while True:
        cmd = raw_input('Enter n to deal a new hand, r to replay the last hand, or e to end game: ')
        if cmd == 'n':
            hand = deal_hand(HAND_SIZE)
            play_hand(hand.copy(), word_list)
            print
        elif cmd == 'r':
            play_hand(hand.copy(), word_list)
            print
        elif cmd == 'e':
            break
        else:
            print "Invalid command."

# -----------------------------------
# COMPUTER PLAYER FUNCTIONS- These functions play the computer's hand.  They find and play the best word.  They will execute mulitple times.
def pick_best_word(hand, points_dict):
    """
    Return the highest scoring word from points_dict that can be made with the given hand.
    
    Return '.' if no words can be made with the given hand.
    """
    freq = get_frequency_dict(hand)     # Create dictionary frequency dictionary for the hand
    best_word = ""
    best_word_value = 0
    for word in points_dict:
        if is_valid_word(word, hand, points_dict):
            word_value = get_word_score(word, HAND_SIZE)
            #print "The word is %s, with value %i.   The best word is %s, with value %i." % (word, word_value, best_word, best_word_value)
            if word_value > best_word_value:
                best_word = word
                best_word_value = word_value
    if best_word_value > 0:
        return best_word
    return "."

def get_words_to_point(word_list):
    """
    Return a dict that maps every word in word_list to its point value.
    """
    word_value_dictionary = {}
    for word in word_list:
        word_value_dictionary[word] = get_word_score(word, 7)
    return word_value_dictionary
    #return len(word_value_dictionary)

def pick_best_word_faster(hand, rearrange_dict):
    """
    Takes a hand {dictionary} and a dictionary of letter combinations that map to a valid word.
    
    Returns the highest value word or '.'-if there is no valid word possible.
    
    Pseudo-code:
    To find some word that can be made out of the letters in HAND:
        For each subset S of the letters of HAND:
            Let w = (string containing the letters of S in sorted order)
            If w in d:
                return d[w]
                
    This function must convert the hand{dictionary} to a string.  In doing so it must check to make sure that the value of each key in the had is > 0
    """
    #print "In pick best. Hand:", hand
    hand_string = ''
    
    for each in hand:
        if hand[each] > 0:
            hand_string += each * hand[each]
        
    #print "Hand sorted: %s" %hand_string
    
    best_word =''
    best_word_score = 0
    subsets = build_substrings(hand_string)
    subset_value = 0
    
    for subset in subsets:
        sorted_subset = sort_word(subset)
        if sorted_subset in rearrange_dict:
            subset_value = get_word_score(sorted_subset, HAND_SIZE)
            if subset_value > best_word_score:
                best_word = rearrange_dict[sorted_subset]                
                best_word_score = subset_value
    
    if best_word_score > 0:
        return best_word
    else:
        return '.'

def get_time_limit(points_dict, k): 
    """
    Return the time limit for the computer player as a function of the multiplier k.
    
    points_dict should be the same dictionary that is created by get_words_to_points.
    """
    start_time = time.time()
    # Do some computation. The only purpose of the computation is so we can
    # figure out how long your computer takes to perform a known task.
    for word in points_dict:
        get_frequency_dict(word)
        get_word_score(word, HAND_SIZE)
    end_time = time.time()
    return (end_time - start_time) * k

def build_substrings(string):
    """
    Works on the premiss that given a set of the substrings of a string the
    the subsets of a string with one more char is the formed by taking all the
    substrings in the known subset and also adding to them the set formed by
    adding the character to every element in the old set and then adding the 
    new char.
    
    """
    result = []
    if len(string) == 1:
        result.append(string)
    else:
        for substring in build_substrings(string[:-1]):
            result.append(substring)
            substring = substring + string[-1]
            result.append(substring)
        result.append(string[-1])
        result = list(set(result))  # Convert result into a set.  Sets have no duplicates. Then convert back to list.
        result.sort()
    # now iterate through substrings and sort the characters of each substring    
    #for each in 
    return result


# -----------------------------------
# PLAY GAME: Build data structures used for entire session and play game.
#
if __name__ == '__main__':
    word_list = load_words()
    point_dict = get_words_to_point(word_list)
    arranged_words = get_word_rearrangements(word_list)
    #print len(arranged_words)
    play_game(word_list)




## Problem 5 ##
# your response here.
# as many lines as you want.
# 
# pick_best_word()
#     This method creates a dictionary of every valid word mapped to the point value.  Then it iterates through the dictionary comparing the hand to the word.  If they word can be made from the hand then the word's score is compared to the word score of the earlier possible word.  The higher score word is retained.
#     Under this method the point value dictionary must be built and then the function iterates through comparing the hand to eveyr possible word.
#     Amortizing the time-cost of building the dictionary over each pick, the time complexity of this method grows with the length of the word list and independently from the size of the hand.  Adding letters to the hand will increase the time to execute but only negligibly.  I think the computational complexity of the function is linear.
# 
#   With a hand size of 7 letters the time to pick best word was less than .6 seconds.
#   With a hand size of 17 letters the time to pick best word was ~.6 seconds.
#   With a hand size of 25 letters the time to pick best word was ~.65 seconds.



#     
# pick_best_word_faster()
#   This method also begins by creating a dictionary.  Each value in the dictioanry is a valid word.  Each key is a alphabetized string of the letters in the word. E.g., {'acot':'taco'}.  Note that each key is unique but the value isn't necessarily unique.  The dictionary value for 'acot' could be 'coat'.  This is because the dictionary only needs to list every valid alpahbetized string of letters.  Not ever valid word.  This makes the dictionary the same size or shorter than the dictionary created in pick_best_word().  For the word list used in this problem the savings is ~14,000 entries (83667 words, 69091 dict keys)
#     Armed with this dictionary the function can take advantage of the speed of the "in dictionary" function, which I thinks is logarithmic.  The next part of this function is build a set of substrings of hand.  The function then iterates through this set of substrings checking if they are in the dictionary, and comparing their point value to the prior highest value string in the dictionary.  The function returns the highest point value value from the dictionary.
#     This method is much faster than pick_best_word() because is takes adavantice of the bysect search functionality built into search dicstionaries.  This bysect search algorithm grow logarithmically based on the length of dictionary.
#   Adding letters to the hand will increase the time to execute the function that creates the subsets, but they dicitonary search is the more significant funciton.  I think the computational complexity of the function is logarithmic.

#   With a hand size of 7 letters the time to pick best word was less than .001 seconds.
#   With a hand size of 17 letters the time to pick best word was between .3 and .5 seconds.
#   With a hand size of 25 letters the time to pick best word was between 15 and 45 seconds.

#   Comparing the two functions, it appears the pick_best_word_faster() is much faster for relatively small hands and any size dictionary.  But pick_best_word() is faster if the hands will be large.  Not surprisingly the 'better' function depends on the specifics of the problem.

# Problem Set 5: Ghost
# Name: 
# Collaborators: None
# Time: 
#

import random

# -----------------------------------
# Helper code
# (you don't need to understand this helper code)
import string

WORDLIST_FILENAME = "words.txt"

def load_words():
    """
    Returns a list of valid words. Words are strings of lowercase letters.
    
    Depending on the size of the word list, this function may
    take a while to finish.
    """
    print "Loading word list from file..."
    # inFile: file
    inFile = open(WORDLIST_FILENAME, 'r', 0)
    # wordlist: list of strings
    wordlist = []
    for line in inFile:
        wordlist.append(line.strip().lower())
    print "  ", len(wordlist), "words loaded."
    return wordlist

def get_frequency_dict(sequence):
    """
    Returns a dictionary where the keys are elements of the sequence
    and the values are integer counts, for the number of times that
    an element is repeated in the sequence.

    sequence: string or list
    return: dictionary
    """
    # freqs: dictionary (element_type -> int)
    freq = {}
    for x in sequence:
        freq[x] = freq.get(x,0) + 1
    return freq


# (end of helper code)
# -----------------------------------

# Actually load the dictionary of words and point to it with 
# the wordlist variable so that it can be accessed from anywhere
# in the program.
wordlist = load_words()

# TO DO: your code begins here!

# Problem Set 5: 6.00 Word Game
# Name: Scott Brenner
# Collaborators: 
# Time: 
# Problem 1: 10 minutes
# Problem 2: 08 minutes
# Problem 3: 27 minutes
# Problem 4: 00 minutes 10:55 AM 11:29 AM
# Problem 5: 00 minutes




import random
import string

VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
HAND_SIZE = 7

SCRABBLE_LETTER_VALUES = {
    'a': 1, 'b': 3, 'c': 3, 'd': 2, 'e': 1, 'f': 4, 'g': 2, 'h': 4, 'i': 1, 'j': 8, 'k': 5, 'l': 1, 'm': 3, 'n': 1, 'o': 1, 'p': 3, 'q': 10, 'r': 1, 's': 1, 't': 1, 'u': 1, 'v': 4, 'w': 4, 'x': 8, 'y': 4, 'z': 10
}

# -----------------------------------
# Helper code
# (you don't need to understand this helper code)

WORDLIST_FILENAME = "words.txt"

def load_words():
    """
    Returns a list of valid words. Words are strings of lowercase letters.
    
    Depending on the size of the word list, this function may
    take a while to finish.
    """
    print "Loading word list from file..."
    # inFile: file
    inFile = open(WORDLIST_FILENAME, 'r', 0)
    # wordlist: list of strings
    wordlist = []
    for line in inFile:
        wordlist.append(line.strip().lower())
    print "  ", len(wordlist), "words loaded."
    return wordlist

def get_frequency_dict(sequence):
    """
    Returns a dictionary where the keys are elements of the sequence
    and the values are integer counts, for the number of times that
    an element is repeated in the sequence.

    sequence: string or list
    return: dictionary
    """
    # freqs: dictionary (element_type -> int)
    freq = {}
    for x in sequence:
        freq[x] = freq.get(x,0) + 1
    return freq

# (end of helper code)
# -----------------------------------

#
# Problem #1: Scoring a word
#
def get_word_score(word, n):
    """
    Returns the score for a word. Assumes the word is a
    valid word.

    The score for a word is the sum of the points for letters
    in the word, plus 50 points if all n letters are used on
    the first go.

    Letters are scored as in Scrabble; A is worth 1, B is
    worth 3, C is worth 3, D is worth 2, E is worth 1, and so on.

    word: string (lowercase letters)
    returns: int >= 0
    """
    # TO DO ...
    # Initialize score to 0.  If word uses all letters set value to 50.
    score = 0
    if len(word) >= n: score = 50

    for letter in word: score += SCRABBLE_LETTER_VALUES[letter]

    return score
#
# Make sure you understand how this function works and what it does!
#
def display_hand(hand):
    """
    Displays the letters currently in the hand.

    For example:
       display_hand({'a':1, 'x':2, 'l':3, 'e':1})
    Should print out something like:
       a x x l l l e
    The order of the letters is unimportant.

    hand: dictionary (string -> int)
    """
    for letter in hand.keys():
        for j in range(hand[letter]):
            print letter,              # print all on the same line
    print                              # print an empty line

#
# Make sure you understand how this function works and what it does!
#
def deal_hand(n):
    """
    Returns a random hand containing n lowercase letters.
    At least n/3 the letters in the hand should be VOWELS.

    Hands are represented as dictionaries. The keys are
    letters and the values are the number of times the
    particular letter is repeated in that hand.

    n: int >= 0
    returns: dictionary (string -> int)
    """
    hand={}
    num_vowels = n / 3
    
    for i in range(num_vowels):
        x = VOWELS[random.randrange(0,len(VOWELS))]
        hand[x] = hand.get(x, 0) + 1
        
    for i in range(num_vowels, n):    
        x = CONSONANTS[random.randrange(0,len(CONSONANTS))]
        hand[x] = hand.get(x, 0) + 1
        
    return hand

#
# Problem #2: Update a hand by removing letters
#
def update_hand(hand, word):
    """
    Assumes that 'hand' has all the letters in word.
    In other words, this assumes that however many times
    a letter appears in 'word', 'hand' has at least as
    many of that letter in it. 

    Updates the hand: uses up the letters in the given word
    and returns the new hand, without those letters in it.

    Has no side effects: does not mutate hand.

    word: string
    hand: dictionary (string -> int)    
    returns: dictionary (string -> int)
    """
    # TO DO ...
    newHand = dict(hand)
    for letter in word:
        newHand[letter] = newHand.get(letter, 0) - 1
        # print newHand
    return newHand

        
#
# Problem #3: Test word validity
#
def is_valid_word(word, hand, word_list):
    """
    Returns True if word is in the word_list and is entirely
    composed of letters in the hand. Otherwise, returns False.
    Does not mutate hand or word_list.
    
    word: string
    hand: dictionary (string -> int)
    word_list: list of lowercase strings
    """
    # TO DO ...
    countingHand = dict(hand)

    # Check if word is in dictionary using bisect search
    if word in word_list:
        # Check if hand has necessary letter. If letter is in hand decrement letter count in hand
        for letter in word:
            if countingHand.get(letter, 0) > 0:
                countingHand[letter] -= 1
            else:
                return False # The words had a letter that was not in the hand.
    else: return False
    return True

#
# Problem #4: Playing a hand
#
def play_hand(hand, word_list):
    """
    Allows the user to play the given hand, as follows:

    * The hand is displayed.
    
    * The user may input a word.

    * An invalid word is rejected, and a message is displayed asking
      the user to choose another word.

    * When a valid word is entered, it uses up letters from the hand.

    * After every valid word: the score for that word and the total
      score so far are displayed, the remaining letters in the hand 
      are displayed, and the user is asked to input another word.

    * The sum of the word scores is displayed when the hand finishes.

    * The hand finishes when there are no more unused letters.
      The user can also finish playing the hand by inputing a single
      period (the string '.') instead of a word.

    * The final score is displayed.

      hand: dictionary (string -> int)
      word_list: list of lowercase strings
    """
    # TO DO ...
    score = 0
    # The hand is displayed.
    player_hand = deal_hand(HAND_SIZE)
    print 'Dealing...Here is your hand:', display_hand(hand)

    # The user may input a word.
    word = raw_input('play a word:')
    
    # An invalid word is rejected, and a message is displayed asking the user to choose another word.
    if is_valid_word(word, hand, word_list):
        
        # When a valid word is entered, it uses up letters from the hand.
        hand = update_hand(hand, word)
        
        # After every valid word: the score for that word and the total      score so far are displayed, the remaining letters in the hand are displayed, and the user is asked to input another word.
        wordScore = get_word_score(word, HAND_SIZE)
        print "That word scores", wordScore, "points."
        score += wordScore
        print "Your total score:", score
        print "Your have the remaining letters:", display_hand(hand)
        word = raw_input("You can also finish playing the hand by inputing a single period '.'")
        
    else:
        word = raw_input("That word isn't in the dictionary.  Try again:")
        




    # The sum of the word scores is displayed when the hand finishes.

    # The hand finishes when there are no more unused letters. The user can also finish playing the hand by inputing a single period (the string '.') instead of a word.

    # The final score is displayed.


#play_hand({'t':2,'a':2,'c':2,'o':1}, load_words())
    
    
#
# Problem #5: Playing a game
# Make sure you understand how this code works!
# 
def play_game(word_list):
    """
    Allow the user to play an arbitrary number of hands.

    * Asks the user to input 'n' or 'r' or 'e'.

    * If the user inputs 'n', let the user play a new (random) hand.
      When done playing the hand, ask the 'n' or 'e' question again.

    * If the user inputs 'r', let the user play the last hand again.

    * If the user inputs 'e', exit the game.

    * If the user inputs anything else, ask them again.
    """
    # TO DO ...
    print "play_game not implemented."         # delete this once you've completed Problem #4
    play_hand(deal_hand(HAND_SIZE), word_list) # delete this once you've completed Problem #4
    
    ## uncomment the following block of code once you've completed Problem #4
#    hand = deal_hand(HAND_SIZE) # random init
#    while True:
#        cmd = raw_input('Enter n to deal a new hand, r to replay the last hand, or e to end game: ')
#        if cmd == 'n':
#            hand = deal_hand(HAND_SIZE)
#            play_hand(hand.copy(), word_list)
#            print
#        elif cmd == 'r':
#            play_hand(hand.copy(), word_list)
#            print
#        elif cmd == 'e':
#            break
#        else:
#            print "Invalid command."

#
# Build data structures used for entire session and play game
#
if __name__ == '__main__':
    word_list = load_words()
    play_game(word_list)

# Problem Set 4
# Name: 
# Collaborators: 
# Time: 

#
# Problem 1
# Start time: 2011-02-06 5:10 PM
# End time: 2011-02-06 5:31 PM
# Total time: 21 minutes.

# Write a function, called nestEggFixed, which takes four arguments: a salary, a percentage of your salary to save in an investment account, an annual growth percentage for the investment account, and a number of years to work. This function should return a list, whose values are the size of your retirement account at the end of each year, with the most recent year's value at the end of the list.

##  Complete the implementation of:
def nestEggFixed(salary, save, growthRate, years):
    """
    - salary: the amount of money you make each year.
    - save: the percent of your salary to save in the investment account each
      year (an integer between 0 and 100).
    - growthRate: the annual percent increase in your investment account (an
      integer between 0 and 100).
    - years: the number of years to work.
    - return: a list whose values are the size of your retirement account at
      the end of each year.
    """
    # End of year 1 -->   F[0] = salary * save * 0.01
    # End of year 2 -->   F[1] = F[0] * (1 + 0.01 * growthRate) + salary * save * 0.01
    # End of year 3 --> F[2] = F[1] * (1 + 0.01 * growthRate) + salary * save * 0.01
    
    # TODO: Your code here.
    answer = [0]
    for each in range(0,years):
        #print each
        temp = answer[-1] * (1 + 0.01 * growthRate) + salary * save * 0.01
        answer.append(temp)
        #print answer
    del answer[0]
    return answer

def testNestEggFixed():
    salary     = 10000
    save       = 10
    growthRate = 15
    years      = 5
    savingsRecord = nestEggFixed(salary, save, growthRate, years)
    print savingsRecord
    # Output should have values close to:
    # [1000.0, 2150.0, 3472.5, 4993.375, 6742.3812499999995]

    # TODO: Add more test cases here.
    salary     = 40000
    save       = 12
    growthRate = 7
    years      = 20
    savingsRecord = nestEggFixed(salary, save, growthRate, years)
    print savingsRecord

    salary     = 80000
    save       = 12
    growthRate = 7
    years      = 20
    savingsRecord = nestEggFixed(salary, save, growthRate, years)
    print savingsRecord

#   testNestEggFixed()  #Just for testing 

#
# Problem 2
#
# Start time: 2011-02-06 5:32 PM
# End time: 2011-02-06  5:41 PM
# Total time: 9 minutes.

# Write a function, called nestEggVariable, which takes three arguments: a salary (salary), a percentage of your salary to save (save), and a list of annual growth percentages on investments (growthRates). The length of the last argument defines the number of years you plan to work; growthRates[0] is the growth rate of the first year, growthRates[1] is the growth rate of the second year, etc. (Note that because the retirement fund's initial value is 0, growthRates[0] is, in fact, irrelevant.) This function should return a list, whose values are the size of your retirement account at the end of each year.


def nestEggVariable(salary, save, growthRates):
    """
    - salary: the amount of money you make each year.
    - save: the percent of your salary to save in the investment account each
      year (an integer between 0 and 100).
    - growthRate: a list of the annual percent increases in your investment
      account (integers between 0 and 100).
    - return: a list of your retirement account value at the end of each year.
    """
    # TODO: Your code here.
    answer = [0]
    for each in range(len(growthRates)):
        #print each
        temp = answer[-1] * (1 + 0.01 * growthRates[each]) + salary * save * 0.01
        answer.append(temp)
        #print answer
    del answer[0]
    return answer
    
def testNestEggVariable():
    salary      = 10000
    save        = 10
    growthRates = [3, 4, 5, 0, 3]
    savingsRecord = nestEggVariable(salary, save, growthRates)
    print savingsRecord
    # Output should have values close to:
    # [1000.0, 2040.0, 3142.0, 4142.0, 5266.2600000000002]

    # TODO: Add more test cases here.
    salary      = 40000
    save        = 10
    growthRates = [3, 7, 8, 10, 3,7, 8, 10, 3,7, 8, 10, 3,7, 8, 10, 3]
    savingsRecord = nestEggVariable(salary, save, growthRates)
    print savingsRecord

    salary      = 80000
    save        = 10
    growthRates = [3, 0, 15, 0, 31,7, 8, 10, 3]
    savingsRecord = nestEggVariable(salary, save, growthRates)
    print savingsRecord

    salary      = 650000
    save        = 10
    growthRates = [7, 8, 10, 3, 7, 8, 10, 3, 13, 7, 8, 10, 3, 14, 15, 10, 13]
    savingsRecord = nestEggVariable(salary, save, growthRates)
    print savingsRecord

#testNestEggVariable() # Just for testing

#
# Problem 3
#
# Start time: 2011-02-06 5:46 PM
# End time: 2011-02-06 5:57 PM
# Total time:  11 minutes.

# Write a function, called postRetirement, which takes three arguments: an initial amount of money in your retirement fund (savings), a list of annual growth percentages on investments while you are retired (growthRates), and your annual expenses (expenses). Assume that the increase in the investment account savings is calculated before subtracting the annual expenditures (as shown in the above table). Your function should return a list of fund sizes after each year of retirement, accounting for annual expenses and the growth of the retirement fund. Like problem 2, the length of the growthRates argument defines the number of years you plan to be retired.

# Note that if the retirement fund balance becomes negative, expenditures should continue to be subtracted, and the growth rate comes to represent the interest rate on the debt(i.e. the formulas in the above table still apply).

def postRetirement(savings, growthRates, expenses):
    """
    - savings: the initial amount of money in your savings account.
    - growthRate: a list of the annual percent increases in your investment
      account (an integer between 0 and 100).
    - expenses: the amount of money you plan to spend each year during
      retirement.
    - return: a list of your retirement account value at the end of each year.
    """
    # TODO: Your code here.
    answer = [savings]
    for each in range(len(growthRates)):
        temp = answer[-1] * (1 + 0.01 * growthRates[each]) - expenses
        answer.append(temp)
#    del answer[0]
    return answer[-1]




def testPostRetirement():
    savings     = 100000
    growthRates = [10, 5, 0, 5, 1]
    expenses    = 30000
    savingsRecord = postRetirement(savings, growthRates, expenses)
    print savingsRecord
    # Output should have values close to:
    # [80000.000000000015, 54000.000000000015, 24000.000000000015,
    # -4799.9999999999854, -34847.999999999985]

    # TODO: Add more test cases here.
    savings     = 367000
    growthRates = [10, 5, 0, 5, 1,5,6,7,8,9,1,2,3,4,5,6,12,13,14]
    expenses    = 30000
    savingsRecord = postRetirement(savings, growthRates, expenses)
    print savingsRecord

    savings     = 900000
    growthRates = [10, 5, 0,10, 5, 0, 5, 1]
    expenses    = 60000
    savingsRecord = postRetirement(savings, growthRates, expenses)
    print savingsRecord

    savings     = 1500000
    growthRates = [10, 5, 0, 5, 1,10, 5, 0, 5, 1,6,7,8,4,3,1,8,9,0,21, 5, 0, 5, 1,6,7,8,4,3,1,8,9,0,12]
    expenses    = 30000
    savingsRecord = postRetirement(savings, growthRates, expenses)
    print savingsRecord

    savings     = 1000000
    growthRates = [10, 5, 0, 5, 1,6,7,8,4,3,1,8,9,0,12]
    expenses    = 18000
    savingsRecord = postRetirement(savings, growthRates, expenses)
    print savingsRecord
    
    
# testPostRetirement() #Just for testing    

#
# Problem 4
#
# Start time: 2011-02-06 6:02 PM
# End time: 2011-02-06 6:42 PM
#
# Total time: minutes.


# Write a function, called findMaxExpenses, which takes five arguments: a salary(salary), a percentage of your salary to save (save), a list of annual growth percentages on investments while you are still working (preRetireGrowthRates), a list of annual growth percentages on investments while you are retired (postRetireGrowthRates), and a value for epsilon (epsilon). As with problems 2 and 3, the lengths of preRetireGrowthRates and postRetireGrowthRates determine the number of years you plan to be working and retired, respectively.

# Use the idea of binary search to find a value for the amount of expenses you can withdraw each year from your retirement fund, such that at the end of your retirement,the absolute value of the amount remaining in your retirement fund is less than epsilon(note that you can overdraw by a small amount). 

# Start with a range of possible values for your annual expenses between 0 and your savings at the start of your retirement (HINT #1: this can be determined by utilizing your solution to problem 2). Your function should print out the current estimate for the amount of expenses on each iteration through the binary search (HINT #2: your binary search should make use of your solution to problem 3), and should return the estimate for the amount of expenses to withdraw. (HINT #3: the answer should lie between zero and the initial value of the savings + epsilon.)

def findMaxExpenses(salary, save, preRetireGrowthRates, postRetireGrowthRates,
                    epsilon):
    """
    - salary: the amount of money you make each year.
    - save: the percent of your salary to save in the investment account each
      year (an integer between 0 and 100).
    - preRetireGrowthRates: a list of annual growth percentages on investments
      while you are still working.
    - postRetireGrowthRates: a list of annual growth percentages on investments
      while you are retired.
    - epsilon: an upper bound on the absolute value of the amount remaining in
      the investment fund at the end of retirement.
    """
    # TODO: Your code here.

    # Start with a range of possible values for your annual expenses between 0 and your savings at the start of your retirement (HINT #1: this can be determined by utilizing your solution to problem 2).
    low = 0
    
    ##  Set the high guess to value of the nest egg at moment of retirement or 1, which ever is higher.
    high = max(nestEggVariable(salary, save, preRetireGrowthRates)[-1],1)
    
    balanceAtRetirement = nestEggVariable(salary, save, preRetireGrowthRates)[-1]

    ##  Bisect the range between high & low and initialize the guess to this value.
    guess = (low + high) / 2
    
    ctr = 1
    
    ##  Set the remaining balance to the balance at the end of retirement (death?).
    remainingBalance = postRetirement(balanceAtRetirement, postRetireGrowthRates, guess)
    
    while abs(remainingBalance) > epsilon and ctr <= 100:
        #print 'low:', low, 'high:', high, 'guess:', guess, 'remainingBalance:',remainingBalance
        #print 'guess - remainingBalance', guess - remainingBalance
        if remainingBalance < 0:
            high = guess
        else:
            low = guess
        ctr += 1
        guess = (low + high)/2
        remainingBalance = postRetirement(balanceAtRetirement, postRetireGrowthRates, guess)
    assert ctr <= 100, 'Iteration count exceeded'
    return guess
    
def testFindMaxExpenses():
    salary                = 10000
    save                  = 10
    preRetireGrowthRates  = [3, 4, 5, 0, 3]
    postRetireGrowthRates = [10, 5, 0, 5, 1]
    epsilon               = .01
    expenses = findMaxExpenses(salary, save, preRetireGrowthRates,
                               postRetireGrowthRates, epsilon)
    print expenses
    # Output should have a value close to:
    # 1229.95548986

    # TODO: Add more test cases here.

    salary                = 80000
    save                  = 10
    preRetireGrowthRates  = [3, 4, 5, 0, 3,6,7,8,5,4,7,4,8,9,11,21,11,2,5]
    postRetireGrowthRates = [3, 4, 5, 0, 3,6,7,8,5,4,7,4,8,2,5,10, 5, 0, 5, 1]
    epsilon               = 1000
    expenses = findMaxExpenses(salary, save, preRetireGrowthRates,
                               postRetireGrowthRates, epsilon)
    print expenses
    
    salary                = 100000
    save                  = 15
    preRetireGrowthRates  = [3, 4, 5, 0, 3,6,7,8,5,4,7,4,8,9,11,21,11,2,5,3, 4, 5, 0, 3]
    postRetireGrowthRates = [10, 5, 0,3, 4, 5, 0, 3,6,7,8,5,4,7,4,8,9,11,21,11,2,5, 5, 1]
    epsilon               = .01
    expenses = findMaxExpenses(salary, save, preRetireGrowthRates,
                               postRetireGrowthRates, epsilon)
    print expenses
    
    salary                = 1000
    save                  = 90
    preRetireGrowthRates  = [3, 4, 5, 0, 3,6,7,8,5,4,7,4,8,9,11,21,11,2,53, 4, 5, 0, 3]
    postRetireGrowthRates = [10, 5, 0, 5, 1,3, 4, 5, 0, 3,6,7,8,5,4,7,4,8,9,11,21,11,2,5]
    epsilon               = .01
    expenses = findMaxExpenses(salary, save, preRetireGrowthRates,
                               postRetireGrowthRates, epsilon)
    print expenses

testFindMaxExpenses() # just to test

# Problem Set 3 (Problem 1)  ps3a.py
# Name: Scott Brenner
# Collaborators: None
# Date: 2011-01-29
# Time: 2:45 PM
#
 
#!/usr/local/bin/python
 
from string import *        #    used for find()
 
# Problem 1.
# Write two functions, called countSubStringMatch and countSubStringMatchRecursive that take two arguments, a key string and a target string. These functions iteratively and recursively count the number of instances of the key in the target string. You should complete definitions for
#    Targets and keys
target = "atgacatgcacaagtatgcat"
key = "atgc"
 
 
def countSubStringMatch(target,key):
    """This function returns the number of times a key string appears in target string.  This function iterates through the taret string."""
    count = 0
    start = 0
    while find(target, key, start) != -1:
        count += 1
        start = find(target, key, start) + 1
    return count
 
 
def countSubStringMatchRecursive (target, key):
    """This function returns the number of times a key string appears in target string.  This function uses recursion."""
    answer = 0
    next_match = find(target,key)
    if next_match == -1:
        return answer
    else:
        answer = 1 + countSubStringMatchRecursive(target[next_match+1:], key)
        return answer
 
print countSubStringMatch(target,key)
print countSubStringMatchRecursive(target,key)

#*****************************************************

# Problem Set 3 (Problem 2) ps3b.py
# Name: Scott Brenner
# Collaborators: None
# Date: 2011-02-01
# Start Time: 11:29 AM
# End Time: 12:04 PM
# I reused code I had drafted earlier.

#!/usr/local/bin/python

from string import *		#	used for find()


# Problem 2.
# Write the function subStringMatchExact. This function takes two arguments: a target string, and a key string. It should return a tuple of the starting points of matches of the key string in the target string, when indexing starts at 0. Complete the definition for

#	def subStringMatchExact(target,key):

#	For example, would return the tuple (5, 15). The file ps3_template.py includes some test strings that you can use to test your function. In particular, we provide two target strings and four key strings.  Test your function on each combination of key and target string, as well as other examples that you create. Place your answer in a file named ps3b.py

#	Targets and keys
target1 = 'atgacatgcacaagtatgcat'
target2 = 'atgaatgcatggatgtaaatgcag'

key10 = 'a'
key11 = 'atg'
key12 = 'atgc'
key13 = 'atgca'


def subStringMatchExact (target, key):
	"""This function returns a tuple of the starting position(s) of a key string within a target string"""
	answer_tuple = () # initialize the tuple we will return
	start = 0 # use this initial the starting point for find()
	while find(target, key, start) >=0:
		start = find(target, key, start)
		answer_tuple += (start,)
		start+=1
	return answer_tuple
	
####	Run Program with a variety of strings and keys	####
print "atgacatgcacaagtatgcat", "atgc"
print subStringMatchExact("atgacatgcacaagtatgcat", "atgc")
print target1, key10
print subStringMatchExact(target1, key10)
print target1, key11
print subStringMatchExact(target1, key11)
print target1, key12
print subStringMatchExact(target1, key12)
print target1, key13
print subStringMatchExact(target1, key13)
print target2, key10
print subStringMatchExact(target2, key10)
print target2, key11
print subStringMatchExact(target2, key11)
print target2, key12
print subStringMatchExact(target2, key12)
print target2, key13
print subStringMatchExact(target2,key13)



#*****************************************************
# Problem Set 3 (Problem 3)   ps3c.py
# Name: Scott Brenner
# Collaborators: None
# Date: 2011-02-01
# Time: 11:29 AM
#

#!/usr/local/bin/python

from string import *		#	used for find()


# Problem 3.
# Write a function, called constrainedMatchPair which takes three arguments: a tuple representing starting points for the first substring, a tuple representing starting points for the second substring, and the length of the first substring. The function should return a tuple of all members (call it n) of the first tuple for which there is an element in the second tuple (call it k) such that n+m+1 = k, where m is the length of the first substring. Complete the definition

# To test this function, we have provided a function called subStringMatchOneSub, which takes two arguments: a target string and a key string. This function will return a tuple of all starting points of matches of the key to the target, such that at most one element of the key is incorrectly matched to the target. This function is provided for you in the file ps3_template.py and invokes the function you are to write. Save your answers in a file named ps3c.py.

# these are some example strings for use in testing your code

#  target strings

target1 = 'atgacatgcacaagtatgcat'
#		   01234567890123456789
target2 = 'atgaatgcatggatgtaaatgcag'

# key strings

key10 = 'a'
key11 = 'atg' 	# matches in target1 == (0, 5, 15)	length == 3
key12 = 'atgc'	# matches in target1 == (5, 15)
key13 = 'atgca'


#### This is the method I defined.  ####
def constrainedMatchPair(firstMatch,secondMatch,length):
	"""This function takes three arguments: a tuple representing starting points for the first substring, a tuple representing starting points for the second substring, and the length of the first substring. The function should return a tuple of all members (call it n) of the first tuple for which there is an element in the second tuple (call it k) such that n+m+1 = k, where m is the length of the first substring."""
	answer = ()
	for i in firstMatch:
		for j in secondMatch:
			if i + length + 1 == j:
				answer += (i,)
	return answer

#### This is the method I defined in the earlier problem.  ####
def subStringMatchExact (target, key):
	"""This function returns a tuple of the starting position(s) of a key string within a target string"""
	answer_tuple = () # initialize the tuple we will return
	start = 0 # use this initial the starting point for find()
	while find(target, key, start) >=0:
		start = find(target, key, start)
		answer_tuple += (start,)
		start+=1
	return answer_tuple

### the following procedure you will use in Problem 3


def subStringMatchOneSub(key,target):
    """search for all locations of key in target, with one substitution"""
    allAnswers = ()
    for miss in range(0,len(key)):
        # miss picks location for missing element
        # key1 and key2 are substrings to match
        key1 = key[:miss]
        key2 = key[miss+1:]
        print 'breaking key',key,'into',key1,key2
        # match1 and match2 are tuples of locations of start of matches
        # for each substring in target
        match1 = subStringMatchExact(target,key1)
        match2 = subStringMatchExact(target,key2)
        # when we get here, we have two tuples of start points
        # need to filter pairs to decide which are correct
        filtered = constrainedMatchPair(match1,match2,len(key1))
        allAnswers = allAnswers + filtered
        print 'match1',match1
        print 'match2',match2
        print 'possible matches for',key1,key2,'start at',filtered
    return allAnswers

print subStringMatchOneSub(key11,target1)



#*****************************************************
#!/usr/local/bin/python
# Problem Set 3 (Problem 4)    ps3d.py
# Name: Scott Brenner
# Collaborators: None
# Date: 2011-02-01
# Time: 11:29 AM
#
#	This was so hard to solve.  I think it took over eight hours spread over a week.  I kept getting stuck on how to remove the perfect matches from the tuple that was returned.

#	If you remove the matches from the beginning of the tuple using positions, the positions, of course, shift.  If you try to do it by matching the perfect matches to the entire realm of matches, you can't just rely on comparison of the perfect start to a member of the entire realm.  You must test a conjunction of ALL perfect matches to the member of the entire realm.  I couldn't get this to work. Instead I built a list of the positions of the perfect matches and then removed those elements from the answer tuple.  The key was learning to iterate through a tuple backwards.  That way removing an element did not alter the position of the elements yet to be removed.

from string import *		#	used for find()

# Problem 4
# Write a function, called subStringMatchExactlyOneSub which takes two arguments: a target string and a key string. This function should return a tuple of all starting points of matches of the key to the target, such that at exactly one element of the key is incorrectly matched to the target. Complete the definition.  Save your answers in a file named ps3d.py.

target1 = 'atgacatgcacaagtatgcatatgacatgcacaagtatgcatatgacatgcacaagtatgcatatgacatgcacaagtatgcat'
#		   01234567890123456789
target2 = 'atgaatgcatggatgtaaatgcag'

# key strings

key10 = 'a'
key11 = 'atg' 	
key12 = 'atgc'
key13 = 'atgca'



def subStringMatchExactlyOneSub(target,key):
	"""
	This function takes two arguments: a target string and a key string. 
	
	It returns a tuple of all starting points of matches of the key to the target, such that at exactly one element of the key is incorrectly matched to the target.
	"""

	possible_answer = subStringMatchOneSub(key,target)
	answer = possible_answer
	perfect_matches = subStringMatchExact(target,key)
	to_remove_from_answer = ()

	#	this for loop identifies the positions in possible_answer that contain perfect matches.
	for i in range(0,len(possible_answer)):
		for j in range(0,len(perfect_matches)):
			if possible_answer[i] == perfect_matches[j]:
				#print "matches:", possible_answer[i]
				to_remove_from_answer += (i,)
				#print to_remove_from_answer

	# this for loop removes the items from the possible_answer tuple begin at the end and working forward. 
	for m in reversed(to_remove_from_answer):
		#print to_remove_from_answer[-m]
		#print m
		answer = answer[:m] + answer[m+1:]
		# print answer
	return answer


def constrainedMatchPair(firstMatch,secondMatch,length):  
	"""
	This function takes three arguments: a tuple representing starting points for the first substring, a tuple representing starting points for the second substring, and the length of the first substring.
	
	The function returns a tuple of all members (call it n) of the first tuple for which there is an element in the second tuple (call it k) such that n+m+1 = k, where m is the length of the first substring.
	"""
	
	answer = ()
	for i in firstMatch:
		for j in secondMatch:
			if i + length + 1 == j:
				answer += (i,)
	return answer

def subStringMatchExact(target, key):
	"""
	This function returns a tuple of the starting position(s) of a key string within a target string.
	"""
	answer_tuple = () # initialize the tuple we will return
	start = 0 # use this initial the starting point for find()
	while find(target, key, start) >=0:
		start = find(target, key, start)
		answer_tuple += (start,)
		start+=1
	return answer_tuple

def subStringMatchOneSub(key,target):
    """
	Search for all locations of key in target, with one substitution
	"""
    allAnswers = ()
    for miss in range(0,len(key)):
        # miss picks location for missing element
        # key1 and key2 are substrings to match
        key1 = key[:miss]
        key2 = key[miss+1:]
        #print 'breaking key',key,'into',key1,key2
        # match1 and match2 are tuples of locations of start of matches
        # for each substring in target
        match1 = subStringMatchExact(target,key1)
        match2 = subStringMatchExact(target,key2)
        # when we get here, we have two tuples of start points
        # need to filter pairs to decide which are correct
        filtered = constrainedMatchPair(match1,match2,len(key1))
        allAnswers = allAnswers + filtered
        #print 'match1',match1
        #print 'match2',match2
        #print 'possible matches for',key1,key2,'start at',filtered
    return allAnswers
    
#print subStringMatchOneSub(key12,target1)
print subStringMatchExactlyOneSub(target1,key11)

#!/usr/bin/env python
# encoding: utf-8

# 6.00 Problem Set 12
#
# Name: Scott Brenner
# Collaborators: http://curiousreef.com/class/mit-opencourseware-600-introduction/lesson/23/assgn/1/
# Time: Too long.

import numpy
import random
import pylab

class NoChildException(Exception):
	"""
	NoChildException is raised by the reproduce() method in the SimpleVirus
	and ResistantVirus classes to indicate that a virus particle does not
	reproduce. You can use NoChildException as is, you do not need to
	modify/add any code.
	"""	

#
# PROBLEM 1
#

class SimpleVirus(object):
	"""
	Representation of a simple virus (does not model drug effects/resistance).
	"""
	
	def __init__(self, maxBirthProb, clearProb):
		"""
		Initialize a SimpleVirus instance, saves all parameters as attributes
		of the instance.
		maxBirthProb: Maximum reproduction probability (a float between 0-1)				
		clearProb: Maximum clearance probability (a float between 0-1).
		"""
		# TODO
		self.maxBirthProb = maxBirthProb
		self.clearProb = clearProb
		
	def doesClear(self):
		"""
		Stochastically determines whether this virus is cleared from the
		patient's body at a time step. 
		
		returns: Using a random number generator (random.random()), this method
		returns True with probability self.clearProb and otherwise returns
		False.
		"""
		# TODO
		if random.random() <= self.clearProb:
			return True
		else:
			return False
	
	def reproduce(self, popDensity):
		"""
		Stochastically determines whether this virus particle reproduces at a
		time step. Called by the update() method in the SimplePatient and
		Patient classes. The virus particle reproduces with probability
		self.maxBirthProb * (1 - popDensity).
		
		If this virus particle reproduces, then reproduce() creates and returns
		the instance of the offspring SimpleVirus (which has the same
		maxBirthProb and clearProb values as its parent).		 
		
		popDensity: the population density (a float), defined as the current
		virus population divided by the maximum population.		 
		
		returns: a new instance of the SimpleVirus class representing the
		offspring of this virus particle. The child should have the same
		maxBirthProb and clearProb values as this virus. Raises a
		NoChildException if this virus particle does not reproduce.			   
		"""
		# TODO
		if random.random() <= ( self.maxBirthProb * ( 1 - popDensity ) ):
			# print "virus reproduces"
			return SimpleVirus( self.maxBirthProb, self.clearProb )
		else:
			raise NoChildException('In reproduce()')
	

class SimplePatient(object):
	"""
	Representation of a simplified patient. The patient does not take any drugs
	and his/her virus populations have no drug resistance.
	"""
	
	def __init__(self, viruses, maxPop):
		"""
		Initialization function, saves the viruses and maxPop parameters as
		attributes.
		
		viruses: the list representing the virus population (a list of
		SimpleVirus instances)
		
		maxPop: the  maximum virus population for this patient (an integer)
		"""
		# TODO
		self.viruses = viruses
		self.maxPop = maxPop
	
	def getTotalPop(self):
		"""
		Gets the current total virus population. 

		returns: The total virus population (an integer)
		"""
		# TODO		
		return len( self.viruses )
	
	def update(self):
		"""
		Update the state of the virus population in this patient for a single
		time step. update() should execute the following steps in this order:

		- Determine whether each virus particle survives and updates the list
		  of virus particles accordingly.

		- The current population density is calculated. This population density
		  value is used until the next call to update() 

		- Determine whether each virus particle should reproduce and add
		  offspring virus particles to the list of viruses in this patient.					

		returns: the total virus population at the end of the update (an
		integer)
		"""
		# TODO
		# Determine whether each virus particle survives and updates the 
		# list of virus particles accordingly.
		newViruses = []
		for index, virus in reversed( list( enumerate( self.viruses ) ) ):
			if virus.doesClear():
				# print "Virus clears"
				# pop virus from viruses list
				self.viruses.pop( index )
			else:
				popDensity = self.getTotalPop()/float(self.maxPop)
				try:
					# determine if surving virus reproduces
					# append any offspring to new virus list
					newViruses.append( virus.reproduce( popDensity ) )
				except NoChildException:
					continue
		# print "self.viruses =", self.viruses
		# print "newViruses =",  newViruses
		# add the new viruses to the list of patient viruses
		self.viruses = self.viruses + newViruses
		# print self.viruses

		return self.getTotalPop()
	
#
# PROBLEM 2
#

def problem2():
	"""
	Run the simulation and plot the graph for problem 2 (no drugs are used,
	viruses do not have any drug resistance).	
	
	Instantiates a patient, runs a simulation for 300 timesteps, and plots the
	total virus population as a function of time.	
	"""
	# TODO
	# Create 100 viruses with
	#	maxBirthProb = 0.1 
	#	clearProb = 0.05 
	listOfViruses = [] 
	print "\ncreating virues...",
	for each in range( 100 ):
		listOfViruses.append( SimpleVirus( 0.1, .05 ) )
		print each, 
	
	# Create a patient with 100 viruses and maxPop of 1000
	print "\nCreating patient"
	testPatient = SimplePatient( listOfViruses, 1000)
	
	# Run the 300 step times on patient.  Record the virus population after each step.  The initial population is 100.
	listOfVirusPop = [ ]
	timeSteps = []
	print "\nRunning time step",
	for each in range( 300 ):
		print each,
		listOfVirusPop.append( testPatient.update() )
		timeSteps.append( each )
	
	# graph results
	pylab.figure()
	pylab.plot( timeSteps, listOfVirusPop )
	pylab.ylabel( 'Viruse Population' )
	pylab.xlabel( 'Timesteps' )
	pylab.title( 'ps12.py - Problem 2: Total virus population over time' )
	# pylab.show()


problem2()
# Writeup:  Somewhere between 100 and 150 steps the virus population stops growing, stabilizing around 475 (fluctuating between 450 & 500).


#
# PROBLEM 3
#

class ResistantVirus(SimpleVirus):
	"""
	Representation of a virus which can have drug resistance.
	"""	
	
	def __init__(self, maxBirthProb, clearProb, resistances, mutProb):
		"""
		Initialize a ResistantVirus instance, saves all parameters as attributes
		of the instance.
		
		maxBirthProb: Maximum reproduction probability (a float between 0-1)		
		
		clearProb: Maximum clearance probability (a float between 0-1).
		
		resistances: A dictionary of drug names (strings) mapping to the state
		of this virus particle's resistance (either True or False) to each drug.
		e.g. {'guttagonol':False, 'grimpex',False}, means that this virus
		particle is resistant to neither guttagonol nor grimpex.
		
		mutProb: Mutation probability for this virus particle (a float). This is
		the probability of the offspring acquiring or losing resistance to a drug.		
		"""
		# TODO
		self.maxBirthProb = maxBirthProb
		self.clearProb = clearProb
		self.resistances = resistances
		self.mutProb = mutProb
	
	def getResistance(self, drug):
		"""
		Get the state of this virus particle's resistance to a drug. This method
		is called by getResistPop() in Patient to determine how many virus
		particles have resistance to a drug.		
		
		drug: the drug (a string).
		
		returns: True if this virus instance is resistant to the drug, False
		otherwise.
		"""
		# TODO
		# lookup drug in the self.resistances dictionary 
		# if the value is true return true, else return false.
		return self.resistances.get( drug, False )		 
	
	def reproduce(self, popDensity, activeDrugs):
		"""
		Stochastically determines whether this virus particle reproduces at a
		time step. Called by the update() method in the Patient class.
		
		If the virus particle is not resistant to any drug in activeDrugs,
		then it does not reproduce. Otherwise, the virus particle reproduces
		with probability:	   
		
		self.maxBirthProb * (1 - popDensity).					   
		
		If this virus particle reproduces, then reproduce() creates and returns
		the instance of the offspring ResistantVirus (which has the same
		maxBirthProb and clearProb values as its parent). 
		
		For each drug resistance trait of the virus (i.e. each key of
		self.resistances), the offspring has probability 1-mutProb of
		inheriting that resistance trait from the parent, and probability
		mutProb of switching that resistance trait in the offspring.		
		
		For example, if a virus particle is resistant to guttagonol but not
		grimpex, and `self.mutProb` is 0.1, then there is a 10% chance that
		that the offspring will lose resistance to guttagonol and a 90% 
		chance that the offspring will be resistant to guttagonol.
		There is also a 10% chance that the offspring will gain resistance to
		grimpex and a 90% chance that the offspring will not be resistant to
		grimpex.
		
		popDensity: the population density (a float), defined as the current
		virus population divided by the maximum population		
		
		activeDrugs: a list of the drug names acting on this virus particle
		(a list of strings). 
		
		returns: a new instance of the ResistantVirus class representing the
		offspring of this virus particle. The child should have the same
		maxBirthProb and clearProb values as this virus. Raises a
		NoChildException if this virus particle does not reproduce.		 
		"""
		# TODO
		# 	The instructions are unclear on whether offspring viruses inherit
		#	the same mutProb as their partent?	I assumed that they do.
				
		for drug in activeDrugs:
			if not self.getResistance( drug ):
				raise NoChildException()
		# If we get here then we know the virus is resistent to all of the activeDrugs
		
		# Now let's see if it reproduces
		if random.random() <= ( self.maxBirthProb * ( 1 - popDensity ) ):
			# figure out the resistances, mutProb
			newResistances = {}
			for drug in self.resistances:
				if random.random() <= ( 1 - self.mutProb ):
					newResistances[ drug ] = self.resistances[ drug ]
				else:
					newResistances[ drug ] = not self.resistances[ drug ]
			return ResistantVirus( self.maxBirthProb, self.clearProb, newResistances, self.mutProb )
		else:
			raise NoChildException()

					
class Patient( SimplePatient ):
	"""
	Representation of a patient. The patient is able to take drugs and his/her
	virus population can acquire resistance to the drugs he/she takes.
	"""
	def __init__(self, viruses, maxPop):
		"""
		Initialization function, saves the viruses and maxPop parameters as
		attributes. Also initializes the list of drugs being administered
		(which should initially include no drugs).			   
		
		viruses: the list representing the virus population (a list of
		SimpleVirus instances)
		
		maxPop: the  maximum virus population for this patient (an integer)
		"""
		# TODO
		self.viruses = viruses
		self.maxPop = maxPop
		self.presecribedDrugs = []
	
	def addPrescription(self, newDrug):
		"""
		Administer a drug to this patient. After a prescription is added, the 
		drug acts on the virus population for all subsequent time steps. If the
		newDrug is already prescribed to this patient, the method has no effect.
		
		newDrug: The name of the drug to administer to the patient (a string).
		
		postcondition: list of drugs being administered to a patient is updated
		"""
		# TODO
		self.presecribedDrugs.append( newDrug )
	
	def getPrescriptions(self):
		"""
		Returns the drugs that are being administered to this patient.

		returns: The list of drug names (strings) being administered to this
		patient.
		"""
		# TODO
		return self.presecribedDrugs
	
	def getResistPop(self, drugResist):
		"""
		Get the population of virus particles resistant to the drugs listed in 
		drugResist.		

		drugResist: Which drug resistances to include in the population (a list
		of strings - e.g. ['guttagonol'] or ['guttagonol', 'grimpex'])

		returns: the population of viruses (an integer) with resistances to all
		drugs in the drugResist list.
		"""
		# TODO
		resistantPopulation = 0
		for virus in self.viruses:
			drugsResisted = 0
			for drug in drugResist:		# drugResist is a list of drugs
				if virus.getResistance( drug ):
					drugsResisted += 1
			if drugsResisted == len( drugResist ):
				resistantPopulation += 1
		return resistantPopulation
	
	def update(self):
		"""
		Update the state of the virus population in this patient for a single
		time step. update() should execute these actions in order:

		- Determine whether each virus particle survives and update the list of 
		  virus particles accordingly
		  
		- The current population density is calculated. This population density
		  value is used until the next call to update().

		- Determine whether each virus particle should reproduce and add
		  offspring virus particles to the list of viruses in this patient. 
		  The listof drugs being administered should be accounted for in the
		  determination of whether each virus particle reproduces. 

		returns: the total virus population at the end of the update (an
		integer)
		"""
		# TODO
		newViruses = []
		for index, virus in reversed( list( enumerate( self.viruses ) ) ):
			if virus.doesClear():
					self.viruses.pop( index )
			else:
				popDensity = self.getTotalPop() / float( self.maxPop )
				try:
					newViruses.append( virus.reproduce( popDensity, self.presecribedDrugs ) )
				except NoChildException:
					continue
		self.viruses = self.viruses + newViruses
		return self.getTotalPop()
	

#
# PROBLEM 4
#
def problem4():
	"""
	Runs simulations and plots graphs for problem 4.
	
	Instantiates a patient, runs a simulation for 150 timesteps, adds
	guttagonol, and runs the simulation for an additional 150 timesteps.
	
	Total virus population vs. time  and guttagonol-resistant virus population
	vs. time are plotted
	"""
	# TODO
	simulationSteps = 300
	#	Patient variables.
	initialViruseCount = 100 
	maxPop = 1000
	# Virus variables:
	maxBirthProb = 0.1
	clearProb = 0.05
	resistances = { 'guttagonol':False }
	mutProb = 0.005
	
	#	Create viruses
	listOfViruses = [] 
	print "\nCreating viruses...",
	for each in range( initialViruseCount ):
		listOfViruses.append( ResistantVirus( maxBirthProb, clearProb, resistances, mutProb) ) 
	
	# Create a patient with 100 viruses and maxPop of 1000
	print "\nCreating patient"
	testPatient = Patient( listOfViruses, maxPop )
	
	# Run 300 timestep on patient.  Record the virus population after each step.  The initial population is 100.  At the 150th timestep 
	listOfVirusPop = [ ]
	guttagonolResistant = [ ]
	for each in range( simulationSteps ):
		listOfVirusPop.append( testPatient.update() )
		guttagonolResistant.append( testPatient.getResistPop( ['guttagonol'] )  )
		if each == 150: testPatient.addPrescription( "guttagonol" )
			
	# graph results
	pylab.figure()
	pylab.plot( listOfVirusPop, label='Total')
	pylab.plot( guttagonolResistant, label='Guttagonol-resistant viruses')
	pylab.ylabel( 'Viruse Population' )
	pylab.xlabel( 'Timesteps' )
	pylab.title( 'Problem 4: Total virus population over time. Guttagonol prescribed at 150.' )
	pylab.legend( loc = 2 )
	pylab.show()

problem4()
# As in the other simulations the virus population stabilizes after 150 time steps at about 450-500 viruses. Then number of Guttagonol resistant viruses is negligible until Guttagonol is introduced.  After Guttagonol is introduced, the virus population plummets until a sufficient number develop resistance to Guttagonol, the the virus population appears to return to 450.
# The trends were consistent with my intuition, but I was surprised that the virus population, after the introduction of Guttagonol, return to 450-500.  I thought it would recover, but stabilize at a lower population.  I figured that since some of the descendants of each virus would mutate to lose their resistance to Guttagonol only a smaller population could be sustained.


#
# PROBLEM 5
#
def problem5():
	"""
	Runs simulations and make histograms for problem 5.
	
	Runs multiple simulations to show the relationship between delayed treatment
	and patient outcome.
	
	Histograms of final total virus populations are displayed for delays of 300,
	150, 75, 0 timesteps (followed by an additional 150 timesteps of
	simulation).
	
	If the virus population is less than 50, the patient is considered cured or in remission.
	"""
	# TODO
	numPatients = 200
	
	# ==================================================================
	# = Run simulation for 300 steps, then treat, then 150 more steps. =
	# ==================================================================
	title = "ps12.py - Problem 5: " + str(numPatients) + " patients-- 300 timesteps, Treat, 150 more timesteps."  
	print
	print title
	virusCounts = []
	numCured = 0
	for each in range( numPatients ):
		finalViruses = runPatietTreatment( 450, 300, "guttagonol" )
		# print "\nPatient", each, finalViruses, 
		virusCounts.append( finalViruses )
		if finalViruses <= 50:
			numCured += 1	
	print "\nOf the %i patients in the trial, %i were cured ( %3.1f%% ).  %3.1f%% were not cured." % ( numPatients, numCured, 100 * ( float( numCured ) / float( numPatients )) , 100 * (1 - float( numCured ) / float( numPatients ) ) )
		
	# graph results
	pylab.figure()
	pylab.hist( virusCounts )
	pylab.ylabel( 'Number of Patients' )
	pylab.xlabel( 'Final Total Virus Populations --' + str(100 * ( float( numCured ) / float( numPatients ))) + "% cured."  )
	pylab.title( title )
	
	# ==================================================================
	# = Run simulation for 150 steps, then treat, then 150 more steps. =
	# ==================================================================
	title = "Problem 5:" + str(numPatients) + " patients-- 150 timesteps, Treat, 150 more timesteps."  
	print
	print title
	virusCounts = []
	numCured = 0
	for each in range( numPatients ):
		finalViruses = runPatietTreatment( 300, 150, "guttagonol" )
		# print "\nPatient", each, finalViruses, 
		virusCounts.append( finalViruses )
		if finalViruses <= 50:
			numCured += 1
	print "\nOf the %i patients in the trial, %i were cured ( %3.1f%% ).  %3.1f%% were not cured." % ( numPatients, numCured, 100 * ( float( numCured ) / float( numPatients )) , 100 * (1 - float( numCured ) / float( numPatients ) ) )
		
	# graph results
	pylab.figure()
	pylab.hist( virusCounts )
	pylab.ylabel( 'Number of Patients' )
	pylab.xlabel( 'Final Total Virus Populations --' + str(100 * ( float( numCured ) / float( numPatients ))) + "% cured."  )
	pylab.title( title )
	
	# ==================================================================
	# = Run simulation for 75 steps, then treat, then 150 more steps. =
	# ==================================================================
	title = "Problem 5:" + str(numPatients) + " patients--  75 timesteps, Treat, 150 more timesteps." 
	print
	print title
	virusCounts = []
	numCured = 0
	for each in range( numPatients ):
		finalViruses = runPatietTreatment( 225, 75, "guttagonol" )
		# print "\nPatient", each, finalViruses, 
		virusCounts.append( finalViruses )
		if finalViruses <= 50:
			numCured += 1
	print "\nOf the %i patients in the trial, %i were cured ( %3.1f%% ).  %3.1f%% were not cured." % ( numPatients, numCured, 100 * ( float( numCured ) / float( numPatients )) , 100 * (1 - float( numCured ) / float( numPatients ) ) )
		
	# graph results
	pylab.figure()
	pylab.hist( virusCounts )
	pylab.ylabel( 'Number of Patients' )
	pylab.xlabel( 'Final Total Virus Populations --' + str(100 * ( float( numCured ) / float( numPatients ))) + "% cured."  )
	pylab.title( title )
	
	# ==================================================================
	# = Run simulation for 0 steps, then treat, then 150 more steps. =
	# ==================================================================
	title = "Problem 5:" + str(numPatients) + " patients--0 timesteps, treat, 75 more timesteps."
	print
	print title
	virusCounts = []
	numCured = 0
	for each in range( numPatients ):
		finalViruses = runPatietTreatment( 75, 0, "guttagonol" )
		# print "\nPatient", each, finalViruses, 
		virusCounts.append( finalViruses )
		if finalViruses <= 50:
			numCured += 1
	print "\nOf the %i patients in the trial, %i were cured ( %3.1f%% ).  %3.1f%% were not cured." % ( numPatients, numCured, 100 * ( float( numCured ) / float( numPatients )) , 100 * (1 - float( numCured ) / float( numPatients ) ) )
		
	# graph results
	pylab.figure()
	pylab.hist( virusCounts )
	pylab.ylabel( 'Number of Patients' )
	pylab.xlabel( 'Final Total Virus Populations --' + str(100 * ( float( numCured ) / float( numPatients ))) + "% cured."  )
	pylab.title( title )
	pylab.show()


def runPatietTreatment( simulationSteps, timeTillTreatment, drug, initialViruseCount = 100, maxPop = 1000, maxBirthProb = 0.1, clearProb = 0.05, mutProb = 0.005, 	resistances = { 'guttagonol':False } ):
	"""
	This helper function takes the above parametrs and returns
	the virus populaton at the end of the treatment.
	"""
	# Create Patient
	virusCount = 0
	listOfViruses = []
	for each in range( initialViruseCount ):
		listOfViruses.append( ResistantVirus( maxBirthProb, clearProb, resistances, mutProb) )
	testPatient = Patient( listOfViruses, maxPop )
	
	for each in range( simulationSteps ):
		virusCount = testPatient.update()
		if each == timeTillTreatment: testPatient.addPrescription( drug )
	return virusCount

problem5()

# Writeup:
# I repeated each condition 200 times.  This was more that enough to obtain a reasonable distribution.  I can tell the distribution is reasonable because the number of trial in each “bucket” of the histogram is above.  In addition, the outcome matched my understanding of reality--the longer treatment is delayed, the less likely it is to be successful.  
# 
# This relationship arises in the model because the longer treatment delay, the more time the viruses have to mutate Guttagonol resistance.  If the drug is administered right at the start there are few viruses, and none are resistant.  The more time the elapses, the larger the virus population and the larger the population of Guttagonol-resistant viruses
# 
# When treatment is delayed until after 300 timesteps only  2.5% of the patients are cured or in remission.97.5% are not cured.
# 
# When treatment is delayed until after 150 timesteps only  5% of the patients are cured or in remission.95% are not cured.
# 
# When treatment is delayed until after 75 timesteps only 16% of the patients are cured or in remission.84% are not cured.
# 
# When treatment is not delayed 99.5% of the patients are cured or in remission. .54% are not cured.
# Delay 			% Cured
# 300				2.5%
# 150				5%
# 75				16%
# 0					99.5%

#
# PROBLEM 6
#
def problem6():
	"""
	Runs simulations and make histograms for problem 6.
	
	Runs multiple simulations to show the relationship between administration
	of multiple drugs and patient outcome.
	
	Histograms of final total virus populations are displayed for lag times of
	150, 75, 0 timesteps between adding drugs (followed by an additional 150
	timesteps of simulation).
	
	viruses = 100
	maxPop = 1000
	
	maxBirthProb = 0.1
	clearProb = 0.05
	resistances = {‘guttagonol’:False ‘grimpex’:False}
	mutProb = 0.005
	
	Run the simulation for 150 time steps before administering guttagonol to the patient. Then run the simulation for 300, 150, 75, and 0 time steps before administering a second drug, grimpex, to the patient. Finally, run the simulation for an additional 150 time steps.
	
	
	"""
	# Initial Values
	patientsPerScheme = 30
	treatmentSchemes = [ 300, 150, 75, 0]
	initialViruseCount = 100
	maxPop = 1000
	maxBirthProb = 0.1
	clearProb = 0.05
	resistances = {'guttagonol':False, 'grimpex':False}
	mutProb = 0.005
	
	# Create a list of virusus
	listOfViruses = []
	for each in range( initialViruseCount ):
		listOfViruses.append( ResistantVirus( maxBirthProb, clearProb, resistances, mutProb) )
	
	
	for timeTillTreatment in treatmentSchemes:
		finalVirusCounts = [ ]
		numCured = 0
		for patient in range( patientsPerScheme ):
			testPatient = Patient( listOfViruses, maxPop )
			continueTrial = True
			stepCount = 1
			while stepCount < timeTillTreatment + 301:
				virusCount = testPatient.update()
				stepCount += 1
				if stepCount == 150:
					testPatient.addPrescription( "guttagonol" )
				if stepCount == timeTillTreatment + 150:
					testPatient.addPrescription( "grimpex" )
			finalVirusCounts.append( virusCount )
			if virusCount <= 50:
				numCured += 1
		
		print "These are the final virus counts after running 150 steps, treating with Guttagonol, running %i more steps, adding Grimpex, then running 150 more steps:" % timeTillTreatment 
		print finalVirusCounts
		print "\nOf the %i patients in the scheme, %i were cured ( %3.1f%% ).  %3.1f%% were not cured." % ( patientsPerScheme, numCured, 100 * ( float( numCured ) / float( patientsPerScheme )) , 100 * (1 - float( numCured ) / float( patientsPerScheme ) ) )
		title = "ps12.py - Problem 6: %i steps till treatment with 2nd drug. Cure rate = %2.0f%%." % ( timeTillTreatment, 100 * ( float( numCured ) / float( patientsPerScheme )))
		# graph results
		pylab.figure()
		pylab.hist( finalVirusCounts )
		pylab.ylabel( 'Number of Patients' )
		pylab.xlabel( 'Final Total Virus Populations' )
		pylab.title( title )
	pylab.show()

problem6()
# Write up:
# As with the earlier experiments, delaying treatment reduces the likelihood that the treatment will eradicate the viruses.  The more time the viruses are given to build their population and evolved resistance to a drug the more likely the drug will fail.
# 
# However, in this dual drug treatment is more effective than a single drug treatment, even when the second drug is delayed.  This is likely because the first drug had reduced the population of the viruses.

# Delay 		% Cured
# 300			~7%
# 150			~10%
# 75			~93%
# 0				~100%

#
# PROBLEM 7
#
def problem7( guttagonolAt, grimpexAt ):
	"""
	Run simulations and plot graphs examining the relationship between
	administration of multiple drugs and patient outcome.
	
	Plots of total and drug-resistant viruses vs. time are made for a
	simulation with a 300 time step delay between administering the 2 drugs and
	a simulations for which drugs are administered simultaneously.		
	"""
	# TODO
	# Initial Values
	initialViruseCount = 100
	maxPop = 1000
	maxBirthProb = 0.1
	clearProb = 0.05
	resistances = {'guttagonol':False, 'grimpex':False}
	mutProb = 0.005
	totalViruses = [ ]
	guttagonolResistant = [ ]
	grimpexResistant = []
	dualResistant = []
	stepCount = 1
		
	# Create a list of virusus
	listOfViruses = []
	for each in range( initialViruseCount ):
		listOfViruses.append( ResistantVirus( maxBirthProb, clearProb, resistances, mutProb) )	
	
	#Create Patient 
	testPatient = Patient( listOfViruses, maxPop )
	
	# this while loop asumes that grimpex is adminstered last and the 300 more time steps are simulated.
	while stepCount < grimpexAt + 301:
		virusCount = testPatient.update()
		stepCount += 1
		if stepCount == guttagonolAt:
			testPatient.addPrescription( "guttagonol" )
		if stepCount == grimpexAt:
			testPatient.addPrescription( "grimpex" )
		totalViruses.append( testPatient.getTotalPop() )
		guttagonolResistant.append( testPatient.getResistPop( ['guttagonol'] )  )
		grimpexResistant.append(  testPatient.getResistPop( ['grimpex'] )  )
		dualResistant.append( testPatient.getResistPop( ['guttagonol', 'grimpex'] )  )
	# graph results
	title = "ps12.py - Problem 7: Guttagonol @%i; Grimpex@ %i." % ( guttagonolAt, grimpexAt )
	
	pylab.figure()
	pylab.plot( totalViruses, label='Total')
	pylab.plot( guttagonolResistant, label='Guttagonol-resistant virus')
	pylab.plot( grimpexResistant, label='Grimpex-resistant virus')
	pylab.plot( dualResistant, label='Resistant to both drugs')
	pylab.ylabel( 'Number Viruses' )
	pylab.xlabel( 'Time' )
	pylab.title( title )
	pylab.legend( loc = 1 )
	pylab.show()

problem7( guttagonolAt = 150, grimpexAt = 300 )
problem7( guttagonolAt = 150, grimpexAt = 150 )

# ====================
# = Problem 8 writup =
# ====================
# To model patients forgetting to take their drugs I would add a property to the patient object and modify the getPrescriptions() method. 
# 
# The property, a float, would model the likelihood that a patient would take their prescriptions, e.g., .9 for a patient who takes their prescriptions 90% of the time.
# 
# The getPrescriptions() method would be modified to model this likelihood.  For example if the likelihood the patient would take their drugs is .9 then the method would return the active drugs only 90% of the time.

#!/usr/local/bin/python

##	Problem 1.
	##	Show that it is possible to buy exactly 50, 51, 52, 53, 54, and 55 McNuggets, by finding solutions to the Diophantine equation. You can solve this in your head, using paper and pencil, or writing a program. However you chose to solve this problem, list the combinations of 6, 9 and 20 packs of McNuggets you need to buy in order to get each of the exact amounts.  Given that it is possible to buy sets of 50, 51, 52, 53, 54 or 55 McNuggets by combinations of 6, 9 and 20 packs, show that it is possible to buy 56, 57,..., 65 McNuggets. In other words, show how, given solutions for 50-55, one can derive solutions for 56-65.  If it is possible to buy x,x+1,...,x+5 sets of McNuggets,for some x,then it is possible to buy any number of McNuggets >= x, given that McNuggets come in 6, 9 and 20 packs.

	##	6a + 9b + 20c = n
	##	6a = n - 9b -20c 
	##	a = n/6 - 3/2b - 10/3c
	
	# 49 = (2*20) + (0*6) + (1*9)  # just curious
	# 50 = (1*20) + (2*6) + (2*9)
	# 51 = (0*20) + (4*6) + (3*9)
	# 52 = (2*20) + (2*6) + (0*9)
	# 53 = (1*20) + (1*6) + (3*9)
	# 54 = (0*20) + (0*6) + (6*9)
	# 55 = (2*20) + (1*6) + (1*9)
##------
	# 56 = (1*20) + (3*6) + (2*9)
	# 57 = (0*20) + (4*6) + (3*9)
	# 58 = (2*20) + (3*6) + (0*9)
	# 59 = (1*20) + (2*6) + (3*9)
	# 60 = (0*20) + (1*6) + (6*9)
	# 61 = (2*20) + (2*6) + (1*9)
	# 62 = (1*20) + (4*6) + (2*9)
	# 63 = (0*20) + (6*6) + (3*9)
	# 64 = (2*20) + (4*6) + (0*9)
	# 65 = (1*20) + (3*6) + (3*9)
	
#	Problem 2: Explain, in English, why this theorem is true.
## For this type of problem, if you can find a string of sequential numbers that is as long as the smallest counting unit then you can count to any subsequent number by adding this smallest counting unit a member of this base sequential series. Wow. 


# Problem 3
#
	#	Write an iterative program that finds the largest number of McNuggets that cannot be bought in exact quantity. Your program should print the answer in the following format (where the correct number is provided in place of <n>):

#	largest number of McNuggets that cannot be bought in exact quantity:
	#	Hint: your program should follow the outline above.
	#	Hint: think about what information you need to keep track of as you loop through possible ways of buying exactly n McNuggets. This will guide you in deciding what state variables you will need to utilize.
	#	Save your code for Problem 3 in ps2a.py.



#	Using this theorem, we can write an exhaustive search to find the largest number of McNuggets that cannot be bought in exact quantity. The format of the search should probably follow this outline:
#	Hypothesize possible instances of numbers of McNuggets that cannot be purchased exactly, starting with 1
#For each possible instance, called n,
	#Test if there exists non-negative integers a, b, and c, such that 6a+9b+20c = n. (This can be done by looking at all feasible combinations of a, b, and c) 
	#If not, n cannot be bought in exact quantity, save n
#	When you have found six consecutive values of n that in fact pass the test of having an exact solution, the last answer that was saved (not the last value of n that had a solution) is the correct answer, since you know by the theorem that any amount larger can also be bought in exact quantity

print 'Problem 3'
print

def is_n_solveable(n):
	a = 0
	b = 0
	c = 0
	for a in range(10):
		#print 'in a for loop. a:', a,'b:',b,'c:',c,'n:',n
		if 6*a + 9*b + 20*c == n:
			return 1
			#ns_passed_test.append(n)
			#print n, "passed"	
		for b in range(10):
			#print 'in b for loop. a:', a,'b:',b,'c:',c,'n:',n
			if 6*a + 9*b + 20*c == n:
				return 1
				#ns_passed_test.append(n)
				#print n, "passed"
			for c in range(10):
				#print 'in c for loop. a:', a,'b:',b,'c:',c,'n:',n
				if 6*a + 9*b + 20*c == n:
					return 1
					#ns_passed_test.append(n)
					#print n, "passed"
	return 0

counter = 0
highest_number_to_test = 43

for n in range(highest_number_to_test+7):
	if is_n_solveable(n):
		counter = counter + 1
	else:
		counter = 0

	if counter == 6:
		print n-6, "is highest number of nuggets that can not be ordered in a 6,9,20 combo."
	elif n == highest_number_to_test+7:
		print 'The highest number of noggest that cannot be ordereed in a in 6,9,20 combo is greater than', highest_number_to_test

print 
print 'End of problem 3'
print 

##	Problem 4.
##	Assume that the variable packages is bound to a tuple of length 3, the values of which specify the sizes of the packages, ordered from smallest to largest. Write a program that uses exhaustive search to find the largest number (less than 200) of McNuggets that cannot be bought in exact quantity. We limit the number to be less than 200 (although this is an arbitrary choice) because in some cases there is no largest value that cannot be bought in exact quantity, and we don't want to search forever. Please use ps2b_template.py to structure your code.
##	Have your code print out its result in the following format:
##	"Given package sizes <x>, <y>, and <z>, the largest number of McNuggets that cannot be bought in exact quantity is: <n>"

##	Test your program on a variety of choices, by changing the value for packages. Include the case (6,9,20), as well as some other test cases of your own choosing.

##	This problem took 4-5 hours over the course of a couple days.

print 'Problem 4'
print 

packages = (6, 9, 20)

def is_n_solveable(n,packages):
	"""Takes a value n and a 3-member tuple.  The tuple describes the three package size, e.g., 6, 9, 20 McNuggets. The function tests whether any combination of the packages will add up to exactly n."""

	a = 0
	b = 0
	c = 0
	for a in range(10):
		#print 'in a for loop. a:', a,'b:',b,'c:',c,'n:',n
		if packages[0]*a + packages[1]*b + packages[2]*c == n:
			return 1
			#ns_passed_test.append(n)
			#print n, "passed"	
		for b in range(10):
			#print 'in b for loop. a:', a,'b:',b,'c:',c,'n:',n
			if packages[0]*a + packages[1]*b + packages[2]*c == n:
				return 1
				#ns_passed_test.append(n)
				#print n, "passed"
			for c in range(10):
				#print 'in c for loop. a:', a,'b:',b,'c:',c,'n:',n
				if packages[0]*a + packages[1]*b + packages[2]*c == n:
					return 1
					#ns_passed_test.append(n)
					#print n, "passed"
	return 0

counter = 0	

x = 6
y = 9
z = 20

for n in range(100):
	if is_n_solveable(n, packages):
		counter = counter + 1
	else:
		counter = 0
	if counter == packages[0]:
		print 'Given package sizes', packages[0], ',', packages[1], ', and', packages[2], 'the largest number of McNuggets that cannot be bought in exact quantity is:', n-packages[0]
print		
print 'end of Problem 4'
print 

		
print 'Problem 4.1: the prescribed format.'

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
packages_1 = (16,19,20)   # variable that contains package sizes
packages_2 = (7,15,20)   # variable that contains package sizes
packages_3 = (9,12,20)   # variable that contains package sizes
packages_4 = (11,16,20)   # variable that contains package sizes
packages_5 = (4,9,16)   # variable that contains package sizes

six_packages = (packages,packages_1,packages_2,packages_3,packages_4,packages_5)
packages_to_test = len(six_packages)

def is_n_solveable(n,packages):
	"""Takes a value n and a 3-member tuple.  The tuple describes the three package size, e.g., 6, 9, 20 McNuggets. The function tests whether any combination of the packages will add up to exactly n."""
	a = 0	# Initialize the multiples of each package size.
	b = 0
	c = 0
	for a in range(10):
		# print 'in a for loop. a:', a,'b:',b,'c:',c,'n:',n
		# print packages[0]
		
		if packages[0]*a + packages[1]*b + packages[2]*c == n:
			return 1
			#ns_passed_test.append(n)
			#print n, "passed"	
		for b in range(10):
			#print 'in b for loop. a:', a,'b:',b,'c:',c,'n:',n
			if packages[0]*a + packages[1]*b + packages[2]*c == n:
				return 1
				#ns_passed_test.append(n)
				#print n, "passed"
			for c in range(10):
				#print 'in c for loop. a:', a,'b:',b,'c:',c,'n:',n
				if packages[0]*a + packages[1]*b + packages[2]*c == n:
					return 1
					#ns_passed_test.append(n)
					#print n, "passed"
	return 0

	
def test_multiple_pack_combos(packages):
	"""This function takes a tuple of tuples and tests each tuple to see what is the highest number of nuggets that cannot be exactly purchased by the packages sizes described in the tuples."""
	for n in range(1, 150):   # only search for solutions up to size 150
		## complete code here to find largest size that cannot be bought
		## when done, your answer should be bound to bestSoFar
		
		
		if is_n_solveable(n, packages):
			bestSoFar = bestSoFar + 1
		else:
			bestSoFar = 0
		
		if bestSoFar == packages[0]:
			print 'Given package sizes', packages[0], ',', packages[1], ', and', packages[2], 'the largest number of McNuggets that cannot be bought in exact quantity is:', n-packages[0]
			
for each in range(packages_to_test-1):
	#	print six_packages[each]
	test_multiple_pack_combos(six_packages[each])

#!/usr/local/bin/python

##	Problem 1.  Write a program that computes and prints the 1000th prime number.
## This problem took just over one hour to program.

#	start with the first candiate
candidates = [1,3]

#	start with the know primes
primes = [2]

def next_odd_number(x):
	"""
	This function takes an odd number and
	returns the next odd number.
	"""
	if x%2 == 0:
		print "Error: next_odd_number was pass an non-odd number."
		return None
	else:
		return x+2

		
def isPrime(x):
	"""
	This function takes an integer and returns a 
	1 if the number is prime and a 0 if it is not prime.
	"""
	counter = 1
	while counter <= x/2:
		#print counter
		#print x/2
		counter = counter + 1
		#print counter
		if x%counter == 0:
			return 0
	return 1

print 'Begining of Problem 1.'

while len(primes) <= 1000:
	if isPrime(candidates[-1]):
		primes.append(candidates[-1])
	# 	print primes
	# else:
	# 	print candidates[-1], 'is not prime'
	next_candidate = next_odd_number(candidates[-1])
	candidates.append(next_candidate)
print primes[999]
print 'end of Problem 1.'
print
print

##	Problem 2.  Write a program that computes the sum of the logarithms of all the primes from 2 to some number n, and print out the sum of the logs of the primes, the number n, and the ratio of these two quantities. Test this for different values of n.
## You should be able to make only some small changes to your solution to Problem 1 to solve this problem as well.
## Hints:  While you should see the ratio of the sum of the logs of the primes to the value n slowly get closer to 1, it does not approach this limit monotonically.

## Probably took two hours+ to make this work.

print 'Begining of Problem 2.'

import math
from math import *
		
def find_primes_up_to_n(n):
	"""
	This function takes a number, n, and 
	returns the largest prime less than or equal to n.
	"""
	#	start with the first candiate
	candidates = [1,3]  # 1,3,5,7,11,13,17,19
	
	#	start with the lowest known prime
	primes = [2]
	prime_sum = 0.0
	while primes[-1] <= n:
		if isPrime(candidates[-1]):
			primes.append(candidates[-1])
			prime_sum = prime_sum + math.log(primes[-1])
		next_candidate = next_odd_number(candidates[-1])
		candidates.append(next_candidate)
	
	primes = primes[0:-1]
	
	print 'N', n,'; the largest prime <=', n, 'is', primes[-1], ';Sum of logs:', prime_sum
	return prime_sum

trials = [5,7,956,78,98,1454,3412,6789,23124]

for each in trials:
	answer = find_primes_up_to_n(each)
	print 'and the ratio of these two quantities is ', each / answer
	print 'end of Problem 2.'

# Problem Set 0 
# Name: Scott Brenner
# Collaborators: None
# Date: 2011-01-04
# Start time: 7:05 PM
# End time: 7:18 PM
#

print ('Problem Set 0')
print ('Problem 1')

var_lname =  raw_input('What is your last name?')
#get user input and assign it to var_lname


var_fname =  raw_input('What is your first name?')
#get user input and assign it to var_fname

print var_lname
print var_fname