rfh

# Problem Set 11: Simulating robots
# Name:
# Collaborators:
# Time:

import math
import random
import ps11_visualize
import pylab

# === Provided classes

class Position(object):
    """
    A Position represents a location in a two-dimensional room.
    """
    def __init__(self, x, y):
        """
        Initializes a position with coordinates (x, y).

        x: a real number indicating the x-coordinate
        y: a real number indicating the y-coordinate
        """
        self.x = x
        self.y = y
    def getX(self):
        return self.x
    def getY(self):
        return self.y
    def getNewPosition(self, angle, speed):
        """
        Computes and returns the new Position after a single clock-tick has
        passed, with this object as the current position, and with the
        specified angle and speed.

        Does NOT test whether the returned position fits inside the room.

        angle: integer representing angle in degrees, 0 <= angle < 360
        speed: positive float representing speed

        Returns: a Position object representing the new position.
        """
        old_x, old_y = self.getX(), self.getY()
        # Compute the change in position
        delta_y = speed * math.cos(math.radians(angle))
        delta_x = speed * math.sin(math.radians(angle))
        # Add that to the existing position
        new_x = old_x + delta_x
        new_y = old_y + delta_y
        return Position(new_x, new_y)


# === Problems 1 and 2

class RectangularRoom(object):
    """
    A RectangularRoom represents a rectangular region containing clean or dirty
    tiles.

    A room has a width and a height and contains (width * height) tiles. At any
    particular time, each of these tiles is either clean or dirty.
    """
    def __init__(self, width, height):
        """
        Initializes a rectangular room with the specified width and height.
        Initially, no tiles in the room have been cleaned.

        width: an integer > 0
        height: an integer > 0
        """
        if width < 0: raise ValueException('Width cannot be less than 0')
        if height < 0: raise ValueException('Height cannot be less than 0')
        self.width = width
        self.height = height
        self.cleanedTiles = []
    def cleanTileAtPosition(self, pos):
        """
        Mark the tile under the position POS as cleaned.
        Assumes that POS represents a valid position inside this room.

        pos: a Position
        """
        coords = int(pos.getX()), int(pos.getY())
        if coords in self.cleanedTiles:
            return
        self.cleanedTiles.append(coords)
    def isTileCleaned(self, m, n):
        """
        Return True if the tile (m, n) has been cleaned.

        Assumes that (m, n) represents a valid tile inside the room.

        m: an integer
        n: an integer
        returns: True if (m, n) is cleaned, False otherwise
        """
        return (int(m), int(n)) in self.cleanedTiles
    def getNumTiles(self):
        """
        Return the total number of tiles in the room.

        returns: an integer
        """
        return self.width * self.height
    def getNumCleanedTiles(self):
        """
        Return the total number of clean tiles in the room.

        returns: an integer
        """
        return len(self.cleanedTiles)
    def getRandomPosition(self):
        """
        Return a random position inside the room.

        returns: a Position object.
        """
        return Position(random.randrange(0, self.width), random.randrange(0, self.height))
    def isPositionInRoom(self, pos):
        """
        Return True if POS is inside the room.

        pos: a Position object.
        returns: True if POS is in the room, False otherwise.
        """
        return 0 <= pos.getX() <= self.width and 0 <= pos.getY() <= self.height

class BaseRobot(object):
    """
    Represents a robot cleaning a particular room.

    At all times the robot has a particular position and direction in
    the room.  The robot also has a fixed speed.

    Subclasses of BaseRobot should provide movement strategies by
    implementing updatePositionAndClean(), which simulates a single
    time-step.
    """
    def __init__(self, room, speed):
        """
        Initializes a Robot with the given speed in the specified
        room. The robot initially has a random direction d and a
        random position p in the room.

        The direction d is an integer satisfying 0 <= d < 360; it
        specifies an angle in degrees.

        p is a Position object giving the robot's position.

        room:  a RectangularRoom object.
        speed: a float (speed > 0)
        """
        self.room = room
        self.speed = speed
        self.direction = random.randrange(0, 360)
        self.position = room.getRandomPosition()
    def getRobotPosition(self):
        """
        Return the position of the robot.

        returns: a Position object giving the robot's position.
        """
        return self.position
    def getRobotDirection(self):
        """
        Return the direction of the robot.

        returns: an integer d giving the direction of the robot as an angle in
        degrees, 0 <= d < 360.
        """
        return self.direction
    def setRobotPosition(self, position):
        """
        Set the position of the robot to POSITION.

        position: a Position object.
        """
        self.position = position
    def setRobotDirection(self, direction):
        """
        Set the direction of the robot to DIRECTION.

        direction: integer representing an angle in degrees
        """
        self.direction = direction


class Robot(BaseRobot):
    """
    A Robot is a BaseRobot with the standard movement strategy.

    At each time-step, a Robot attempts to move in its current
    direction; when it hits a wall, it chooses a new direction
    randomly.
    """
    def updatePositionAndClean(self):
        """
        Simulate the passage of a single time-step.

        Move the robot to a new position and mark the tile it is on as having
        been cleaned.
        """
        newPosition = self.position.getNewPosition(self.direction, self.speed)
        while not self.room.isPositionInRoom(newPosition):
            self.direction = random.randrange(0, 360)
            newPosition = self.position.getNewPosition(self.direction, self.speed)

        self.room.cleanTileAtPosition(newPosition)
        self.position = newPosition


# === Problem 3

def runSimulation(num_robots, speed, width, height, minCoverage, numTrials,
                  robotType, visualize = False):
    """
    Runs NUM_TRIALS trials of the simulation and returns a list of
    lists, one per trial. The list for a trial has an element for each
    timestep of that trial, the value of which is the percentage of
    the room that is clean after that timestep. Each trial stops when
    MIN_COVERAGE of the room is clean.

    The simulation is run with NUM_ROBOTS robots of type ROBOT_TYPE,
    each with speed SPEED, in a room of dimensions WIDTH x HEIGHT.

    Visualization is turned on when boolean VISUALIZE is set to True.

    num_robots: an int (num_robots > 0)
    speed: a float (speed > 0)
    width: an int (width > 0)
    height: an int (height > 0)
    minCoverage: a float (0 <= minCoverage <= 1.0)
    num_trials: an int (num_trials > 0)
    robotType: class of robot to be instantiated (e.g. Robot or
                RandomWalkRobot)
    visualize: a boolean (True to turn on visualization)
    """
    def percentageOfRoomCleaned(room):
        return float(room.getNumCleanedTiles()) / room.getNumTiles()

    results = []
    for trialNum in range(1, numTrials + 1):
        if visualize:
            anim = ps11_visualize.RobotVisualization(num_robots, width, height)

        trialResults = [] 
        room = RectangularRoom(width, height)
        robots = []
        for robotNum in range(0, num_robots):
            robots.append(robotType(room, speed))
        while percentageOfRoomCleaned(room) < minCoverage:
            if visualize:
                anim.update(room, robots)
            trialResults.append(percentageOfRoomCleaned(room))
            for robo in robots:
                robo.updatePositionAndClean()

        if visualize:
            anim.done()
        results.append(trialResults)

    return results

#print(runSimulation(1, 1, 15, 15, 1.0, 100, Robot, True))

# === Provided function
def computeMeans(list_of_lists):
    """
    Returns a list as long as the longest list in LIST_OF_LISTS, where
    the value at index i is the average of the values at index i in
    all of LIST_OF_LISTS' lists.

    Lists shorter than the longest list are padded with their final
    value to be the same length.
    """
    # Find length of longest list
    longest = 0
    for lst in list_of_lists:
        if len(lst) > longest:
           longest = len(lst)
    # Get totals
    tots = [0]*(longest)
    for lst in list_of_lists:
        for i in range(longest):
            if i < len(lst):
                tots[i] += lst[i]
            else:
                tots[i] += lst[-1]
    # Convert tots to an array to make averaging across each index easier
    tots = pylab.array(tots)
    # Compute means
    means = tots/float(len(list_of_lists))
    return means

def computeAverageTime(listOfLists):
    totalTime = 0
    for l in listOfLists:
        totalTime += len(l)

    return float(totalTime) / len(listOfLists)

# === Problem 4
def showPlot1():
    """
    Produces a plot showing dependence of cleaning time on room size.
    """
    numTrials = 50
    averageTimes = []
    roomSideSizes = (5, 10, 15, 20, 25)
    roomAreas = []

    for size in roomSideSizes:
        roomAreas.append(size**2)
        averageTimes.append(computeAverageTime(runSimulation(1, 1.0, size, size, .75, numTrials, Robot)))

    pylab.figure()
    pylab.plot(roomAreas, averageTimes)
    pylab.ylabel('Timesteps')
    pylab.xlabel('Room area')
    pylab.title('Time to clean 75%% of a square room with 1 robot (%d trials)' % numTrials)

