zpritchard

# Problem Set 5, Part 2

#########
# GHOST #
#########

# -----------------------------------
# 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().upper())
    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 isvalid(wordSoFar, wordlist):
    """
    Takes in the word created so far as well as a list of valid words.

    Returns, in a tuple:
    [0] Whether the game has ended (a word has been or cannot be formed)
    [1] An updated word list containing the remaining possible words
    """
    numltr = len(wordSoFar)
    # Make a list of all possible words that can be formed.
    # The word list is updated to include only these words.
    newwordlist = [word for word in wordlist if wordSoFar in word[0:numltr]]

    # Checks to see if any possible words were found
    if len(newwordlist) == 0:
        gameover = True
        print '\nThere is no word that begins with the letters',\
              wordSoFar + '!'
        
    # Checks to see if a word has already been formed
    elif wordSoFar in wordlist and numltr > 3:
        gameover = True
        print '\nYou have formed the word', wordSoFar + '!'
    else: gameover = False
    
    return (gameover, newwordlist)

def swapPlayer(p):
    """Switches the player from 1 to 2 or vice versa"""
    if p == 1:
        p = 2
    else: p = 1
    return p

def playGhost(p):
    """
    This represents a round of the game.

    The input is the starting player; the winner is the output.
    """
    word = ''
    wordlist = masterwordlist
    gameover = False
    while not gameover:
        # This runs until the player enters an acceptable character
        while True:
            print '\nThe word so far is:', word
            ltr = raw_input("It's your turn, Player " + str(p) +\
                            '. ' + 'Add a letter! ').upper()

            # Stops the loop when a letter is entered
            if (ltr in string.ascii_letters) and (len(ltr) == 1):
                word += ltr
                break
            # Helpful message if an unacceptable character is entered
            print '\nInvalid input. Try again!'
            
        gameover,wordlist = isvalid(word, wordlist)
        p = swapPlayer(p)
    print 'Player',p,'wins!'
    return p

def ghost():
    """
    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.

    A player loses if he or she:
    (1) Forms a complete word greater than 3 letters long
    (2) Creates a fragment which cannot become a word by adding more letters
        ("QZ", for example)
    """
    scores = [0,0]
    first = 1 # Player 1 goes first in the first game. It then alternates.
    while True:
        action = raw_input('\nWelcome to Ghost! Enter "1" to play a round,'+\
                           '"2" to reset the scores, or "3" to exit. ')
        if action is '1':
            winrar = playGhost(first)
            scores[winrar-1] += 1
            print '\nThe overall score is:'
            print 'Player 1:',scores[0]
            print 'Player 2:',scores[1],'\n'
            first = swapPlayer(first)
        elif action is '2':
            scores = [0,0]
            print 'The scores have been reset.'
        elif action is '3':
            break
        else: print '\nInvalid input. How about trying one of the given'+\
              'options?'

if __name__ == '__main__':
    masterwordlist = load_words()
    ghost()

# Problem Set 5: 6.00 Word Game

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
    """
    score = 0

    # Gets letter values from SCRABBLE_LETTER_VALUES dictionary,
    # defined above
    for letter in word:
        score += SCRABBLE_LETTER_VALUES[letter]

    # 50 additional points awarded for using all letters in hand
    if len(word) == n:
        score += 50
    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.upper(),      # print all on the same line
    print                              # print an empty line


def deal_hand(n):
    """
    Returns a random hand containing n lowercase letters.
    At least n/3 the letters in the hand should be VOWELS.

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

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

#
# 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)
    """
    H = hand.copy() # Hand is copied to prevent mutation

    # Removes each letter in the word from the hand
    for letter in word:
        H[letter] -= 1
    return H

#
# 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
    """
    # The period is treated as valid in order to allow the user to quit
    if word == '.': return True
    
    testhand = hand.copy() # Copy the hand to prevent mutation

    # Makes sure each letter in the word is in the player's hand
    for ltr in word:
        testhand[ltr] = testhand.get(ltr,0) - 1
        if testhand[ltr] < 0:
            print "You don't have the letter",ltr.upper(),"in your hand!"
            return False

    # Makes sure the word is a word
    if word not in word_list:
        print word.upper(),"isn't a word! Try again."
        return False

    # The word is valid if it passed both checks
    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

    # Runs until there are no letters left in the hand
    while sum(hand.values()) != 0:
        valid = False
        while not valid:
            print '\nCurrent hand:'
            display_hand(hand)
            word = raw_input('\nMake a word! Enter "." to end this hand. ').lower()
            valid = is_valid_word(word, hand, word_list)

        if word == '.': break  # Ends the hand if the player quits
        wordscore = get_word_score(word, HAND_SIZE)
        score += wordscore
        print word.upper(),'is worth',wordscore,\
              'points, for a total score of', score, 'on this hand.'
        hand = update_hand(hand, word)

    print '\nYou scored',score,'points!'
        

