hendrix

Problem set 7
Mark Calderwood

1) What is the computational complexity of fact0? 
def fact0(i):

it is O(i) (linear with respect to size of i) because the function is called
once each time it recurses through from i to 0.

2) What is the computational complexity of fact1?

Also O(i) (linear) because the function contains code in a loop
that is executed a number of times = to i

3) What is the computation complexity of makeSet?

O(s) where s is the number of character in s, it is looping through s 1
character at a time and performing some operations in each loop

4) What is the computation complexity of intersect?

Exponential because we have a double loop (not sure how to write this
in asymptotic notation so for every char in s1 we do something for
ever char in s2 therefor we have s1 x s2 number of operations

5) Present a hand simulation of the code below.

1 - We bind the list [1] to s1
2 - We bind the list [2] to s2
3 - We call the function swap0 with s1 and s2 as arguments
4 - swap0 checks that the arguments are lists
5 - Inside swap0 we create a local variable tmp which we assign to a copy of s1
6 - We make a local variable called s1 and assign it a copy of s2
7 - We make a local s2 and assign it to tmp
8 - We print the global s1 & s2 which have not been changed

6) Present a hand simulation of the code below.

1 - We bind the list [1] to s1
2 - We bind the list [2] to s2
3 - We call the function swap1 with s1 and s2 as arguments
4 - swap1 checks the arguments are lists
5 - swap1 returns the two arguments in the opposite order
6 - These are bound to s1 and s2 effectively switching them
7 - We print s1 and s2 and see that they have been changed

7) Present a hand simulation of the code below.