def showPlot2():
    """
    Produces a plot showing dependence of cleaning time on number of robots.
    """
    numTrials = 50
    averageTimes = []
    for numRobots in range(1, 11):
        averageTimes.append(computeAverageTime(runSimulation(numRobots, 1.0, 25, 25, .75, numTrials, Robot)))

    pylab.figure()
    pylab.plot(range(1, 11), averageTimes)
    pylab.ylabel('Timesteps')
    pylab.xlabel('Number of robots')
    pylab.title('Time to clean 75%% of a 25x25 room (%d trials)' % numTrials)

def showPlot3():
    """
    Produces a plot showing dependence of cleaning time on room shape.
    """
    numTrials = 50
    averageTimes = []
    widthHeightRatios = []
    for width, height in ((20, 20), (25, 16), (40, 10), (50, 8), (80, 5), (100, 4)):
        widthHeightRatios.append(float(width) / height)
        averageTimes.append(computeAverageTime(runSimulation(2, 1.0, width, height, .75, numTrials, Robot)))

    pylab.figure()
    pylab.plot(widthHeightRatios, averageTimes)
    pylab.ylabel('Timesteps')
    pylab.xlabel('Width to height ratio for room size')
    pylab.title('Time to clean 75%% of a room with the same area, but varying widths/heights using 2 robots (%d trials)' % numTrials)


def showPlot4():
    """
    Produces a plot showing cleaning time vs. percentage cleaned, for
    each of 1-5 robots.
    """
    numTrials = 15
    pylab.figure()
    labels = []

    for numRobots in range(1, 6):
        label = "%d robot(s)" % numRobots
        labels.append(label)
        results = computeMeans(runSimulation(numRobots, 1.0, 25, 25, 1, numTrials, Robot))
        pylab.plot(results * 100, range(0, len(results)), label=label)

    pylab.legend(labels)
    pylab.ylabel('Timesteps')
    pylab.xlabel('Minimum coverage %')
    pylab.title('Time to clean vs Minimum coverage %% with 1-5 robots (%d trials)' % numTrials)

#showPlot1()
#showPlot2()
#showPlot3()
#showPlot4()
#pylab.show()


# === Problem 5

class RandomWalkRobot(Robot):
    """
    A RandomWalkRobot is a robot with the "random walk" movement
    strategy: it chooses a new direction at random after each
    time-step.
    """
    def updatePositionAndClean(self):
        self.direction = random.randrange(0, 360)
        Robot.updatePositionAndClean(self)

#runSimulation(1, 1.0, 25, 25, 1, 1, RandomWalkRobot, True)

# === Problem 6

def showPlot5():
    """
    Produces a plot comparing the two robot strategies.
    """
    numTrials = 10
    pylab.figure()
    labels = []
    robotTypes = (Robot, RandomWalkRobot)

    for numRobots in range(1, 3):
        for robotType in robotTypes:
            label = "%d %s robot(s)" % (numRobots, robotType.__name__)
            labels.append(label)
            results = computeMeans(runSimulation(numRobots, 1.0, 25, 25, 1, numTrials, robotType))
            pylab.plot(results * 100, range(0, len(results)), label=label)

    pylab.legend(labels)
    pylab.ylabel('Timesteps')
    pylab.xlabel('Minimum coverage %')
    pylab.title('Time to clean vs Minimum coverage %% with 1-5 robots of type Robot and RandomWalkRobot (%d trials)' % numTrials)

showPlot5()
pylab.show()

# Backend code for PS10

import random
import string

# Global Constants
VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
HAND_SIZE = 30
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
}
HUMAN_SOLO = 0
HUMAN_VS_HUMAN = 1
HUMAN_VS_COMP = 2

WORDLIST_FILENAME = "words.txt"

def getFrequencyDict(sequence):
    """
    Given a sequence of letters, convert the sequence to a dictionary of
    letters -> frequencies. Used by containsLetters().

    returns: dictionary of letters -> frequencies
    """
    freq = {}
    for x in sequence:
        freq[x] = freq.get(x,0) + 1
    return freq

def getWordScore(word):
    """
    Computes the score of a word (no bingo bonus is added).

    word: The word to score (a string).

    returns: score of the word.
    """
    score = 0
    for ch in word:
        score += SCRABBLE_LETTER_VALUES[ch]
    if len(word) == HAND_SIZE:
        score += 50
    return score

#
# Problem 2: Representing a Hand
#
class Hand(object):
    def __init__(self, handSize, initialHandDict = None):
        """
        Initialize a hand.

        handSize: The size of the hand

        postcondition: initializes a hand with random set of initial letters.
        """
        num_vowels = handSize / 3
        if initialHandDict is None:
            initialHandDict = {}
            for i in range(num_vowels):
                x = VOWELS[random.randrange(0,len(VOWELS))]
                initialHandDict[x] = initialHandDict.get(x, 0) + 1
            for i in range(num_vowels, handSize):
                x = CONSONANTS[random.randrange(0,len(CONSONANTS))]
                initialHandDict[x] = initialHandDict.get(x, 0) + 1
        self.initialSize = handSize

        for letter, frequency in initialHandDict.items():
            if frequency < 1:
                del initialHandDict[letter]

        self.handDict = initialHandDict
    def update(self, word):
        """
        Remove letters in word from this hand.

        word: The word (a string) to remove from the hand
        postcondition: Letters in word are removed from this hand
        """
        for letter, frequency in getFrequencyDict(word).items():
            self.handDict[letter] = self.handDict[letter] - frequency
            if 0 == self.handDict[letter]:
                del self.handDict[letter]
        
    def containsLetters(self, letters):
        """
        Test if this hand contains the characters required to make the input
        string (letters)

        returns: True if the hand contains the characters to make up letters,
        False otherwise
        """
        for letter, frequency in getFrequencyDict(letters).items():
            if self.handDict.get(letter, 0) < frequency:
                return False

        return True

    def isEmpty(self):
        """
        Test if there are any more letters left in this hand.

        returns: True if there are no letters remaining, False otherwise.
        """
        return not len(self.handDict)

    def __eq__(self, other):
        """
        Equality test, for testing purposes

        returns: True if this Hand contains the same number of each letter as
        the other Hand, False otherwise
        """
        return self.handDict == other.handDict
    def __str__(self):
        """
        Represent this hand as a string

        returns: a string representation of this hand
        """
        string = ''
        for letter in self.handDict.keys():
            for j in range(self.handDict[letter]):
                string = string + letter + ' '
        return string

#
# Problem 3: Representing a Player
#

class Player(object):
    """
    General class describing a player.
    Stores the player's ID number, hand, and score.
    """
    def __init__(self, idNum, hand):
        """
        Initialize a player instance.

        idNum: integer: 1 for player 1, 2 for player 2.  Used in informational
        displays in the GUI.

        hand: An object of type Hand.

        postcondition: This player object is initialized
        """
        self.points = 0.
        self.idNum = idNum
        self.hand = hand
    def getHand(self):
        """
        Return this player's hand.

        returns: the Hand object associated with this player.
        """
        return self.hand
    def addPoints(self, points):
        """
        Add points to this player's total score.

        points: the number of points to add to this player's score

        postcondition: this player's total score is increased by points
        """
        self.points += points
    def getPoints(self):
        """
        Return this player's total score.

        returns: A float specifying this player's score
        """
        return self.points
    def getIdNum(self):
        """
        Return this player's ID number (either 1 for player 1 or
        2 for player 2).

        returns: An integer specifying this player's ID number.
        """
        return self.idNum
    def __cmp__(self, other):
        """
        Compare players by their scores.

        returns: 1 if this player's score is greater than other player's score,
        -1 if this player's score is less than other player's score, and 0 if
        they're equal.
        """
        return cmp(self.getPoints(), other.getPoints())
    def __str__(self):
        """
        Represent this player as a string

        returns: a string representation of this player
        """
        return 'Player %d\n\nScore: %.2f\n' % \
               (self.getIdNum(), self.getPoints())

#
# Problem 4: Representing a Computer Player
#

class ComputerPlayer(Player):
    """
    A computer player class.
    Does everything a Player does, but can also pick a word using the
    PickBestWord method.
    """
    def pickBestWord(self, wordlist):
        """
        Pick the best word available to the computer player.

        returns: The best word (a string), given the computer player's hand and
        the wordlist
        """
        bestScore = 0
        bestWord = ''
        for word in wordlist.getList():
            if self.hand.containsLetters(word):
                wordScore = getWordScore(word)
                if wordScore > bestScore:
                    bestScore = wordScore
                    bestWord = word

        return bestWord
    def playHand(self, callback, wordlist):
        """
        Play a hand completely by passing chosen words to the callback
        function.
        """
        while callback(self.pickBestWord(wordlist)): pass

class HumanPlayer(Player):
    """
    A Human player class.
    No methods are needed because everything is taken care of by the GUI.
    """

class Wordlist(object):
    """
    A word list.
    """
    def __init__(self):
        """
        Initializes a Wordlist object.

        postcondition: words are read in from a file (WORDLIST_FILENAME, a
        global constant) and stored as a list.
        """
        inputFile = open(WORDLIST_FILENAME)
        try:
            self.wordlist = []
            for line in inputFile:
                self.wordlist.append(line.strip().lower())
        finally:
            inputFile.close()
    def containsWord(self, word):
        """
        Test whether this wordlist includes word

        word: The word to check (a string)

        returns: True if word is in this Wordlist, False if word is not in
        Wordlist
        """
        return word in self.wordlist
    def getList(self):
        return self.wordlist