#
# Problem #5: Playing a game
# 
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 the game: ').lower()
        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 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.
    """
    curBal = 0
    out = []
    for a in xrange(0,years):
        addint = curBal * (1 + growthRate * 0.01)
        addprinc = salary * save * 0.01
        curBal = addint + addprinc
        out.append(curBal)
    return out

  ###############
 ## 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.
    """
    out = []
    curBal = 0
    for rate in growthRates:
        addint = curBal * (1 + rate * 0.01)
        addprinc = salary * save * 0.01
        curBal = addint + addprinc
        out.append(curBal)
    return out    

  #############
 ## 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.
    """
    out = []
    curBal = savings
    for rate in growthRates:
        curBal = curBal * (1 + 0.01 * rate) - expenses
        out.append(curBal)
    return out

#################
 ## 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.
    """
    preRetire = nestEggVariable(salary, save, preRetireGrowthRates)
    bal = preRetire[-1]

    hi = bal
    lo = 0
    count = 0
    finalBal = bal
    while abs(finalBal) > epsilon and count <=100:
        expenses = (hi + lo) / 2
        postRetire = postRetirement(bal, postRetireGrowthRates, expenses)
        finalBal = postRetire[-1]
        print 'Iteration',str(count) + ',','Expense estimate:',expenses
        if finalBal > epsilon:
            lo = expenses
        elif finalBal < -epsilon:
            hi = expenses
        count += 1
    return expenses

from string import *

def countSubStringMatch(target, key):
    """counts the instances of key in target iteratively (exact matches only)"""
    count = 0
    while find(target,key) != -1:
        count += 1
        target = target[find(target,key)+1:]
    return count

def countSubStringMatchRecursive(target,key):
    """counts the instances of key in target recursively (exact matches only)"""
    idx = find(target,key)
    if idx == -1: return 0
    else: return 1 + countSubStringMatchRecursive(target[idx+1:],key)

def subStringMatchExact(target, key):
    """searches for instances of key in target (exact matches only)"""
    out = ()
    idx = -1
    # The target is searched from one past the previously found index
    # (initialized at -1 so as to start searching at 0) to find
    # each instance of the key in the target.
    while find(target,key,idx+1) != -1:
        idx = find(target,key,idx+1)
        out += (idx,)
    return out

def constrainedMatchPair(firstMatch, secondMatch, length):
    """for each element in firstMatch, searches for an element in secondMatch
    that represents an instance of the key with one substution"""
    out = ()
    for i in firstMatch:
        for j in secondMatch:
            if i + length + 1 == j:
                out += (i,)
    return out

#####Provided with assignment##############################################
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:]
        # 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
    return allAnswers
###########################################################################

def subStringMatchExactlyOneSub(target,key):
    """searches for instances of key in target with exactly one substitution"""
    exact = str(subStringMatchExact(target,key))
    both = subStringMatchOneSub(key, target) # has exact matches & single subs
    out = ()
    # The element is added to the output if it (1) is not in the
    # list of exact matches and (2) has not already been added
    # to the output.
    for i in both:
        if countSubStringMatch(exact,str(i)) == 0 and\
           countSubStringMatch(str(out),str(i)) == 0:
            out += (i,)
    return out

def mcSolver(n, packs):
    x = packs[0]
    y = packs[1]
    z = packs[2]
    for i in xrange(0,n/x+1):
        for j in xrange(0,n/y+1):
            for k in xrange(0,n/z+1):
                if i*x + j*y + k*z == n:
                    return (i, j, k)
    else: return 'No solution.'


#Problem 1
for a in xrange(50,66):
    print a,':',mcSolver(a,(6,9,20))

#Problem 2------------------------------------------------#
#The theorem is true because if six consecutive values are#
#possible to buy, the next (7th) is simply 6 more than the#
#first one, and we already know that you can buy a pack of#
#6 nuggets. Similarly, every larger number can be obtained#
#---------------------------------------------------------#

#Problem 3
mcsolved = 0
n = 0
while mcsolved < 6:
    n += 1
    N = mcSolver(n,(6,9,20))
    if N == 'No solution.':
        mcsolved = 0
    else: mcsolved += 1

print 'Largest number of McNuggets that cannot be bought in exact quantity:',n-6

#Problem 4
bestSoFar = 0
packs = (6,9,20)
for n in xrange(1,201):
    if mcSolver(n, packs) == 'No solution.':
        bestSoFar = n

print 'Given package sizes',str(packs[0])+', '+str(packs[1])+', and '+\
      str(packs[2])+',','the largest number of nuggets that cannot be bought'+\
      'in exact quantity is:',bestSoFar

############
#Problem 1:#
############
from math import *
n = 1
primes = 1 #the 1 prime already "found" is 2
while (primes != 1000):
    n += 2 #increments by 2 (only odd nums considered)
    for div in range(3, int(sqrt(n)+1)):
        rem = n%div
        if rem == 0: break
    else: primes +=  1
else: print n



############
#Problem 2:#
############

def genPrimes(lim):
    yield 2
    for n in xrange(3,lim,2):
        for div in xrange(3, int(sqrt(n)+1)):
            rem = n % div
            if rem == 0: break
        else: yield n

def sumlog(N):
    total = sum(log(n) for n in N)
    return total

n = int(raw_input('Give me a number: '))
tot = sumlog(genPrimes(n))
ratio = float(tot)/n
print 'Your number is',n
print 'The sum of the logs of the primes from 2 to',n,'is',tot
print 'The ratio is',ratio

lastName = raw_input('Enter your last name: ')
firstName = raw_input('Enter your first name: ')
name = firstName + '\n' + lastName
print name