nickrt

#Problem set 6
#Name: Nick
#Collaborators: None
#Time: 5:00
#

import random
import string
import time

VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
HAND_SIZE = 7
POINTS_DICT = None#Problem 3
REARRANGE_DICT = None#Problem 4

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 = "/Users/Nick/Desktop/Introduction to CS and Programming/Assignments/6/Supporting Files/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)
# -----------------------------------


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

#
# 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


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, 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
    """
    freq = get_frequency_dict(word)
    for letter in word:
        if freq[letter] > hand.get(letter, 0):
            return False
    return word in POINTS_DICT.keys()

#
#Problem 3##############################################################
#

def get_words_to_points(word_list):
    points_dict = {}
    for word in range(len(word_list)):
        points_dict[word_list[word]] = get_word_score(word_list[word],HAND_SIZE)
    return points_dict

def pick_best_word(hand):
    """
    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.
    """
    highest = 0
    best = None
    for word in POINTS_DICT.keys():
        wordDict = get_frequency_dict(word)
        works = True
        for letter in wordDict.keys():
            if hand.get(letter,0) < wordDict[letter]: works = False
        if works == True and POINTS_DICT[word] > highest:
            highest = POINTS_DICT[word]
            best = word
    if highest == 0: return '.'
    else:
        return best

#######################################################################

#
#Problem 4#############################################################
#

def get_word_rearrangements(word_list):
    rearrange_dict = {}
    for word in word_list:
        sorted_string = ''
        for letter in sorted(word):
            sorted_string += letter
        rearrange_dict[sorted_string] = word
    return rearrange_dict

def pick_best_word_faster(handDict):
    word = ''
    highest = 0
    hand = ''
    for i in handDict.keys():
        hand += i*handDict[i]
    subSets = []
    for r in range(len(hand)):
        subSets += combinations(hand, r)
    for combList in range(len(subSets)):
        comb = ''
        subSets[combList] = sorted(subSets[combList])
        for letter in subSets[combList]:
            comb += letter
        if comb in REARRANGE_DICT.keys():
            points = POINTS_DICT[REARRANGE_DICT[comb]]
            if points > highest:
                word = REARRANGE_DICT[comb]
    if word != '':
        return word
    else: return '.'
def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = list(iterable)
    n = len(pool)
    if r > n:
        return
    indices = range(r)
    yield list(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield list(pool[i] for i in indices)

    
    
########################################################################


#
#Problem 2##############################################################
#
def get_time_limit(points_dict, k):
    """
Returns the time limit for the computer 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()
    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 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 = 0.0
    initial_handlen = sum(hand.values())
    while True:#Problem 2
        time_limit = raw_input('Enter time limit, in seconds, for players: ')#Problem 2
        try:#Problem 2
            time_limit = float(time_limit)#Problem 2
            break
        except:#Problem 2
            print('Not a number')#Problem 2
    total_time = 0#Problem 2

    time_limit = get_time_limit(POINTS_DICT, time_limit)#Problem 3
    
    while sum(hand.values()) > 0:
        print 'Current Hand:',
        display_hand(hand)
        start_time = time.time()#Problem 1
        ##userWord = raw_input('Enter word, or a . to indicate that you are finished: ')
        userWord = pick_best_word_faster(hand)
        end_time = time.time()#Problem 1
        word_time = end_time - start_time#Problem 1
        word_time_exact = word_time
        total_time += word_time#Problem 2
        if total_time >= time_limit: break #Problem 2
                          
        if word_time < 1: word_time = 1#Problem 1
        if userWord == '.':
             break
        else:
            isValid = is_valid_word(userWord, hand, word_list)
            if not isValid:
                print 'Invalid word, please try again.'
            else:
                print 'It took %.2f seconds to provide an answer.' % (word_time_exact) #Problem 1
                points = get_word_score(userWord, initial_handlen) / word_time#Problem 1(the divide by part)
                total += points
                print '%s earned %.2f points. Total: %.2f points' % (userWord, points, total)
                hand = update_hand(hand, userWord)
    if total_time < time_limit:#Problem 2
        print 'Total score: %.2f points.' % total
    else:#Problem 2
        print 'Total time excceds %.2f seconds.  You scored %.2f points.' % (time_limit, total)#Problem 2



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 = 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()

    POINTS_DICT = get_words_to_points(word_list) #Problem 3
    REARRANGE_DICT = get_word_rearrangements(word_list)#Problem 4
    play_game(word_list)