class EndHand(Exception): pass

class Game(object):
    """
    Stores the state needed to play a round of the word game.
    """
    def __init__(self, mode, wordlist):
        """
        Initializes a game.

        mode: Can be one of three constant values - HUMAN_SOLO, HUMAN_VS_COMP,
        and HUMAN_VS_HUMAN

        postcondition: Initializes the players nd their hands.
        """
        hand = Hand(HAND_SIZE)
        hand2 = Hand(HAND_SIZE, hand.handDict.copy())
        if mode == HUMAN_SOLO:
            self.players = [HumanPlayer(1, hand)]
        elif mode == HUMAN_VS_COMP:
            self.players = [HumanPlayer(1, hand),
                            ComputerPlayer(2, hand2)]
        elif mode == HUMAN_VS_HUMAN:
            self.players = [HumanPlayer(1, hand),
                            HumanPlayer(2, hand2)]
        self.playerIndex = 0
        self.wordlist = wordlist
    def getCurrentPlayer(self):
        """
        Gets the Player object corresponding to the active player.

        returns: The active Player object.
        """
        return self.players[self.playerIndex]
    def nextPlayer(self):
        """
        Changes the game state so that the next player is the active player.

        postcondition: playerIndex is incremented
        """
        if self.playerIndex + 1 < len(self.players):
            self.playerIndex = self.playerIndex + 1
            return True
        else:
            return False
    def gameOver(self):
        """
        Determines if the game is over

        returns: True if the playerIndex >= the number of players, False
        otherwise
        """
        return self.playerIndex >= len(self.players)
    def tryWord(self, word):
        if word == '.':
            raise EndHand()
        player = self.getCurrentPlayer()
        hand = player.getHand()
        if self.wordlist.containsWord(word) and hand.containsLetters(word):
            points = getWordScore(word)
            player.addPoints(points)
            hand.update(word)
            if hand.isEmpty():
                raise EndHand()
            return points
        else:
            return None
    def getWinner(self):
        return max(self.players)
    def getNumPlayers(self):
        return len(self.players)
    def isTie(self):
        return len(self.players) > 1 and \
               self.players[0].getPoints() == self.players[1].getPoints()
    def __str__(self):
        """
        Convert this game object to a string

        returns: the concatenation of the string representation of the players
        """
        string = ''
        for player in self.players:
            string = string + str(player)
        return string



# Test code
import ps10; reload(ps10)
from ps10 import *

def isClose(float1, float2):
    """
    Helper function - are two floating point values close?
    """
    return abs(float1 - float2) < .01

def testResult(boolean):
    """
    Helper function - print 'Test Failed' if boolean is false, 'Test
    Succeeded' otherwise.
    """
    if boolean:
        print 'Test Succeeded'
    else:
        print 'Test Failed'

def testHand():
    """
    Test the hand class. Add your own test cases
    """
    h = Hand(8, {'a':3, 'b':2, 'd':3})
    expected = {'a': 2, 'b': 1, 'd': 2};
    print("\nTesting that handDict %s is changed to %s after h.update('bad')" % (h.handDict, expected))
    h.update('bad')
    testResult(h.handDict == expected)
    print("\nTesting that h.containsLetters('aabdd') returns True and h.isEmpty() returns False with handDict %s" % h.handDict)
    testResult(h.containsLetters('aabdd') and not h.isEmpty())

    expected = {'a': 1, 'b': 1}
    print("\nTesting that handDict %s is changed to %s after h.update('dad')" % (h.handDict, expected))
    h.update('dad')
    testResult(h.handDict == expected)
    print("\nTesting that h.containsLetters('ab') returns True and h.isEmpty() returns False with handDict %s" % h.handDict)
    testResult(h.containsLetters('ab') and not h.isEmpty())

    expected = {}
    print("\nTesting that handDict %s is changed to %s after h.update('ab')" % (h.handDict, expected))
    h.update('ab')
    testResult(h.handDict == expected)
    print("\nTesting that h.isEmpty() returns True with handDict %s" % h.handDict)
    testResult(h.isEmpty())

    h = Hand(8, {'a':3, 'b':2, 'd':3})
    print("\nTesting that h.containsLetters('z') returns False handDict %s" % h.handDict)
    testResult(not h.containsLetters('z'))

    h = Hand(8, {'a':3, 'b':2, 'd':3})
    oh = Hand(8, {'a':3, 'b':2, 'd':3})
    print("\nTesting that hand with %s is equal to hand with %s" % (h.handDict, oh.handDict))
    testResult(h == oh)

    h = Hand(8, {'a':3, 'b':2, 'd':3})
    oh = Hand(8, {'d':3, 'b':2, 'a':3, 'c':0})
    print("\nTesting that hand with %s is equal to hand with %s" % (h.handDict, oh.handDict))
    testResult(h == oh)

    h = Hand(8, {'b':3, 'c':2, 'e':3})
    oh = Hand(8, {'a':3, 'b':2, 'd':3})
    print("\nTesting that hand with %s is not equal to hand with %s" % (h.handDict, oh.handDict))
    testResult(h != oh)

def testPlayer():
    """
    Test the Player class. Add your own test cases.
    """
    hand = Hand(6, {'c':1, 'a':1, 'b':1 ,'d':1, 'o':1, 'e':1})
    p = Player(1, hand)
    print("\nTesting that p.getHand() returns an instance of Hand")
    testResult(type(p.getHand()) == Hand)

    print("\nTesting that the Player constructor initializes p.hand to %s, p.points to %0.1f and p.idNum to %d" % (hand, 0., 1))
    testResult(p.hand == hand)
    testResult(p.points == 0)
    testResult(p.idNum == 1)

    print("\nTesting that p.getHand() returns p.hand")
    testResult(p.getHand() == p.hand)

    print("\nTesting that p.getPoints returns p.points")
    testResult(p.getPoints() == p.points)

    print("\nTesting that p.getIdNum returns p.idNum")
    testResult(p.getIdNum() == p.idNum)

    print("\nTesting that calling p.addPoints(5.) and p.addPoints(12.) sets the total number of points close to 17")
    p.addPoints(5.)
    p.addPoints(12.)
    testResult(isClose(p.getPoints(), 17))

    p1 = Player(1, Hand(1, {'a': 1}))
    p2 = Player(2, Hand(1, {'b': 1}))
    print("\nTesting that p1 with %0.1f points is equal to p2 with %0.1f points" % (p1.getPoints(), p2.getPoints()))
    testResult(p1 == p2)

    p1.addPoints(1)
    print("\nTesting that p1 with %0.1f points is greater than p2 with %0.1f points" % (p1.getPoints(), p2.getPoints()))
    testResult(p1 > p2)

    print("\nTesting that p2 with %0.1f points is less than p1 with %0.1f points" % (p2.getPoints(), p1.getPoints()))
    testResult(p2 < p1)

def testComputerPlayer():
    """
    Test the ComputerPlayer class. Add your own test cases.
    """
    wordlist = Wordlist()
    p = ComputerPlayer(1, Hand(6, {'c':1, 'a':1, 'b':1 ,'d':1, 'o':1, 'e':1}))
    expected = 'abode'
    print("Testing that the best word formed with the hand %s is %s and the best score possible is %0.1f" % (p.getHand(), expected, getWordScore(expected)))
    bestWord = p.pickBestWord(wordlist)
    testResult(bestWord == expected)
    testResult(getWordScore(bestWord) == getWordScore(expected))

    p = ComputerPlayer(1, Hand(7, {'h': 1, 'a': 2, 'z': 1, 'm': 3, 'o': 1, 'c': 2, 'k': 1}))
    expected = 'hammock'
    print("\nTesting that the best word formed with the hand %s is %s and the best score possible is %0.1f" % (p.getHand(), expected, getWordScore(expected)))
    bestWord = p.pickBestWord(wordlist)
    testResult(bestWord == expected)
    testResult(getWordScore(bestWord) == getWordScore(expected))

    p = ComputerPlayer(1, Hand(1, {'x': 1}))
    expected = ''
    print("\nTesting that the best word formed with the hand %s is %s and the best score possible is %0.1f" % (p.getHand(), expected, getWordScore(expected)))
    bestWord = p.pickBestWord(wordlist)
    testResult(bestWord == expected)
    testResult(getWordScore(bestWord) == getWordScore(expected))

def testAll():
    """
    Run all Tests
    """

    print "Uncomment the tests in this file as you complete each problem."

    print "PROBLEM 2 -----------------------------------------"
    testHand()
    print

    print 'PROBLEM 3 -----------------------------------------'
    testPlayer()
    print

    print 'PROBLEM 4 -----------------------------------------'
    testComputerPlayer()
    print

testAll()

