chrcoe

#Problem Set 7
#Name: chrcoe
#Collaborators: none
#Time: 10 min
#

#1)
def fact0(i):
    '''recursive function with complexity O(n).
    It is linear because the fucntion is called one time until i = 1 or i = 0'''
    assert type(i) == int and i >= 0
    if i == 0 or i == 1:
        return 1
    return i * fact0(i-1)

#2)
def fact1(i):
    '''Complexity is linear because the function's while loop
    is called however many times i is. O(n)'''
    assert type(i) == int and i >= 0
    res = 1
    while i > 1:
        res = res * i
        i -= 1
    return res

#3)
def makeSet(s):
    '''Complexity is linear because the function's while loop
    is called however many times s is. O(n)
    Only doing one thing each time through the loop as well.'''
    assert type(s) == str
    res = ''
    for c in s:
        if not c in res:
            res = res + c
    return res

#4)
def intersect(s1, s2):
    '''the loop is only doing one thing and it depends on s1 and uses s2.
    should be O(n) - linear'''
    assert type(s1) == str and type(s2) == str
    s1 = makeSet(s1)
    s2 = makeSet(s2)
    res = ''
    for e in s1:
        if e in s2:
            res = res + e
    return res

#5)
def swap0(s1, s2):
    '''hand simulation of swap0.
    takes two #'s and swaps their values'''
    assert type(s1) == list and type(s2) == list
    tmp = s1[:]
    #tmp -> [1]
    s1 = s2[:]
    #s1 -> [2]
    s2 = tmp
    #s2 = [1]
    return #s1 = 2 and s2 = 1 ... effectively swapping the #'s

s1 = [1]
s2 = [2]
swap0(s1, s2)
print s1, s2
#>>> [2] [1]

#6)
def swap1(s1, s2):
    '''hand simulation of swap0.
    takes two #'s and swaps their values'''
    assert type(s1) == list and type(s2) == list
    return s2, s1 #returns s1 as value of s2 and s2 as value of s1

s1 = [1]
s2 = [2]
s1, s2 = swap1(s1, s2)
print s1, s2
#>>> [2] [1]

#7)
def rev(s):
    '''reverses the order of items in list s'''
    assert type(s) == list
    for i in range(len(s)/2):
        tmp = s[i]  #tmp(s[0])->1 
                    #tmp(s[1])->2
                    #tmp(s[2])->3
        s[i] = s[-(i+1)]    #s[0]->s[-1]->3
                            #s[1]->s[-2]->2
                            #s[2]->s[-3]->3
        s[-(i+1)] = tmp #s[-1]->3
                        #s[-2]->2
                        #s[-3]->1
s = [1,2,3]
rev(s)
print s
#>>> [3,2,1]

# Problem Set 6: Modifed 6.00 Word Game (from ps5.py)
# Name: chrcoe
# Collaborators: hendrix from curiousreef for substrings algorithm
# Time: 2:25 min
#

import time
import random
import string

VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
HAND_SIZE = 7
#HAND_SIZE = 25 #test seems to be one too big for this computer
#HAND_SIZE = 24 #test seems to be the max usuable, any higher, I get a MemoryError
#HAND_SIZE = 23

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

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

    wordScore = 0
    for letter in word:
        wordScore += SCRABBLE_LETTER_VALUES[letter]

    #print wordScore
    if len(word) == n:
        wordScore += 50  #adds 50 to score for using all n letters on first try
    return wordScore

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

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

    newHand = hand.copy()

    for letter in word:
        newHand[letter] += -1
    return newHand
    

###
### Test word validity
### UPDATED for problem #3 of Problem Set 6.
# now takes the argument points_dict instead of word_list
def is_valid_word(word, hand, points_dict): 
    """
    Returns True if word is in the points_dict and is entirely
    composed of letters in the hand. Otherwise, returns False.
    Does not mutate hand or points_dict.
    
    word: string
    hand: dictionary (string -> int)
    points_dict: dictionary (string -> int)
    returns: boolean value
    """
    newHand = hand.copy()

    if points_dict.has_key(word):     #test if the word is in points_dict
        for letter in word:     #tests every letter in word to see if it is in hand
            if newHand.get(letter, 0) > 0:  #if it's positive (meaning it is there)
                newHand[letter] -= 1        #remove 1 of the letters for next check
            else:return False
        return True
    else: return False

