BTheMad

# Problem Set 11: Simulating robots
# Name: Alex

import math
import ps11_visualize
from matplotlib import pyplot
import random
# === Provided classes
class Position(object):
    """
    A Position represents a location in a two-dimensional room.
    """
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def getX(self):
        return self.x
    def getY(self):
        return self.y
    def getNewPosition(self, angle, speed):
        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):
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.tiles = {}
        for i in range(self.width):
            for j in range(self.height):
                self.tiles[(i, j)] = False

    def cleanTileAtPosition(self, pos):
        self.tiles[int(pos.getX()), int(pos.getY())] = True
        
    def isTileCleaned(self, m, n):
        return self.tiles[m, n]

    def getNumTiles(self):
        return len(self.tiles)
    
    def getNumCleanedTiles(self):
        return len(filter((lambda k: self.tiles[k] == True), self.tiles))
    
    def getRandomPosition(self):
        x = random.choice(range(self.width))
        y = random.choice(range(self.height))
        return Position(x, y)

    def isPositionInRoom(self, pos):
        if pos.getX() > 0 and pos.getY() > 0 and \
           pos.getX() < self.width and pos.getY() < self.height:
            return True
        else:
            return False


class BaseRobot(object):
    def __init__(self, room, speed):
        self.room = room
        self.speed = speed
        self.p = self.room.getRandomPosition()
        self.d = random.choice(range(360))

    def getRobotPosition(self):
        return self.p
    
    def getRobotDirection(self):
        return self.d
    
    def setRobotPosition(self, position):
        self.p = position
    
    def setRobotDirection(self, direction):
        self.d = direction


class Robot(BaseRobot):
    def updatePositionAndClean(self):
        while 1:
            tmp_p = self.p.getNewPosition(self.d, self.speed)
            if self.room.isPositionInRoom(tmp_p):
                break
            else:
                self.d = (random.choice(range(360)))
        self.p = tmp_p
        self.room.cleanTileAtPosition(self.p)

# === Problem 3
def runSimulation(num_robots, speed, width, height, min_coverage, num_trials,
                  robot_type, visualize):
    """
    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)
    min_coverage: a float (0 <= min_coverage <= 1.0)
    num_trials: an int (num_trials > 0)
    robot_type: class of robot to be instantiated (e.g. Robot or
                RandomWalkRobot)
    visualize: a boolean (True to turn on visualization)
    """
    result = []
    # anim = ps11_visualize.RobotVisualization(num_robots, width, height)
    for i in range(0, num_trials):
#        anim = ps11_visualize.RobotVisualization(num_robots, width, height)
        # Initialize room and robots
        room = RectangularRoom(width, height)
        robots = []
        for j in range(0, num_robots):
            robots.append(robot_type(room, speed))
        # Run the simulation
        room_coverrage = 0
        trial_result = []
        while room_coverrage < min_coverage:
            for r in robots:
                r.updatePositionAndClean()
            room_coverrage = (float(room.getNumCleanedTiles()) / room.getNumTiles())
            trial_result.append(room_coverrage)
#            anim.update(room, robots)
        result.append(trial_result)
#        anim.done()
    return result

# === 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 avg_list_len(list):
    """Documentation"""
    total_lenght = 0.0
    for l in list:
        total_lenght += len(l)
    return total_lenght / len(list)

# === Problem 4
def showPlot1():
    """
    Produces a plot showing dependence of cleaning time on room size.
    """
    num_robots = 1
    num_trials = 5
    speed = 1
    min_coverage = 0.75
    x_values = []
    y_values = []
    for i in range(5, 30, 5):
        y_values.append(avg_list_len(runSimulation(num_robots, speed, i, i,
                        min_coverage, num_trials, Robot, False)))
        x_values.append(i)
    pyplot.plot(x_values, y_values)
    pyplot.xlabel('Room size')
    pyplot.ylabel('Time')
    pyplot.title('Time by room size')
    pyplot.show()

# showPlot1()

def showPlot2():
    """
    Produces a plot showing dependence of cleaning time on number of robots.
    """
    room_width = 25
    room_height = 25
    num_trials = 5
    speed = 1
    min_coverage = 0.75
    x_values = []
    y_values = []
    for i in range(1, 11):
        y_values.append(avg_list_len(runSimulation(i, speed, room_width, room_height,
                        min_coverage, num_trials, Robot, False)))
        x_values.append(i)
    print y_values
    pyplot.plot(x_values, y_values)
    pyplot.xlabel('Robot count')
    pyplot.ylabel('Time')
    pyplot.title('Time by robot count')
    pyplot.show()

#showPlot2()

def showPlot3():
    """
    Produces a plot showing dependence of cleaning time on room shape.
    """
    room_width = [20, 25, 40, 50, 80, 100]
    room_height = [20, 16, 10, 8, 5, 4]
    num_trials = 20
    speed = 1
    min_coverage = 0.75
    x_values = []
    y_values = []
    for i in range(6):
        print i
        tw = room_width[i]
        th = room_height[i]
        y_values.append(avg_list_len(runSimulation(2, speed, tw, th,
                        min_coverage, num_trials, Robot, False)))
        x_values.append(i)
    print y_values
    pyplot.plot(x_values, y_values)
    pyplot.xlabel('Room dims')
    pyplot.ylabel('Time')
    pyplot.title('Time by room shape')
    pyplot.show()

# showPlot3()