1.1) True, though the solution might not be optimal
1.2) True, so long as they contain optimal substructure and overlapping sub problems
1.3) False, dynamic programming *can* find an optimal solution
1.4) False, Classes themselves are objects in addition to class instances
1.5) True
1.6) False, can have more than one branch

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

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

        If the list is empty, raises a ValueError exception.

    Side effects: none
    """

    if len(L) == 0:
        raise ValueError('List cannot be empty')

    sortedList = sorted(L)
    if len(sortedList) % 2 != 0:
        return sortedList[len(sortedList) // 2]

    return (sortedList[len(sortedList) // 2 - 1] + sortedList[len(sortedList) // 2]) / 2.0

3)
16
L = [
    Circle(0),
    Square(1),
    Circle(2),
    Square(3),
    Circle(4),
    Square(5),
    Circle(6),
    Square(7),
    Circle(8),
    Square(9),
]

Circle with radius 4
Circle with radius 8

4) True

4.1)
n is number of items in the knapsack
p sub i is the price of the element i
x sub i is whether item i is selected for inclusion
w sub i is the weight of item i
C is a constant representing the maximum weight allowed

4.2)
formula 1 calculates all possible possible values
formula 2 calculates all possible combinations with the weight constraint

5)
merge_sort(sequence)
    if length of sequence is 1,
        return sequence

    if length of sequence is 2,
        if sequence[0] is less than sequence[1],
            return sequence
        else
            return [sequence[1], sequence[0]]

    sorted_first_half = merge_sort(first half of sequence)
    sorted_second_half = merge_sort(second half of sequence)

    return merge(sorted_first_half, sorted_second_half)

merge(sequence_1, sequence_2)
    while sequence_1 and sequence_2 have items left
        if sequence_1[0] is greater than sequence_2[0],
            remove element 0 from sequence_1 and add it to sorted_sequence
        else
            remove element 0 form sequence_2 and add it to sorted_sequence

    if sequence_1 has elements left,
        add the rest of sequence_1 to sorted_sequence

    if sequence_2 has elements left,
        add the rest of sequence_2 to sorted_sequence

    return sorted_sequence

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

def findNumber(maxVal):
    """Assumes that maxVal is a positive integer. Returns a number, num,
       such that cmpGuess(num) == 0."""

    low = 0
    high = maxVal

    while True:
        guess = low + (high - low) / 2
        result = cmpGuess(guess)
        if (result == 0): return guess
        if (result == -1):
            low = guess
        else:
            high = guess

from string import *

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

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

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

#
# Problem 1: Create the Triangle class
#
class Triangle(Shape):
    def __init__(self, base, height):
        """
        Sets the base and height
        """

        self.base       = float(base)
        self.height     = float(height)

    def area(self):
        """
        Calculates and returns the area
        """

        return self.base * self.height / 2

    def getBase(self):
        return self.base

    def getHeight(self):
        return self.height

    def __str__(self):
        """
        Returns a string representation of the triangle
        """

        return 'Triangle with base %0.1f and height %0.1f' % (self.base, self.height)

    def __eq__(self, other):
        """
        Whether the two objects are equal
        """

        return type(other) == Triangle and (self.base, self.height) == (other.getBase(), other.getHeight())

#
# Problem 2: Create the ShapeSet class
#

class ShapeSet:
    def __init__(self):
        """
        Initialize any needed variables
        """
        self.shapes = []
        self.shapesCategorized = {
            Circle: [],
            Square: [],
            Triangle: []
        }

    def addShape(self, sh):
        """
        Add shape sh to the set; no two shapes in the set may be
        identical
        sh: shape to be added
        """
        if type(sh) not in self.shapesCategorized:
            raise ValueError('Object needs to be a Circle, Square or Triangle')

        for shape in self.shapes:
            if shape == sh:
                raise ValueError('Duplicate Shape')

        self.shapes.append(sh)
        self.shapesCategorized[type(sh)].append(sh)
        

    def __iter__(self):
        """
        Return an iterator that allows you to iterate over the set of
        shapes, one shape at a time
        """
        self.iterPointer = 0
        return self

    def next(self):
        if self.iterPointer >= len(self.shapes):
            raise StopIteration

        self.iterPointer += 1
        return self.shapes[self.iterPointer - 1]

    def __str__(self):
        """
        Return the string representation for a set, which consists of
        the string representation of each shape, categorized by type
        (circles, then squares, then triangles)
        """
        string = ''
        for shapeType in self.shapesCategorized:
            for shape in self.shapesCategorized[shapeType]:
                string += shape.__str__() + "\n"
        return string[:-3]


#
# Problem 3: Find the largest shapes in a ShapeSet
#
def findLargest(shapes):
    """
    Returns a tuple containing the elements of ShapeSet with the
       largest area.
    shapes: ShapeSet
    """
    largestSet = ()
    for shape in shapes:
        if not len(largestSet) or shape.area() > largestSet[0].area():
            largestSet = (shape,)
        elif shape.area() == largestSet[0].area():
            largestSet += (shape,)

    return largestSet


#
# Problem 4: Read shapes from a file into a ShapeSet
#
def readShapesFromFile(filename):
    """
    Retrieves shape information from the given file.
    Creates and returns a ShapeSet with the shapes found.
    filename: string
    """
    shset = ShapeSet()
    for line in open(filename, 'r', 0):
        shapeData = line.strip().split(',')
        if shapeData[0] == 'circle':
            shset.addShape(Circle(shapeData[1]))
        elif shapeData[0] == 'square':
            shset.addShape(Square(shapeData[1]))
        elif shapeData[0] == 'triangle':
            shset.addShape(Triangle(shapeData[1], shapeData[2]))
        else:
            raise ValueError('File contained unsupported shape: %s' % shapeData[0])

    return shset 

import time
from pprint import pprint

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

#
# Problem 1: Building A Subject Dictionary
#
def loadSubjects(filename):
    """
    Returns a dictionary mapping subject name to (value, work), where the name
    is a string and the value and work are integers. The subject information is
    read from the file named by the string filename. Each line of the file
    contains a string of the form "name,value,work".

    returns: dictionary mapping subject name to (value, work)
    """

    subjectMapping = {}

    inputFile = open(filename)
    for line in inputFile:
        words = line.strip().split(',')
        subjectMapping[words[0]] = (int(words[1]), int(words[2]))

    return subjectMapping

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

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

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

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

#
# Problem 2: Subject Selection By Greedy Optimization
#
def greedyAdvisor(subjects, maxWork, comparator):
    """
    Returns a dictionary mapping subject name to (value, work) which includes
    subjects selected by the algorithm, such that the total work of subjects in
    the dictionary is not greater than maxWork.  The subjects are chosen using
    a greedy algorithm.  The subjects dictionary should not be mutated.

    subjects: dictionary mapping subject name to (value, work)
    maxWork: int >= 0
    comparator: function taking two tuples and returning a bool
    returns: dictionary mapping subject name to (value, work)
    """
    subjectsToTake = {}
    currentBest = None
    done = False

    while not done:
        currentBest = None
        for subject in subjects:
            # If we have not selected the subject already and we either
            # do not have a "best" subject yet or the current subject is
            # better than our current best and we can fit it in with regards
            # to our maximum workload
            if not(subject in subjectsToTake) and (not currentBest or comparator(subjects[subject], subjects[currentBest])) and not(maxWork - subjects[subject][1] < 0):
                currentBest = subject

        # Cannot fit another subject in
        if not currentBest:
            done = True
        else:
            subjectsToTake[currentBest] = subjects[currentBest]
            maxWork -= subjects[currentBest][1]

    return subjectsToTake


def bruteForceAdvisor(subjects, maxWork):
    """
    Returns a dictionary mapping subject name to (value, work), which
    represents the globally optimal selection of subjects using a brute force
    algorithm.

    subjects: dictionary mapping subject name to (value, work)
    maxWork: int >= 0
    returns: dictionary mapping subject name to (value, work)
    """
    nameList = subjects.keys()
    tupleList = subjects.values()
    bestSubset, bestSubsetValue = \
            bruteForceAdvisorHelper(tupleList, maxWork, 0, None, None, [], 0, 0)
    outputSubjects = {}
    for i in bestSubset:
        outputSubjects[nameList[i]] = tupleList[i]
    return outputSubjects

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

#
# Problem 3: Subject Selection By Brute Force
#
def bruteForceTime():
    """
    Runs tests on bruteForceAdvisor and measures the time required to compute
    an answer.
    """
    start = time.time()
    print "Starting brute force"
    print bruteForceAdvisor(loadSubjects('subjects.txt'), 9)
    print "Ending brute force, took %0.2f seconds" % (time.time() - start)

# Problem 3 Observations
# ======================
#
# Anything over 8 for maxWork is unreasonable (10+ seconds is too much)

#
# Problem 4: Subject Selection By Dynamic Programming
#
def dpAdvisor(subjectsInfoDict, maxWork):
    """
    Returns a dictionary mapping subject name to (value, work) that contains a
    set of subjectsInfoDict that provides the maximum value without exceeding maxWork.

    subjectsInfoDict: dictionary mapping subject name to (value, work)
    maxWork: int >= 0
    returns: dictionary mapping subject name to (value, work)
    """
    selectedSubjectsDict = {}

    # Just the subject names
    subjects = subjectsInfoDict.keys()

    # Just the subject workload/value pairs
    workloadValueTuples = subjectsInfoDict.values()

    # Start searching for the optimal selection, starting at the top of
    # the subjects stack
    maxValue, selectedSubjects = dpAdvisorHelper(subjects, workloadValueTuples, len(subjects) - 1, maxWork, (), {})

    for subject in selectedSubjects:
        selectedSubjectsDict[subject] = subjectsInfoDict[subject]

    return selectedSubjectsDict

def dpAdvisorHelper(subjects, workloadValueTuples, index, maxWork, selectedSubjects, memo):
    memoIndex = (index, maxWork)

    # Check if the current index/maxWork combination is memoized
    try: return memo[memoIndex]
    except KeyError: pass

    # Index 0 means we are at the last subject
    if index == 0:
        # If we have room, include it, if not, do not
        if workloadValueTuples[index][1] <= maxWork:
            memo[memoIndex] = (workloadValueTuples[index][0], (subjects[index],))
        else:
            memo[memoIndex] = (0, ())

        return memo[memoIndex]

    # Selections if we do not choose the current subject
    withoutCurrentSubject = dpAdvisorHelper(subjects, workloadValueTuples, index - 1, maxWork, selectedSubjects, memo)

    # If we cannot include the current subject, then skip it
    if workloadValueTuples[index][1] > maxWork:
        memo[memoIndex] = withoutCurrentSubject
        return memo[memoIndex]

    # Get the selected subjects and maximum value with the current
    # subject selected
    withValue, withSelected = dpAdvisorHelper(subjects, workloadValueTuples, index - 1, maxWork - workloadValueTuples[index][1], selectedSubjects, memo)
    withValue += workloadValueTuples[index][0]

    without_value, without_selected = withoutCurrentSubject

    # Compare the two and determine which one is better
    if withValue > without_value:
        memo[memoIndex] = (withValue, (subjects[index],) + withSelected)
    else:
        memo[memoIndex] = withoutCurrentSubject

    return memo[memoIndex]

#
# Problem 5: Performance Comparison
#
def dpTime():
    """
    Runs tests on dpAdvisor and measure the time required to compute
    an answer.
    """
    start = time.time()
    print "Starting dp"
    print dpAdvisor(loadSubjects('subjects.txt'), 30)
    print "Ending dp, took %0.2f seconds" % (time.time() - start)

dpTime()
printSubjects(dpAdvisor(loadSubjects('subjects.txt'), 30))
# Problem 5 Observations
# ======================
#
# As the input and maximum workload grows, the dpAdvisor function gets much
# faster than the bruteForceAdvisor function. With the subjects loaded from
# the subjects.txt file and a maximum workload of 9, dpAdvisor is 2226 times
# faster.

# Problem 1
#
# What is the computational complexity of fact0?
#
# Linear, a constant amount of operations are called
# n times, where n is the size of the input (in this
# case an integer)
#
def fact0(i):
    assert type(i) == int and i >= 0
    if i == 0 or i == 1:
        return 1

    return i * fact0(i-1)

# Problem 2
#
# What is the computational complexity of fact1? Explain your answer.
#
# Linear, like the recursive version, a constant amount of operations
# are executed once per iteration in the while loop. The number of
# iterations is equal to the size of the input
#
def fact1(i):
    assert type(i) == int and i >= 0

    res = 1
    while i > 1:
        res = res * i
        i -= 1

    return res

# Problem 3
#
# What is the computational complexity of makeSet? Explain your answer.
#
# Linear, a constant amount of operations are executed once per
# iteration. The number of iterations is equal to the number of elements
# in s.
#
def makeSet(s):
    assert type(s) == str

    res = ''
    for c in s:
        if not c in res:
            res = res + c

    return res

# Problem 4
#
# What is the computational complexity of intersect? Explain your answer.
#
# Linear, the number of operations is O(makeSet) + O(makeSet) + the number
# of elements in s1
#
def intersect(s1, s2):
    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

# Problem 5
#
# Present a hand simulation of the code below. Describe the value to
# which each identifier is bound after each step of the computation.
# Note that “s1” and “s2” exist in more than one scope.
#
# s1    -> [1]
# s2    -> [2]
#
# (in function)
# tmp   -> [1]
# s1    -> [2]
# s2    -> [1]
# 
# print s1, s2 will print [2] and [1]
#
def swap0(s1, s2):
    assert type(s1) == list and type(s2) == list
    tmp = s1[:]
    s1 = s2[:]
    s2 = tmp
    return

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

# Problem 6
#
# Present a hand simulation of the following code:
#
# s1    -> [1]
# s2    -> [2]
#
# s1    -> s2
# s2    -> s1
#
# print s1, s2 will print [2] and [1]
#
def swap1(s1, s2):
    assert type(s1) == list and type(s2) == list
    return s2, s1

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

# Problem 7
#
# Present a hand simulation of the following code:
#
# s     -> [1,2,3]
#
# (in function)
# i     -> 0
# tmp   -> 1
# s[0]  -> 3
# s[-1] -> 1
#
# print s will print [3,2,1]
#
def rev(s):
    assert type(s) == list
    for i in range(len(s)/2):
        tmp = s[i]
        s[i] = s[-(i+1)]
        s[-(i+1)] = tmp

s = [1,2,3]
rev(s)
print s

import random
import string
import time

VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
HAND_SIZE = 20
POINTS_DICT = {}

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

def getWordScore(word, n):
    """
    Returns the score for a word. Assumes the word is a
    valid word.

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

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

    word: string (lowercase letters)
    returns: int >= 0
    """
    score = 0
    for letter in word:
        score += SCRABBLE_LETTER_VALUES[letter]

    if len(word) == n:
        score += 50

    return score

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

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

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

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

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

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

def updateHand(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)
    """
    wordFreqDict = get_frequency_dict(word)
    updatedHand = {}

    for letter in hand:
        updatedHand[letter] = hand[letter] - wordFreqDict.get(letter, 0)
        if not updatedHand[letter]:
            del updatedHand[letter]

    return updatedHand