# get_time_limit function from problem set.
# called by main function calls at bottom of program
# stored in global variable time_limit
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.

    points_dict: dictionary (string -> int)
    k: int
    returns: float
    """
    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

#
# Problem #3: Computer player -> time taken: 95 min
#
def get_words_to_points(word_list):
    """
    Return a dict that maps every word in word_list to its point value.

    word_list: list of lowercase strings
    returns: dictionary (string -> int)
    """
    #walk through word_list and return get_word_score(word_from_wordlist, HAND_SIZE)
    scores = {}
    for word in word_list:
        scores[word] = get_word_score(word, HAND_SIZE)
    return scores

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.
    
    hand: dictionary (string -> int)
    points_dict: dictionary (string -> int)
    returns: list index 0
    """
    #walk through points_dict to add all words that are 'makeable' with current hand
    #add these to a makeable_dict dictionary with word:score and sort this by highest score
    #return the highest scoring word possible form this sorted list.
    possibleWords = {}
    for word in points_dict:
        if is_valid_word(word, hand, points_dict):
            possibleWords[word] = points_dict[word]
    bestScore = [0,0]
    if possibleWords: 
        for word in possibleWords: #compares current word to the word in bestScore[1]
            if possibleWords[word] > bestScore[1]: #if current word is better than bestScore[0]
                bestScore[0] = word 
                bestScore[1] = possibleWords[word]
    if bestScore[0] == 0:
        return '.' #player gives up
    return bestScore[0] #else returns the word

#
# Problem #4: Even Faster Computer player -> time taken: 25 min (so far)
#
def get_word_rearrangements(word_list):
    """
    Return a dict that maps every word in word_list to that word sorted alphabetically.

    word_list: list of lowercase strings
    returns: sorted dictionary (string -> int) 
    """
    #walk through word_list and return sorted version
    rearrange_dict = {}
    for word in word_list:
        tempList = [] #convert word into list from a string
        tempList = list(word)
        tempList.sort()
        sortedList = "" #null string-we need this to put the now sorted list back into rearrange_dict
        for letter in tempList:
            sortedList += letter #adds each letter from tempList in order into sortedList
        rearrange_dict[sortedList] = word #from pseudocode given
    return rearrange_dict

def pick_best_word_faster(hand, rearrange_dict):
    """
    Return the highest scoring word from rearrange_dict that can be made with the given hand.
    Return '.' if no words can be made with the given hand.

    hand: dictionary (string -> int)
    rearrange_dict: dictionary (string -> int)
    returns: list index 0
    """

    def substrings(string):
        """
        Given a string provides all the substrings.
        needed help on this from hendrix of curiousreef
        """
        result = []
        if len(string) == 1:
            result.append(string)
        else:
            for substring in substrings(string[:-1]):
                result.append(substring)
                substring = substring + string[-1]
                result.append(substring)
            result.append(string[-1])
        return result

    stringHand = ""
    for letter in hand.keys():
        for i in range(hand[letter]):
            stringHand +=letter

    sortedHand = ""
    listHand = list(stringHand) #list version of hand
    listHand.sort()
    for letter in listHand:
        sortedHand += letter

    possibleWords = {}
    for word in substrings(sortedHand):
        if word in rearrange_dict:
            possibleWords[rearrange_dict[word]]=points_dict[rearrange_dict[word]]
    bestScore = [0,0]
    if possibleWords: 
        for word in possibleWords: #compares current word to the word in bestScore[1]
            if possibleWords[word] > bestScore[1]: #if current word is better than bestScore[0]
                bestScore[0] = word 
                bestScore[1] = possibleWords[word]
    if bestScore[0] == 0:
        return '.' #player gives up
    return bestScore[0] #else returns the word