def showPlot4():
    """
    Produces a plot showing cleaning time vs. percentage cleaned, for
    each of 1-5 robots.
    """
    room_width = 25
    room_height = 25
    num_trials = 1
    speed = 1
    for r in range(1, 6):
        x_values = []
        y_values = []
        for i in range(1, 101):
            cleanage_per = float(i) / 100
            y_values.append(avg_list_len(runSimulation(r, speed, room_width,
                            room_height, cleanage_per, num_trials, Robot, False)))
            x_values.append(i)
        pyplot.figure(1)
        pyplot.plot(x_values, y_values, label = str(r) + ' robots')
    pyplot.xlabel('% cleanage')
    pyplot.ylabel('Time')
    pyplot.title('Time by % cleaned and robots')
    pyplot.show()

#showPlot4()
# === Problem 5

class RandomWalkRobot(BaseRobot):
    """
    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):
        while 1:
            self.d = (random.choice(range(360)))
            tmp_p = self.p.getNewPosition(self.d, self.speed)
            if self.room.isPositionInRoom(tmp_p):
                break
            else:
                self.d = (random.choice(range(360)))
        self.p = tmp_p
        self.room.cleanTileAtPosition(self.p)

#runSimulation(1, 1, 10, 10, 1, 1, RandomWalkRobot, True)
# === Problem 6

def showPlot5():
    """
    Produces a plot comparing the two robot strategies.
    """
    num_robots = 5
    num_trials = 10
    speed = 1
    min_coverage = 0.75
    x_values = []
    y_values = []
    for i in range(5, 30, 5):
        y_values.append(avg_list_len(runSimulation(num_robots, speed, i, i,
                        min_coverage, num_trials, Robot, False)))
        x_values.append(i)
    pyplot.figure(1)
    pyplot.plot(x_values, y_values, label='Logic')

    x_values = []
    y_values = []
    for i in range(5, 30, 5):
        y_values.append(avg_list_len(runSimulation(num_robots, speed, i, i,
                        min_coverage, num_trials, RandomWalkRobot, False)))
        x_values.append(i)
    pyplot.figure(1)
    pyplot.plot(x_values, y_values, label='Random')
    pyplot.xlabel('Room size')
    pyplot.ylabel('Time')
    pyplot.title('Time by room size')
    pyplot.legend()
    pyplot.show()

showPlot5()

# 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
        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 in word:
            self.handDict[letter] = self.handDict.get(letter, 0) - 1
            if self.handDict[letter] == 0:
                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
        """
        tmpDict = self.handDict.copy()
        for letter in letters:
            if tmpDict.get(letter, 0) == 0:
                return False
            else:
                tmpDict[letter] = tmpDict.get(letter, 0) - 1
        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.
        """
        if self.handDict:
            return False
        else:
            return True
    
    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
        """
        if self.handDict.equal(other):
            return True
        else:
            return False
    
    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.points, 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
        """
        word = "."
        score = 0
        best_score = 0
        h = self.getHand()
        for tmp_word in wordlist.getList():
            if h.containsLetters(tmp_word):
                score = getWordScore(tmp_word)
                if score > best_score:
                    word = tmp_word
                    best_score = score
        return word
    
    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):
    def __init__(self, mode, wordlist):
        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):
        return self.players[self.playerIndex]
    def nextPlayer(self):
        if self.playerIndex + 1 < len(self.players):
            self.playerIndex = self.playerIndex + 1
            return True
        else:
            return False
    def gameOver(self):
        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):
        string = ''
        for player in self.players:
            string = string + str(player)
        return string

# 6.00 Problem Set 9
#
# Name: Alex
# Collaborators:
# Time:

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
#
## TO DO: Implement the `Triangle` class, which also extends `Shape`.
class Triangle(Shape):
    """docstring for Triangle"""
    def __init__(self, base, height):
        self.base = float(base)
        self.height = float(height)
    
    def area(self):
        """Returns approximate area of the triangle"""
        return (0.5 * self.base * self.height)
    
    def __str__(self):
        return 'Triangle with base %0.2f and height %0.2f' %(self.base, self.height)
    
    def __eq__(self, other):
        """Two triangles are equal if their base and height are"""
        return type(other) == Triangle \
        and self.base == other.base \
        and self.height == other.height

#
# Problem 2: Create the ShapeSet class
#
## TO DO: Fill in the following code skeleton according to the
##    specifications.

class ShapeSet:
    def __init__(self):
        """
        Initialize any needed variables
        """
        self.place = 0
        self.shapes_list = []

    def add_shape(self, sh):
        """
        Add shape sh to the set; no two shapes in the set may be
        identical
        sh: shape to be added
        """
        for shape in self.shapes_list:
            if sh == shape:
                raise ValueError('Duplicate shape')
        self.shapes_list.append(sh)

    def __iter__(self):
        """
        Return an iterator that allows you to iterate over the set of
        shapes, one shape at a time
        """
        self.place = 0
        return self
    
    def next(self):
        """docstring for next"""
        if self.place >= len(self.shapes_list):
            raise StopIteration
        self.place += 1
        return self.shapes_list[self.place - 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)
        """
        tr = []
        ci = []
        sq = []
        tmp_str = ''
        for shape in self.shapes_list:
            if type(shape) == Square:
                sq.append(shape.__str__())
            elif type(shape) == Circle:
                ci.append(shape.__str__())
            elif type(shape) == Triangle:
                tr.append(shape.__str__())
        if len(tr) > 0:
            tmp_str += '=== Triangles === \n'
            for t in tr:
                tmp_str += t + '\n'
        if len(ci) > 0:
            tmp_str += '=== Circles === \n'
            for c in ci:
                tmp_str += c + '\n'
        if len(sq) > 0:
            tmp_str += '=== Squares === \n'
            for s in sq:
                tmp_str += s + '\n'
        
        return tmp_str