def canMakeWord(word, hand):
    """
    Returns True if word can be made with the provided hand,
    False if it cannot
    """

    wordFreqDict = get_frequency_dict(word)
    for letter in wordFreqDict:
        if hand.get(letter, 0) < wordFreqDict[letter]:
            return False

    return True

def isValidWord(word, hand, pointsDict):
    """
    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
    """
    return pointsDict.get(word, False) and canMakeWord(word, hand)

def displayHand(hand):
    """
    Displays the current hand
    """

    for letter in hand:
        print letter,hand[letter]

def getWordInput(hand):
    word = raw_input('Enter a word or . to indicate that you are finished: ')
    inputIsValid = isValidWord(word, hand, POINTS_DICT) or word == '.'

    while not inputIsValid:
        word = raw_input('Word not valid. Please choose another word: ')
        inputIsValid = isValidWord(word, hand, POINTS_DICT) or word == '.'

    return word

def getWordsToPoints(wordList):
    """
    Return a dict that maps every word in wordList to its point value.
    """
    pointsDict = {}
    for word in wordList:
        pointsDict[word] = getWordScore(word, HAND_SIZE)
    
    return pointsDict

def pickBestWord(hand, pointsDict):
    """
    Return the highest scoring word from pointsDict that can be made with the given hand.

    Return '.' if no words can be made with the given hand.
    """

    bestScore = 0
    bestWord = '.'

    for word in pointsDict.keys():
        if canMakeWord(word, hand) and pointsDict[word] > bestScore:
            bestScore = pointsDict[word]
            bestWord = word

    return bestWord

def createCombinations(string):
    if len(string) == 1:
        return [string]

    solutions = []

    # Let T = the current string of letters
    # Let S = the current starting letter in our string
    # Let R = the rest of the string starting with the letter
    # immediately following S
    # Let K = the solutions for R
    # 
    # The solution for T is is the set of 
    # [S] + [S + K[0], S + K[1], S + K[2], ..., S + K[n]] + K

    solutions.append(string[0])
    subsolutions = createCombinations(string[1:])

    for subso in subsolutions:
        solutions.append(string[0] + subso)
        solutions.append(subso)

    return solutions

def pickBestWordFaster(hand, pointsDict, wordRearrangements):
    bestScore = 0
    bestWord = '.'
    currentHandAsString = ''

    for letter in hand:
        for i in range(hand[letter]):
            currentHandAsString += letter

    sortedCurrentHandAsString = ''.join(sorted(currentHandAsString))

    allPossibleSolutions = createCombinations(sortedCurrentHandAsString)

    for solution in allPossibleSolutions:
        if solution in wordRearrangements and pointsDict[wordRearrangements[solution]] > bestScore:
            bestScore = pointsDict[wordRearrangements[solution]]
            bestWord = wordRearrangements[solution]

    return bestWord