#
# Problem #1: How long? time taken: 20 min
# Problem #2: time Limit time taken: 5 min 
#
def play_hand(hand, points_dict): 
    """
    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
    """
    #max_time = float(raw_input('Enter time limit (in seconds): '))
    max_time = time_limit
    print '\nTime limit set as:',time_limit,'seconds.'
    time_left = max_time
    print '\nCurrent hand:',
    #display_hand(hand)
    newHand = hand.copy()
    display_hand(newHand)
    #print sum(newHand.values()),'before loop\n'
    currentScore = 0.0
    #wordScore = get_word_score(userWord,HAND_SIZE)

    while sum(newHand.values()) != 0:
        start_time = time.time() #added ability to time how long user takes
        #userWord = str(raw_input('Enter a word from the given hand (or . to quit):'))
        #userWord = pick_best_word(newHand,points_dict)
        userWord = pick_best_word_faster(newHand,rearrange_dict)
        #this will call pick_best_word which will be the computer playing.
        end_time = time.time()
        total_time = end_time - start_time
        time_left -= total_time
        print 'It took',round(total_time,4),'seconds to enter \'',userWord,'\'.','You have',round(time_left,4),'seconds remaining.'
        #print sum(newHand.values()),'beg of loop\n'
        if userWord == '.': #when you press . you quit prematurely
            break
        if time_left <= 0: #tests time left
            print 'Total time exceeds,',max_time,'seconds.'
            break
        elif not is_valid_word(userWord, newHand, points_dict): #test for word validity
            print 'Invalid word'
            print '\nCurrent hand:',
            display_hand(newHand)
        else:
            roundedTotal = 1 + total_time #fixing divide by zero errors by making points
                        #awarded as such: Normal word score/1 + time taken to answer
            wordScore=round(get_word_score(userWord,HAND_SIZE)/roundedTotal,4)
            currentScore += wordScore
            print '\''+userWord+'\'','earns you',wordScore,'points.','Total:',currentScore,'points.'
            newHand = update_hand(newHand, userWord)
            print '\nCurrent hand:',
            display_hand(newHand)
            
        #print sum(newHand.values()),'end of loop\n'
            
    print '\nFinal score:',currentScore,'Thanks for playing!'
#   
# Playing a game
# Make sure you understand how this code works!
# 
def play_game(points_dict):
    """
    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.
    """
    
    #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
    #testDict = {'h':1,'e':2,'l':4,'o':2,'j':1}    #for testing only
    #testDict1 = {'h':1,'e':1,'l':2,'o':1}
    #play_hand(testDict1, word_list)          #for testing only
    
    ## 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 q to quit: ')
        if cmd == 'n':
            hand = deal_hand(HAND_SIZE)
            play_hand(hand.copy(), points_dict)
            print
        elif cmd == 'r':
            play_hand(hand.copy(), points_dict)
            print
        elif cmd == 'q':
            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) #builds points_dict list of values for each word
    rearrange_dict = get_word_rearrangements(word_list) #builds rearrange_dict list of values for each word
    time_limit = get_time_limit(points_dict,1) #sets global time_limit based on computer
    play_game(points_dict)
    
##=========================================================================
##
## Problem 5 ##
## Characterize the time complexity of your implementation (in terms of the
##  size of word_list and the number of letters in a hand) of both
##  pick_best_word and pick_best_word_faster.
##
##=========================================================================

# Problem Set 5: Ghost
# Name: Chris Coe
# Collaborators: none
# Time: 60 min
#

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



def changePlayers(p):
    """Makes player 1 become player 2 and vice versa"""
    if p == 1:
        p = 2
    else: p = 1
    return p

def is_valid(wordFragment, wordlist): #time taken: 60min
    """
    Returns True if wordFragment is in the word_list.  Will not fail
    if the word is a fragment of a valid word.  Does not mutate
    word or wordlist.
    
    wordFragment: string (the word fragment so far)
    wordlist: list of lowercase strings
    """
    length = len(wordFragment)
##    newWordlist = [word for word in wordlist  #creates a new list to check based
##                   if wordFragment in word[0:length]] #letters input so far
    newWordlist = []
    
    for word in wordlist:
        if wordFragment in word[0:length]:
            newWordlist.append(word)
            
    if len(newWordlist) == 0:
        gameover = True
        print '\nThere is no word that begins with the letters',wordFragment

    elif wordFragment in wordlist and length > 3:
        gameover = True
        print 'You formed the word',wordFragment
        print
    else: gameover = False
    return (gameover, newWordlist)


def play_game(p):
    """
    Plays one round of ghost game with two players.

    p = int (player #)
    """
    word = ''
    gameover = False
    primeWordlist = wordlist
    while not gameover:
        while True:
            letter = raw_input('Player '+str(p)+' Enter your letter: ').lower()
            if (letter in string.ascii_letters) and (len(letter)==1):
                word += letter
                print 'Current word fragment: \''+word+'\'\n'
                break
            else: print '\nInvalid input, please try again.'
        gameover,primeWordlist = is_valid(word, primeWordlist) #checks if the fragment is part of a valid word
        p = changePlayers(p) #switch whose turn it is
    return p
            