#
##Problem 5#######################################################
#Complexity of pick_best_word in terms of word_list and HAND_SIZE
#
#O(len(word_list))
#
#
#Complexity of pick_best_word_faster in terms of word_list and HAND_SIZE
#
#O(x ** HAND_SIZE)
#
#Pick best word is faster for short hands, but the longer the hand gets the
#longer the function takes.
###################################################################

# Problem Set 5: Ghost
# Name: Nick
# Collaborators: None
# Time: 0:50
#

import random

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

WORDLIST_FILENAME = "/Users/Nick/Desktop/Introduction to CS and Programming/Assignments/5/Supporting Files/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.
word_list = load_words()


def search(word, word_list, first, last):
    if (last-first) < 2: return word_list[first] == word or word_list[last] == word
    mid = first + (last-first)/2
    if word_list[mid] == word: return True
    if word_list[mid] > word: return search(word, word_list, first, mid - 1)
    return search(word, word_list, mid + 1, last)


def ghost():
    print 'Welcome to Ghost!'
    print 'Player 1 goes first.'
    turn = '1'
    word = ''
    while not search(string.lower(word), word_list, 0, len(word_list)-1) or len(word) <= 3:
        if word != '':
            if turn == '1': turn = '2'
            else: turn = '1'
            print "Player "+turn+"'s turn."
        letter = string.upper(str(raw_input('Player ' + turn + ' says letter: ')))
        while not letter in string.ascii_letters or letter == '':
            print 'Error: Not a letter'
            letter = string.upper(str(raw_input('Player ' + turn + ' says letter: ')))
        word += letter
        print
        print "Current word fragment: '"+word+"'"
    print "Player " + turn + " loses because '"+ word +"' is a word!"
    if turn == '1': turn = '2'
    else: turn = '1'
    print 'Player ' + turn + ' wins!'

# Problem Set 5: 6.00 Word Game
# Name: Nick
# Collaborators: None
# Time: 2:00
#

import random
import string

VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
HAND_SIZE = 10

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 = "/Users/Nick/Desktop/Introduction to CS and Programming/Assignments/5/Supporting Files/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
    """
    if word == '':
        return 0
    if len(word) == n: score = 50
    else: score = 0
    for letter in word:
        score += SCRABBLE_LETTER_VALUES[letter]
    return score

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#Is this wrong?
        
    for i in range(num_vowels, n):    
        x = CONSONANTS[random.randrange(0,len(CONSONANTS))]
        hand[x] = hand.get(x, 0) + 1#Is this wrong?
        
    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)
    """
    testHand = dict.copy(hand)
    wordDict = get_frequency_dict(word)
    for letter in wordDict.keys():
        testHand[letter] -= wordDict[letter]
    return testHand

#
# Problem #3: Test word validity
#