#
# 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
    """
    largest = ()
    largest_area = 0
    for shape in shapes:
        if shape.area() > largest_area:
            largest_area = shape.area()
            largest = (shape, )
        elif shape.area() == largest_area:
            largest += (shape, )
    return largest

#
# 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
    """
    input_file = open(filename)
    ss = ShapeSet()
    tshape = []
    for line in input_file:
        tshape.append(line.split(','))
    for shape in tshape:
        if shape[0] == 'circle':
            ss.add_shape(Circle(shape[1].strip()))
        elif shape[0] == 'square':
            ss.add_shape(Square(shape[1].strip()))
        elif shape[0] == 'triangle':
            ss.add_shape(Triangle(shape[1].strip(), shape[2].strip()))
    
    return ss

ss = readShapesFromFile("shapes.txt")
print ss

# 6.00 Problem Set 8
#
# Intelligent Course Advisor
#
# Name: Alex
#

import time

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

    # The following sample code reads lines from the specified file and prints
    # each one.
    inputFile = open(filename)
    subject_dict = {}
    for line in inputFile:
        name, value, work = line.split(',')
        value = int(value)
        work = int(work.strip())
        subject_dict[name] = (value, work)
    return subject_dict

    # TODO: Instead of printing each line, modify the above to parse the name,
    # value, and work of each subject and create a dictionary mapping the name
    # to the (value, work).

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]
    if val1 > val2:
        return 1
    else:
        return -1

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]
    if work1 < work2:
        return 1
    else:
        return -1

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]
    if float(val1) / work1 > float(val2) / work2:
        return 1
    else:
        return -1

#
# 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)
    """
    adv_subjects = {}
    work_cnt = 0
    tmp_subj = [(v, w, n) for n, (v, w) in subjects.iteritems()]
    for v, w, n in sorted(tmp_subj, cmp=comparator, reverse=True):
        if (work_cnt + w < maxWork):
            adv_subjects[n] = (v, w)
            work_cnt += w
        else:
            break
    return adv_subjects

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.
    """
    filename = 'subjects.txt'
    max_work = 5
    subject_dict = loadSubjects(filename)
    start_time = time.time()
    adv_subjects = bruteForceAdvisor(subject_dict, max_work)
    end_time = time.time()
    total_time = end_time - start_time
    printSubjects(adv_subjects)
    print "Total time with max_work = %d is %0.4f seconds" %(max_work, total_time)