def playGhost():
    """
    Play the exciting two-player word game Ghost!

    Players alternate entering letters to form a word, or more accurately,
    to NOT form a word while forming the beginnings of a word.

    Each fragment must be the beginning of an actual word.
    Player looses is word wormed is longer than 3 letters.
    """
    print 'Welcome to Ghost!'
    firstPlayer = raw_input('Enter first player\'s name:')
    secondPlayer = raw_input('Enter second player\'s name:')

    while True:
        menuChoice = int(raw_input('Please choose from the options below:\n'+
                               '\t1: Start a new game\n\t2: Exit\n\t'))
        if menuChoice == 1:
            player = play_game(1) #first player starts
            if player == 1:
                print firstPlayer,'wins!\n'
            else: print secondPlayer,'wins!\n'
        elif menuChoice == 2: print 'Thank you for playing Ghost!'break
        else: print 'Invalid input. Try again'
        
# 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.

if __name__ == '__main__':
    wordlist = load_words()
    playGhost()

# Problem Set 5: 6.00 Word Game
# Name: Chris Coe
# Collaborators: curiousreef/openstudy for help on validity algorithm
# Time: 150 min
#

import random
import string

VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
HAND_SIZE = 7
#HAND_SIZE = 10 #for testing only
#HAND_SIZE = 5 #for testing only


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): #time taken: 5 min
    """
    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
    """

    wordScore = 0
    for letter in word:
        wordScore += SCRABBLE_LETTER_VALUES[letter]

    #print wordScore
    if len(word) == n:
        wordScore += 50  #adds 50 to score for using all n letters on first try
    return wordScore

#
# 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): #time taken: 25 min
    """
    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)
    """

    newHand = hand.copy()

    for letter in word:
        newHand[letter] += -1
        #newHand[letter] = 0 #will stop loop 1 letter to soon
        #del newHand[letter] #this gives same result as above option...
    return newHand
    

###
### Problem #3: Test word validity
###
def is_valid_word(word, hand, word_list): #time taken: 60min
    """
    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
    """
    newHand = hand.copy()

    if word in word_list:       #test if the word is in word_list
        for letter in word:     #tests every letter in word to see if it is in hand
            if newHand.get(letter, 0) > 0:  #if it's positive (meaning it is there)
                newHand[letter] -= 1        #remove 1 of the letters for next check
            else:return False
        return True
    else: return False

#
# Problem #4: Playing a hand
#
def play_hand(hand, word_list): #time taken: 60 min
    """
    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
    """
    print '\nCurrent hand:',
    #display_hand(hand)
    newHand = hand.copy()
    display_hand(newHand)
    #print sum(newHand.values()),'before loop\n'
    currentScore = 0
    #wordScore = get_word_score(userWord,HAND_SIZE)

    while sum(newHand.values()) != 0:
        userWord = str(raw_input('Enter a word from the given hand (or . to quit):'))
        #print sum(newHand.values()),'beg of loop\n'
        if userWord == '.': #when you press . you quit prematurely
            break
        elif not is_valid_word(userWord, newHand, word_list): #test for word validity
            print 'Invalid word'
            print '\nCurrent hand:',
            display_hand(newHand)
        else:
            wordScore = get_word_score(userWord,HAND_SIZE)
            currentScore += wordScore
            print '\''+userWord+'\'','earns you',wordScore,'points.','Total:',currentScore,'points.'
            newHand = update_hand(newHand, userWord)
            print '\nCurrent hand:',
            display_hand(newHand)
            
        #print sum(newHand.values()),'end of loop\n'
            
    print '\nFinal score:',currentScore,'Thanks for playing!'
#   
# Problem #5: Playing a game
# Make sure you understand how this code works!
# 
def play_game(word_list):#time taken: 5 seconds
    """
    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.
    """
    
    #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
    #testDict = {'h':1,'e':2,'l':4,'o':2,'j':1}    #for testing only
    #testDict1 = {'h':1,'e':1,'l':2,'o':1}
    #play_hand(testDict1, word_list)          #for testing only
    
    ## 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: Chris Coe
# Time: 2:10 min total