def search(word, word_list, first, last):
    if (last-first) < 2: return word_list[first] == word or word_list[last] == word
    mid = first + (last-first)/2
    if word_list[mid] == word: return True
    if word_list[mid] > word: return search(word, word_list, first, mid - 1)
    return search(word, word_list, mid + 1, last)

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
    """
    validWord = search(word, word_list, 0, len(word_list)-1)
    if validWord == False:
        return False
    testHand = dict.copy(hand)
    wordDict = get_frequency_dict(word)

    for letter in wordDict.keys():
        if testHand.get(letter,0) == 0: return False
        if testHand[letter] < wordDict[letter]: 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
    """
    score = 0
    done = False
    emptyHand = False
    while done == False and emptyHand == False:
        display_hand(hand)
        word = str(raw_input('Enter a word, or a . to indicate that you are finished: '))
        while is_valid_word(word, hand, word_list) == False and word != '.':
            print 'Invalid word, please try again.'
            display_hand(hand)
            word = str(raw_input('Enter a word, or a . to indicate that you are finished: '))
        if word == '.':
            done = True
        else:
            points = get_word_score(word, HAND_SIZE)
            score += points
            print word + ' earned ' + str(points) + ' points. Total: '+ str(score) + ' points.'
            hand = update_hand(hand, word)
        emptyHand = True
        for letter in hand.keys():
            if hand[letter] != 0:
                emptyHand = False

    print 'Total Score: ' + str(score) + ' points.'
#
# 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.
    """
    ## 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)

#4
def first_N(n):
    oddSquares = ()
    for i in range(n+1):
        if i*i%2 != 0:
            oddSquares += (i*i,)
    print oddSquares

#6
def findSide():
    """asks the user to enter the area and the length of one side of the rectangle.
    Returns a floating point number that is the length of the adjacent side."""
    area = float(raw_input('Input area of rectangle as a floating point: '))
    side1 = float(raw_input('Input a side length of rectangle as a floating point: '))
    side2 = area/side1
    return side2
    
#8
def mcDonalds(num):
    for a in range(num/6+1):
        for b in range(num/9+1):
            for c in range(num/20+1):
                if 6*a+9*b+20*c == num:
                    return True
    return False

# Problem Set 4
# Name: Nick
# Collaborators: None
# Time: 0:40

#
# Problem 1
#

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.
    """
    fund = [salary*save*.01] #Initial funds after first year
    for i in range(1, years):#Changing the funds every year based on the previous term in the list and savings
        fund.append(fund[i-1]*(1+.01*growthRate)+salary*save*.01)
    return fund#returns final amount saved
    
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.

#
# Problem 2
#

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.
    """
    fund = [salary*save*.01]#Initial savings after first year

    #This part calculates the final funds after the set number of years have passed
    #fund is i-1 because you are looking at the previous term, and growth rate is i
    #because you are looking at that term
    for i in range(1,len(growthRates)):
        fund.append(fund[i-1]*(1+.01*growthRates[i])+salary*save*.01)
    return fund

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.

#
# Problem 3
#

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.
    """
    fund = [savings * (1+.01*growthRates[0]) - expenses] #Initial funds after 1 year of retirement

    #Same kind of thing as the last one but instead of
    #+ salary*save*.01 you have - expenses
    for i in range(1,len(growthRates)):
        fund.append(fund[i-1]*(1+.01*growthRates[i]) - expenses)
    return fund

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.