# Problem 3 Observations
# ======================
#
# TODO: write here your observations regarding bruteForceTime's performance
#
# Problem 4: Subject Selection By Dynamic Programming
#
def dpAdvisor(subjects, maxWork):
    """
    Returns a dictionary mapping subject name to (value, work) that contains a
    set of subjects that provides the maximum value without exceeding maxWork.

    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 = \
            dpAdvisorHelper(tupleList, maxWork, 0, None, None, [], 0, 0, {})
    outputSubjects = {}
    for i in bestSubset:
        outputSubjects[nameList[i]] = tupleList[i]
    return outputSubjects

def dpAdvisorHelper(subjects, maxWork, i, bestSubset, bestSubsetValue,
                                subset, subsetValue, subsetWork, memo):
    global numCalls
    numCalls += 1
    try: return memo[0]
    except KeyError:
        # Hit the end of the list.
        if i >= len(subjects):
            if bestSubset == None or subsetValue > bestSubsetValue:
                # Found a new best.
                memo[0] = subset[:], subsetValue
                return subset[:], subsetValue
            else:
                # Keep the current best.
                memo[0] = bestSubset, bestSubsetValue
                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 = dpAdvisorHelper(subjects,
                        maxWork, i+1, bestSubset, bestSubsetValue, subset,
                        subsetValue + s[VALUE], subsetWork + s[WORK], memo)
                subset.pop()
            bestSubset, bestSubsetValue = dpAdvisorHelper(subjects,
                    maxWork, i+1, bestSubset, bestSubsetValue, subset,
                    subsetValue, subsetWork, memo)
            memo[0] = bestSubset, bestSubsetValue
            return bestSubset, bestSubsetValue

#
# Problem 5: Performance Comparison
#
def dpTime():
    """
    Runs tests on dpAdvisor and measures the time required to compute an
    answer.
    """
    filename = 'subjects.txt'
    max_work = 15
    # subject_dict = loadSubjects(filename)
    subject_dict = {'6.00': (16, 8), '1.00': (7, 7), '6.01': (5, 3), '15.01': (9, 6)}
    # start_time = time.time()
    
    adv_subjects = dpAdvisor(subject_dict, max_work)
    print numCalls
    # end_time = time.time()
    printSubjects(adv_subjects)
    adv_subjects = bruteForceAdvisor(subject_dict, max_work)
    # print numCalls
    # total_time = end_time - start_time
    printSubjects(adv_subjects)
    # print "Total time with max_work = %d is %0.4f seconds" %(max_work, total_time)

numCalls = 0
dpTime()

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

import random
import time

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

SCRABBLE_LETTER_VALUES = {
    'a': 1, 'b': 3, 'c': 3, 'd': 2, 'e': 1, 'f': 4, 'g': 2, 'h': 4, 'i': 1, 'j': 8, 'k': 5, 'l': 1, 'm': 3, 'n': 1, 'o': 1, 'p': 3, 'q': 10, 'r': 1, 's': 1, 't': 1, 'u': 1, 'v': 4, 'w': 4, 'x': 8, 'y': 4, 'z': 10
}

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

WORDLIST_FILENAME = "words.txt"

def load_words():
    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):
    # freqs: dictionary (element_type -> int)
    freq = {}
    for x in sequence:
        freq[x] = freq.get(x,0) + 1
    return freq


# (end of helper code)
# -----------------------------------

#
# Problem #1: Scoring a word
#
def get_word_score(word, n):
    score = 0
    if len(word) == 0:
        return score
    elif word == '.':
        return score
    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):
    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):
    hand={}
    num_vowels = n / 3

    for i in range(num_vowels):
        x = VOWELS[random.randrange(0,len(VOWELS))]
        hand[x] = hand.get(x, 0) + 1

    for i in range(num_vowels, n):
        x = CONSONANTS[random.randrange(0,len(CONSONANTS))]
        hand[x] = hand.get(x, 0) + 1

    return hand

#
# Problem #2: Update a hand by removing letters
#
def update_hand(hand, word):
    for letter in word:
        hand[letter] = hand.get(letter, 0) - 1
        if hand[letter] == 0:
            del hand[letter]
    return hand

#
# Problem #3: Test word validity
#
def is_valid_word(word, hand, points_dict):
    freq = get_frequency_dict(word)
    for letter in word:
        if freq[letter] > hand.get(letter, 0):
            return False
    if points_dict.get(word) > 0:
        return True
    else:
        return False

#
# Problem #6.3: Get points for words
#
def get_words_to_points(word_list):
    """Return a dict that maps every word in a word_list to its point value."""
    points_dict = {}
    for word in word_list:
        points_dict[word] = get_word_score(word, HAND_SIZE)

    return points_dict

#
# Problem #6.3: Get points for words
#
def pick_best_word(hand, points_dict):
    """Find best word with given hand and points dictionary"""
    word = "."
    score = 0
    best_score = 0
    for tmp_word in points_dict.keys():
        if is_valid_word(tmp_word, hand, points_dict):
            score = get_word_score(tmp_word, HAND_SIZE)
            if score > best_score:
                word = tmp_word
                best_score = score
    return word

#
# Problem #6.4: Get a sequence of letters for a word
#
def get_word_rearrangements(word):
    """Get a string of letters, that are contained in a word"""
    tmp_list = list(word)
    tmp_list.sort()
    sequence = "".join(tmp_list)

    return sequence

#
# Problem #6.4: Get a sequence of letters for a hand
#
def get_hand_rearrangements(hand):
    """ Get a rearrangements for a given hand """
    tmp_list = []
    for letter in hand.keys():
        for j in range(hand[letter]):
            tmp_list.append(letter)
    tmp_list.sort()
    sequence = "".join(tmp_list)

    return sequence

#
# Problem #6.4: Create a rearrangement dictionary
#
def get_rearrange_dic(word_list):
    """Create a list of words as sequences of letter for a word list"""
    rearrange_dict = {}
    for word in word_list:
        rearrange_dict[get_word_rearrangements(word)] = word
    return rearrange_dict

def get_sets_recursive(word, word_list):
    """Generate all possible string from a given, without order changed"""
    if len(word) > 0:
        str_word = "".join(word)
        if str_word not in word_list:
            word_list.append(str_word)
        for letter in word:
            tmp_word = word[:]
            tmp_word.remove(letter)
            if len(tmp_word) > 0 and "".join(tmp_word) not in word_list:
                get_sets_recursive(tmp_word, word_list)
    return word_list

#
# Problem #6.4: Generate all sequences from a word
#
def get_all_hand_sets(word):
    """Generate all possible string from a given, without order changed"""
    word_list = get_sets_recursive(list(word), [])

    return word_list

#
# Problem #6.4: Pick word faster, than ever
#
def pick_best_word_faster(hand, rearrange_dict):
    """Faster version of picking word algorithm"""
    hand_rearrangements = get_hand_rearrangements(hand)
    hand_sets = get_all_hand_sets(hand_rearrangements)
    max_score_word = '.'
    max_score = 0
    score = 0
    word = '.'
    for sub_set in hand_sets:
        if sub_set in rearrange_dict.keys():
            word = rearrange_dict[sub_set]
            score = get_word_score(word, HAND_SIZE)
            if score > max_score:
                max_score_word = word
                max_score = score

    return max_score_word

#
# Problem #6.3: Get timelimit for a computer
#
def get_time_limit(points_dict, k):
    """
    Return the time limit for the computer player as a function of the multiplier k.
    points_dict should be the same dictionary that is created by get_words_to_points.
    """
    start_time = time.time()
    # Do some computation. The only purpose of the computation is so we can
    # figure out how long your computer takes to perform a known task.
    for word in points_dict:
        get_frequency_dict(word)
        get_word_score(word, HAND_SIZE)
    end_time = time.time()
    return (end_time - start_time) * k

#
# Problem #4: Playing a hand
#
def play_hand(hand, points_dict, rearrange_dict):
    """
      hand: dictionary (string -> int)
      word_list: list of lowercase strings
    """
    total_score = 0
    game_finished = False
    time_limit = get_time_limit(points_dict, 10)
    print "Time limit is set to %0.2f" %time_limit
    total_time = 0
    time_left = 0

    while not game_finished:
        score = 0
        round_start = 0
        round_end = 0
        round_time = 0
        print "Current hand: ",
        display_hand(hand)
        round_start = time.time()
        round_start = time.time()
        word = pick_best_word(hand, points_dict)
        round_end = time.time()
        round_time = round_end - round_start
        print "###################### %s #########################" %word
        print "###################### %d #########################" %get_word_score(word, HAND_SIZE)
        print "###################### %0.5f #########################" %round_time
        round_start = time.time()
        word = pick_best_word_faster(hand, rearrange_dict)
        round_end = time.time()
        round_time = round_end - round_start
        print "###################### %s #########################" %word
        print "###################### %d #########################" %get_word_score(word, HAND_SIZE)
        print "###################### %0.5f #########################" %round_time
        round_end = time.time()
        round_time = round_end - round_start
        total_time += round_time
        time_left = time_limit - total_time
        if word == ".":
            game_finished = True
        elif len(hand) == 0:
            game_finished = True
        elif total_time > time_limit:
            print "Total time exceeds %d seconds" %time_limit
            game_finished = True
        else:
            if is_valid_word(word, hand, points_dict):
                score = get_word_score(word, HAND_SIZE) / round_time
                total_score += score
                print "It took %0.2f seconds to provide an answer." %round_time
                print "You have %0.2f seconds remaining." %(time_left)
                print "%s earned %0.2f points. Total: %0.2f points." %(word, score, total_score)
                hand = update_hand(hand.copy(), word)
            else:
                print "Invalid word, please try again."
                print "You have %0.2f seconds remaining." %(time_left)



    if game_finished:
        print "Total score: %0.2f" %total_score


#
# Problem #5: Playing a game
# Make sure you understand how this code works!
#
def play_game(points_dict, rearrange_dict):
    hand = deal_hand(HAND_SIZE) # random init
    while True:
        cmd = raw_input('Enter n to deal a new hand, r to replay the last hand, or e to end game: ')
        if cmd == 'n':
            hand = deal_hand(HAND_SIZE)
            play_hand(hand.copy(), points_dict, rearrange_dict)
            print
        elif cmd == 'r':
            play_hand(hand.copy(), points_dict, rearrange_dict)
            print
        elif cmd == 'e':
            break
        else:
            print "Invalid command."

#
# Build data structures used for entire session and play game
#
if __name__ == '__main__':
    word_list = load_words()
    points_dict = get_words_to_points(word_list)
    rearrange_dict = get_rearrange_dic(word_list)
    play_game(points_dict, rearrange_dict)

# Problem Set 5: Ghost
# Name: 
# Collaborators: 
# Time: 
#

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

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

def lost_by_word(word, wordlist):
    """Did player lost the game?"""
    if len(word) > 3 and word in wordlist:
        return True
    return False

def lost_by_no_word(word, wordlist):
    for tmp_word in wordlist:
        if word in tmp_word[0:len(word)]:
            print tmp_word
            return False
    return True

def test_lost_by_word(wordlist):
    succeed = True

    word = "eye"
    if lost_by_word(word, wordlist):
        print "Must return False and got True with word " + word
        succeed = False

    word = "banana"
    if not lost_by_word(word, wordlist):
        print "Must return True and got False with word " + word
        succeed = False

    if succeed:
        print "All test passed"
    else:
        print "Failed"

def test_lost_by_no_word(wordlist):
    succeed = True

    word = "zar"
    if not lost_by_no_word(word, wordlist):
        print "Must return True and got False with word " + word
        succeed = False

    word = "pyn"
    if lost_by_no_word(word, wordlist):
        print "Must return False and got True with word " + word
        succeed = False

    if succeed:
        print "All test passed"
    else:
        print "Failed"


def ghost(wordlist):
    print "Welcome to Ghost"
    print "Player 1 goes first."
    game_over = False
    fragment = ''
    current_player = 1

    while not game_over:
        print "Current word fragment: '" + fragment + "'"

        no_letter = True
        while no_letter:
            letter = raw_input("Player " + str(current_player) + " says letter: ")

            if letter not in string.ascii_letters:
                print "A letter please!"
            else:
                no_letter = False

        fragment += letter.lower()
        #print fragment
        if lost_by_word(fragment, wordlist):
            game_over = True
            print "Player " + str(current_player) + " loses because '" + fragment + "' is a word!"
        if lost_by_no_word(fragment, wordlist):
            game_over = True
            print "Player " + str(current_player) + " loses no word begins with " + fragment

        if current_player == 1:
            current_player = 2
        else:
            current_player = 1

        if game_over:
            print "Player " + str(current_player) + " wins!"



wordlist = load_words()
ghost(wordlist)
# test_lost_by_word(wordlist)
# test_lost_by_no_word(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: Scoring a word
#
def get_word_score(word, n):
    """
    Returns the score for a word. Assumes the word is a
    valid word.

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

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

    word: string (lowercase letters)
    returns: int >= 0
    """
    score = 0
    if len(word) == 0:
        return score
    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: Update a hand by removing letters
#
def update_hand(hand, word):
    """
    Assumes that 'hand' has all the letters in word.
    In other words, this assumes that however many times
    a letter appears in 'word', 'hand' has at least as
    many of that letter in it. 

    Updates the hand: uses up the letters in the given word
    and returns the new hand, without those letters in it.

    Has no side effects: does not mutate hand.

    word: string
    hand: dictionary (string -> int)    
    returns: dictionary (string -> int)
    """
    for letter in word:
        hand[letter] = hand.get(letter, 0) - 1
        if hand[letter] == 0:
            del hand[letter]
    return hand

#
# Problem #3: Test word validity
#
def is_valid_word(word, hand, word_list):
    """
    Returns True if word is in the word_list and is entirely
    composed of letters in the hand. Otherwise, returns False.
    Does not mutate hand or word_list.
    
    word: string
    hand: dictionary (string -> int)
    word_list: list of lowercase strings
    """
    if word not in word_list:
        return False
    for letter in word:
        if hand.get(letter, 0) == 0:
            return False
        else:
            hand[letter] = hand.get(letter, 0) - 1

    return True

#
# Problem #4: Playing a hand
#
def play_hand(hand, word_list):
    """
    Allows the user to play the given hand, as follows:

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

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

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

    * After every valid word: the score for that word and the total
      score so far are displayed, the remaining letters in the hand 
      are displayed, and the user is asked to input another word.

    * The sum of the word scores is displayed when the hand finishes.

    * The hand finishes when there are no more unused letters.
      The user can also finish playing the hand by inputing a single
      period (the string '.') instead of a word.

    * The final score is displayed.

      hand: dictionary (string -> int)
      word_list: list of lowercase strings
    """
    total_score = 0
    game_finished = False

    while not game_finished:
        score = 0
        print "Current hand: ",
        display_hand(hand)
        word = raw_input("Enter word, or a . to indicate that you are finished:");
        if word == ".":
            game_finished = True
        elif len(hand) == 0:
            game_finished = True
        else:
            if is_valid_word(word, hand, word_list):
                score = get_word_score(word, HAND_SIZE)
                total_score += score
                print "%s earned %0.2f points. Total: %0.2f points." %(word, score, total_score)
                hand = update_hand(hand.copy(), word)
            else:
                print "Invalid word, please try again."
    if game_finished:
        print "Total score: %0.2f" %total_score

#
# Problem #5: Playing a game
# Make sure you understand how this code works!
# 
def play_game(word_list):
    """
    Allow the user to play an arbitrary number of hands.

    * Asks the user to input 'n' or 'r' or 'e'.

    * If the user inputs 'n', let the user play a new (random) hand.
      When done playing the hand, ask the 'n' or 'e' question again.

    * If the user inputs 'r', let the user play the last hand again.

    * If the user inputs 'e', exit the game.

    * If the user inputs anything else, ask them again.
    """
    
    ## uncomment the following block of code once you've completed Problem #4
    hand = deal_hand(HAND_SIZE) # random init
    while True:
        cmd = raw_input('Enter n to deal a new hand, r to replay the last hand, or e to end game: ')
        if cmd == 'n':
            hand = deal_hand(HAND_SIZE)
            play_hand(hand.copy(), word_list)
            print
        elif cmd == 'r':
            play_hand(hand.copy(), word_list)
            print
        elif cmd == 'e':
            break
        else:
            print "Invalid command."

#
# Build data structures used for entire session and play game
#
if __name__ == '__main__':
    word_list = load_words()
    play_game(word_list)

#
# Problem 1
#
def nestEggFixed(salary, save, growthRate, years):
    """
    - salary: the amount of money you make each year.
    - save: the percent of your salary to save in the investment account each
      year (an integer between 0 and 100).
    - growthRate: the annual percent increase in your investment account (an
      integer between 0 and 100).
    - years: the number of years to work.
    - return: a list whose values are the size of your retirement account at
      the end of each year.
    """
    savings = [salary * save * 0.01]
    cur_savings = 0
    for cur_year in range(1, years):
        cur_savings = savings[cur_year - 1] * (1 + 0.01 * growthRate) \
                      + salary * save * 0.01
        savings.append(cur_savings)
    return savings

def testNestEggFixed():
    salary = 10000
    save = 10
    growthRate = 15
    years = 5
    savingsRecord = nestEggFixed(salary, save, growthRate, years)
    print savingsRecord
    # Output should have values close to:
    # [1000.0, 2150.0, 3472.5, 4993.375, 6742.3812499999995]


#
# Problem 2
#
def nestEggVariable(salary, save, growthRates):
    """
    - salary: the amount of money you make each year.
    - save: the percent of your salary to save in the investment account each
      year (an integer between 0 and 100).
    - growthRate: a list of the annual percent increases in your investment
      account (integers between 0 and 100).
    - return: a list of your retirement account value at the end of each year.
    """
    savings = [salary * save * 0.01]
    cur_savings = 0
    for cur_year in range(1, len(growthRates)):
        cur_savings = savings[cur_year - 1] * \
                      (1 + 0.01 * growthRates[cur_year]) \
                      + salary * save * 0.01
        savings.append(cur_savings)
    return savings

def testNestEggVariable():
    salary = 10000
    save = 10
    growthRates = [3, 4, 5, 0, 3]
    savingsRecord = nestEggVariable(salary, save, growthRates)
    print savingsRecord
    # Output should have values close to:
    # [1000.0, 2040.0, 3142.0, 4142.0, 5266.2600000000002]


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

def testPostRetirement():
    savings = 100000
    growthRates = [10, 5, 0, 5, 1]
    expenses = 30000
    savingsRecord = postRetirement(savings, growthRates, expenses)
    print savingsRecord
    # Output should have values close to:
    # [80000.000000000015, 54000.000000000015, 24000.000000000015,
    # -4799.9999999999854, -34847.999999999985]


#
# Problem 4
#
def findMaxExpenses(salary, save, preRetireGrowthRates, postRetireGrowthRates,
                    epsilon):
    """
    - salary: the amount of money you make each year.
    - save: the percent of your salary to save in the investment account each
      year (an integer between 0 and 100).
    - preRetireGrowthRates: a list of annual growth percentages on investments
      while you are still working.
    - postRetireGrowthRates: a list of annual growth percentages on investments
      while you are retired.
    - epsilon: an upper bound on the absolute value of the amount remaining in
      the investment fund at the end of retirement.
    """
    num_of_years = len(preRetireGrowthRates)
    all_savings = nestEggVariable(salary, save, preRetireGrowthRates)
    savings = all_savings[num_of_years - 1]
    low = 0
    high = savings
    expenses = (high + low) / 2
    rest = postRetirement(savings, postRetireGrowthRates, expenses)[num_of_years - 1]
    while abs(rest) > epsilon:
        if rest > 0:
            low = expenses
        else:
            high = expenses
        expenses = (high + low) / 2
        all_rest = postRetirement(savings, postRetireGrowthRates, expenses)
        rest = all_rest[num_of_years - 1]
    return expenses

def testFindMaxExpenses():
    salary = 10000
    save = 10
    preRetireGrowthRates = [3, 4, 5, 0, 3]
    postRetireGrowthRates = [10, 5, 0, 5, 1]
    epsilon = .01
    expenses = findMaxExpenses(salary, save, preRetireGrowthRates,
                               postRetireGrowthRates, epsilon)
    print expenses
    # Output should have a value close to:
    # 1229.95548986

    # TODO: Add more test cases here.

testFindMaxExpenses()

###############
## Problem 1 ##
###############
from string import *


def count_sub_string_match(target, key):
    """Find all occurrences of a string in another"""
    counter = 0
    position = 0
    pointer = 0
    while(pointer < len(target)):
        position = find(target, key, pointer)
        if position != -1:
            counter += 1
            pointer = position + 1
        else:
            pointer += 1
    return counter


def count_sub_string_match_recursive(target, key):
    """Find all occurrences of a string in another with recursion"""
    counter = 0
    position = 0
    position = find(target, key)
    if position == -1:
        return 0
    else:
        position += 1
        return 1 + count_sub_string_match_recursive(target[position:], key)


def test_count_sub_string():
    """testing our functions"""
    target1 = 'atgacatgcacaagtatgcat'
    target2 = 'atgaatgcatggatgtaaatgcag'
    key10 = 'a'
    key11 = 'atg'
    key12 = 'atgc'
    key13 = 'atgca'
    # Testing iterative version
    print "Iterative function"
    print count_sub_string_match(target1, key10)
    print count_sub_string_match(target1, key11)
    print count_sub_string_match(target1, key12)
    print count_sub_string_match(target1, key13)
    print count_sub_string_match(target2, key10)
    print count_sub_string_match(target2, key11)
    print count_sub_string_match(target2, key12)
    print count_sub_string_match(target2, key13)
    # Testing recursive version
    print "Recursive function"
    print count_sub_string_match_recursive(target1, key10)
    print count_sub_string_match_recursive(target1, key11)
    print count_sub_string_match_recursive(target1, key12)
    print count_sub_string_match_recursive(target1, key13)
    print count_sub_string_match_recursive(target2, key10)
    print count_sub_string_match_recursive(target2, key11)
    print count_sub_string_match_recursive(target2, key12)
    print count_sub_string_match_recursive(target2, key13)

test_count_sub_string()

###############
## Problem 2 ##
###############
from string import *


def count_sub_string_match_exact(target, key):
    """Find all occurrences of a string in another"""
    position_list = []
    position = 0
    pointer = 0
    while(pointer < len(target)):
        position = find(target, key, pointer)
        if position != -1:
            position_list.append(position)
            pointer = position + 1
        else:
            pointer += 1
    return tuple(position_list)


def test_count_sub_string():
    """testing our functions"""
    target1 = 'atgacatgcacaagtatgcat'
    target2 = 'atgaatgcatggatgtaaatgcag'
    key10 = 'a'
    key11 = 'atg'
    key12 = 'atgc'
    key13 = 'atgca'
    # Testing iterative version
    print "Iterative function"
    print count_sub_string_match_exact(target1, key10)
    print count_sub_string_match_exact(target1, key11)
    print count_sub_string_match_exact(target1, key12)
    print count_sub_string_match_exact(target1, key13)
    print count_sub_string_match_exact(target2, key10)
    print count_sub_string_match_exact(target2, key11)
    print count_sub_string_match_exact(target2, key12)
    print count_sub_string_match_exact(target2, key13)

test_count_sub_string()


###############
## Problem 3 ##
###############
from string import *


def sub_string_match_exact(target, key):
    """Find all occurrences of a string in another"""
    position_list = []
    position = 0
    pointer = 0
    while(pointer < len(target)):
        position = find(target, key, pointer)
        if position != -1:
            position_list.append(position)
            pointer = position + 1
        else:
            pointer += 1
    return tuple(position_list)


def constrained_match_pair(first_match, second_match, length):
    """ Find intersection """
    intersection = []
    for n in first_match:
        for m in second_match:
            if n + length + 1 == m:
                intersection.append(n)
    return tuple(intersection)


def sub_string_match_one_sub(target, key):
    """search for all locations of key in target, with one substitution"""
    allAnswers = ()
    for miss in range(0, len(key)):
        # miss picks location for missing element
        # key1 and key2 are substrings to match
        key1 = key[:miss]
        key2 = key[miss+1:]
        print 'breaking key', key, 'into', key1, key2
        # match1 and match2 are tuples of locations of start of matches
        # for each substring in target
        match1 = sub_string_match_exact(target, key1)
        match2 = sub_string_match_exact(target, key2)
        # when we get here, we have two tuples of start points
        # need to filter pairs to decide which are correct
        filtered = constrained_match_pair(match1, match2, len(key1))
        allAnswers = allAnswers + filtered
        print 'match1', match1
        print 'match2', match2
        print 'possible matches for', key1, key2, 'start at', filtered
        print ''
    return allAnswers


def test_count_sub_string():
    """testing our functions"""
    target1 = 'atgacatgcacaagtatgcat'
    target2 = 'atgaatgcatggatgtaaatgcag'
    #key10 = 'a'
    key11 = 'atg'
    key12 = 'atgc'
    key13 = 'atgca'
    # Testing problem 3    
    # print sub_string_match_one_sub(target1, key10)
    print sub_string_match_one_sub(target1, key11)
    print sub_string_match_one_sub(target1, key12)
    print sub_string_match_one_sub(target1, key13)
    # print sub_string_match_one_sub(target2, key10)
    print sub_string_match_one_sub(target2, key11)
    print sub_string_match_one_sub(target2, key12)
    print sub_string_match_one_sub(target2, key13)

test_count_sub_string()


###############
## Problem 4 ##
###############
from string import *


def sub_string_match_exact(target, key):
    """Find all occurrences of a string in another"""
    position_list = ()
    position = 0
    pointer = 0
    while(pointer < len(target)):
        position = find(target, key, pointer)
        if position != -1:
            position_list += (position,)
            pointer = position + 1
        else:
            pointer += 1
    return position_list


def constrained_match_pair(first_match, second_match, length):
    """ Find intersection """
    intersection = ()
    for n in first_match:
        for m in second_match:
            if n + length + 1 == m:
                intersection += (n,)
    return intersection


def sub_string_match_one_exactly_one_sub(target, key):
    """search for all locations of key in target, with one substitution"""
    allAnswers = ()
    for miss in range(0, len(key)):
        print allAnswers
        # miss picks location for missing element
        # key1 and key2 are substrings to match
        key1 = key[:miss]
        key2 = key[miss+1:]
        print 'breaking key', key, 'into', key1, key2
        # match1 and match2 are tuples of locations of start of matches
        # for each substring in target
        match1 = sub_string_match_exact(target, key1)
        match2 = sub_string_match_exact(target, key2)
        # when we get here, we have two tuples of start points
        # need to filter pairs to decide which are correct
        filtered = constrained_match_pair(match1, match2, len(key1))
        for one_sub in filtered:
            if one_sub not in match2:
                allAnswers = allAnswers + (one_sub,)
        print 'match1', match1
        print 'match2', match2
        print 'possible matches for', key1, key2, 'start at', filtered
        print ''
    return allAnswers


def test_count_sub_string():
    """testing our functions"""
    target1 = 'atgacatgcacaagtatgcat'
    target2 = 'atgaatgcatggatgtaaatgcag'
    key10 = 'a'
    key11 = 'atg'
    key12 = 'atgc'
    key13 = 'atgca'
    # Testing problem 3    
    # print sub_string_match_one_exactly_one_sub(target1, key10)
    # print sub_string_match_one_exactly_one_sub(target1, key11)
    # print sub_string_match_one_exactly_one_sub(target1, key12)
    # print sub_string_match_one_exactly_one_sub(target1, key13)
    # print sub_string_match_one_exactly_one_sub(target2, key10)
    # print sub_string_match_one_exactly_one_sub(target2, key11)
    # print sub_string_match_one_exactly_one_sub(target2, key12)
    print sub_string_match_one_exactly_one_sub(target2, key13)

test_count_sub_string()

# Problem 3
a = 1
b = 1
c = 1
eq = 6 * a + 9 * b + 20 * c

n = 200

max_a = n / 6 + 1
max_b = n / 9 + 1
max_c = n / 20 + 1

n_tuple = ()
for n in range(1, n):
    for a in range(0, max_a):
        for b in range(0, max_b):
            for c in range(0, max_c):
                eq = 6 * a + 9 * b + 20 * c
                if eq == n:
                    print n
                    print 'We found it: a =', a, ',  b=', b, ', c=', c
                    is_unique = True
                    for tmp_n in n_tuple:
                        if tmp_n == n:
                            is_unique = False
                    if is_unique:
                        n_tuple += (n,)
print n_tuple

maximum = 0
for max_n in range(1, n):
    if max_n not in n_tuple:
        maximum = max_n
        
print 'Largest number of McNuggets that cannot be bought in exact quantity: ', maximum


# Problem 4
bestSoFar = 0           # variable that keeps track of largest number
packages = (3,14,17)     # variable that contains package sizes

max_n = 150
max_values = (max_n/packages[0] +1, max_n/packages[1] + 1, max_n/packages[2] + 1)

n_tuple = ()
for n in range(1, max_n):   # only search for solutions up to size 150
    for a in range(0, max_values[0]):
        for b in range(0, max_values[0]):
            for c in range(0, max_values[0]):
                eq = packages[0] * a + packages[1] * b + packages[2] * c
                if eq == n:
                    is_unique = True
                    for tmp_n in n_tuple:
                        if tmp_n == n:
                            is_unique = False
                    if is_unique:
                        n_tuple += (n,)

print n_tuple
maximum = 0
for max_n in range(1, n):
    if max_n not in n_tuple:
        bestSoFar = max_n
        
print 'Given package sizes', packages[0], ',', packages[1], 'and', packages[2], ' the largest number of McNuggets that cannot be bought in exact quantity is: ', bestSoFar

#Problem Set 1a ( Problem 1 )
step = 2
current_int = 1
prime_cnt = 0

while prime_cnt < 1000:
    is_prime = True
    test_int = 2
    while test_int**2 <= current_int:
        if current_int % test_int == 0:
            is_prime = False
            break
        else:
            is_prime = True
        test_int += 1
    if is_prime:
        prime_cnt += + 1
        print prime_cnt, ' ', current_int    
    current_int = current_int + step


#Problem Set 1b ( Problem 2 )
from math import *
step = 2
current_int = 1
stop_int = 1000
sum_log = 0

while current_int < stop_int:
    is_prime = True
    test_int = 2
    while test_int**2 <= current_int:
        if current_int % test_int == 0:
            is_prime = False
            break
        else:
            is_prime = True
        test_int += 1
    if is_prime:
        sum_log += log(current_int)
    current_int = current_int + step
    
print 'Sum of log: ', sum_log
print 'Value n: ', stop_int
print 'Raito: ', sum_log/current_intlast_name

# Problem Set 0
# Name Alex
# Time 2010-02-15 17:58

last_name  = raw_input('last name?\n**')
first_name = raw_input("first name?\n**")

print first_name + ' ' + last_name