def getWordRearrangements(wordList):
    """
    Builds and returns a dictionary of words where the key is composed
    of all letters in a word, sorted alphabetically and the value is
    the word itself.
    """

    rearranged = {}
    for word in wordList:
        rearranged[''.join(sorted(word))] = word
    return rearranged

def getTimeLimit(pointsDict, k):
    """
    Return the time limit for the computer player as a function of the
    multiplier k
    """
    startTime = time.time()
    for word in pointsDict:
        get_frequency_dict(word)
        getWordScore(word, HAND_SIZE)
    endTime = time.time()
    return (endTime - startTime) * k

def play_hand(hand, word_list):
    """
    Allows the user to play the given hand, as follows:

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

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

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

    * After every valid word: the score for that word 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 'Enter time limit, in seconds, for players: '
    timeLimit = getTimeLimit(POINTS_DICT, 20)
    print "Time Limit: %0.8f seconds " % timeLimit
    timeLeft = timeLimit

    print "Current Hand: "
    displayHand(hand)

    score = 0
    gameIsDone = False

    while len(hand) and not gameIsDone:
        startTime = time.time()
#        word = pickBestWord(hand, POINTS_DICT)
        word = pickBestWordFaster(hand, POINTS_DICT, REARRANGE_DICT)
        print '"%s"' % word
        totalTime = time.time() - startTime

        if word == '.':
            gameIsDone = True
            continue

        print 'It took %0.10f seconds to provide an answer' % totalTime
        timeLeft -= totalTime

        if (timeLeft > 0):
            # Only give a maximum of the total letter score
            if totalTime < 1:
                totalTime = 1
            wordScore = getWordScore(word, HAND_SIZE) / totalTime
            score += wordScore
            hand = updateHand(hand, word)

            print 'Score for "%s": %0.2f. Total score so far: %0.2f' % (word, wordScore, score)
            print "Remaining letters: "
            displayHand(hand)
        else:
            print "Total time exceeds %0.8f seconds" % timeLimit
            gameIsDone = True
        print

    print "Final Score: %0.2f" % score

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)
    while True:
        cmd = raw_input('Enter n to deal a new hand, r to replay the last hand, or e to end game: ')
        if cmd == 'n':
            hand = deal_hand(HAND_SIZE)
            play_hand(hand.copy(), word_list)
            print
        elif cmd == 'r':
            play_hand(hand.copy(), word_list)
            print
        elif cmd == 'e':
            break
        else:
            print "Invalid command."

#
# Build data structures used for entire session and play game
#
if __name__ == '__main__':
    word_list = load_words()
    POINTS_DICT = getWordsToPoints(word_list)
    REARRANGE_DICT = getWordRearrangements(word_list)
#    for rearranged in REARRANGE_DICT:
#        print "Rearranged: %s, Word: %s" % (rearranged, REARRANGE_DICT[rearranged])
    play_game(word_list)


## Problem 5 ##
# 
# pickBestWord:
# Need to iterate all possible words (length(words))
# size of current word * size of word list
# Seems to be quadratic
# 
# pickBestWordFaster
# Need to iterate all possible subsets of sorted(hand), which is dependent 
# f(x) = 1 + 2(f(x - 1))
# Problem size is doubling each step, exponential where n is the size of hand
# This seems to be faster when the hand size is less than 20

# Testing code below
#
# x = 19
# hand = deal_hand(x)
# print "Comparing pickBestWord and PickBestWordFaster with %d" % x
# start = time.time()
# word = pickBestWord(hand, POINTS_DICT)
# end = time.time()
# 
# print "pickBestWord took %0.8f seconds" % (end - start)
# 
# start = time.time()
# word = pickBestWordFaster(hand, POINTS_DICT, REARRANGE_DICT)
# end = time.time()
# print "pickBestWordFaster took %0.8f seconds" % (end - start)

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 get_input_letter():
    letter = raw_input('Input a letter: ')
    
    while not letter in string.ascii_letters:
        letter = raw_input('Invalid letter, please enter again: ')

    return letter

def is_word(word, wordList):
    return word in wordList

def word_starts_with(word, fragment):
    return word[:len(fragment)] == fragment

def can_make_word(wordFragment, wordList):
    wordLength = len(wordFragment)

    for validWord in wordList:
        if word_starts_with(validWord, wordFragment):
            return True

    return False

def ghost(wordList):
    print "Welcome to Ghost!"

    currentPlayer = 'Player 1'
    gameDone = False
    currentWordFragment = ''

    while not gameDone:
        print "Current Player: %s" % currentPlayer
        print "The current word fragment is: '%s'" % currentWordFragment
        currentWordFragment += string.lower(get_input_letter())
        print "New word fragment: '%s'" % currentWordFragment

        if is_word(currentWordFragment, wordList) and len(currentWordFragment) > 3:
            print "'%s' lost because he or she spelled a word" % currentPlayer
            gameDone = True
        elif not can_make_word(currentWordFragment, wordList):
            print "'%s' lost because no word starts with '%s'" % (currentPlayer, currentWordFragment)
            gameDone = True
        elif currentPlayer == 'Player 1':
            currentPlayer = 'Player 2'
        else:
            currentPlayer = 'Player 1'

        print

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

ghost(wordList)

# 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
#
# The function get_word_score should accept a string of lowercase
# letters as input (a word) and return the integer score for that word,
# using the game's scoring rules.

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

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

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

    word: string (lowercase letters)
    returns: int >= 0
    """
    score = 0
    for letter in word:
        score += SCRABBLE_LETTER_VALUES[letter]

    if len(word) == n:
        score += 50

    return score

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

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

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

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

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

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

#
# Problem #2
#
# Implement the update_hand function. Make sure this function has no
# side effects; i.e., it cannot mutate the hand passed in.

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)
    """
    wordFreqDict = get_frequency_dict(word)
    updatedHand = {}

    for letter in hand:
        updatedHand[letter] = hand[letter] - wordFreqDict.get(letter, 0)
        if not updatedHand[letter]:
            del updatedHand[letter]

    return updatedHand


#
# Problem #3
#
# Implement the is_valid_word function

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
    """
    if word not in word_list:
        return False

    wordFreqDict = get_frequency_dict(word)
    for letter in wordFreqDict:
        if hand.get(letter, 0) < wordFreqDict[letter]:
            return False

    return True