#
# Problem 4
#

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.
    """
    savingsRecord = nestEggVariable(salary, save, preRetireGrowthRates)
    initSavings = savingsRecord[-1]#finds the initial savings when you just finish working
    low = 0#sets low end of range
    high = initSavings + epsilon#sets high end of range
    guess = (low + high)/2.0#sets the guess 1/2 way between low and high
    savingsRecord = postRetirement(initSavings, postRetireGrowthRates, guess)
    savings = savingsRecord[-1]#Calculates how much you have left in account after using guess as yearly expenses
    counter = 1#counter to exit loop if too many iterations

    #This loop improves guess every time by cutting out the values lower than guess
    #if you had excess money, and cut out values higher than guess if you were in the red
    #Then it creates a new guess between the new low and high and calculates a new savings
    #left when you die and uses it to see if it is less than epsilon and if so exit loop, if not repeat
    while abs(savings) > epsilon and counter <= 100:
        if savings > 0:
            low = guess
        else:
            high = guess
        guess = (low+high)/2.0
        savingsRecord = postRetirement(initSavings, postRetireGrowthRates, guess)
        savings = savingsRecord[-1]
        counter += 1
    assert counter <= 100, 'Iteration count exceeded'
    return guess#Final answer

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.

#Problem Set 3 (Part I)
#Name: Nick
#Time: 1:00
#

from string import *

def countSubStringMatch(target,key):
    """Returns the number of times the key appears in the target"""
    assert isinstance(target, str), 'target must be a string'
    assert isinstance(key, str), 'key must be a string'
    count = 0
    index = 0
    for i in range(0, len(target)):
        subset = find(target, key, index)
        if subset == -1:
            return count
        else:
            index = subset+1
            count += 1



def countSubStringMatchRecursive (target, key):
    assert isinstance(target, str), 'target must be a string'
    assert isinstance(key, str), 'key must be a string'
    index = find(target, key)
    if index == -1: return 0
    else:
        count = 1
        return count + countSubStringMatchRecursive(target[index+1:], key)



#Problem Set 3 (Part II)
#Name: Nick
#Time: 0:30
#

def subStringMatchExact(target,key):
    assert isinstance(target, str), 'target must be a string'
    assert isinstance(key, str), 'key must be a string'
    indices = ()
    index = 0
    for i in range(0, len(target)):
        value = find(target, key, index)
        if key == '':
            indices = indices + (i,)
        elif value == -1:
            return indices
        else:
            index = value+1
            indices = indices + (value,)
    return indices


#Problem Set 3 (Part III)
#Name: Nick
#Collaborators: None
#Time 1:00
#


def constrainedMatchPair(firstMatch,secondMatch,length):
    indices = ()
    for indexFirst in firstMatch:
        for indexSecond in secondMatch:
            if indexFirst + length + 1 == indexSecond:
                indices = indices + (indexFirst,)
    return indices


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


#Problem Set 3 (Part IV)
#Name: Nick
#Collaborators: None
#Time 0:30
#

def subStringMatchExactlyOneSub(target,key):
    #Gets all possible with at least one sub and converts to set
    allPossible = set(subStringMatchOneSub(key,target))
    #Gets all possible with no sub and converts to set
    exactSolutions = set(subStringMatchExact(target,key))
    #Subtracts them to get index's unique to the first set, sorts, and converts to tuple
    exactlyOneSub = list(allPossible-exactSolutions)
    exactlyOneSub.sort()
    exactlyOneSubTuple = tuple(exactlyOneSub)
    #returs the answer tuple
    return exactlyOneSubTuple

#Problem Set 2 (Part I)
#Name: Nick
#Collaborators: None
#Time: 0:30

n=1 #no need to test values less than 6 because they are all impossible
#I could start at a higher number but I don't want to be imporoper
works=1#this variable is so I can leave loops when I find 1 combonation that works
consecutive = 0#this variable is so I can see when to stop the whole loop because
#the rest will all work
while consecutive < 6:#runs until 6 consecutive values that work are found
    a=0
    b=0#resets the values of a, b, and c for every loop
    c=0
    #This section tests each possible combination of a, b, and c to test if 6a+9b+20c = n
    #and if it does, it stops as soon as possible to not waste computing power
    while a <= n/6 and works == 1:
        if 6*a+9*b+20*c == n:
            works = 0

        b = 0 #resets b after every time a increases 1
        while b <= n/9 and works == 1:
            if 6*a+9*b+20*c == n:
                works = 0

            c = 0 #resets c after every time b increase 1
            while c <= n/20 and works == 1:
                if 6*a+9*b+20*c == n:
                    works = 0
                c += 1
            b += 1
        a += 1
    #This section sees if there was a combination that worked, and if so added 1
    #to consecutive and sets works back equal to 1 so that the loop will run
    #else it resets consecutive and saves n to be a possible final answer
    if works == 0:
        consecutive +=1
        works = 1
    else:
        consecutive = 0
        largestImpossible = n
    n += 1#This tests the next n on the next iteration
    #now it loops back to the begining of the while loop
print 'Largest number of McNuggets that cannot be bought in exact quantity:',largestImpossible
#prints answer



#Problem Set 2 (Part II)
#Name: Nick
#Collaborators: None
#Time: 1:00

bestSoFar = 0     # variable that keeps track of largest number
                  # of McNuggets that cannot be bought in exact quantity
x = int(raw_input('First Package Size? '))
y = int(raw_input('Second Package Size? '))
z = int(raw_input('Third Package Size? '))

packages = (x, y, z)   # variable that contains package sizes

if x < y and x < z: smallest = x
elif y < z: smallest = y
else: smallest = z

consecutive = 0#this variable is so I can see when to stop the whole loop because
#the rest will all work

n = 1#initial condition
for n in range (1,200):#Runs until all others will be possible or n = 200
    a=0
    b=0#resets the values of a, b, and c for every loop
    c=0
    #This section tests each possible combination of a, b, and c to test if 6a+9b+20c = n
    #and if it does, it stops as soon as possible to not waste computing power
    for a in range(0,n/packages[0]+1):
        for b in range(0,n/packages[1]+1):
            for c in range(0,n/packages[2]+1):
                if packages[0]*a+packages[1]*b+packages[2]*c == n:
                    break
            if packages[0]*a+packages[1]*b+packages[2]*c == n:
                break
        if packages[0]*a+packages[1]*b+packages[2]*c == n:
            consecutive += 1
            break

                
    #This section sees if there was a combination that worked, and if so added 1
    #to consecutive and sets works back equal to 1 so that the loop will run
    #else it resets consecutive and saves n to be a possible final answer
    else:
        consecutive = 0
        bestSoFar = n
    if consecutive == smallest:
        break

    #now it loops back to the begining of the for loop
if consecutive == smallest:print 'Given package sizes, ' + str(x)+', '+ str(y) + ', and '+ str(z) + ', the largest number of McNuggets that cannot be bought in exact quantity:',bestSoFar
else: print 'Given package sizes, ' + str(x)+', '+ str(y) + ', and '+ str(z) + ', the largest number was not neccessarily found, but the largest less than 200 is:', bestSoFar
#prints answer, if we were cut off by the 200 limit we printed a different answer

#Problem Set 1
#Name: Nick
#Collaborators: None
#Time: 1:00

#Problem 1

number = 3 #the variable that we will be checking if it is a prime
primeCounter = 1 #Because 2 is the first prime number and our program doesn't find it

while primeCounter < 1000: #will stop loop when the 1000th prime is found
    stopCheck = number/3 #last number it needs to check because 3 is the smallest possible factor of any odd number other than 1
    prime = 0
    i = 3
    while i <= stopCheck and prime == 0:
        check = number%i
        if check == 0:
            prime = 1
        i = i+2
    if prime == 0:
        primeCounter = primeCounter +1
    if primeCounter != 1000:
        number = number +2
print number




#Problem 2

from math import *

n = raw_input('n? ') #the prime number to use to approximate e**n
approximation = log(2)#starting value because our program doesn't count 2
number = 3 #the variable that we will be checking if it is a prime
while number < n: #will stop loop when the 1000th prime is found
    stopCheck = number/3 #last number it needs to check because 3 is the smallest possible factor of any odd number other than 1
    prime = 0 #says that the number is a prime
    i = 3 #i only needs to be odds
    while i <= stopCheck and prime == 0:
        check = number%i #checks what the remainder is
        if check == 0:
            prime = 1 #if no remainder it isnt a prime so number isnt a prime
        i = i+2 #repeats the while loop with the next odd number
    if prime == 0:#if it is a prime
        approximation = approximation + log(number)#add it to the existing sum of primes
    number = number +2 #checks the next odd number if we aren't done
ratio = approximation / n
print 'Sum of Logs:',approximation
print 'n:',n
print 'Ratio:',ratio

#Problem Set0
#Name: Nick
#Collaborators: None
#Time: 0:05

firstName = raw_input('First Name?')
lastName = raw_input('Last Name?')

print firstName, lastName