#
# Problem 1 - 30 min
#

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.
    """
    sizeOfAccount = []
    #End of year 1
    sizeOfAccount.append(salary * save * 0.01)
    #End of year 2
    #sizeOfAccount.append(sizeOfAccount[0] * (1 + 0.01 * growthRate) + salary * save * 0.01)
    #End of year 3
    #sizeOfAccount.append(sizeOfAccount[1] * (1 + 0.01 * growthRate) + salary * save * 0.01)
    for yr in range(1,years):
        sizeOfAccount.append(sizeOfAccount[yr-1] * (1 + 0.01 * growthRate) + salary * save * 0.01)
    return sizeOfAccount

#print nestEggFixed(10000,10,15,5)

def testNestEggFixed():
    salary     = [10000,15000,20654]
    save       = [5,10,15]
    growthRate = [2,4,10]
    years      = [5,10,15]
    for count in range(0,3):
        print 'salary($):',salary[count],'save(% of salary):',save[count],'growthRate(%):',growthRate[count],'years:',years[count]
        savingsRecord = nestEggFixed(salary[count], save[count], growthRate[count], years[count])        
        print savingsRecord
        print
    # Output (for 10000,10,15,5) should have values close to:
    # [1000.0, 2150.0, 3472.5, 4993.375, 6742.3812499999995]

    # Added for loop to have multiple cases tested

#testNestEggFixed()

#
# Problem 2 - 20
#

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.
    """
    sizeOfAccount = []

    saveFromSalary = salary * save * 0.01
    sizeOfAccount.append(saveFromSalary)

    for yr in range(1,len(growthRates)):
        sizeOfAccount.append(sizeOfAccount[yr-1] * (1 + 0.01 * growthRates[yr-1]) + saveFromSalary)
    return sizeOfAccount

def testNestEggVariable():
    salary     = [10000,15000,20654]
    save       = [5,10,15]
    #growthRates = [3, 8, 2, 0, -3, 1, 3]
    growthRates = [-3,-3,-4]
    for c in range(0,len(salary)):
        print 'salary($):',salary[c],'save(% of salary):',save[c],'growthRates(% each year):',growthRates
        savingsRecord = nestEggVariable(salary[c], save[c], growthRates)
        print savingsRecord
        print
    # Output should have values close to:
    # [1000.0, 2040.0, 3142.0, 4142.0, 5266.2600000000002]

    # changed to a for loop and tested with additional years and negative growth years

#testNestEggVariable()

#
# Problem 3 - 10 min
#

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.
    """
    sizeOfAccount = []

    sizeOfAccount.append(savings * (1 + 0.01*growthRates[0]) - expenses)

    for yr in range(1,len(growthRates)):
        sizeOfAccount.append(sizeOfAccount[yr-1] * (1 + 0.01 * growthRates[yr]) - expenses)
    return sizeOfAccount

def testPostRetirement():
    savings     = [100000,500000,1000000]
    growthRates = [10, 5, 0, 5, -1, -2, 1, 3, 2]
    expenses    = [30000,28000,25000]

    for c in range(0,len(savings)):
        print 'savings($):',savings[c],'growthRates(% each year):',growthRates,'expenses($/year):', expenses[c]
        savingsRecord = postRetirement(savings[c], growthRates, expenses[c])
        print savingsRecord
        print
    # Output should have values close to:
    # [80000.000000000015, 54000.000000000015, 24000.000000000015,
    # -4799.9999999999854, -34847.999999999985]

    #for loop to test multiple situations, added more years, pos and neg

#testPostRetirement()

#
# Problem 4 - 70 min
#

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.
    """
    assert epsilon > 0, 'epsilon must be positive, not' + str(epsilon)

    savings = nestEggVariable(salary, save, postRetireGrowthRates)[-1] #savings at end of retirement
    low = 0
    high = savings + epsilon
    currentEstimate = (low + high)/2.0 #current estimate of allowable expenses
    endRetirement = postRetirement(savings, postRetireGrowthRates, currentEstimate)[-1] #
    #print 'Starting Savings:',savings,'\n'
    #print 'End of retirement guess:',endRetirement,'\n'
    
    while abs(endRetirement) > epsilon:
        if endRetirement < 0:     
            high = currentEstimate
        else:
            low = currentEstimate
        currentEstimate = (high + low)/2.0
        endRetirement = postRetirement(savings, postRetireGrowthRates, currentEstimate)[-1]
        print currentEstimate #current estimate for the amount of expenses on each iteration
        #print endRetirement
    return currentEstimate

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