#
# Problem #4
#
# Implement the play_hand function. This function allows the user to
# play out a single 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
    """

    print "Current Hand: ", hand

    score = 0
    user_terminated_game = False

    while len(hand) and not user_terminated_game:
        word = raw_input('Enter a word or . to indicate that you are finished: ')
        word_is_valid = is_valid_word(word, hand, word_list) or word == '.'

        while not word_is_valid:
            word = raw_input('Word not valid. Please choose another word: ')
            word_is_valid = is_valid_word(word, hand, word_list) or word == '.'

        if word == '.':
            user_terminated_game = True
            continue

        word_score = get_word_score(word, HAND_SIZE)
        score += word_score
        hand = update_hand(hand, word)

        print "Score for " + word + ": ", word_score
        print "Total score so far: ", score
        print "Remaining letters: ", hand

    print "Final Score: ", score

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

1) Are each of the following True or False:
    1.1. Any program that can be written using only function definitions and calls, the basic arithmetic operators, assignment, and conditionals will run in constant time.
        False
    1.2. Newton’s method will always converge on a correct root of a function.
        True
    1.3. In Python, dictionaries are immutable.
        False
    1.4. The value of ‘math.sqrt(2.0)*math.sqrt(2.0) == 2.0’ is True.
        False
    1.5. One should always avoid iteration when a recursive solution is possible.
        False
    1.6. Typically, the use of functions in a program reduces the total number of lines of code.
        True
    1.7. In Python, retrieving the value associated with a dictionary key takes roughly constant time.
        True

2) Consider the implementations of compare1 and compare 2, where a and b are floats.
    2.1) Do compare1 and compare2 return the same value for all possible inputs? If not, give a pair of inputs for which they return a different value.
        Yes
    2.2) Do compare1 and compare2 print the same thing for all possible inputs? If not, give a pair of inputs for which they print different things.
        No, they will print different results when provided a negative number for either a or b. compare1 modifies the actual parameter used for both comparing and printing the result, whereas compare2 keeps the original value when printing.
        compare1(-1, -2)
        Results in
        1 and 2 have the same absolute value.

        compare2(-1, -2)
        Results in
        -1 and -2 have the same absolute value.

3) Consider the following implementation of a function f, where x is a positive integer:
    def f(x):
        xs = str(x)
        if len(xs) == 1:
            return int(xs)

        n = int(xs[0]) + int(xs[1])

        if len(xs) == 2:
            return n
        else:
            return n + f(xs[2:])

    What does f(2112) return?

    xs = "2112"
    n = 2 + 1
    n = 3

    xs = "12"
    n = 1 + 2
    n = 3

    n = 6

    3.2) Write a specification of f.
        Returns the sum of all individual integers 

4) Provide a Python implementation of a function first_N that takes a positive integer, n, as its only argument. The function should print the first n perfect squares that are not even numbers. E.g., if n were 2 it should print the perfect squares 1 and 9.
    def first_N(n):
        currentRoot = 1
        while n > 0:
            if (currentRoot * currentRoot) % 2 != 0:
                print (currentRoot * currentRoot)
                n = n - 1
            currentRoot = currentRoot + 1

5) Write pseudo code for an exhaustive enumeration variant of guess and check.
    function guessandcheck(guess, values)
        iterate through all possible combinations
            if current value is same as guess, return guess
            else, next combo

6) Provide a Python implementation for the function findSide specified below
    def findSide():
        """asks the user to enter the area of a rectangle and the length of one side of the rectangle.
           Returns a floating point number that is the length of the adjacent side."""

        print "Enter area of rectangle"
        area = float(raw_input())
        print "Enter length of one side"
        side = float(raw_input())

        return (area / side)
        

7) Does the following function meet its specification? If not, change the program so that it is consistent with the specification.
    def f(L): 
        """Returns a copy of the list L without modifying L.""" 
        result = [] 
        for e in L: 
            result = result + e
        return result
Yes

8) At McDonalds one can buy chicken nuggets in packages containing 6, 9 or 20 pieces. Write a Python function that accepts an integer, num, as an argument and decides whether or not it is possible to buy num nuggets at McDonalds.

    def can_buy_nuggets_for_size(size):
        for a in range(0, (size / 6)):
            for b in range(0, (size / 9)):
                for c in range(0, (size / 20)):
                    current_combo = (6 * a) + (9 * b) + (20 * c)
                    if current_combo == size:
                        return True
        return False

9) Write an appropriate specification for the function below. Assume that n is an integer.
    def f(n):
        """
        Reverses the characters in n
        """

        s = str(n)
        if len(s) <= 1: return s
        return s[-1] + f(int(s[:-1]))

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

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

    yearlyAddAmount = salary * .01 * save

    savingsEachYear = (yearlyAddAmount,)

    for year in range(1, years):
        lastYearsBalance    = savingsEachYear[-1]
        thisYearsBalance    = lastYearsBalance * (1 + .01 * growthRate) + yearlyAddAmount
        savingsEachYear     = savingsEachYear + (thisYearsBalance,)

    return savingsEachYear

def testNestEggFixed():
    salary     = 10000
    save       = 10
    growthRate = 15
    years      = 5

    print "Testing nestEggFixed with salary: %d, save: %d, growthRate: %d, years: %d" % (salary, save, growthRate, years)
    savingsRecord = nestEggFixed(salary, save, growthRate, years)

    print "Should be", (1000.0, 2150.0, 3472.5, 4993.375, 6742.3812499999995)
    print "Is actually", savingsRecord

    # TODO: Add more test cases here.
    assert savingsRecord[0] < savingsRecord[1]
    assert savingsRecord[1] < savingsRecord[2]
    assert savingsRecord[2] < savingsRecord[3]
    assert savingsRecord[3] < savingsRecord[4]


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

def nestEggVariable(salary, save, growthRates):
    """
    - salary: the amount of money you make each year.
    - save: the percent of your salary to save in the investment account each
      year (an integer between 0 and 100).
    - growthRate: a list of the annual percent increases in your investment
      account (integers between 0 and 100).
    - return: a list of your retirement account value at the end of each year.
    """
    yearlyAddAmount = salary * .01 * save

    savingsEachYear = (yearlyAddAmount,)

    years = len(growthRates)

    for year in range(1, years):
        lastYearsBalance    = savingsEachYear[-1]
        thisYearsBalance    = lastYearsBalance * (1 + .01 * growthRates[year]) + yearlyAddAmount

        savingsEachYear = savingsEachYear + (thisYearsBalance,)

    return savingsEachYear
        

def testNestEggVariable():
    salary      = 10000
    save        = 10
    growthRates = [3, 4, 5, 0, 3]

    print "Testing nestEggVariable with salary: %d, save: %d, growthRates: " % (salary, save), growthRates
    savingsRecord = nestEggVariable(salary, save, growthRates)

    print "Should be", (1000.0, 2040.0, 3142.0, 4142.0, 5266.2600000000002)
    print "Is actually", savingsRecord

    assert savingsRecord[0] < savingsRecord[1]
    assert savingsRecord[1] < savingsRecord[2]
    assert savingsRecord[2] < savingsRecord[3]
    assert savingsRecord[3] < savingsRecord[4]


#
# Problem 3
#
# Write a function, called postRetirement, which takes three arguments:
# an initial amount of money in your retirement fund (savings), a list
# of annual growth percentages on investments while you are retired
# (growthRates), and your annual expenses (expenses). Assume that the
# increase in the investment account savings is calculated before
# subtracting the annual expenditures (as shown in the above table).
# Your function should return a list of fund sizes after each year of
# retirement, accounting for annual expenses and the growth of the
# retirement fund. Like problem 2, the length of the growthRates
# argument defines the number of years you plan to be retired.
#
# Note that if the retirement fund balance becomes negative,
# expenditures should continue to be subtracted, and the growth rate
# comes to represent the interest rate on the debt (i.e. the formulas in
# the above table still apply).
# 

def postRetirement(savings, growthRates, expenses):
    """
    - savings: the initial amount of money in your savings account.
    - growthRate: a list of the annual percent increases in your investment
      account (an integer between 0 and 100).
    - expenses: the amount of money you plan to spend each year during
      retirement.
    - return: a list of your retirement account value at the end of each year.
    """
    year1 = savings * (1 + 0.01 * growthRates[0]) - expenses
    savingsEachYear = (year1,)
    years = len(growthRates)

    for year in range(1, years):
        lastYearsBalance = savingsEachYear[-1]
        thisYearsBalance = lastYearsBalance * (1 + 0.01 * growthRates[year]) - expenses

        savingsEachYear = savingsEachYear + (thisYearsBalance,)

    return savingsEachYear


def testPostRetirement():
    savings     = 100000
    growthRates = [10, 5, 0, 5, 1]
    expenses    = 30000

    print "Testing postRetirement with savings: %d, expenses: %d, growthRates: " % (savings, expenses), growthRates
    savingsRecord = postRetirement(savings, growthRates, expenses)

    print "Should be", (80000.000000000015, 54000.000000000015, 24000.000000000015, -4799.9999999999854, -34847.999999999985)
    print "Is actually", savingsRecord
    
    assert savingsRecord[0] > savingsRecord[1]
    assert savingsRecord[1] > savingsRecord[2]
    assert savingsRecord[2] > savingsRecord[3]
    assert savingsRecord[3] > savingsRecord[4]


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

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.
    """
    yearsWorking = len(preRetireGrowthRates)
    yearsRetired = len(postRetireGrowthRates)

    savings = nestEggVariable(salary, save, preRetireGrowthRates)[-1]

    count = 0

    low = 0
    high = savings
    guess = (high - low) / 2
    finalBalance = epsilon + 1

    while abs(finalBalance) >= epsilon:
        print "Current guess for expenses: %0.2f" % guess
        finalBalance = postRetirement(savings, postRetireGrowthRates, guess)[-1]
        print "Final balance for this guess is: %0.8f" % finalBalance

        if (finalBalance < epsilon):
            high = guess
        else:
            low = guess
            
        guess = (high - low) / 2 + low

    assert count < 100, 'Maximum number of iterations exceeded'

    return guess

def testFindMaxExpenses():
    salary                = 10000
    save                  = 10
    preRetireGrowthRates  = [3, 4, 5, 0, 3]
    postRetireGrowthRates = [10, 5, 0, 5, 1]
    epsilon               = .01

    print "Testing findMaxExpenses with salary: %d, save: %d, epsilon: %0.2f, pre & post retirement growth rates respectively" % (salary, save, epsilon), preRetireGrowthRates, postRetireGrowthRates
    expenses = findMaxExpenses(salary, save, preRetireGrowthRates,
                               postRetireGrowthRates, epsilon)

    print "Should be close to 1229.95548986"
    print "Is actually %0.8f" % expenses

testNestEggFixed()
print
testNestEggVariable()
print
testPostRetirement()
print
testFindMaxExpenses()

from string import *

# Problem 1
#
# Write two functions, called countSubStringMatch and 
# countSubStringMatchRecursive that take two arguments, a key string and
# a target string. These functions iteratively and recursively count the
# number of instances of the key in the target string. You should
# complete definitions for
#
# def countSubStringMatch(target,key):
#
# and
#
# def countSubStringMatchRecursive (target, key):

# Iterative function counts number of instances of "key" in "target"
def countSubStringMatch(target, key):
    """
    Iterative function counts number of instances of "key" in "target"
    """

    found = 0
    current = find(target, key)
    while current != -1:
        found = found + 1
        current = find(target, key, current +1)
    return found

key = 'abc'
target = 'abcdabce'

print "Iterative implementation of 'countSubStringMatch' found '%s' %d times in '%s'" % (key, countSubStringMatch(target, key), target)