1 - We bind the list[1,2,3] to s
2 - We call revs with s as the argument
3 - revs checks that s is a list
4 - We work out the middle point of s
5 - We initialise a loop to go from the begining of s to the middle
6 - Going through the loop we bind a local variable tmp to the actual
object s's first character (s[0])
7 - We make the first character of the actual object s a copy of the last character ( s[0] = s[-(0+1)] aka s[0] = s[-1] )
8 - We make the last character tmp
9 - The loop return to the begining but i is now = 1
10 - We store the 2nd charcter of s (s[1]) in tmp
11 - We replace the 2nd character with the 2nd last character (s[1] = s[-(1+1)], in this case this is also the second character
12 - We replace the second last character with tmp
13 - the loop is finished because 3/1 = 1 so we print s which is now [3,2,1}

# Problem Set 6: 6.00 Word Game 2
# Name: Mark Calderwood
# Collaborators: 
# Time:

import random
import string
import time

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

#---6.0 problem 3 functions

def get_words_to_points(word_list):
    """
    Return a dict that maps every word in word_list to its point value.
    """
    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.
    """
    makeable_words = {}
    for word in points_dict:
        if is_valid_word(word, hand, points_dict):
            makeable_words[word] = points_dict[word]
    current_best = [0,0]
    if makeable_words:
        for word in makeable_words:
            if makeable_words[word] > current_best[1]:
                current_best[0] = word
                current_best[1] = makeable_words[word]        
    return current_best[0]

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 a 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 get_word_rearrangements(word_list):
    """
    Return a dict that maps every word in the wordlist to itself sorted 
    alphabetically e.g. zap to apz for quick access
    """
    rearrange_dict = {}
    for word in word_list:
        temp = [] # to convert the word into a list for sorting
        temp = list(word)
        temp.sort()
        sorted = "" # create a string to put the sorted list back into
        for i in temp:
            sorted = sorted + i # & add each letter from the 1 at a time
        rearrange_dict[sorted] = word #if more than 1 word has the same letters
        # just overwrite the old one and keep only the last (it will score the same)
    return rearrange_dict

def pick_best_word_faster(hand, rearrange_dict):
    """
    Return the highest scoring word from points_dict that can be made with the
    given hand (but faster!).
    Return '.' if no words can be made with the given hand.
    """
    
    def substrings(string):
        """
        Given a string provides all the substrings.
        
        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 substrings(string[:-1]):
                result.append(substring)
                substring = substring + string[-1]
                result.append(substring)
            result.append(string[-1])
        return result

    
    #prelim, convert the hand into a string
    hand_string = ""
    for letter in hand.keys():
        for j in range(hand[letter]):
            hand_string = hand_string + letter
    
    #1st sort the hand
    sorted_hand = ""
    hand_list = list(hand_string)
    hand_list.sort()
    for i in hand_list:
        sorted_hand = sorted_hand + i
    #2nd determine which words we can make stored as a dictionary with points
    makeable_words = {}
    for sub in substrings(sorted_hand):
        if sub in rearrange_dict:
            makeable_words[rearrange_dict[sub]]=points_dict[rearrange_dict[sub]]
        
    #3rd choose best word
    current_best = [0,0]
    if makeable_words:
        for word in makeable_words:
            if makeable_words[word] > current_best[1]:
                current_best[0] = word
                current_best[1] = makeable_words[word]        
    return current_best[0]
    

#---End of 6.0 problem functions

#
# 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
    score = 0
    for letter in word:
        score = score + SCRABBLE_LETTER_VALUES[letter]
    if len(word) == n:
        score = 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

#
# 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)
    """
    newHand = hand.copy()
    for i in word:
        newHand[i] -= 1
    return newHand

#
# Problem #3: Test word validity
#
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)
    """
    helperHand = hand.copy()
    if points_dict.has_key(word):
        for i in word:
            if helperHand.get(i, 0) > 0:
                helperHand[i] -= 1
            else: return False
        return True
    else: return False

#
# Problem #4: Playing a hand
#
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.
    
    * The time it takes for the word to be entered is recorded

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

    def get_time():
        """
        Asks the player for the amount of time they wish on the clock for this 
        hand
        
        Returns: float
        """
        while True:
            time = raw_input("What should the time limit for this hand be?")
            try:
                time_limit = float(time)
                return time_limit
            except:
                print"time is not in valid format, please input a number"
    
    def get_input():
        """
        Asks the player for a word and returns the word and the time taken
        
        Returns: a two element tuple containing the word as the 1st element and
        the time taken as the second
        """
        start_time = time.time()
        word = raw_input("Enter word, or . to indicate that you are finished: ")
        end_time = time.time()
        total_time = end_time - start_time
        if total_time < 0.001:
            total_time = 0.001
        return (word, total_time)
    
    computers_hand = hand.copy()
    time_limit = get_time()
    totalScore = 0.0
    word = ''
    while word != '.':
        print "Current Hand: ",
        display_hand(hand)
        input = get_input()
        word = input[0]
        input_time = input[1]
        time_limit -= input_time
        if time_limit >= 0:
            if is_valid_word(word, hand, points_dict):
                hand = update_hand(hand, word)
                score = points_dict[word]#/input_time
                totalScore += score
                print word, "in %0.2f seconds earned %0.2f points. Total: %0.2f points." % (
                input_time, score, totalScore)
                print "time remaining is: %0.2f" % time_limit
            elif word == '.':
                slow_time_start = time.time()
                best_word = pick_best_word(computers_hand, points_dict)
                slow_time_stop = time.time()
                slow_time_total = slow_time_stop - slow_time_start
                fast_time_start = time.time()
                fastest_word = pick_best_word_faster(computers_hand, rearrange_dict)
                fast_time_stop = time.time()
                fast_time_total = fast_time_stop - fast_time_start
                print "The computers word would have been %s scoring : %i in %0.5f seconds" \
                % (best_word, points_dict[best_word], slow_time_total)
                print "The fast computers word would have been %s scoring : %i in %0.5f seconds" \
                % (fastest_word, points_dict[best_word], fast_time_total)
                break
            else: 
                print "Invalid word, please try again"
                print "time remaining is: %0.2f" % time_limit
        else:
            print "Sorry you ran out of time"
            slow_time_start = time.time()
            best_word = pick_best_word(computers_hand, points_dict)
            slow_time_stop = time.time()
            slow_time_total = slow_time_stop - slow_time_start
            fast_time_start = time.time()
            fastest_word = pick_best_word_faster(computers_hand, rearrange_dict)
            fast_time_stop = time.time()
            fast_time_total = fast_time_stop - fast_time_start
            print "The computers word would have been %s scoring : %i in %0.5f seconds" \
            % (best_word, points_dict[best_word], slow_time_total)
            print "The fast computers word would have been %s scoring : %i in %0.5f seconds" \
            % (fastest_word, points_dict[best_word], fast_time_total)
            break

#
# Problem #5: 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.
    """
    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(), points_dict)
        elif cmd == 'r':
            play_hand(hand.copy(), points_dict)
        elif cmd == 'e':
            print "Thanks for playing, maybe you can try again another time?"
            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)
    rearrange_dict = get_word_rearrangements(word_list)
    #time_limit = get_time_limit(points_dict, 5)
    play_game(points_dict)

#
# Problem 5 #
# I think my original pick_best_word function is running in linear time 
# linked to the size of the word_list.  It's not quite that simple because
# as the hand size grows the number of potential words added to the 
# makeable_words list grows which then have to be itterated over to determine
# the best but I think this is neglible as once the hand size gets very large
# (large enough that there are enough letters so every word can be made) 
# then the number of opperations won't increase any more by adding to the hand 
# size.
#
# I think the pick_best_word_faster function runs in at least exponetial time 
# but linked to the size of the hand.  This is because the function that splits
# the hand into all the substrings takes a looong time to run as hand size gets
# larger and there are clearly more than linear opperations in it.  Also the
# number of substrings produced which then have to be looped through increases
# in a more than linear fashion with respect to hand size, perhaps the overall
# order of growth is something like exponential, it certainly takes a long time
# to run very quickly.  This would reflect the results I got from timing my 
# program, as hand size increases this function becomes very very slow! (I 
# started running it with hand size 25 over 20 minutes ago and it hasn't
# finished yet where it took 17.80048 seconds with hand size 24)

import random

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

def get_letter(message):
    """
    Asks the player for a letter, checks that it is a valid
    letter and returns that letter if it is.
    
    message: string
    return: string
    """
    letter = raw_input(message)
    while True:
        if letter in string.ascii_letters and len(letter) == 1:
            return letter
        else:
            letter = raw_input("not a valid letter, please try again: ")

def update_stub(stub, letter):
    """
    Adds a valid letter to a given stub and returns the new stub.
    
    letter: string
    stub: string
    """
    new_stub = stub + letter
    print "Current word fragment is: %s" % string.upper(new_stub)
    return new_stub

def validate_stub(stub, wordlist):
    """
    Checks if a given stub is a valid part word, also checking if 
    it is a full word already returning a code for each result:
    0 = not a valid word fragment
    1 = a valid fragment
    2 = already a complete word longer than 3 characters
    
    stub: string
    wordlist: list
    """
    def slice_words(stub, wordlist):
        """
        Slices each item in the wordlist to the same number of characters
        as the stub then returns the unique items in this new list.
        
        stub: string
        wordlist: list
        """
        length = len(stub)
        sliced_list = []
        for word in wordlist:
            sliced_list.append(word[:length])
        return set(sliced_list) # cast the list to a set to remove all dups
    if stub in slice_words(stub, wordlist):
        if stub in wordlist and len(stub) > 3:
            return 2
        else:
            return 1
    else:
        return 0
    

# TODO: write outer loop that will ask to play again or exit
def main_loop():
    play_again = 1
    while play_again == 1:
        inner_loop()
        again = string.upper(raw_input("Play again (Y or N)"))
        while True:
            if again == "Y":
                play_again = 1
                break
            elif again == "N":
                play_again = 0
                break
            else:
                again = string.upper(raw_input("Please enter Y or N"))

def inner_loop():
    letter = ""
    stub = ""
    player = 1
    game_state = 1
    print "Welcome to Ghost!"
    print "Player 1 goes first"
    while game_state == 1:
        letter = get_letter("Player %i's letter: " % player)
        stub = update_stub(stub, letter)
        if player == 1:
            player += 1
        elif player == 2:
            player -= 1
        game_state = validate_stub(stub, wordlist)
    
    game_states = {0: "is not a valid word fragment",
                   1: "is a valid stub",
                   2: "is a full word"}
    if player == 1:
        player += 1
    elif player == 2:
        player -= 1
    print "player %i looses because '%s' %s" % (player, string.upper(stub), 
                                                game_states[game_state])

main_loop()

# Problem Set 5: 6.00 Word Game
# Name: 
# Collaborators: 
# Time: 
#

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
    """
    if word == "":
        return 0
    score = 0
    for letter in word:
        score = score + SCRABBLE_LETTER_VALUES[letter]
    if len(word) == n:
        score = 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

#
# 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)
    """
    newHand = hand.copy()
    for i in word:
        newHand[i] -= 1
    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
    """
    helperHand = hand.copy()
    if word in word_list:
        for i in word:
            if helperHand.get(i, 0) > 0:
                helperHand[i] -= 1
            else: return False
        return True
    else: return False

#
# 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
    """
    totalScore = 0
    word = ''
    while word != '.':
        print "Current Hand: ",
        display_hand(hand)
        word = raw_input("Enter word, or . to indicate that you are finished: ")
        if is_valid_word(word, hand, word_list):
            hand = update_hand(hand, word)
            score = get_word_score(word, HAND_SIZE)
            totalScore += score
            print word, "earned %i points. Total: %i points." % (score, totalScore)
        elif word == '.':
            break
        else: print "Invalid word, please try again"

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

def percentage(value):
    percentage = float(value)/100
    return percentage

def nestEggOneYear(salary, save):
    yearsSavings = salary * percentage(save)
    return yearsSavings

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.
    """
    currentYear = 0
    fundValues = []
    while currentYear <= years:
        if currentYear == years:
            return fundValues
        elif currentYear == 0:
            fundValues.append(nestEggOneYear(salary, save))
            currentYear += 1
        else:
            fundValues.append((fundValues[currentYear - 1] * (1 + percentage(growthRate)))\
            + nestEggOneYear(salary, save))
            currentYear += 1
    return fundValues
            
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.

#testNestEggFixed()

#
# 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.
    """
    currentYear = 0
    numberOfYears = len(growthRates)
    fundValues = []
    while currentYear <= numberOfYears:
        if currentYear == numberOfYears:
            return fundValues
        elif currentYear == 0:
            fundValues.append(nestEggOneYear(salary, save))
            currentYear += 1
        else:
            fundValues.append((fundValues[currentYear - 1] * 
            (1 + percentage(growthRates[currentYear]))) + 
            nestEggOneYear(salary, save))
            currentYear += 1
    return fundValues


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.

#testNestEggVariable()

#
# 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.
    """
    
    def postRetirementOneYear(savings, growthRate, expenses):
        """
        helper function to calculate one years fund size
        """
        fundSize = (savings * (1 + percentage(growthRate))) - expenses
        return fundSize
    
    currentYear = 0
    numberOfYears = len(growthRates)
    fundValues = []
    while currentYear <= numberOfYears:
        if currentYear == numberOfYears:
            return fundValues
        elif currentYear == 0:
            fundValues.append(postRetirementOneYear(savings, growthRates[0], expenses))
            currentYear += 1
        else:
            fundValues.append(postRetirementOneYear(fundValues[currentYear - 1]
            , growthRates[currentYear], expenses))
            currentYear += 1
    return fundValues

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.


#testPostRetirement()

#
# 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.
    """
    fundValuesBeforeRetirement = nestEggVariable(salary, save, 
    preRetireGrowthRates)
    fundAtRetirement = fundValuesBeforeRetirement[-1]
    upperBound = fundAtRetirement
    lowerBound = 0
    def guessGenerator(upperBound, lowerBound):
        guess = (upperBound + lowerBound)/2.0
        return guess
    guess = guessGenerator(upperBound, lowerBound)
    print "current guess is %s" % guess
    def moneyAtDeath(fundAtRetirement, postRetireGrowthRates, guess):
        fundValuesAfterRetirement = postRetirement(fundAtRetirement, 
        postRetireGrowthRates, guess)
        fundValueAtDeath = fundValuesAfterRetirement[-1]
        #print "moneyAtDeath with this guess is %s" % fundValueAtDeath
        return fundValueAtDeath
    fundValueAtDeath = moneyAtDeath(fundAtRetirement, postRetireGrowthRates, guess)
    print fundValueAtDeath
    if abs(fundValueAtDeath) <= epsilon:
        return guess
    while abs(fundValueAtDeath) > epsilon:
        if fundValueAtDeath < 0:
            upperBound = guess
            guess = guessGenerator(upperBound, lowerBound)
            print "current guess is %s" % guess
            fundValueAtDeath = moneyAtDeath(fundAtRetirement, postRetireGrowthRates,
            guess)
        elif fundValueAtDeath > 0:
            lowerBound = guess
            guess = guessGenerator(upperBound, lowerBound)
            print "current guess is %s" % guess
            fundValueAtDeath = moneyAtDeath(fundAtRetirement, postRetireGrowthRates,
            guess)
    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.

#testFindMaxExpenses()

from string import *

# this is a code file that you can use as a template for submitting your
# solutions


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

#  target strings

target1 = 'atgacatgcacaagtatgcat'
target2 = 'atgaatgcatggatgtaaatgcag'

# key strings

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

#problem 1

def countSubStringMatch(target,key):
    """Given a target string and a given substring
        returns the number of occurances of the substring"""
    countOfMatches = 0
    currentPosition = 0
    while currentPosition  <= len(target):
        if find(target, key, currentPosition) == -1:
            if countOfMatches > 0:
                return countOfMatches
            else:                
                return 0
        else:
            countOfMatches += 1
            currentPosition = find(target, key, currentPosition) + 1
    return countOfMatches

def countSubStringMatchRecursive(target, key):
    """Given a target string and a given substring
        returns the number of occurances of the substring
        (recursive)"""
    currentPosition = find(target, key)
    if find(target, key) == -1:
        return 0
    else:
        return 1 + countSubStringMatchRecursive(target[currentPosition+1:], key)

#problem 2

def subStringMatchExact(target,key):
    """Given a target string and a given substring
        returns the number of occurances of the substring"""
    locationOfMatches = []
    countOfMatches = 0
    currentPosition = 0
    while currentPosition  <= len(target):
        if find(target, key, currentPosition) == -1:
            if countOfMatches > 0:
                result = tuple(locationOfMatches)
                return result
            else:                
                return ()
        else:
            countOfMatches += 1
            currentPosition = find(target, key, currentPosition)
            locationOfMatches.append(currentPosition)
            currentPosition += 1
    result = tuple(locationOfMatches)
    return result

#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
        
def constrainedMatchPair(first, second, length):
    locationOfMatches = []
    for position in first:
        for location in second:
            if position + length + 1 == location:
                locationOfMatches.append(position)
                #print "location of matches = "
                #print locationOfMatches
            #else:
                #print "position = %i, length = %i, location = %i" % (position, length, location)
    result = tuple(locationOfMatches)
    return result


#problem 4

def subStringMatchExactlyOneSub(key,target):
    result = list(subStringMatchOneSub(key, target))
    matchesWithOneSubOrLess = subStringMatchOneSub(key, target)
    matchesExact = subStringMatchExact(target, key)
    for match in matchesWithOneSubOrLess:
        if match in matchesExact:
            result.remove(match)
    readiedResult = tuple(result)
    return readiedResult

###
### template of code for Problem 4 of Problem Set 2, Fall 2008
###

bestSoFar = 1     # variable that keeps track of largest number
                  # of McNuggets that cannot be bought in exact quantity
buyable = False
packages = (6,9,20)   # variable that contains package sizes

for n in range(1, 55):   # only search for solutions up to size 200
    ## complete code here to find largest size that cannot be bought
    ## when done, your answer should be bound to bestSoFar
    print n
    for a in range (0, 55):
        for b in range (0, 55):
            for c in range (0, 55):
                if n == (packages[0] * a) + (packages[1] * b) + (packages[2] * c):
                    print n
                    buyable = True
                    break
                else:
                    buyable = False
            if buyable == True : break
        if buyable == True : break

    if buyable == False:
        bestSoFar = n

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

-------------------------------------------------------------------------

###
### template of code for Problem 4 of Problem Set 2, Fall 2008
###

bestSoFar = 1     # variable that keeps track of largest number
                  # of McNuggets that cannot be bought in exact quantity
buyable = False
packages = (7,9,20)   # variable that contains package sizes

for n in range(1, 200):   # only search for solutions up to size 200
    ## complete code here to find largest size that cannot be bought
    ## when done, your answer should be bound to bestSoFar
    print n
    for a in range (0, 200):
        for b in range (0, 200):
            for c in range (0, 200):
                if n == (packages[0] * a) + (packages[1] * b) + (packages[2] * c):
                    print n
                    buyable = True
                    break
                else:
                    buyable = False
            if buyable == True : break
        if buyable == True : break

    if buyable == False:
        bestSoFar = n

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

# Problem Set 1 a
# Name: Mark Calderwood

primecount = 2
candidate = 5
divsor = 2
isprime = 1

while primecount < 1000:
    divisor = (candidate - 1)/2 
# start with the candidate -1 (to make it even) and then divide this
#by two, (a numbers biggest factor is always the one that goes
#into it twice)

    while divisor > 2: 
# we know it isn't even so we need to check if it is divisible by
# everything bigger than 2
        if candidate % divisor == 0:
            isprime = 0
            break
        else:
            isprime = 1
            divisor -= 1

    if isprime == 1:
        #print candidate ("scaffolding" code)
        primecount += 1
        candidate += 2
    else:
        candidate += 2

print candidate - 2 # remove the last increment before printing


# Problem Set 1 b
# Name: Mark Calderwood

from math import *

primecount = 2
candidate = 5
divsor = 2
isprime = 1
sumoflogs = log(2) + log(3)

while primecount < 1000:
    divisor = (candidate - 1)/2 
# start with the candidate -1 (to make it even) and then divide this
# by two, (a numbers biggest factor is always the one that goes
#into it twice)

    while divisor > 2: 
# we know it isn't even so we need to check if it is divisible by
# everything bigger than 2
        if candidate % divisor == 0:
            isprime = 0
            break
        else:
            isprime = 1
            divisor -= 1

    if isprime == 1:
        print candidate
        sumoflogs = sumoflogs + log(candidate)
        print sumoflogs
        print candidate/sumoflogs
        primecount += 1
        candidate += 2
    else:
        candidate += 2