##    My Output (supposed to print estimate during each iteration):
##        1353.815
##        676.9075
##        1015.36125
##        1184.588125
##        1269.2015625
##        1226.89484375
##        1248.04820312
##        1258.62488281
##        1263.91322266
##        1266.55739258
##        1265.23530762
##        1264.57426514
##        1264.90478638
##        1264.73952576
##        1264.82215607
##        1264.78084091
##        1264.76018333
##        1264.74985455
##        1264.74985455 #final answer

testFindMaxExpenses()

###==================================================
## Problem Set 2 (Part I)
## Time: 1:10
###==================================================

currentTesNum = 1

lastNum = 0

solutions = 0

a = 6
b = 9
c = 20


while solutions<6: #when we find 6 consecutive solutions...
    solved=False
    #Ax+By+Cz = n Diophantine Equation
    for countForA in range(0,a+1): ##nested for loop helps count 'all feasible solutions'
        for countForB in range(0,b+1):
            for countForC in range(0,c+1): 
                if currentTestNum == a*countForA + b*countForB + c*countForC:
                    solved = True
                    #print currentTestNum
    if solved == True:
        solutions += 1
    else:
        lastNum = currentTestNum
        solutions = 0

    currentTestNum += 1

print "Largest number of McNuggets that cannot be bought in exact quantity:",lastNum

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

###==================================================
## Problem Set 2 (Part II)
## Time: 25 
###==================================================


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

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
    #Ax+By+Cz = n Diophantine Equation
    solved=False
    for countForA in range(0,packages[0]+1):
        for countForB in range(0,packages[1]+1):
            for countForC in range(0,packages[2]+1):
                if n == packages[0]*countForA + packages[1]*countForB + packages[2]*countForC:
                    solved = True
                    #print n
    if solved != True:
        bestSoFar = n
        
    
print "Given package sizes",packages[0],",",packages[1],", and",packages[2],'\n'
print "Largest number of McNuggets that cannot be bought in exact quantity:",bestSoFar

# Problem Set 1a
# Name: Chris Coe
# Collaborators: OpenStudy help
# Time: 1:50
#
# Program to compute and prints the 1000th prime number

prime = 3 #first prime that isn't 2 or 0...
count = 1
divisor = 2 #first even

while count<1000:
    while divisor<prime:  #this loop determines if it can be
                                #divided by a number other than itself
        if prime%divisor == 0:
            divisor=prime+1
        else: divisor += 1

    if divisor == prime:   #when prime and divisor are =, it means
                                #that prime is only divisible by itself and 1
                                #so we increase count to increase our main
                                #once.
        count += 1
        #print prime
    prime += 1              #we then need to add 1 to prime or it will be
                                #stuck at the same value forever
    divisor=2                   #need to reset divisor for each number we are
                                #testing.


print 'the 1000th prime is: ',prime-1   #prime will be the 1001st prime #
                                        #because prime+=1 is calc. again during
                                        #the last counter loop iteration

#==============================================

# Problem Set 1b
# Name: Chris Coe
# Collaborators: OpenStudy help
# Time: 30 min
#
# Program to compute sum of logs of all primes from 2 to some number n
# Print out the sum of the logs of the primes, the number n, and the ratio
# of these two quantities

from math import *

prime = 3 #first prime that isn't 2 or 0...
count = 1
divisor = 2 #first even
logSums = log(2) # need to include log(2) since the prime = 3 to start

numberN = int(raw_input('Please enter a max number for n: '))

while count<numberN:
    while divisor<prime:        
        if prime%divisor == 0:
            divisor=prime+1
        else: divisor += 1

    if divisor == prime:       
        count += 1
        if prime<numberN:
            logSums += log(prime) #take log(prime) and add it to what is in logSums
    prime += 1                  
    divisor=2                  

print 'n: ',numberN
print 'Sum of the logs of the prime #\'s: ', logSums
print 'Ratio of Sum of logs to value n: ', logSums/numberN

lastName = raw_input('Please enter your last name: ')
firstName = raw_input('Please enter your first name: ')
#print 'Your name is: ' + firstName + ' ' + lastName
print "Your name is: %s %s" %(firstName, lastName)