def countSubStringMatchRecursive(target, key):
    """
    Recursive function counts number of instances of "key" in "target"
    """

    index = find(target, key)
    if index == -1:
        return 0

    nextIndex = index + 1
    return 1 + countSubStringMatchRecursive(target[nextIndex:], key)

key = 'abc'
target = 'abcdabce'

print "Recursive implementation of 'countSubStringMatch' found '%s' %d times in '%s'" % (key, countSubStringMatchRecursive(target, key), target)

print

# Problem 2
#
# Write the function subStringMatchExact. This function takes two
# arguments: a target string, and a key string. It should return a tuple
# of the starting points of matches of the key string in the target
# string, when indexing starts at 0. Complete the definition for
#
# def subStringMatchExact(target,key):
#
# For example,
#
# subStringMatchExact("atgacatgcacaagtatgcat","atgc")
#
# would return the tuple (5, 15).

def subStringMatchExact(target, key):
    """
    Returns a tuple containing all starting indexes for found matches of
    key in target
    """

    foundIndexes = ()
    current = find(target, key)
    while current != -1:
        foundIndexes = foundIndexes + (current,)
        current = find(target, key, current + 1)

    return foundIndexes

#  target strings
target1 = 'atgacatgcacaagtatgcat'
target2 = 'atgaatgcatggatgtaaatgcag'

# key strings
key10 = 'a'
key11 = 'atg'
key12 = 'atgc'
key13 = 'atgca'

print "target: '%s', key: '%s', indexes: " % (target1, key10), subStringMatchExact(target1, key10)
print "target: '%s', key: '%s', indexes: " % (target1, key11), subStringMatchExact(target1, key11)
print "target: '%s', key: '%s', indexes: " % (target1, key12), subStringMatchExact(target1, key12)
print "target: '%s', key: '%s', indexes: " % (target1, key13), subStringMatchExact(target1, key13)
print

print "target: '%s', key: '%s', indexes: " % (target2, key10), subStringMatchExact(target2, key10)
print "target: '%s', key: '%s', indexes: " % (target2, key11), subStringMatchExact(target2, key11)
print "target: '%s', key: '%s', indexes: " % (target2, key12), subStringMatchExact(target2, key12)
print "target: '%s', key: '%s', indexes: " % (target2, key13), subStringMatchExact(target2, key13)
print

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

def constrainedMatchPair(firstMatches, secondMatches, length):
    """
    Returns a tuple of all starting indexes for the provided tuple of
    first matches that have a corresponding index in secondMatches such
    that the index in second match starts directly when the index from
    the first match ends
    """

    foundMatches = ()
    for firstMatch in firstMatches:
        for secondMatch in secondMatches:
            if (firstMatch + length + 1) == secondMatch:
                foundMatches = foundMatches + (firstMatch,)

    return foundMatches

# Test function
def subStringMatchOneSub(key,target):
    """
    search for all locations of key in target, with one substitution
    """

    allAnswers = ()
    print "key: '%s', target: '%s'" % (key, target)
    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 '%s' into '%s' and '%s'" % (key, 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 "matches for '%s': " % (key1,), match1
        print "matches for '%s': " % (key2,), match2
        print "possible matches for '%s*%s' start at: " % (key1, key2), filtered
    return allAnswers

subStringMatchOneSub(key11, target1)

print

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

def subStringMatchExactlyOneSub(target, key):
    """
    Returns a tuple of all starting points for matches of key in target
    such that one character in the match is incorrect
    """

    print "Looking for instances of '%s' with exactly one substitution in '%s'" % (key, target)

    exactMatches = subStringMatchExact(target, key)
    partialAndExactMatches = ()

    for gap in range(0, len(key)):
        key1 = key[:gap]
        key2 = key[gap+1:]
        print "Splitting '%s' into '%s' and '%s'" % (key, key1, key2)

        match1 = subStringMatchExact(target, key1)
        print "Exact matches for '%s':" % (key1), match1
        match2 = subStringMatchExact(target, key2)
        print "Exact matches for '%s':" % (key2), match2

        currentPartialAndExactMatches = constrainedMatchPair(match1, match2, len(key1))
        print "Partial and exact matches for '%s*%s': " % (key1, key2), currentPartialAndExactMatches
        partialAndExactMatches = partialAndExactMatches + currentPartialAndExactMatches

    partialMatches = ()
    for candidate in partialAndExactMatches:
        if not candidate in exactMatches:
            partialMatches = partialMatches + (candidate,)

    return partialMatches

target = 'azcdabzdabcadcd'
key = 'abcd'

matchesExactlyOneSub = subStringMatchExactlyOneSub(target, key)
print "Matches in '%s' for '%s' with exactly 1 substitution: " % (target, key), matchesExactlyOneSub

# Problem 1 Part 1

lookingFor = (50, 51, 52, 53, 54, 55)
for a in range(0, 55 / 6 + 1):
    for b in range(0, 55 / 9 + 1):
        for c in range(0, 55 / 20 + 1):
            solution = (6 * a) + (9 * b) + (20 * c)
            if solution in lookingFor:
                print "Combination found for %d: (%d packages of 6, %d packages of 9, %d packages of 20)" % (solution, a, b, c)

# Problem 2
#
# Because we know there is a valid combination for purchasing 50, 51,
# 52, 53, 54 and 55 Chicken McNuggets, and because we are able to
# purchase packages in sizes 6 or 9, we know there must be valid combinations 
# for purchasing 56-65 as we only need to add another package of "6" to our
# solution for purchasing "50" to get "56", another package of "6" to
# our solution for purchasing "51" to get "57", another package of "6"
# to our solution for purchasing "52" to get "58", another package of "6"
# to our solution for purchasing "53" or another package of "9" to our
# solution for puchasing "50" to get "59", etc.


# Problem 3
#
# Use this to write an exhaustive search to find the *largest* number of
# chicken nuggets that *cannot* be bought

foundInARow = 0
maxThatCannotBePurchased = 0

for i in range(0, 50):
    canPurchaseThisAmount = False

    for a in range(0, i / 6 + 1):
        for b in range(0, i / 9 + 1):
            for c in range(0, i / 20 + 1):
                solution = (6 * a) + (9 * b) + (20 * c)
                if solution == i:
                    canPurchaseThisAmount = True

    if canPurchaseThisAmount:
        foundInARow += 1
        if 6 == foundInARow:
            break;
    else:
        foundInARow = 0
        maxThatCannotBePurchased = i

print "Largest number of McNuggets that cannot be bought in exact quantity: %d" % maxThatCannotBePurchased

# Problem 4
#
# Assume that the variable packages is bound to a tuple of length 3, the
# values of which specify the sizes of the packages, ordered from
# smallest to largest. Write a program that uses exhaustive search to
# find the largest number (less than 200) of McNuggets that cannot be
# bought in exact quantity.

packages = (15, 24, 32)
maxThatCannotBePurchased = 0

for i in range(0, 200):
    canPurchaseThisAmount = False

    for a in range(0, i / packages[0] + 1):
        for b in range(0, i / packages[1] + 1):
            for c in range(0, i / packages[2] + 1):
                solution = (packages[0] * a) + (packages[1] * b) + (packages[2] * c)
                if solution == i:
                    canPurchaseThisAmount = True

    if canPurchaseThisAmount:
        foundInARow += 1
        if packages[0] == foundInARow:
            break;
    else:
        foundInARow = 0
        maxThatCannotBePurchased = i
 
print "Given that sizes %d, %d, and %d, the largest number of McNuggets that cannot be bought in exact quantity is: %d" % (packages[0], packages[1], packages[2], maxThatCannotBePurchased)

# Problem 1
#
# Write a program that computes and prints out the 1000th prime number
from math import *

def isPrime(number):
    """
    Determines whether 'number' is prime or not.
    """

    # Guard clauses
    if      1 >= number: return False
    elif    2 == number: return True

    divisor = 2

    # Only need to try divisors less than half of 'number'
    # as 
    #
    #   number / divisor 
    #   for all: (number / 2) < divisor < number
    #
    # will never divide evenly
    while divisor < number // 2:
        if 0 == number % divisor: return False
        divisor += 1 

    return True


primeCounter = 1
current = 3
print "Found Prime: #1: 2"

while (primeCounter < 1000):
    if isPrime(current):
        primeCounter += 1
        print "Found Prime: #%d: %d" % (primeCounter, current)

    current += 2


# Problem 2
#
# Write a program that prints the sum of log(x) where x is every prime number less than n.
# It should also print out the number n and the ratio of these two quantities.
from math import *

n = 500
current = 3
primeLogSum = log(2)

while current <= n:
    if isPrime(current):
        primeLogSum += log(current)

    current += 2

print "Sum of logarithms: %s"   % str(primeLogSum)
print "n: %s"                   % str(n)
print "ratio: %s"               % str(primeLogSum / n)

last_name = raw_input("What is your last name?")
first_name = raw_input("What is your first name?")

print first_name + " " + last_name