Python: Problem Set 7

Problem 7 simulates the growth of a virus in a subject. Due to odds of multiplying or self healing, the virus population varies greatly up and down. In this simulation, the graph shows that this virus does not exceed 15% of host cells. This is due to the inverse relationship between the number of virus cells and their likelihood to reproduce: self.maxBirthProb * (1 – popDensity). This would not be so bad for the virus if it were not for the probability of virus cells to cleanse themselves (5%).

Problem 7b computationally shows the odds of rolling a Yahtzee, five six-sided die landing on the same number. Mathematically we know this is 6/7776, the number of desired outcomes over the number of possible outcomes. By simulating a number of trials (20) with increasing numbers of dice rolls, we can see that as our rolls exceed 100K and grow to 2^20, the mean of the resulting ratios becomes very close to the number we expect, 0.00077.

# Problem Set 7: Simulating the Spread of Disease and Virus Population Dynamics 
# Name: Casey
# Collaborators:
# Time: 2hr

import numpy
import random
import pylab

''' 
Begin helper code
'''

class NoChildException(Exception):
    """
    NoChildException is raised by the reproduce() method in the SimpleVirus
    and ResistantVirus classes to indicate that a virus particle does not
    reproduce. You can use NoChildException as is, you do not need to
    modify/add any code.
    """

'''
End helper code
'''

#
# PROBLEM 1
#
class SimpleVirus(object):

    """
    Representation of a simple virus (does not model drug effects/resistance).
    """
    def __init__(self, maxBirthProb, clearProb):

        """
        Initialize a SimpleVirus instance, saves all parameters as attributes
        of the instance.        
        maxBirthProb: Maximum reproduction probability (a float between 0-1)        
        clearProb: Maximum clearance probability (a float between 0-1).
        """
        # TODO
        assert isinstance(maxBirthProb, float) and 0 <= maxBirthProb <= 1
        assert isinstance(clearProb, float) and 0 <= maxBirthProb <= 1        
        self.maxBirthProb = maxBirthProb
        self.clearProb = clearProb

    def doesClear(self):

        """ Stochastically determines whether this virus particle is cleared from the
        patient's body at a time step. 
        returns: True with probability self.clearProb and otherwise returns
        False.
        """

        # TODO
        if random.random() < self.clearProb:
            return True
        else:
            return False
    
    def reproduce(self, popDensity):

        """
        Stochastically determines whether this virus particle reproduces at a
        time step. Called by the update() method in the SimplePatient and
        Patient classes. The virus particle reproduces with probability
        self.maxBirthProb * (1 - popDensity).
        
        If this virus particle reproduces, then reproduce() creates and returns
        the instance of the offspring SimpleVirus (which has the same
        maxBirthProb and clearProb values as its parent).         

        popDensity: the population density (a float), defined as the current
        virus population divided by the maximum population.         
        
        returns: a new instance of the SimpleVirus class representing the
        offspring of this virus particle. The child should have the same
        maxBirthProb and clearProb values as this virus. Raises a
        NoChildException if this virus particle does not reproduce.               
        """

        # TODO
        if random.random() < self.maxBirthProb * (1 - popDensity):
            return SimpleVirus(self.maxBirthProb, popDensity)
        else:
            NoChildException()   



class SimplePatient(object):

    """
    Representation of a simplified patient. The patient does not take any drugs
    and his/her virus populations have no drug resistance.
    """    

    def __init__(self, viruses, maxPop):

        """

        Initialization function, saves the viruses and maxPop parameters as
        attributes.

        viruses: the list representing the virus population (a list of
        SimpleVirus instances)

        maxPop: the  maximum virus population for this patient (an integer)
        """

        # TODO
        assert isinstance(viruses, list)
        assert isinstance(maxPop, int)
        self.viruses = viruses
        self.maxPop = maxPop

    def getTotalPop(self):

        """
        Gets the current total virus population. 
        returns: The total virus population (an integer)
        """

        # TODO
        return len(self.viruses)


    def update(self):

        """
        Update the state of the virus population in this patient for a single
        time step. update() should execute the following steps in this order:
        
        - Determine whether each virus particle survives and updates the list
        of virus particles accordingly.   
        - The current population density is calculated. This population density
          value is used until the next call to update() 
        - Determine whether each virus particle should reproduce and add
          offspring virus particles to the list of viruses in this patient.                    

        returns: The total virus population at the end of the update (an
        integer)
        """

        # TODO
        # need: a list of virus particles
        # already exists as var viruses
        # loop and survive or clear
        survive_list = []
        for i in range(0, len(self.viruses)):
            if not self.viruses[i].doesClear():
                survive_list.append(self.viruses[i])
        self.viruses = survive_list
        # update the pop density
        now_density  =  self.getTotalPop() / float(self.maxPop)
        # for each virus particle, reproduce or not
        new_viruses = []
        for i in range(0, len(self.viruses)):
            virus = self.viruses[i]
            a = virus.reproduce(now_density)
            if a:
                new_viruses.append(a)
        self.viruses = self.viruses + new_viruses
        # return total virus pop as an int


#
# PROBLEM 2
#
def simulationWithoutDrug():

    """
    Run the simulation and plot the graph for problem 2 (no drugs are used,
    viruses do not have any drug resistance).    
    Instantiates a patient, runs a simulation for 300 timesteps, and plots the
    total virus population as a function of time.    
    """

    # TODO
    a = SimpleVirus(0.1, 0.05)
    disease = [a]*100
    patient = SimplePatient(disease, 1000)
    pop_over_time = []
    for i in range(0, 300):
        patient.update()
        pop_over_time.append(patient.getTotalPop())
    pylab.plot(pop_over_time)
    pylab.ylabel("Virus cells")
    pylab.xlabel("Time")
    pylab.title("Virus population in patient")
    pylab.show()
simulationWithoutDrug()

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

# Problem Set 7: Simulating the Spread of Disease and Virus Population Dynamics

# Name: Casey

# Collaborators:

# Time: 2hr

import numpy

import random

import pylab

'''

Begin helper code

'''

class NoChildException(Exception):

"""

NoChildException is raised by the reproduce() method in the SimpleVirus

and ResistantVirus classes to indicate that a virus particle does not

reproduce. You can use NoChildException as is, you do not need to

modify/add any code.

"""

'''

End helper code

'''

# PROBLEM 1

class SimpleVirus(object):

"""

Representation of a simple virus (does not model drug effects/resistance).

"""

def __init__(self, maxBirthProb, clearProb):

"""

Initialize a SimpleVirus instance, saves all parameters as attributes

of the instance.

maxBirthProb: Maximum reproduction probability (a float between 0-1)

clearProb: Maximum clearance probability (a float between 0-1).

"""

# TODO

assert isinstance(maxBirthProb, float) and 0 <= maxBirthProb <= 1

assert isinstance(clearProb, float) and 0 <= maxBirthProb <= 1

self.maxBirthProb = maxBirthProb

self.clearProb = clearProb

def doesClear(self):

""" Stochastically determines whether this virus particle is cleared from the

patient's body at a time step.

returns: True with probability self.clearProb and otherwise returns

False.

"""

# TODO

if random.random() < self.clearProb:

return True

else:

return False

def reproduce(self, popDensity):

"""

Stochastically determines whether this virus particle reproduces at a

time step. Called by the update() method in the SimplePatient and

Patient classes. The virus particle reproduces with probability

self.maxBirthProb * (1 - popDensity).

If this virus particle reproduces, then reproduce() creates and returns

the instance of the offspring SimpleVirus (which has the same

maxBirthProb and clearProb values as its parent).

popDensity: the population density (a float), defined as the current

virus population divided by the maximum population.

returns: a new instance of the SimpleVirus class representing the

offspring of this virus particle. The child should have the same

maxBirthProb and clearProb values as this virus. Raises a

NoChildException if this virus particle does not reproduce.

"""

# TODO

if random.random() < self.maxBirthProb * (1 - popDensity):

return SimpleVirus(self.maxBirthProb, popDensity)

else:

NoChildException()

class SimplePatient(object):

"""

Representation of a simplified patient. The patient does not take any drugs

and his/her virus populations have no drug resistance.

"""

def __init__(self, viruses, maxPop):

"""

Initialization function, saves the viruses and maxPop parameters as

attributes.

viruses: the list representing the virus population (a list of

SimpleVirus instances)

maxPop: the maximum virus population for this patient (an integer)

"""

# TODO

assert isinstance(viruses, list)

assert isinstance(maxPop, int)

self.viruses = viruses

self.maxPop = maxPop

def getTotalPop(self):

"""

Gets the current total virus population.

returns: The total virus population (an integer)

"""

# TODO

return len(self.viruses)

def update(self):

"""

Update the state of the virus population in this patient for a single

time step. update() should execute the following steps in this order:

- Determine whether each virus particle survives and updates the list

of virus particles accordingly.

- The current population density is calculated. This population density

value is used until the next call to update()

- Determine whether each virus particle should reproduce and add

offspring virus particles to the list of viruses in this patient.

returns: The total virus population at the end of the update (an

integer)

"""

# TODO

# need: a list of virus particles

# already exists as var viruses

# loop and survive or clear

survive_list = []

for i in range(0, len(self.viruses)):

if not self.viruses[i].doesClear():

survive_list.append(self.viruses[i])

self.viruses = survive_list

# update the pop density

now_density = self.getTotalPop() / float(self.maxPop)

# for each virus particle, reproduce or not

new_viruses = []

for i in range(0, len(self.viruses)):

virus = self.viruses[i]

a = virus.reproduce(now_density)

if a:

new_viruses.append(a)

self.viruses = self.viruses + new_viruses

# return total virus pop as an int

# PROBLEM 2

def simulationWithoutDrug():

"""

Run the simulation and plot the graph for problem 2 (no drugs are used,

viruses do not have any drug resistance).

Instantiates a patient, runs a simulation for 300 timesteps, and plots the

total virus population as a function of time.

"""

# TODO

a = SimpleVirus(0.1, 0.05)

disease = [a]*100

patient = SimplePatient(disease, 1000)

pop_over_time = []

for i in range(0, 300):

patient.update()

pop_over_time.append(patient.getTotalPop())

pylab.plot(pop_over_time)

pylab.ylabel("Virus cells")

pylab.xlabel("Time")

pylab.title("Virus population in patient")

pylab.show()

simulationWithoutDrug()

# Monte Carlo Simulation Yahtzee!
# Casey
# 3hr

import pylab
import random
import time
'''
def stdDev(X):
    mean = sum(X)/float(len(X))
    tot = 0.0
    for x in X:
        tot += (x - mean)**2
    return (tot/len(X))**0.5
'''
def roll(num_rolls):
    yahtzee = 0
    for i in range(0, num_rolls):
        result = []
        for j in range(0, 5):
            result.append(random.choice([1,2,3,4,5,6]))
        if len(set(result)) == 1:
            yahtzee += 1
    not_yahtzee = num_rolls - yahtzee
    return (yahtzee/float(not_yahtzee))

# for some number exponent, that becomes the number of rolls
# the number of trials to turn into mean stays the same ie. 20
def yahtzee(minExp, maxExp, numTrials):
    mean_ratios = []
    xAxis = []
    for exp in range(minExp, maxExp + 1):
        xAxis.append(2**exp)
    for num_rolls in xAxis:
        ratios = []
        for trial in range(numTrials):
            ratios.append(roll(num_rolls))        
        mean_ratios.append(sum(ratios)/numTrials)
        print num_rolls
    pylab.plot(xAxis, mean_ratios, 'bo')
    pylab.title("Mean ratio of rolling Yahtzee given increasing rolls")
    pylab.xlabel("Number of rolls")
    pylab.ylabel("Yahtzees over all other")
    pylab.semilogx()
    pylab.show()
    
yahtzee(10, 20, 20)

# Monte Carlo Simulation Yahtzee!

# Casey

# 3hr

import pylab

import random

import time

'''

def stdDev(X):

mean = sum(X)/float(len(X))

tot = 0.0

for x in X:

tot += (x - mean)**2

return (tot/len(X))**0.5

'''

def roll(num_rolls):

yahtzee = 0

for i in range(0, num_rolls):

result = []

for j in range(0, 5):

result.append(random.choice([1,2,3,4,5,6]))

if len(set(result)) == 1:

yahtzee += 1

not_yahtzee = num_rolls - yahtzee

return (yahtzee/float(not_yahtzee))

# for some number exponent, that becomes the number of rolls

# the number of trials to turn into mean stays the same ie. 20

def yahtzee(minExp, maxExp, numTrials):

mean_ratios = []

xAxis = []

for exp in range(minExp, maxExp + 1):

xAxis.append(2**exp)

for num_rolls in xAxis:

ratios = []

for trial in range(numTrials):

ratios.append(roll(num_rolls))

mean_ratios.append(sum(ratios)/numTrials)

print num_rolls

pylab.plot(xAxis, mean_ratios, 'bo')

pylab.title("Mean ratio of rolling Yahtzee given increasing rolls")

pylab.xlabel("Number of rolls")

pylab.ylabel("Yahtzees over all other")

pylab.semilogx()

pylab.show()

yahtzee(10, 20, 20)

Python: Problem Set 6

Problem set 6 involves modeling robots that clean rooms. We have room object with tiles to be cleaned, robots which “move” and mark tiles as cleaned. All robots begin at random positions in the room, pointed in a random direction. Standard robots move in the same direction until reaching a wall, when they pick a new direction. Random-walking-robots pick a new direction on each step. This looks like spinning when visualized with Tkinter. The visualization module is provided as a helper file with the lesson, not made by me. This came in handy for figuring out that I was not flooring() the robots position either on passing or getting the variable for cleaning. It was clear once I could see that robots would clean if they were moving straight along one axis, but not if they were in a decimal position “between” the tiles. They could clean the grout, but not the tile

The second part to the problem is to measure how long it takes both types of robots to clean a room. Graphing is done in Pylab. The random walking robot takes more than twice the time to clean 80% of the tiles in a square room.

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Problem Set 6: Simulating robots
# Name: Casey
# Collaborators: None
# Time: 6hr

import math
import random

import ps6_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).
        """
        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: float 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

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
        """
        # what is the pythonic way to check for an int
        assert type(width) == int and type(height) == int
        assert height > 0 and width > 0
        self.h = height
        self.w = width
        self.tiles = {}
        # I assign originally assigned w*h along wrong axes
        for i in range(0, width):
            for j in range(0, height):
                self.tiles[(i, j)] = False
    
    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
        """
        # if robots move in floats, changes indexes to floats
        self.tiles[(math.floor(pos.getX()), math.floor(pos.getY()))] = True

    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 self.tiles[(m,n)]
    
    def getNumTiles(self):
        """
        Return the total number of tiles in the room.

        returns: an integer
        """
        return self.h * self.w

    def getNumCleanedTiles(self):
        """
        Return the total number of clean tiles in the room.

        returns: an integer
        """
        count = 0
        for i in self.tiles:
            if self.tiles[i] == True:
                count += 1
        return count

    def getRandomPosition(self):
        """
        Return a random position inside the room.

        returns: a Position object.
        """
        x = random.randint(0, self.w-1)
        y = random.randint(0, self.h-1)
        a = Position(x, y)
        return a

    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 self.tiles.has_key((math.floor(pos.getX()),math.floor(pos.getY())))


class Robot(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 Robot 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 and a random position in the
        room. The robot cleans the tile it is on.

        room:  a RectangularRoom object.
        speed: a float (speed > 0)
        """
        # type check room
        assert isinstance(room, RectangularRoom)
        # fact check speed
        assert type(speed) == float and speed > 0
        self.room = room
        self.speed = speed
        self.position = room.getRandomPosition()
        self.direction = random.randint(0, 360)

    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.
        """
        # where does the direction assignment go?
        # if this returns the direction, where is it stored?
        # ^ read the init description "initially has a random direction"
        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

    def updatePositionAndClean(self):
        """
        Simulate the raise passage of a single time-step.

        Move the robot to a new position and mark the tile it is on as having
        been cleaned.
        """
        # plot a straight line according to direction
        # move 1 step along line according to speed
        # calculate new position, floor rounded
        # going to need Polar coordinates and Cartesian coordinates
        # x = dist*cos*angle
        # y = dist*sin*angle
        # Or just need to read methods below the Position object
        # Position.getNewPosition(self, angle, speed)
        self.setRobotPosition(self.position.getNewPosition(self.direction, self.speed))
        self.room.cleanTileAtPosition(self.position.getX(), self.position.getY())


# === Problem 2
class StandardRobot(Robot):
    """
    A StandardRobot is a Robot with the standard movement strategy.

    At each time-step, a StandardRobot 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.
        """
        # calculate new position, given cur position, angle and speed
        spot = self.position.getNewPosition(self.direction, self.speed)
        while not self.room.isPositionInRoom(spot):
            self.setRobotDirection(random.randint(0,360))
            spot = self.position.getNewPosition(self.direction, self.speed)

        self.setRobotPosition(spot)
        self.room.cleanTileAtPosition(self.getRobotPosition())

# === Problem 3

def runSimulation(num_robots, speed, width, height, min_coverage, num_trials,
                  robot_type):
    """
    Runs NUM_TRIALS trials of the simulation and returns the mean number of
    time-steps needed to clean the fraction MIN_COVERAGE of the room.

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

    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)
    """
    # don't think this is very python way to validate input
    assert type(num_robots) == int and num_robots > 0
    assert type(speed) == float and speed > 0
    assert type(width) == int and type(height) == int and width > 0 and height > 0
    assert type(min_coverage) == float and 0 <= min_coverage <= 1.0
    assert type(num_trials) == int and num_trials > 0
#    assert isinstance(robot_type, Robot) #or isinstance(robot_type, RandomWalkRobot)
    counter = 0
    for i in range(1,num_trials):
        #anim = ps6_visualize.RobotVisualization(num_robots, width, height, .5)
        # make a new room for each trial
        coverage = 0
        room = RectangularRoom(width, height)
        # add robots to a list
        robots = []
        for j in range(0, num_robots):
            rob = robot_type(room, speed)
            robots.append(rob)
            
        while coverage < min_coverage:
            #anim.update(room, robots)
            # tell each robot to in list to clean
            for i in range(0, len(robots)):
                robots[i].updatePositionAndClean()
            # update time steps and coverage so we eventually exit loop
            counter += 1
            # must float one, else keep getting 0
            coverage = float(room.getNumCleanedTiles()) / room.getNumTiles()
        #anim.done()
    return counter / num_trials    
#uncomment to run    
# print runSimulation(10, 1.0, 15, 20, 0.8, 30, StandardRobot)

# === Problem 4
#
# 1) How long does it take to clean 80% of a 20x20 room with each of 1-10 robots?
#
# 2) How long does it take two robots to clean 80% of rooms with dimensions 
#	 20x20, 25x16, 40x10, 50x8, 80x5, and 100x4?

def showPlot1():
    """
    Produces a plot showing dependence of cleaning time on number of robots.
    How long does it take to clean 80% of a 20×20 room with each of 1-10 robots?
    """ 
    ydata = []
    # run n trials and store avg in list for each number of robots 
    # runSimulation(num_robots, speed, width, height, min_coverage, num_trials, robot_type):
    for i in range(1,11):
        avg = runSimulation(i, 1.0, 20, 20, 0.8, 30, StandardRobot)
        ydata.append(avg)

    pylab.plot(ydata)
    pylab.title('Average time to clean 20x20 room with 1-10 robots')
    pylab.xlabel('Robots')
    pylab.ylabel('Time')
    pylab.show()
#uncomment to run    
#showPlot1()
def showPlot2():
    """
    Produces a plot showing dependence of cleaning time on room shape.
    How long does it take two robots to clean 80% of rooms with dimensions 
    20×20, 25×16, 40×10, 50×8, 80×5, and 100×4?    
    """
    ydata = []
    shapes = [(20,20), (25,16), (40,10), (50,8), (80,5), (100,4)]
    for i,j in shapes:
        avg = runSimulation(2, 1.0, i, j, 0.8, 50, StandardRobot)
        ydata.append(avg)
    
    pylab.plot(ydata)
    pylab.title('Average time for 2 robots to clean various rooms')
    # use xticks or the x-axis will default to a 1:N increment
    pylab.xticks(pylab.arange(len(shapes)), shapes)
    pylab.xlabel('Room Dimensions')
    pylab.ylabel('Time')
    pylab.show()
#uncomment to run
#showPlot2()

# === 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):
        """
        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.
        """
        # calculate new position, given cur position, angle and speed
        spot = self.position.getNewPosition(self.direction, self.speed)
        while not self.room.isPositionInRoom(spot):
            self.setRobotDirection(random.randint(0,360))
            spot = self.position.getNewPosition(self.direction, self.speed)

        self.setRobotPosition(spot)
        self.room.cleanTileAtPosition(self.getRobotPosition())
        # pick a new direction before next step
        self.setRobotDirection(random.randint(0, 360))

#print runSimulation(10, 1.0, 20, 20, 0.7, 10, RandomWalkRobot)

# === Problem 6

# For the parameters tested below (cleaning 80% of a 20x20 square room),
# RandomWalkRobots take approximately twice as long to clean the same room as
# StandardRobots do.
def showPlot3():
    """
    Produces a plot comparing the two robot strategies.
    """
    standard = []
    random = []
    # run n trials and store avg in list for each number of robots 
    # runSimulation(num_robots, speed, width, height, min_coverage, num_trials, robot_type):
    for i in range(0,5):
        avg = runSimulation(5, 1.0, 20, 20, 0.8, 30, StandardRobot)
        standard.append(avg)
        avg = runSimulation(5, 1.0, 20, 20, 0.8, 30, RandomWalkRobot)
        random.append(avg)

    pylab.plot(standard, 'k', label='turns on collision')
    pylab.plot(random, 'b', label='turns constantly')
    pylab.legend(loc='upper left')
    pylab.title('Average time to clean 20x20 room with different robots')
    pylab.xticks(pylab.arange(5))
    pylab.xlabel('Five Trials')
    pylab.ylabel('Time')
    pylab.show()
#showPlot3()

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

#!/usr/bin/env python

# -*- coding: utf-8 -*-

# Problem Set 6: Simulating robots

# Name: Casey

# Collaborators: None

# Time: 6hr

import math

import random

import ps6_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).

"""

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: float 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

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

"""

# what is the pythonic way to check for an int

assert type(width) == int and type(height) == int

assert height > 0 and width > 0

self.h = height

self.w = width

self.tiles = {}

# I assign originally assigned w*h along wrong axes

for i in range(0, width):

for j in range(0, height):

self.tiles[(i, j)] = False

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

"""

# if robots move in floats, changes indexes to floats

self.tiles[(math.floor(pos.getX()), math.floor(pos.getY()))] = True

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 self.tiles[(m,n)]

def getNumTiles(self):

"""

Return the total number of tiles in the room.

returns: an integer

"""

return self.h * self.w

def getNumCleanedTiles(self):

"""

Return the total number of clean tiles in the room.

returns: an integer

"""

count = 0

for i in self.tiles:

if self.tiles[i] == True:

count += 1

return count

def getRandomPosition(self):

"""

Return a random position inside the room.

returns: a Position object.

"""

x = random.randint(0, self.w-1)

y = random.randint(0, self.h-1)

a = Position(x, y)

return a

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 self.tiles.has_key((math.floor(pos.getX()),math.floor(pos.getY())))

class Robot(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 Robot 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 and a random position in the

room. The robot cleans the tile it is on.

room: a RectangularRoom object.

speed: a float (speed > 0)

"""

# type check room

assert isinstance(room, RectangularRoom)

# fact check speed

assert type(speed) == float and speed > 0

self.room = room

self.speed = speed

self.position = room.getRandomPosition()

self.direction = random.randint(0, 360)

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.

"""

# where does the direction assignment go?

# if this returns the direction, where is it stored?

# ^ read the init description "initially has a random direction"

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

def updatePositionAndClean(self):

"""

Simulate the raise passage of a single time-step.

Move the robot to a new position and mark the tile it is on as having

been cleaned.

"""

# plot a straight line according to direction

# move 1 step along line according to speed

# calculate new position, floor rounded

# going to need Polar coordinates and Cartesian coordinates

# x = dist*cos*angle

# y = dist*sin*angle

# Or just need to read methods below the Position object

# Position.getNewPosition(self, angle, speed)

self.setRobotPosition(self.position.getNewPosition(self.direction, self.speed))

self.room.cleanTileAtPosition(self.position.getX(), self.position.getY())

# === Problem 2

class StandardRobot(Robot):

"""

A StandardRobot is a Robot with the standard movement strategy.

At each time-step, a StandardRobot 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.

"""

# calculate new position, given cur position, angle and speed

spot = self.position.getNewPosition(self.direction, self.speed)

while not self.room.isPositionInRoom(spot):

self.setRobotDirection(random.randint(0,360))

spot = self.position.getNewPosition(self.direction, self.speed)

self.setRobotPosition(spot)

self.room.cleanTileAtPosition(self.getRobotPosition())

# === Problem 3

def runSimulation(num_robots, speed, width, height, min_coverage, num_trials,

robot_type):

"""

Runs NUM_TRIALS trials of the simulation and returns the mean number of

time-steps needed to clean the fraction MIN_COVERAGE of the room.

The simulation is run with NUM_ROBOTS robots of type ROBOT_TYPE, each with

speed SPEED, in a room of dimensions WIDTH x HEIGHT.

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)

"""

# don't think this is very python way to validate input

assert type(num_robots) == int and num_robots > 0

assert type(speed) == float and speed > 0

assert type(width) == int and type(height) == int and width > 0 and height > 0

assert type(min_coverage) == float and 0 <= min_coverage <= 1.0

assert type(num_trials) == int and num_trials > 0

# assert isinstance(robot_type, Robot) #or isinstance(robot_type, RandomWalkRobot)

counter = 0

for i in range(1,num_trials):

#anim = ps6_visualize.RobotVisualization(num_robots, width, height, .5)

# make a new room for each trial

coverage = 0

room = RectangularRoom(width, height)

# add robots to a list

robots = []

for j in range(0, num_robots):

rob = robot_type(room, speed)

robots.append(rob)

while coverage < min_coverage:

#anim.update(room, robots)

# tell each robot to in list to clean

for i in range(0, len(robots)):

robots[i].updatePositionAndClean()

# update time steps and coverage so we eventually exit loop

counter += 1

# must float one, else keep getting 0

coverage = float(room.getNumCleanedTiles()) / room.getNumTiles()

#anim.done()

return counter / num_trials

#uncomment to run

# print runSimulation(10, 1.0, 15, 20, 0.8, 30, StandardRobot)

# === Problem 4

# 1) How long does it take to clean 80% of a 20x20 room with each of 1-10 robots?

# 2) How long does it take two robots to clean 80% of rooms with dimensions

# 20x20, 25x16, 40x10, 50x8, 80x5, and 100x4?

def showPlot1():

"""

Produces a plot showing dependence of cleaning time on number of robots.

How long does it take to clean 80% of a 20×20 room with each of 1-10 robots?

"""

ydata = []

# run n trials and store avg in list for each number of robots

# runSimulation(num_robots, speed, width, height, min_coverage, num_trials, robot_type):

for i in range(1,11):

avg = runSimulation(i, 1.0, 20, 20, 0.8, 30, StandardRobot)

ydata.append(avg)

pylab.plot(ydata)

pylab.title('Average time to clean 20x20 room with 1-10 robots')

pylab.xlabel('Robots')

pylab.ylabel('Time')

pylab.show()

#uncomment to run

#showPlot1()

def showPlot2():

"""

Produces a plot showing dependence of cleaning time on room shape.

How long does it take two robots to clean 80% of rooms with dimensions

20×20, 25×16, 40×10, 50×8, 80×5, and 100×4?

"""

ydata = []

shapes = [(20,20), (25,16), (40,10), (50,8), (80,5), (100,4)]

for i,j in shapes:

avg = runSimulation(2, 1.0, i, j, 0.8, 50, StandardRobot)

ydata.append(avg)

pylab.plot(ydata)

pylab.title('Average time for 2 robots to clean various rooms')

# use xticks or the x-axis will default to a 1:N increment

pylab.xticks(pylab.arange(len(shapes)), shapes)

pylab.xlabel('Room Dimensions')

pylab.ylabel('Time')

pylab.show()

#uncomment to run

#showPlot2()

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

"""

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.

"""

# calculate new position, given cur position, angle and speed

spot = self.position.getNewPosition(self.direction, self.speed)

while not self.room.isPositionInRoom(spot):

self.setRobotDirection(random.randint(0,360))

spot = self.position.getNewPosition(self.direction, self.speed)

self.setRobotPosition(spot)

self.room.cleanTileAtPosition(self.getRobotPosition())

# pick a new direction before next step

self.setRobotDirection(random.randint(0, 360))

#print runSimulation(10, 1.0, 20, 20, 0.7, 10, RandomWalkRobot)

# === Problem 6

# For the parameters tested below (cleaning 80% of a 20x20 square room),

# RandomWalkRobots take approximately twice as long to clean the same room as

# StandardRobots do.

def showPlot3():

"""

Produces a plot comparing the two robot strategies.

"""

standard = []

random = []

# run n trials and store avg in list for each number of robots

# runSimulation(num_robots, speed, width, height, min_coverage, num_trials, robot_type):

for i in range(0,5):

avg = runSimulation(5, 1.0, 20, 20, 0.8, 30, StandardRobot)

standard.append(avg)

avg = runSimulation(5, 1.0, 20, 20, 0.8, 30, RandomWalkRobot)

random.append(avg)

pylab.plot(standard, 'k', label='turns on collision')

pylab.plot(random, 'b', label='turns constantly')

pylab.legend(loc='upper left')

pylab.title('Average time to clean 20x20 room with different robots')

pylab.xticks(pylab.arange(5))

pylab.xlabel('Five Trials')

pylab.ylabel('Time')

pylab.show()

#showPlot3()

Python: Problem Set 5

Problem Set 5 makes use of Google’s RSS feed to search for keywords and return stories matching those words. The exercise I believe is the first to begin using classes and inheritance. In order to avoid code duplication, a generic WordTrigger is created to look for for a “word” inside a “text.” Then, we create subclasses of triggers to look at the title, summary, or subject fields. Later on, it creates AND/OR functions to make more useful searches.

My functions passed the ps6_test.py, but when I try using provided main_thread’s implementation that pulls RSS stories from google (stories = process(“http://news.google.com/?output=rss”)), only the title trigger seemed to work. I suspect the provided feedparser.py may not be up to date with the RSS feed. On the other hand, feedparser.py looks like it is mapping the description element to “summary”, so the error is not obvious to me.

if element == 'description':
element = 'summary'

# 6.00 Problem Set 5
# RSS Feed Filter

import feedparser
import string
import time
from project_util import translate_html
from news_gui import Popup

#-----------------------------------------------------------------------
#
# Problem Set 5

#======================
# Code for retrieving and parsing
# Google and Yahoo News feeds
# Do not change this code
#======================

def process(url):
    """
    Fetches news items from the rss url and parses them.
    Returns a list of NewsStory-s.
    """
    feed = feedparser.parse(url)
    entries = feed.entries
    ret = []
    for entry in entries:
        guid = entry.guid
        title = translate_html(entry.title)
        link = entry.link
        summary = translate_html(entry.summary)
        try:
            subject = translate_html(entry.tags[0]['term'])
        except AttributeError:
            subject = ""
        newsStory = NewsStory(guid, title, subject, summary, link)
        ret.append(newsStory)
    return ret

#======================
# Part 1
# Data structure design
#======================

# Problem 1

# TODO: NewsStory
class NewsStory():
    def __init__(self, guid, title, subject, summary, link):
        self.guid = guid
        self.title = title
        self.subject = subject
        self.summary = summary
        self.link = link
    def get_guid(self):
        return self.guid
    def get_title(self):
        return self.title
    def get_subject(self):
        return self.subject
    def get_summary(self):
        return self.summary
    def get_link(self):
        return self.link

#======================
# Part 2
# Triggers
#======================

class Trigger(object):
    def evaluate(self, story):
        """
        Returns True if an alert should be generated
        for the given news item, or False otherwise.
        """
        raise NotImplementedError
"""
It must implement the evaluate method that takes a news item (NewsStory object)
as an input and returns True if an alert should be generated for that item. We will not use the
implementation of the Trigger class
"""

# Whole Word Triggers
# Problems 2-5

# TODO: WordTrigger
# It returns True if the whole word word is present
class WordTrigger(Trigger):
    def is_word_in(self, word, text):
        text = text.replace("'", " ")
        alphabet = list('abcdefghijkl mnopqrstuvwxyz')
        text = "".join(letter for letter in text if letter in alphabet)
        text = text.split()
        for a in text:
            if word == a:
                return True
            else:
                continue
        return False

# TODO: TitleTrigger
# it should treat Intel and intel as being equal
class TitleTrigger(WordTrigger):
    def __init__(self, word):
        self.word = word
        
    def evaluate(self, story):
        return self.is_word_in(self.word.lower(), story.title.lower())
        
# TODO: SubjectTrigger
class SubjectTrigger(WordTrigger):
    def __init__(self, word):
        self.word = word
        
    def evaluate(self, story):
        return self.is_word_in(self.word.lower(), story.subject.lower())

# TODO: SummaryTrigger
class SummaryTrigger(WordTrigger):
    def __init__(self, word):
        self.word = word
        
    def evaluate(self, story):
        return self.is_word_in(self.word.lower(), story.summary.lower())

# Composite Triggers
# Problems 6-8

# TODO: NotTrigger
# given a trigger T (any trigger) and news item x 
# Not trigger returns the equivalent of not T.evaluate(x)
# n = NotTrigger(self.tt)
# b = NewsStory("guid", "title", "subj", "summary", "link")
# self.assertFalse(n.evaluate(b), "Expected False. Was not was False!")

class NotTrigger(Trigger):
    def __init__(self, otherTrigger):
        self.otherTrigger = otherTrigger
        
    def evaluate(self, story):
        return not self.otherTrigger.evaluate(story)
        # why is self.otherTrigger a Trigger and otherTrigger is a NewsStory?
        # Is a NewsStory part of a Trigger? Where does it reside?
        
                
# TODO: AndTrigger
class AndTrigger(Trigger):
    def __init__(self, T1, T2):
        self.T1 = T1
        self.T2 = T2
        
    def evaluate(self, story):
        return self.T1.evaluate(story) and self.T2.evaluate(story)

# TODO: OrTrigger
class OrTrigger(Trigger):
    def __init__(self, T1, T2):
        self.T1 = T1
        self.T2 = T2
        
    def evaluate(self, story):
        return self.T1.evaluate(story) or self.T2.evaluate(story)

# Phrase Trigger
# Question 9

# TODO: PhraseTrigger
# constructor takes the phrase as arg
# method takes the story as arg
class PhraseTrigger(Trigger):
    def __init__(self, phrase):
        self.phrase = phrase
        
    def evaluate(self, story):
        title = self.phrase in story.title
        subject = self.phrase in story.subject
        summary = self.phrase in story.summary
        return title or subject or summary


#======================
# Part 3
# Filtering
#======================

def filter_stories(stories, triggerlist):
    """
    Takes in a list of NewsStory-s.
    Returns only those stories for whom
    a trigger in triggerlist fires.
    """
    # TODO: Problem 10
    # This is a placeholder (we're just returning all the stories, with no filtering) 
    # return stories
    matches = []
    for trigs in triggerlist:
        for stors in stories:
            if trigs.evaluate(stors):
                matches.append(stors)
    return matches

#======================
# Part 4
# User-Specified Triggers
#======================

def readTriggerConfig(filename):
    """
    Returns a list of trigger objects
    that correspond to the rules set
    in the file filename
    """
    # Here's some code that we give you
    # to read in the file and eliminate
    # blank lines and comments
    triggerfile = open(filename, "r")
    all = [ line.rstrip() for line in triggerfile.readlines() ]
    lines = []
    for line in all:
        if len(line) == 0 or line[0] == '#':
            continue
        lines.append(line)

    # TODO: Problem 11
    # 'lines' has a list of lines you need to parse
    # Build a set of triggers from it and
    # return the appropriate ones
    # print lines
    # ['t1 TITLE nfl', 't2 SUBJECT Japan', 't3 PHRASE Supreme Court', 't4 AND t2 t3', 'ADD t1 t4']
    allTriggers ={
        "TITLE": TitleTrigger,
        "SUBJECT": SubjectTrigger,
        "SUMMARY": SummaryTrigger,
        "NOT": NotTrigger,
        "AND": AndTrigger,
        "OR": OrTrigger,
        "PHRASE": PhraseTrigger
    }
    
    triggers = {}
    results = []
    for line in lines:
        line = line.split()
        if line[0] == "ADD":
            for i in line[1:]:
                results.append(triggers[i])
            return results
        name = line[0]
        trigger = line[1]
        if trigger == "AND" or trigger == "OR":
            arg1 = triggers[line[2]]
            arg2 = triggers[line[3]]
            triggers[name] = allTriggers[trigger](arg1, arg2) #pass the objects, not the string
        else:
            arg = "".join(line[2:])
            triggers[name] = allTriggers[trigger](arg)
    
import thread

def main_thread(p):
    # A sample trigger list - you'll replace
    # this with something more configurable in Problem 11
    t1 = SubjectTrigger("Obama")
    t2 = SummaryTrigger("MIT")
    t3 = PhraseTrigger("Supreme Court")
    t4 = OrTrigger(t2, t3)
    triggerlist = [t1, t4]
    
    # TODO: Problem 11
    # After implementing readTriggerConfig, uncomment this line 
    triggerlist = readTriggerConfig("triggers.txt")

    guidShown = []
    
    while True:
        print "Polling..."

        # Get stories from Google's Top Stories RSS news feed
        stories = process("http://news.google.com/?output=rss")
        # Get stories from Yahoo's Top Stories RSS news feed
        stories.extend(process("http://rss.news.yahoo.com/rss/topstories"))

        # Only select stories we're interested in
        stories = filter_stories(stories, triggerlist)
    
        # Don't print a story if we have already printed it before
        newstories = []
        for story in stories:
            if story.get_guid() not in guidShown:
                newstories.append(story)
        
        for story in newstories:
            guidShown.append(story.get_guid())
            p.newWindow(story)

        print "Sleeping..."
        time.sleep(SLEEPTIME)

SLEEPTIME = 60 #seconds -- how often we poll
if __name__ == '__main__':
    p = Popup()
    thread.start_new_thread(main_thread, (p,))
    p.start()

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

if element == 'description':

element = 'summary'

# 6.00 Problem Set 5

# RSS Feed Filter

import feedparser

import string

import time

from project_util import translate_html

from news_gui import Popup

#-----------------------------------------------------------------------

# Problem Set 5

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

# Code for retrieving and parsing

# Google and Yahoo News feeds

# Do not change this code

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

def process(url):

"""

Fetches news items from the rss url and parses them.

Returns a list of NewsStory-s.

"""

feed = feedparser.parse(url)

entries = feed.entries

ret = []

for entry in entries:

guid = entry.guid

title = translate_html(entry.title)

link = entry.link

summary = translate_html(entry.summary)

try:

subject = translate_html(entry.tags[0]['term'])

except AttributeError:

subject = ""

newsStory = NewsStory(guid, title, subject, summary, link)

ret.append(newsStory)

return ret

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

# Part 1

# Data structure design

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

# Problem 1

# TODO: NewsStory

class NewsStory():

def __init__(self, guid, title, subject, summary, link):

self.guid = guid

self.title = title

self.subject = subject

self.summary = summary

self.link = link

def get_guid(self):

return self.guid

def get_title(self):

return self.title

def get_subject(self):

return self.subject

def get_summary(self):

return self.summary

def get_link(self):

return self.link

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

# Part 2

# Triggers

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

class Trigger(object):

def evaluate(self, story):

"""

Returns True if an alert should be generated

for the given news item, or False otherwise.

"""

raise NotImplementedError

"""

It must implement the evaluate method that takes a news item (NewsStory object)

as an input and returns True if an alert should be generated for that item. We will not use the

implementation of the Trigger class

"""

# Whole Word Triggers

# Problems 2-5

# TODO: WordTrigger

# It returns True if the whole word word is present

class WordTrigger(Trigger):

def is_word_in(self, word, text):

text = text.replace("'", " ")

alphabet = list('abcdefghijkl mnopqrstuvwxyz')

text = "".join(letter for letter in text if letter in alphabet)

text = text.split()

for a in text:

if word == a:

return True

else:

continue

return False

# TODO: TitleTrigger

# it should treat Intel and intel as being equal

class TitleTrigger(WordTrigger):

def __init__(self, word):

self.word = word

def evaluate(self, story):

return self.is_word_in(self.word.lower(), story.title.lower())

# TODO: SubjectTrigger

class SubjectTrigger(WordTrigger):

def __init__(self, word):

self.word = word

def evaluate(self, story):

return self.is_word_in(self.word.lower(), story.subject.lower())

# TODO: SummaryTrigger

class SummaryTrigger(WordTrigger):

def __init__(self, word):

self.word = word

def evaluate(self, story):

return self.is_word_in(self.word.lower(), story.summary.lower())

# Composite Triggers

# Problems 6-8

# TODO: NotTrigger

# given a trigger T (any trigger) and news item x

# Not trigger returns the equivalent of not T.evaluate(x)

# n = NotTrigger(self.tt)

# b = NewsStory("guid", "title", "subj", "summary", "link")

# self.assertFalse(n.evaluate(b), "Expected False. Was not was False!")

class NotTrigger(Trigger):

def __init__(self, otherTrigger):

self.otherTrigger = otherTrigger

def evaluate(self, story):

return not self.otherTrigger.evaluate(story)

# why is self.otherTrigger a Trigger and otherTrigger is a NewsStory?

# Is a NewsStory part of a Trigger? Where does it reside?

# TODO: AndTrigger

class AndTrigger(Trigger):

def __init__(self, T1, T2):

self.T1 = T1

self.T2 = T2

def evaluate(self, story):

return self.T1.evaluate(story) and self.T2.evaluate(story)

# TODO: OrTrigger

class OrTrigger(Trigger):

def __init__(self, T1, T2):

self.T1 = T1

self.T2 = T2

def evaluate(self, story):

return self.T1.evaluate(story) or self.T2.evaluate(story)

# Phrase Trigger

# Question 9

# TODO: PhraseTrigger

# constructor takes the phrase as arg

# method takes the story as arg

class PhraseTrigger(Trigger):

def __init__(self, phrase):

self.phrase = phrase

def evaluate(self, story):

title = self.phrase in story.title

subject = self.phrase in story.subject

summary = self.phrase in story.summary

return title or subject or summary

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

# Part 3

# Filtering

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

def filter_stories(stories, triggerlist):

"""

Takes in a list of NewsStory-s.

Returns only those stories for whom

a trigger in triggerlist fires.

"""

# TODO: Problem 10

# This is a placeholder (we're just returning all the stories, with no filtering)

# return stories

matches = []

for trigs in triggerlist:

for stors in stories:

if trigs.evaluate(stors):

matches.append(stors)

return matches

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

# Part 4

# User-Specified Triggers

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

def readTriggerConfig(filename):

"""

Returns a list of trigger objects

that correspond to the rules set

in the file filename

"""

# Here's some code that we give you

# to read in the file and eliminate

# blank lines and comments

triggerfile = open(filename, "r")

all = [ line.rstrip() for line in triggerfile.readlines() ]

lines = []

for line in all:

if len(line) == 0 or line[0] == '#':

continue

lines.append(line)

# TODO: Problem 11

# 'lines' has a list of lines you need to parse

# Build a set of triggers from it and

# return the appropriate ones

# print lines

# ['t1 TITLE nfl', 't2 SUBJECT Japan', 't3 PHRASE Supreme Court', 't4 AND t2 t3', 'ADD t1 t4']

allTriggers ={

"TITLE": TitleTrigger,

"SUBJECT": SubjectTrigger,

"SUMMARY": SummaryTrigger,

"NOT": NotTrigger,

"AND": AndTrigger,

"OR": OrTrigger,

"PHRASE": PhraseTrigger

}

triggers = {}

results = []

for line in lines:

line = line.split()

if line[0] == "ADD":

for i in line[1:]:

results.append(triggers[i])

return results

name = line[0]

trigger = line[1]

if trigger == "AND" or trigger == "OR":

arg1 = triggers[line[2]]

arg2 = triggers[line[3]]

triggers[name] = allTriggers[trigger](arg1, arg2) #pass the objects, not the string

else:

arg = "".join(line[2:])

triggers[name] = allTriggers[trigger](arg)

import thread

def main_thread(p):

# A sample trigger list - you'll replace

# this with something more configurable in Problem 11

t1 = SubjectTrigger("Obama")

t2 = SummaryTrigger("MIT")

t3 = PhraseTrigger("Supreme Court")

t4 = OrTrigger(t2, t3)

triggerlist = [t1, t4]

# TODO: Problem 11

# After implementing readTriggerConfig, uncomment this line

triggerlist = readTriggerConfig("triggers.txt")

guidShown = []

while True:

print "Polling..."

# Get stories from Google's Top Stories RSS news feed

stories = process("http://news.google.com/?output=rss")

# Get stories from Yahoo's Top Stories RSS news feed

stories.extend(process("http://rss.news.yahoo.com/rss/topstories"))

# Only select stories we're interested in

stories = filter_stories(stories, triggerlist)

# Don't print a story if we have already printed it before

newstories = []

for story in stories:

if story.get_guid() not in guidShown:

newstories.append(story)

for story in newstories:

guidShown.append(story.get_guid())

p.newWindow(story)

print "Sleeping..."

time.sleep(SLEEPTIME)

SLEEPTIME = 60 #seconds -- how often we poll

if __name__ == '__main__':

p = Popup()

thread.start_new_thread(main_thread, (p,))

p.start()

Python: Problem Set 4

Problem set 4 is to implement a Caesar Cipher including encryption and decrpytion of a text string. For example, encrypting a text by 1 and decrypting it:

>>> import ps4
Loading word list from file…
55909 words loaded.
>>> s = ps4.apply_shift(“The files are *in* the computer”, 1)
>>> s
‘Uifagjmftabsfa*jo*auifadpnqvufs’
>>> ps4.find_best_shift(ps4.wordlist, s)
1
>>> ps4.apply_coder(s, ps4.build_decoder(1))
‘The files are *in* the computer‘

On a multiple-shift decryption, my control flow only allows the function to decrypt text from left to right. That way we keep track of our position in the text as we shift our way across it, while also counting the number of shifts to find each valid word according to the dictionary. Until I implemented this, my valid_word checker might find a word farther down the string, move the ‘cursor’ and get completely derailed. This is obvious around line 475.

Another ‘ah-ha’ moment was trying to keep track of the counter through a recursive function. To do so, I turned the ‘start’ variable in the same function as above into an array instead of an int. start[0] functions as the cursor, start[1] as the number of shifts, and further tuples track where shifts started and how many occurred. I am not entirely sure this is allowed per the instructions, but the means are currently justifying the end result.

# 6.00 Problem Set 4
#
# Caesar Cipher Skeleton
#
import string
import random

WORDLIST_FILENAME = "words.txt"

# -----------------------------------
# Helper code
# (you don't need to understand this helper code)
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)
    # line: string
    line = inFile.readline()
    # wordlist: list of strings
    wordlist = line.split()
    print "  ", len(wordlist), "words loaded."
    return wordlist

wordlist = load_words()

def is_word(wordlist, word):
    """
    Determines if word is a valid word.

    wordlist: list of words in the dictionary.
    word: a possible word.
    returns True if word is in wordlist.

    Example:
    >>> is_word(wordlist, 'bat') returns
    True
    >>> is_word(wordlist, 'asdf') returns
    False
    """
    word = word.lower()
    word = word.strip(" !@#$%^&*()-_+={}[]|\:;'<>?,./\"")
    return word in wordlist

def random_word(wordlist):
    """
    Returns a random word.

    wordlist: list of words  
    returns: a word from wordlist at random
    """
    return random.choice(wordlist)

def random_string(wordlist, n):
    """
    Returns a string containing n random words from wordlist

    wordlist: list of words
    returns: a string of random words separated by spaces.
    """
    return " ".join([random_word(wordlist) for _ in range(n)])

def random_scrambled(wordlist, n):
    """
    Generates a test string by generating an n-word random string
    and encrypting it with a sequence of random shifts.

    wordlist: list of words
    n: number of random words to generate and scamble
    returns: a scrambled string of n random words


    NOTE:
    This function will ONLY work once you have completed your
    implementation of apply_shifts!
    """
    s = random_string(wordlist, n) + " "
    shifts = [(i, random.randint(0, 26)) for i in range(len(s)) if s[i-1] == ' ']
    return apply_shifts(s, shifts)[:-1]

def get_fable_string():
    """
    Returns a fable in encrypted text.
    """
    f = open("fable.txt", "r")
    fable = str(f.read())
    f.close()
    return fable


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

#
# Problem 1: Encryption
#
def build_coder(shift):
    """
    Returns a dict that can apply a Caesar cipher to a letter.
    The cipher is defined by the shift value. Ignores non-letter characters
    like punctuation and numbers.

    shift: -27 < int < 27
    returns: dict

    Example:
    >>> build_coder(3)
    {' ': 'c', 'A': 'D', 'C': 'F', 'B': 'E', 'E': 'H', 'D': 'G', 'G': 'J',
    'F': 'I', 'I': 'L', 'H': 'K', 'K': 'N', 'J': 'M', 'M': 'P', 'L': 'O',
    'O': 'R', 'N': 'Q', 'Q': 'T', 'P': 'S', 'S': 'V', 'R': 'U', 'U': 'X',
    'T': 'W', 'W': 'Z', 'V': 'Y', 'Y': 'A', 'X': ' ', 'Z': 'B', 'a': 'd',
    'c': 'f', 'b': 'e', 'e': 'h', 'd': 'g', 'g': 'j', 'f': 'i', 'i': 'l',
    'h': 'k', 'k': 'n', 'j': 'm', 'm': 'p', 'l': 'o', 'o': 'r', 'n': 'q',
    'q': 't', 'p': 's', 's': 'v', 'r': 'u', 'u': 'x', 't': 'w', 'w': 'z',
    'v': 'y', 'y': 'a', 'x': ' ', 'z': 'b'}
    (The order of the key-value pairs may be different.)
    """
    ### TODO.
    
    assert(-27 < shift < 27)
    alphabet = [' ']
    i = 97
    # build array of alphabet chars beginning with ' '
    while i < 123:
        alphabet.append(chr(i))
        i += 1
    
    # create dict where key is letter and value is letter + shift
    coder = {}
    i = 0
    while i < len(alphabet):
        coder[alphabet[i]] = alphabet[(i + shift) % len(alphabet)]
        i += 1
    i = 1
    # repeat for uppercase
    while i < len(alphabet):
        coder[alphabet[i].upper()] = alphabet[(i + shift) % len(alphabet)].upper()
        i += 1
        
    return coder

def build_encoder(shift):
    """
    Returns a dict that can be used to encode a plain text. For example, you
    could encrypt the plain text by calling the following commands
    >>>encoder = build_encoder(shift)
    >>>encrypted_text = apply_coder(plain_text, encoder)
    
    The cipher is defined by the shift value. Ignores non-letter characters
    like punctuation and numbers.

    shift: 0 <= int < 27
    returns: dict

    Example:
    >>> build_encoder(3)
    {' ': 'c', 'A': 'D', 'C': 'F', 'B': 'E', 'E': 'H', 'D': 'G', 'G': 'J',
    'F': 'I', 'I': 'L', 'H': 'K', 'K': 'N', 'J': 'M', 'M': 'P', 'L': 'O',
    'O': 'R', 'N': 'Q', 'Q': 'T', 'P': 'S', 'S': 'V', 'R': 'U', 'U': 'X',
    'T': 'W', 'W': 'Z', 'V': 'Y', 'Y': 'A', 'X': ' ', 'Z': 'B', 'a': 'd',
    'c': 'f', 'b': 'e', 'e': 'h', 'd': 'g', 'g': 'j', 'f': 'i', 'i': 'l',
    'h': 'k', 'k': 'n', 'j': 'm', 'm': 'p', 'l': 'o', 'o': 'r', 'n': 'q',
    'q': 't', 'p': 's', 's': 'v', 'r': 'u', 'u': 'x', 't': 'w', 'w': 'z',
    'v': 'y', 'y': 'a', 'x': ' ', 'z': 'b'}
    (The order of the key-value pairs may be different.)

    HINT : Use build_coder.
    """
    ### TODO.
    assert( 0 <= shift < 27)
    encoder = build_coder(shift)
    
    return encoder
    
# watch it run
# print build_encoder(3)    

def build_decoder(shift):
    """
    Returns a dict that can be used to decode an encrypted text. For example, you
    could decrypt an encrypted text by calling the following commands
    >>>encoder = build_encoder(shift)
    >>>encrypted_text = apply_coder(plain_text, encoder)
    >>>decrypted_text = apply_coder(plain_text, decoder)
    
    The cipher is defined by the shift value. Ignores non-letter characters
    like punctuation and numbers.

    shift: 0 <= int < 27
    returns: dict

    Example:
    >>> build_decoder(3)
    {' ': 'x', 'A': 'Y', 'C': ' ', 'B': 'Z', 'E': 'B', 'D': 'A', 'G': 'D',
    'F': 'C', 'I': 'F', 'H': 'E', 'K': 'H', 'J': 'G', 'M': 'J', 'L': 'I',
    'O': 'L', 'N': 'K', 'Q': 'N', 'P': 'M', 'S': 'P', 'R': 'O', 'U': 'R',
    'T': 'Q', 'W': 'T', 'V': 'S', 'Y': 'V', 'X': 'U', 'Z': 'W', 'a': 'y',
    'c': ' ', 'b': 'z', 'e': 'b', 'd': 'a', 'g': 'd', 'f': 'c', 'i': 'f',
    'h': 'e', 'k': 'h', 'j': 'g', 'm': 'j', 'l': 'i', 'o': 'l', 'n': 'k',
    'q': 'n', 'p': 'm', 's': 'p', 'r': 'o', 'u': 'r', 't': 'q', 'w': 't',
    'v': 's', 'y': 'v', 'x': 'u', 'z': 'w'}
    (The order of the key-value pairs may be different.)

    HINT : Use build_coder.
    """
    ### TODO.
    ### bug KeyError on decoder['C']
    ### something to do with the do uppercase and i starting at 1?
    
    decoder = {}
    # get a copy of the encoding dict
    temp = build_coder(shift)
    
    # reverse values -> keys
    for i in temp:
        decoder[temp[i]] = i
    return decoder 
    
# watch it run
# print build_decoder(3)    

def apply_coder(text, coder):
    """
    Applies the coder to the text. Returns the encoded text.

    text: string
    coder: dict with mappings of characters to shifted characters
    returns: text after mapping coder chars to original text

    Example:
    >>> apply_coder("Hello, world!", build_encoder(3))
    'Khoor,czruog!'
    >>> apply_coder("Khoor,czruog!", build_decoder(3))
    'Hello, world!'
    """
    ### TODO.
    ### 4/19/15
    ### currently KeyError on punctuation
    encoded_char = []
    
    for i in text:
        # ignore any letter/symbols not present in the coder dict (punctuation)
        if i in coder:
            encoded_char.append(coder[i])
        else:
            encoded_char.append(i)
        
    encoded_text = ''.join(encoded_char)
    
    return encoded_text

# watch it run  
# print apply_coder("Hello, world!", build_encoder(3))    

def apply_shift(text, shift):
    """
    Given a text, returns a new text Caesar shifted by the given shift
    offset. The empty space counts as the 27th letter of the alphabet,
    so spaces should be replaced by a lowercase letter as appropriate.
    Otherwise, lower case letters should remain lower case, upper case
    letters should remain upper case, and all other punctuation should
    stay as it is.
    
    text: string to apply the shift to
    shift: amount to shift the text
    returns: text after being shifted by specified amount.

    Example:
    >>> apply_shift('This is a test.', 8)
    'Apq hq hiham a.'
    """
    ### TODO.
    
    encoded_text = apply_coder(text, build_encoder(shift))
    return encoded_text
    
# watch it run
# print apply_shift('This is a test.', 8)

#
# Problem 2: Codebreaking.
#
def find_best_shift(wordlist, text):
    """
    Decrypts the encoded text and returns the plaintext.

    text: string
    returns: 0 <= int 27

    Example:
    >>> s = apply_coder('Hello, world!', build_encoder(8))
    >>> s
    'Pmttw,hdwztl!'
    >>> find_best_shift(wordlist, s) returns
    8
    >>> apply_coder(s, build_decoder(8)) returns
    'Hello, world!'
    """
    ### TODO
    ### returns the shift int answer
    
    split_string = list(text)
    alpha_string = []
    for i in split_string:
        if i.isalpha():
            alpha_string.append(i)
        else:
            continue

    # print alpha_string
    i = 0
    while i < 27:
        potential_decode = apply_shift(''.join(alpha_string), i)
        
        # print potential_decode
        # split result
        potential_decode = potential_decode.split()
        
        # all words in dictionary?
        winner = True
        for word in potential_decode:
            if word.lower() in wordlist:
                continue
            else:
                winner = False
        if winner == True:
            return abs(i-27)
            
        # all good things must come to an end
        i += 1
    return None

# watch it run
# s = apply_coder('Hello, world!', build_encoder(8))    
# print find_best_shift(wordlist, s)
# print apply_coder(s, build_decoder(8))
   
#
# Problem 3: Multi-level encryption.
#
def apply_shifts(text, shifts):
    """
    Applies a sequence of shifts to an input text.

    text: A string to apply the Ceasar shifts to 
    shifts: A list of tuples containing the location each shift should
    begin and the shift offset. Each tuple is of the form (location,
    shift) The shifts are layered: each one is applied from its
    starting position all the way through the end of the string.  
    returns: text after applying the shifts to the appropriate
    positions

    Example:
    >>> apply_shifts("Do Androids Dream of Electric Sheep?", [(0,6), (3, 18), (12, 16)])
    'JufYkaolfapxQdrnzmasmRyrpfdvpmEurrb?'
    """
    ### TODO.
    
    # for each pair in shifts (text, shifts)
    for i in shifts:
        # get text to shift from [text:]
        text_to_shift = text[i[0]:]
        
        # get prefix to conserve from [:text]
        text = text[:i[0]]
        
        # shift the text by shifts
        shifted_text = apply_shift(text_to_shift, i[1])
        
        # recombine
        text = text + shifted_text
        
    return text
    
# watch it run    
# print apply_shifts("Do Androids Dream of Electric Sheep?", [(0,6), (3, 18), (12, 16)])

#
# Problem 4: Multi-level decryption.
#


def find_best_shifts(wordlist, text):
    """
    Given a scrambled string, returns a shift key that will decode the text to
    words in wordlist, or None if there is no such key.

    Hint: Make use of the recursive function
    find_best_shifts_rec(wordlist, text, start)

    wordlist: list of words
    text: scambled text to try to find the words for
    returns: list of tuples.  each tuple is (position in text, amount of shift)
    
    Examples:
    >>> s = random_scrambled(wordlist, 3)
    >>> s
    'eqorqukvqtbmultiform wyy ion'
    >>> shifts = find_best_shifts(wordlist, s)
    >>> shifts
    [(0, 25), (11, 2), (21, 5)]
    >>> apply_shifts(s, shifts)
    'compositor multiform accents'
    >>> s = apply_shifts("Do Androids Dream of Electric Sheep?", [(0,6), (3, 18), (12, 16)])
    >>> s
    'JufYkaolfapxQdrnzmasmRyrpfdvpmEurrb?'
    >>> shifts = find_best_shifts(wordlist, s)
    >>> print apply_shifts(s, shifts)
    Do Androids Dream of Electric Sheep?
    """
    
def find_best_shifts_rec(wordlist, text, start):
    """
    Given a scrambled string and a starting position from which
    to decode, returns a shift key that will decode the text to
    words in wordlist, or None if there is no such key.

    Hint: You will find this function much easier to implement
    if you use recursion.

    wordlist: list of words
    text: scambled text to try to find the words for
    start: where to start looking at shifts
    returns: list of tuples.  each tuple is (position in text, amount of shift)
    """
    ### TODO.
    ##########
    # my logic assumes that words will be decrypted from left to right in order
    # This seems inefficient
    # I think I am abusing the start variable to pass counting values
    ##########
    
    # best case scenario, start at end AKA no shifts, check if words in dict

    # track the number of shifts in position start[1]
    if len(start) < 2:
        start.append(0)
        print text

    # is every item in result in dictionary?
    text_given = text.split()
    done_shifting = True # best case scenario
    for i in text_given:
        if is_word(wordlist, i):
            continue
        else:
            done_shifting = False # best case didn't happen
            
    if done_shifting == True:
        print "decipher complete"
        print text
        return start[2:]
            
    # save any valid words before start
    valid_words = text[:start[0]]
    
    # shift text after start and count it
    text_to_shift = text[start[0]:]
    shifted_text = apply_shift(text_to_shift, 1)
    start[1] += 1
    
    # split on ' ' and check results for valid words
    split_shifted_text = shifted_text.split(' ')
    # recombine into a string to later resend to recursive function
    unsplit_shifted_text = ' '.join(split_shifted_text)
    recombined_text = valid_words + unsplit_shifted_text
    
    # check for valid words and move start for each
    start_began = start[0]
    for i in split_shifted_text:
        if is_word(wordlist, i):
            # watch it find words
            print i, " is a word"
            a = raw_input(">")            
            start[0] += len(i)+1
        else:
            break # assures decrypt from left to right
    
    if start[0] != start_began:
        start.append((start_began, abs(start[1] - 27)))
        start[1] = 0 # reset shifting counter
        
    # will always run one extra cycle to check correctness at the top
    return find_best_shifts_rec(wordlist, recombined_text, start)    

# watch it run
# s = random_scrambled(wordlist, 3)
# or
# s = apply_shifts("Do Androids Dream of Electric Sheep?", [(0,25), (3, 1), (12, 1)])
# print find_best_shifts_rec(wordlist, s, [0])

def decrypt_fable():
    """
    Using the methods you created in this problem set,
    decrypt the fable given by the function get_fable_string().
    Once you decrypt the message, be sure to include as a comment
    at the end of this problem set how the fable relates to your
    education at MIT.

    returns: string - fable in plain text
    """
    ### TODO.
    s = get_fable_string()
    print find_best_shifts_rec(wordlist, s, [0])
    
# fails on 30th word
# goes into infinite loop
# potentially a problem with a double-space and my recombined strings
# decrypt_fable()

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

# 6.00 Problem Set 4

# Caesar Cipher Skeleton

import string

import random

WORDLIST_FILENAME = "words.txt"

# -----------------------------------

# Helper code

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

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)

# line: string

line = inFile.readline()

# wordlist: list of strings

wordlist = line.split()

print " ", len(wordlist), "words loaded."

return wordlist

wordlist = load_words()

def is_word(wordlist, word):

"""

Determines if word is a valid word.

wordlist: list of words in the dictionary.

word: a possible word.

returns True if word is in wordlist.

Example:

>>> is_word(wordlist, 'bat') returns

True

>>> is_word(wordlist, 'asdf') returns

False

"""

word = word.lower()

word = word.strip(" !@#$%^&*()-_+={}[]|\:;'<>?,./\"")

return word in wordlist

def random_word(wordlist):

"""

Returns a random word.

wordlist: list of words

returns: a word from wordlist at random

"""

return random.choice(wordlist)

def random_string(wordlist, n):

"""

Returns a string containing n random words from wordlist

wordlist: list of words

returns: a string of random words separated by spaces.

"""

return " ".join([random_word(wordlist) for _ in range(n)])

def random_scrambled(wordlist, n):

"""

Generates a test string by generating an n-word random string

and encrypting it with a sequence of random shifts.

wordlist: list of words

n: number of random words to generate and scamble

returns: a scrambled string of n random words

NOTE:

This function will ONLY work once you have completed your

implementation of apply_shifts!

"""

s = random_string(wordlist, n) + " "

shifts = [(i, random.randint(0, 26)) for i in range(len(s)) if s[i-1] == ' ']

return apply_shifts(s, shifts)[:-1]

def get_fable_string():

"""

Returns a fable in encrypted text.

"""

f = open("fable.txt", "r")

fable = str(f.read())

f.close()

return fable

# (end of helper code)

# -----------------------------------

# Problem 1: Encryption

def build_coder(shift):

"""

Returns a dict that can apply a Caesar cipher to a letter.

The cipher is defined by the shift value. Ignores non-letter characters

like punctuation and numbers.

shift: -27 < int < 27

returns: dict

Example:

>>> build_coder(3)

{' ': 'c', 'A': 'D', 'C': 'F', 'B': 'E', 'E': 'H', 'D': 'G', 'G': 'J',

'F': 'I', 'I': 'L', 'H': 'K', 'K': 'N', 'J': 'M', 'M': 'P', 'L': 'O',

'O': 'R', 'N': 'Q', 'Q': 'T', 'P': 'S', 'S': 'V', 'R': 'U', 'U': 'X',

'T': 'W', 'W': 'Z', 'V': 'Y', 'Y': 'A', 'X': ' ', 'Z': 'B', 'a': 'd',

'c': 'f', 'b': 'e', 'e': 'h', 'd': 'g', 'g': 'j', 'f': 'i', 'i': 'l',

'h': 'k', 'k': 'n', 'j': 'm', 'm': 'p', 'l': 'o', 'o': 'r', 'n': 'q',

'q': 't', 'p': 's', 's': 'v', 'r': 'u', 'u': 'x', 't': 'w', 'w': 'z',

'v': 'y', 'y': 'a', 'x': ' ', 'z': 'b'}

(The order of the key-value pairs may be different.)

"""

### TODO.

assert(-27 < shift < 27)

alphabet = [' ']

i = 97

# build array of alphabet chars beginning with ' '

while i < 123:

alphabet.append(chr(i))

i += 1

# create dict where key is letter and value is letter + shift

coder = {}

i = 0

while i < len(alphabet):

coder[alphabet[i]] = alphabet[(i + shift) % len(alphabet)]

i += 1

i = 1

# repeat for uppercase

while i < len(alphabet):

coder[alphabet[i].upper()] = alphabet[(i + shift) % len(alphabet)].upper()

i += 1

return coder

def build_encoder(shift):

"""

Returns a dict that can be used to encode a plain text. For example, you

could encrypt the plain text by calling the following commands

>>>encoder = build_encoder(shift)

>>>encrypted_text = apply_coder(plain_text, encoder)

The cipher is defined by the shift value. Ignores non-letter characters

like punctuation and numbers.

shift: 0 <= int < 27

returns: dict

Example:

>>> build_encoder(3)

{' ': 'c', 'A': 'D', 'C': 'F', 'B': 'E', 'E': 'H', 'D': 'G', 'G': 'J',

'F': 'I', 'I': 'L', 'H': 'K', 'K': 'N', 'J': 'M', 'M': 'P', 'L': 'O',

'O': 'R', 'N': 'Q', 'Q': 'T', 'P': 'S', 'S': 'V', 'R': 'U', 'U': 'X',

'T': 'W', 'W': 'Z', 'V': 'Y', 'Y': 'A', 'X': ' ', 'Z': 'B', 'a': 'd',

'c': 'f', 'b': 'e', 'e': 'h', 'd': 'g', 'g': 'j', 'f': 'i', 'i': 'l',

'h': 'k', 'k': 'n', 'j': 'm', 'm': 'p', 'l': 'o', 'o': 'r', 'n': 'q',

'q': 't', 'p': 's', 's': 'v', 'r': 'u', 'u': 'x', 't': 'w', 'w': 'z',

'v': 'y', 'y': 'a', 'x': ' ', 'z': 'b'}

(The order of the key-value pairs may be different.)

HINT : Use build_coder.

"""

### TODO.

assert( 0 <= shift < 27)

encoder = build_coder(shift)

return encoder

# watch it run

# print build_encoder(3)

def build_decoder(shift):

"""

Returns a dict that can be used to decode an encrypted text. For example, you

could decrypt an encrypted text by calling the following commands

>>>encoder = build_encoder(shift)

>>>encrypted_text = apply_coder(plain_text, encoder)

>>>decrypted_text = apply_coder(plain_text, decoder)

The cipher is defined by the shift value. Ignores non-letter characters

like punctuation and numbers.

shift: 0 <= int < 27

returns: dict

Example:

>>> build_decoder(3)

{' ': 'x', 'A': 'Y', 'C': ' ', 'B': 'Z', 'E': 'B', 'D': 'A', 'G': 'D',

'F': 'C', 'I': 'F', 'H': 'E', 'K': 'H', 'J': 'G', 'M': 'J', 'L': 'I',

'O': 'L', 'N': 'K', 'Q': 'N', 'P': 'M', 'S': 'P', 'R': 'O', 'U': 'R',

'T': 'Q', 'W': 'T', 'V': 'S', 'Y': 'V', 'X': 'U', 'Z': 'W', 'a': 'y',

'c': ' ', 'b': 'z', 'e': 'b', 'd': 'a', 'g': 'd', 'f': 'c', 'i': 'f',

'h': 'e', 'k': 'h', 'j': 'g', 'm': 'j', 'l': 'i', 'o': 'l', 'n': 'k',

'q': 'n', 'p': 'm', 's': 'p', 'r': 'o', 'u': 'r', 't': 'q', 'w': 't',

'v': 's', 'y': 'v', 'x': 'u', 'z': 'w'}

(The order of the key-value pairs may be different.)

HINT : Use build_coder.

"""

### TODO.

### bug KeyError on decoder['C']

### something to do with the do uppercase and i starting at 1?

decoder = {}

# get a copy of the encoding dict

temp = build_coder(shift)

# reverse values -> keys

for i in temp:

decoder[temp[i]] = i

return decoder

# watch it run

# print build_decoder(3)

def apply_coder(text, coder):

"""

Applies the coder to the text. Returns the encoded text.

text: string

coder: dict with mappings of characters to shifted characters

returns: text after mapping coder chars to original text

Example:

>>> apply_coder("Hello, world!", build_encoder(3))

'Khoor,czruog!'

>>> apply_coder("Khoor,czruog!", build_decoder(3))

'Hello, world!'

"""

### TODO.

### 4/19/15

### currently KeyError on punctuation

encoded_char = []

for i in text:

# ignore any letter/symbols not present in the coder dict (punctuation)

if i in coder:

encoded_char.append(coder[i])

else:

encoded_char.append(i)

encoded_text = ''.join(encoded_char)

return encoded_text

# watch it run

# print apply_coder("Hello, world!", build_encoder(3))

def apply_shift(text, shift):

"""

Given a text, returns a new text Caesar shifted by the given shift

offset. The empty space counts as the 27th letter of the alphabet,

so spaces should be replaced by a lowercase letter as appropriate.

Otherwise, lower case letters should remain lower case, upper case

letters should remain upper case, and all other punctuation should

stay as it is.

text: string to apply the shift to

shift: amount to shift the text

returns: text after being shifted by specified amount.

Example:

>>> apply_shift('This is a test.', 8)

'Apq hq hiham a.'

"""

### TODO.

encoded_text = apply_coder(text, build_encoder(shift))

return encoded_text

# watch it run

# print apply_shift('This is a test.', 8)

# Problem 2: Codebreaking.

def find_best_shift(wordlist, text):

"""

Decrypts the encoded text and returns the plaintext.

text: string

returns: 0 <= int 27

Example:

>>> s = apply_coder('Hello, world!', build_encoder(8))

>>> s

'Pmttw,hdwztl!'

>>> find_best_shift(wordlist, s) returns

>>> apply_coder(s, build_decoder(8)) returns

'Hello, world!'

"""

### TODO

### returns the shift int answer

split_string = list(text)

alpha_string = []

for i in split_string:

if i.isalpha():

alpha_string.append(i)

else:

continue

# print alpha_string

i = 0

while i < 27:

potential_decode = apply_shift(''.join(alpha_string), i)

# print potential_decode

# split result

potential_decode = potential_decode.split()

# all words in dictionary?

winner = True

for word in potential_decode:

if word.lower() in wordlist:

continue

else:

winner = False

if winner == True:

return abs(i-27)

# all good things must come to an end

i += 1

return None

# watch it run

# s = apply_coder('Hello, world!', build_encoder(8))

# print find_best_shift(wordlist, s)

# print apply_coder(s, build_decoder(8))

# Problem 3: Multi-level encryption.

def apply_shifts(text, shifts):

"""

Applies a sequence of shifts to an input text.

text: A string to apply the Ceasar shifts to

shifts: A list of tuples containing the location each shift should

begin and the shift offset. Each tuple is of the form (location,

shift) The shifts are layered: each one is applied from its

starting position all the way through the end of the string.

returns: text after applying the shifts to the appropriate

positions

Example:

>>> apply_shifts("Do Androids Dream of Electric Sheep?", [(0,6), (3, 18), (12, 16)])

'JufYkaolfapxQdrnzmasmRyrpfdvpmEurrb?'

"""

### TODO.

# for each pair in shifts (text, shifts)

for i in shifts:

# get text to shift from [text:]

text_to_shift = text[i[0]:]

# get prefix to conserve from [:text]

text = text[:i[0]]

# shift the text by shifts

shifted_text = apply_shift(text_to_shift, i[1])

# recombine

text = text + shifted_text

return text

# watch it run

# print apply_shifts("Do Androids Dream of Electric Sheep?", [(0,6), (3, 18), (12, 16)])

# Problem 4: Multi-level decryption.

def find_best_shifts(wordlist, text):

"""

Given a scrambled string, returns a shift key that will decode the text to

words in wordlist, or None if there is no such key.

Hint: Make use of the recursive function

find_best_shifts_rec(wordlist, text, start)

wordlist: list of words

text: scambled text to try to find the words for

returns: list of tuples. each tuple is (position in text, amount of shift)

Examples:

>>> s = random_scrambled(wordlist, 3)

>>> s

'eqorqukvqtbmultiform wyy ion'

>>> shifts = find_best_shifts(wordlist, s)

>>> shifts

[(0, 25), (11, 2), (21, 5)]

>>> apply_shifts(s, shifts)

'compositor multiform accents'

>>> s = apply_shifts("Do Androids Dream of Electric Sheep?", [(0,6), (3, 18), (12, 16)])

>>> s

'JufYkaolfapxQdrnzmasmRyrpfdvpmEurrb?'

>>> shifts = find_best_shifts(wordlist, s)

>>> print apply_shifts(s, shifts)

Do Androids Dream of Electric Sheep?

"""

def find_best_shifts_rec(wordlist, text, start):

"""

Given a scrambled string and a starting position from which

to decode, returns a shift key that will decode the text to

words in wordlist, or None if there is no such key.

Hint: You will find this function much easier to implement

if you use recursion.

wordlist: list of words

text: scambled text to try to find the words for

start: where to start looking at shifts

returns: list of tuples. each tuple is (position in text, amount of shift)

"""

### TODO.

##########

# my logic assumes that words will be decrypted from left to right in order

# This seems inefficient

# I think I am abusing the start variable to pass counting values

##########

# best case scenario, start at end AKA no shifts, check if words in dict

# track the number of shifts in position start[1]

if len(start) < 2:

start.append(0)

print text

# is every item in result in dictionary?

text_given = text.split()

done_shifting = True # best case scenario

for i in text_given:

if is_word(wordlist, i):

continue

else:

done_shifting = False # best case didn't happen

if done_shifting == True:

print "decipher complete"

print text

return start[2:]

# save any valid words before start

valid_words = text[:start[0]]

# shift text after start and count it

text_to_shift = text[start[0]:]

shifted_text = apply_shift(text_to_shift, 1)

start[1] += 1

# split on ' ' and check results for valid words

split_shifted_text = shifted_text.split(' ')

# recombine into a string to later resend to recursive function

unsplit_shifted_text = ' '.join(split_shifted_text)

recombined_text = valid_words + unsplit_shifted_text

# check for valid words and move start for each

start_began = start[0]

for i in split_shifted_text:

if is_word(wordlist, i):

# watch it find words

print i, " is a word"

a = raw_input(">")

start[0] += len(i)+1

else:

break # assures decrypt from left to right

if start[0] != start_began:

start.append((start_began, abs(start[1] - 27)))

start[1] = 0 # reset shifting counter

# will always run one extra cycle to check correctness at the top

return find_best_shifts_rec(wordlist, recombined_text, start)

# watch it run

# s = random_scrambled(wordlist, 3)

# or

# s = apply_shifts("Do Androids Dream of Electric Sheep?", [(0,25), (3, 1), (12, 1)])

# print find_best_shifts_rec(wordlist, s, [0])

def decrypt_fable():

"""

Using the methods you created in this problem set,

decrypt the fable given by the function get_fable_string().

Once you decrypt the message, be sure to include as a comment

at the end of this problem set how the fable relates to your

education at MIT.

returns: string - fable in plain text

"""

### TODO.

s = get_fable_string()

print find_best_shifts_rec(wordlist, s, [0])

# fails on 30th word

# goes into infinite loop

# potentially a problem with a double-space and my recombined strings

# decrypt_fable()

Python: Problem Set 3

This problem set involves a word game somewhat like Scrabble. In Part A, the player is dealt a hand of semi-random letters and has to make as many valid words as she can. Some letters are weighted higher or lower when it comes to scoring. Some aspects of the game code are provided to begin with. The rest of the functions are left up to us to complete, then put together into a looping game where you can choose to start a New Game, Replay, or Exit. In Part B, a computer player is added, which will pick one or more valid words until no more can be made with the remaining letters.

Key take-aways from lecture:

floats are dangerous, e.g. 0.1 can only be approximated in binary
print(num) may show ‘0.1’ but use repr(num) to see what is actually being stored
When debugging, ask, “How could it have done what it did?”
It’s a better starting point than, “Why didn’t it do what I want?”
Use print statements in a manner similar to bisection search. Check here, then there.
Try to test against small input values and make tests repeatable

Part A

Scoring Words
Dealing with Hands
Word Validation
Playing a Hand
Playing a Game

# 6.00 Problem Set 3A Solutions
#
# The 6.00 Word Game
# Created by: Kevin Luu <luuk> and Jenna Wiens <jwiens>
#
#

import random
import string

VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
HAND_SIZE = 6

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
#
# Casey Brown
# caseycodes@gmail.com
# begin: 20h35
# end: 21h00
# test_ps3a.py passing
#
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 multiplied by the length of 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
    """
    # TO DO...
    # n is not the length of the word, it is the length of the dealt hand
    if len(word) == 0:
        return 0
    else:
        # start with a counter at zero
        score = 0

        # for each letter, add them to the score
        for letter in word:
            score += SCRABBLE_LETTER_VALUES[letter]
            
        # how long is the word? That's our multiplier        
        score *= len(word)
        
        # bonus score
        if len(word) == n:
            score += 50
        
        # return something
        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
#
# Casey Brown
# caseycodes@gmail.com
# begin: 21h30
# end: 21h35
# test_ps3a.py passing
#
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 modify hand.

    word: string
    hand: dictionary (string -> int)    
    returns: dictionary (string -> int)
    """
    # TO DO ...    
    
    # for each letter in word
    for i in word:
        # subtract 1 of that letter from hand
        hand[i] -= 1
    return hand

#
# Problem #3: Test word validity
#
# Casey Brown
# caseycodes@gmail.com
# 15 min, sleep, start over, 20 min
#
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
    """
    # TO DO...
    # copy hand to not modify it when checking for letters
    this_hand = dict(hand)
    if word in word_list:
        is_a_word = True
    else:
        is_a_word = False
    
    # True until proven False
    word_in_hand = True
    for letter in word:
        # will return KeyError if check hand[letter] and letter not in hand
        if this_hand.get(letter, 0) > 0:
            this_hand[letter] -= 1
        else:
            word_in_hand = False
                
    if is_a_word and word_in_hand:
        return True
    else:
        return False

def calculate_handlen(hand):
    handlen = 0
    for v in hand.values():
        handlen += v
    return handlen

#
# Problem #4: Playing a hand
#
# Casey Brown
# caseycodes@gmail.com
# 18h55
#
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 is 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.

      hand: dictionary (string -> int)
      word_list: list of lowercase strings
      
    """
    # TO DO ...
    word = ""
    total_score = 0
    while word != ".":
        display_hand(hand)
        word = raw_input("Enter a word using letters in your hand.\n>>>")
        if is_valid_word(word, hand, word_list):
            print "Your word is valid!"
            update_hand(hand, word)
            print get_word_score(word, HAND_SIZE)
            total_score += get_word_score(word, HAND_SIZE)
        elif word == ".":
            break
        else:
            print "Sorry, that's not a word or you don't have all the letters."
            # 17h20
    print "Your final score was ", total_score, "!"

# 17h10

#
# 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.
    """
    # TO DO...
    game_on = True
    while game_on == True:
        user_choice = raw_input("N: New Game\nR: Replay\nE: Exit\n>>>")
        if user_choice.lower() == "n":
            hand = deal_hand(HAND_SIZE)
            mod_hand = dict(hand)
            play_hand(mod_hand, load_words())
        elif user_choice.lower() == "e":
            game_on = False
        elif user_choice.lower() == "r":
            # figure out how to do if(hand, deal_hand(HAND_SIZE))
            try:
                hand
            except NameError:
                hand = deal_hand(HAND_SIZE)
                mod_hand = dict(hand)
                play_hand(mod_hand, load_words())
            else:
                mod_hand = dict(hand)
                play_hand(mod_hand, load_words())
        else:
            print "Enter either 'n', 'r', or 'e' without quotes"
#
# Build data structures used for entire session and play game
#
if __name__ == '__main__':
    word_list = load_words()
    play_game(word_list)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

# 6.00 Problem Set 3A Solutions

# The 6.00 Word Game

# Created by: Kevin Luu <luuk> and Jenna Wiens <jwiens>

import random

import string

VOWELS = 'aeiou'

CONSONANTS = 'bcdfghjklmnpqrstvwxyz'

HAND_SIZE = 6

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

# Casey Brown

# caseycodes@gmail.com

# begin: 20h35

# end: 21h00

# test_ps3a.py passing

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 multiplied by the length of 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

"""

# TO DO...

# n is not the length of the word, it is the length of the dealt hand

if len(word) == 0:

return 0

else:

# start with a counter at zero

score = 0

# for each letter, add them to the score

for letter in word:

score += SCRABBLE_LETTER_VALUES[letter]

# how long is the word? That's our multiplier

score *= len(word)

# bonus score

if len(word) == n:

score += 50

# return something

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

# Casey Brown

# caseycodes@gmail.com

# begin: 21h30

# end: 21h35

# test_ps3a.py passing

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 modify hand.

word: string

hand: dictionary (string -> int)

returns: dictionary (string -> int)

"""

# TO DO ...

# for each letter in word

for i in word:

# subtract 1 of that letter from hand

hand[i] -= 1

return hand

# Problem #3: Test word validity

# Casey Brown

# caseycodes@gmail.com

# 15 min, sleep, start over, 20 min

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

"""

# TO DO...

# copy hand to not modify it when checking for letters

this_hand = dict(hand)

if word in word_list:

is_a_word = True

else:

is_a_word = False

# True until proven False

word_in_hand = True

for letter in word:

# will return KeyError if check hand[letter] and letter not in hand

if this_hand.get(letter, 0) > 0:

this_hand[letter] -= 1

else:

word_in_hand = False

if is_a_word and word_in_hand:

return True

else:

return False

def calculate_handlen(hand):

handlen = 0

for v in hand.values():

handlen += v

return handlen

# Problem #4: Playing a hand

# Casey Brown

# caseycodes@gmail.com

# 18h55

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

hand: dictionary (string -> int)

word_list: list of lowercase strings

"""

# TO DO ...

word = ""

total_score = 0

while word != ".":

display_hand(hand)

word = raw_input("Enter a word using letters in your hand.\n>>>")

if is_valid_word(word, hand, word_list):

print "Your word is valid!"

update_hand(hand, word)

print get_word_score(word, HAND_SIZE)

total_score += get_word_score(word, HAND_SIZE)

elif word == ".":

break

else:

print "Sorry, that's not a word or you don't have all the letters."

# 17h20

print "Your final score was ", total_score, "!"

# 17h10

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

"""

# TO DO...

game_on = True

while game_on == True:

user_choice = raw_input("N: New Game\nR: Replay\nE: Exit\n>>>")

if user_choice.lower() == "n":

hand = deal_hand(HAND_SIZE)

mod_hand = dict(hand)

play_hand(mod_hand, load_words())

elif user_choice.lower() == "e":

game_on = False

elif user_choice.lower() == "r":

# figure out how to do if(hand, deal_hand(HAND_SIZE))

try:

hand

except NameError:

hand = deal_hand(HAND_SIZE)

mod_hand = dict(hand)

play_hand(mod_hand, load_words())

else:

mod_hand = dict(hand)

play_hand(mod_hand, load_words())

else:

print "Enter either 'n', 'r', or 'e' without quotes"

# Build data structures used for entire session and play game

if __name__ == '__main__':

word_list = load_words()

play_game(word_list)

Part B

Computer Chooses (best scoring first word and so on)
Computer’s Turn to Play
You or the Computer

from ps3a import *
import time
from perm import *


#
#
# Problem #6A: Computer chooses a word
#
#
def comp_choose_word(hand, word_list):
    """
	Given a hand and a word_dict, find the word that gives the maximum value score, and return it.
   	This word should be calculated by considering all possible permutations of lengths 1 to HAND_SIZE.

    hand: dictionary (string -> int)
    word_list: list (string)
    """
    # TO DO...
    all_perms = get_perms(hand, HAND_SIZE)
    
    # store best words here
    valid_words = set()
    best_words = {}
    for i in all_perms:
        # check if there is a word that uses full HAND_SIZE
        if i in word_list:
            # testing
            # print i
            return i
        
        # walk backwards from end of word, checking if it's in word_list
        j = 1
        while j < HAND_SIZE:
            word = i[:-j]
            # watch it work with time.sleep(1)
            # print word
            if word in word_list:
                valid_words.add(word)
                # print word, get_word_score(word, len(word))
            j += 1
    if len(valid_words) == 0:
        return None
        
    for i in valid_words:
        best_words[get_word_score(i, len(word))] = i
    # testing
    # print best_words
    # for i in sorted(best_words):
        # print i
    return best_words[max(best_words.keys())]
#
# Problem #6B: Computer plays a hand
#
def comp_play_hand(hand, word_list):
    """
     Allows the computer to play the given hand, as follows:

     * The hand is displayed.

     * The computer chooses a word using comp_choose_words(hand, word_dict).

     * After every valid word: the score for that word is displayed, 
       the remaining letters in the hand are displayed, and the computer 
       chooses another word.

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

     * The hand finishes when the computer has exhausted its possible choices (i.e. comp_play_hand returns None).

     hand: dictionary (string -> int)
     word_list: list (string)
    """
    # TO DO ...    

    # keep score
    score = 0
    while True:
        # The hand is displayed.
        display_hand(hand)

        # The computer chooses a word using comp_choose_words(hand, word_dict).    
        chosen_word = comp_choose_word(hand, word_list)
        print chosen_word    

        # The hand finishes when the computer has exhausted its possible choices
        # (i.e. comp_play_hand returns None).
    
        if chosen_word == None:
            print score        
            return None
    
        # After every valid word: the score for that word is displayed,
        # the remaining letters in the hand are displayed, and the computer 
        # chooses another word.

        score += get_word_score(chosen_word, len(hand))
        print score
        update_hand(hand, chosen_word)

#
# Problem #6C: Playing a game
#
#
def play_game(word_list):
    """Allow the user to play an arbitrary number of hands.

    1) Asks the user to input 'n' or 'r' or 'e'.
    * If the user inputs 'n', play a new (random) hand.
    * If the user inputs 'r', play the last hand again.
    * If the user inputs 'e', exit the game.
    * If the user inputs anything else, ask them again.

    2) Ask the user to input a 'u' or a 'c'.
    * If the user inputs 'u', let the user play the game as before using play_hand.
    * If the user inputs 'c', let the computer play the game using comp_play_hand (created above).
    * If the user inputs anything else, ask them again.

    3) After the computer or user has played the hand, repeat from step 1

    word_list: list (string)
    """
    # TO DO...
    game_on = True
    user_choice = ""
    while game_on == True:
    
        while user_choice.lower() != "r" and user_choice.lower() != "n":
            user_choice = raw_input("N: New Game\nR: Replay\nE: Exit\n>>>")
            
            if user_choice.lower() == "n":
                hand = deal_hand(HAND_SIZE)
                mod_hand = dict(hand)
                player_choice = ""
                
                while player_choice.lower() != "c" and player_choice.lower() != "u":
                    player_choice = raw_input("U: You play\nC: Computer plays\n>>>")
                    
                    if player_choice.lower() == "u":
                        play_hand(mod_hand, load_words())
                        # remove choice and start over
                        user_choice = ""
                        
                    elif player_choice.lower() == "c":
                        comp_play_hand(mod_hand, load_words())
                        # remove choice and start over                        
                        user_choice = ""
                        
            elif user_choice.lower() == "r":
                player_choice = ""
                mod_hand = dict(hand)
                
                while player_choice.lower() != "c" and player_choice.lower() != "u":
                    player_choice = raw_input("U: You play\nC: Computer plays\n>>>")
                    if player_choice.lower() == "u":
                        play_hand(mod_hand, load_words())
                        # remove choice and start over
                        user_choice = ""
                        
                    elif player_choice.lower() == "c":
                        comp_play_hand(mod_hand, load_words())
                        # remove choice and start over                        
                        user_choice = ""
                
            elif user_choice.lower() == "e":
                print "thanks for playing"
                game_on = False
                return

#
# Build data structures used for entire session and play game
#
# Ya, I think I just built them as I went, oops
if __name__ == '__main__':
    word_list = load_words()
    play_game(word_list)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

from ps3a import *

import time

from perm import *

# Problem #6A: Computer chooses a word

def comp_choose_word(hand, word_list):

"""

Given a hand and a word_dict, find the word that gives the maximum value score, and return it.

This word should be calculated by considering all possible permutations of lengths 1 to HAND_SIZE.

hand: dictionary (string -> int)

word_list: list (string)

"""

# TO DO...

all_perms = get_perms(hand, HAND_SIZE)

# store best words here

valid_words = set()

best_words = {}

for i in all_perms:

# check if there is a word that uses full HAND_SIZE

if i in word_list:

# testing

# print i

return i

# walk backwards from end of word, checking if it's in word_list

j = 1

while j < HAND_SIZE:

word = i[:-j]

# watch it work with time.sleep(1)

# print word

if word in word_list:

valid_words.add(word)

# print word, get_word_score(word, len(word))

j += 1

if len(valid_words) == 0:

return None

for i in valid_words:

best_words[get_word_score(i, len(word))] = i

# testing

# print best_words

# for i in sorted(best_words):

# print i

return best_words[max(best_words.keys())]

# Problem #6B: Computer plays a hand

def comp_play_hand(hand, word_list):

"""

Allows the computer to play the given hand, as follows:

* The hand is displayed.

* The computer chooses a word using comp_choose_words(hand, word_dict).

* After every valid word: the score for that word is displayed,

the remaining letters in the hand are displayed, and the computer

chooses another word.

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

* The hand finishes when the computer has exhausted its possible choices (i.e. comp_play_hand returns None).

hand: dictionary (string -> int)

word_list: list (string)

"""

# TO DO ...

# keep score

score = 0

while True:

# The hand is displayed.

display_hand(hand)

# The computer chooses a word using comp_choose_words(hand, word_dict).

chosen_word = comp_choose_word(hand, word_list)

print chosen_word

# The hand finishes when the computer has exhausted its possible choices

# (i.e. comp_play_hand returns None).

if chosen_word == None:

print score

return None

# After every valid word: the score for that word is displayed,

# the remaining letters in the hand are displayed, and the computer

# chooses another word.

score += get_word_score(chosen_word, len(hand))

print score

update_hand(hand, chosen_word)

# Problem #6C: Playing a game

def play_game(word_list):

"""Allow the user to play an arbitrary number of hands.

1) Asks the user to input 'n' or 'r' or 'e'.

* If the user inputs 'n', play a new (random) hand.

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

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

* If the user inputs anything else, ask them again.

2) Ask the user to input a 'u' or a 'c'.

* If the user inputs 'u', let the user play the game as before using play_hand.

* If the user inputs 'c', let the computer play the game using comp_play_hand (created above).

* If the user inputs anything else, ask them again.

3) After the computer or user has played the hand, repeat from step 1

word_list: list (string)

"""

# TO DO...

game_on = True

user_choice = ""

while game_on == True:

while user_choice.lower() != "r" and user_choice.lower() != "n":

user_choice = raw_input("N: New Game\nR: Replay\nE: Exit\n>>>")

if user_choice.lower() == "n":

hand = deal_hand(HAND_SIZE)

mod_hand = dict(hand)

player_choice = ""

while player_choice.lower() != "c" and player_choice.lower() != "u":

player_choice = raw_input("U: You play\nC: Computer plays\n>>>")

if player_choice.lower() == "u":

play_hand(mod_hand, load_words())

# remove choice and start over

user_choice = ""

elif player_choice.lower() == "c":

comp_play_hand(mod_hand, load_words())

# remove choice and start over

user_choice = ""

elif user_choice.lower() == "r":

player_choice = ""

mod_hand = dict(hand)

while player_choice.lower() != "c" and player_choice.lower() != "u":

player_choice = raw_input("U: You play\nC: Computer plays\n>>>")

if player_choice.lower() == "u":

play_hand(mod_hand, load_words())

# remove choice and start over

user_choice = ""

elif player_choice.lower() == "c":

comp_play_hand(mod_hand, load_words())

# remove choice and start over

user_choice = ""

elif user_choice.lower() == "e":

print "thanks for playing"

game_on = False

return

# Build data structures used for entire session and play game

# Ya, I think I just built them as I went, oops

if __name__ == '__main__':

word_list = load_words()

play_game(word_list)

Python: Problem Set 2

Problem set 2 involves two different problems. The first uses successive approximation to find the root of a function. If, like me, you need a refresher on the derivative of a polynomial, try http://www.freemathhelp.com/derivative-of-polynomial.html. The problem is actually broken down into distinct functions to help us get to the final answer.

The second problem is a bit more fun for those that prefer letters over number crunching. Implement your own game of hangman!

Successive Approximation

# Casey Brown
# 6.00 Problem Set 2
#
# Successive Approximation
#

# 30 minutes
def evaluate_poly(poly, x):
    """
    Computes the polynomial function for a given value x. Returns that value.

    Example:
    >>> poly = (0.0, 0.0, 5.0, 9.3, 7.0)    # f(x) = 7x^4 + 9.3x^3 + 5x^2
    >>> x = -13
    >>> print evaluate_poly(poly, x)  # f(-13) = 7(-13)^4 + 9.3(-13)^3 + 5(-13)^2
    180339.9

    poly: tuple of numbers, length > 0
    x: number
    returns: float
    """
    # TO DO ... 
    result = 0
    assert type(poly) == tuple and len(poly) > 0
    for i in range(0, len(poly)):
        result += poly[i] * x**i
        #print "poly[i] = ", poly[i]        
        #print poly[i], "(", x, ")", "^", i
        #print "x**i = ", x**i
        #print "poly[i] * x**i = ", poly[i] * x**i
        
    return result
    
### answer ### print evaluate_poly((0.0, 0.0, 5.0, 9.3, 7.0), -13)

# 30 minutes figuring out derivatives of a poly freemathhelp.com
# 30 minutes implementing code
def compute_deriv(poly):
    """
    Computes and returns the derivative of a polynomial function. If the
    derivative is 0, returns (0.0,).

    Example:
    >>> poly = (-13.39, 0.0, 17.5, 3.0, 1.0)    # x^4 + 3x^3 + 17.5x^2 - 13.39
    >>> print compute_deriv(poly)        # 4x^3 + 9x^2 + 35^x
    (0.0, 35.0, 9.0, 4.0)

    poly: tuple of numbers, length > 0
    returns: tuple of numbers
    """
    # TO DO ... 
    # (x^0, x^1, x^2, etc.) as tuple
    assert type(poly) == tuple and len(poly) > 0
    # print len(poly)
    result = ()
    for i in range(0, len(poly)):
        if poly[i] != 0.0:
            #print "poly[i] = ", poly[i]
            #print "i - 1 = ", i
            #print "poly[i] * (i) = ", poly[i] * (i)
            result += (poly[i]*(i),)
        else:
            continue
        
    return result
    
### answer ### print compute_deriv((-13.39, 0.0, 17.5, 3.0, 1.0))

# 30 minutes on newton's method
# 1 hour implementing
# 1 hour debugging
# falsely evaluated x_0 once, then started method, so I started th -13.xxx
# just start method on x_0, 0.1
def compute_root(poly, x_0, epsilon):
    """
    Uses Newton's method to find and return a root of a polynomial function.
    Returns a tuple containing the root and the number of iterations required
    to get to the root.

    Example:
    >>> poly = (-13.39, 0.0, 17.5, 3.0, 1.0)    #x^4 + 3x^3 + 17.5x^2 - 13.39
    >>> x_0 = 0.1
    >>> epsilon = .0001
    >>> print compute_root(poly, x_0, epsilon)
    (0.80679075379635201, 8.0)

    poly: tuple of numbers, length > 1.
         Represents a polynomial function containing at least one real root.
         The derivative of this polynomial function at x_0 is not 0.
    x_0: float
    epsilon: float > 0
    returns: tuple (float, int)
    """
    # TO DO ...
    x_n = x_0
    count = 0
    while True:
        y = evaluate_poly(poly, x_n)
        z = evaluate_poly(compute_deriv(poly), x_n)
        if ((x_n - y/z) - epsilon) < x_n < ((x_n - y/z) + epsilon):
            return (x_n, count)
        else: 
            x_n = x_n - y / z
            count += 1
            print x_n
        
poly = (-13.39, 0.0, 17.5, 3.0, 1.0)
x_0 = 0.1
print compute_root(poly, x_0, .0001)

100

101

102

103

104

105

106

107

108

109

# Casey Brown

# 6.00 Problem Set 2

# Successive Approximation

# 30 minutes

def evaluate_poly(poly, x):

"""

Computes the polynomial function for a given value x. Returns that value.

Example:

>>> poly = (0.0, 0.0, 5.0, 9.3, 7.0) # f(x) = 7x^4 + 9.3x^3 + 5x^2

>>> x = -13

>>> print evaluate_poly(poly, x) # f(-13) = 7(-13)^4 + 9.3(-13)^3 + 5(-13)^2

180339.9

poly: tuple of numbers, length > 0

x: number

returns: float

"""

# TO DO ...

result = 0

assert type(poly) == tuple and len(poly) > 0

for i in range(0, len(poly)):

result += poly[i] * x**i

#print "poly[i] = ", poly[i]

#print poly[i], "(", x, ")", "^", i

#print "x**i = ", x**i

#print "poly[i] * x**i = ", poly[i] * x**i

return result

### answer ### print evaluate_poly((0.0, 0.0, 5.0, 9.3, 7.0), -13)

# 30 minutes figuring out derivatives of a poly freemathhelp.com

# 30 minutes implementing code

def compute_deriv(poly):

"""

Computes and returns the derivative of a polynomial function. If the

derivative is 0, returns (0.0,).

Example:

>>> poly = (-13.39, 0.0, 17.5, 3.0, 1.0) # x^4 + 3x^3 + 17.5x^2 - 13.39

>>> print compute_deriv(poly) # 4x^3 + 9x^2 + 35^x

(0.0, 35.0, 9.0, 4.0)

poly: tuple of numbers, length > 0

returns: tuple of numbers

"""

# TO DO ...

# (x^0, x^1, x^2, etc.) as tuple

assert type(poly) == tuple and len(poly) > 0

# print len(poly)

result = ()

for i in range(0, len(poly)):

if poly[i] != 0.0:

#print "poly[i] = ", poly[i]

#print "i - 1 = ", i

#print "poly[i] * (i) = ", poly[i] * (i)

result += (poly[i]*(i),)

else:

continue

return result

### answer ### print compute_deriv((-13.39, 0.0, 17.5, 3.0, 1.0))

# 30 minutes on newton's method

# 1 hour implementing

# 1 hour debugging

# falsely evaluated x_0 once, then started method, so I started th -13.xxx

# just start method on x_0, 0.1

def compute_root(poly, x_0, epsilon):

"""

Uses Newton's method to find and return a root of a polynomial function.

Returns a tuple containing the root and the number of iterations required

to get to the root.

Example:

>>> poly = (-13.39, 0.0, 17.5, 3.0, 1.0) #x^4 + 3x^3 + 17.5x^2 - 13.39

>>> x_0 = 0.1

>>> epsilon = .0001

>>> print compute_root(poly, x_0, epsilon)

(0.80679075379635201, 8.0)

poly: tuple of numbers, length > 1.

Represents a polynomial function containing at least one real root.

The derivative of this polynomial function at x_0 is not 0.

x_0: float

epsilon: float > 0

returns: tuple (float, int)

"""

# TO DO ...

x_n = x_0

count = 0

while True:

y = evaluate_poly(poly, x_n)

z = evaluate_poly(compute_deriv(poly), x_n)

if ((x_n - y/z) - epsilon) < x_n < ((x_n - y/z) + epsilon):

return (x_n, count)

else:

x_n = x_n - y / z

count += 1

print x_n

poly = (-13.39, 0.0, 17.5, 3.0, 1.0)

x_0 = 0.1

print compute_root(poly, x_0, .0001)

Hangman

# 6.00 Problem Set 3
# 
# Hangman
#


# -----------------------------------
# Helper code
# (you don't need to understand this helper code)
import random
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)
    # line: string
    line = inFile.readline()
    # wordlist: list of strings
    wordlist = string.split(line)
    print "  ", len(wordlist), "words loaded."
    return wordlist

def choose_word(wordlist):
    """
    wordlist (list): list of words (strings)

    Returns a word from wordlist at random
    """
    return random.choice(wordlist)

# end of helper code
# -----------------------------------

# actually load the dictionary of words and point to it with 
# the wordlist variable so that it can be accessed from anywhere
# in the program
wordlist = load_words()

# your code begins here!
word = choose_word(wordlist)
word_array = list(word)
guesses = 8
won = False
letters_guessed = []

print "The word is ", len(word), " letters long."
guess = []
for i in range(0, len(word)):
    guess.append("_")

while guesses > 0 and won == False:
    print " ".join(guess)
    print "%d guesses left." % guesses
    print "Letters guessed: ", ",".join(letters_guessed)
    letter = raw_input("Pick a letter.\n>>>")
    letters_guessed.append(letter)
    while letter in word_array:
        guess[word_array.index(letter)] = letter
        word_array[word_array.index(letter)] = 0
    
    if word == "".join(guess):
        won = True
    guesses -= 1

if won == True:
    print "Congratulations! The word was %s." % word
    print "You won!\n"
else:
    print "Close! The word was %s." % word
    print "Better luck next time.\n"

# 6.00 Problem Set 3

# Hangman

# -----------------------------------

# Helper code

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

import random

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)

# line: string

line = inFile.readline()

# wordlist: list of strings

wordlist = string.split(line)

print " ", len(wordlist), "words loaded."

return wordlist

def choose_word(wordlist):

"""

wordlist (list): list of words (strings)

Returns a word from wordlist at random

"""

return random.choice(wordlist)

# end of helper code

# -----------------------------------

# actually load the dictionary of words and point to it with

# the wordlist variable so that it can be accessed from anywhere

# in the program

wordlist = load_words()

# your code begins here!

word = choose_word(wordlist)

word_array = list(word)

guesses = 8

won = False

letters_guessed = []

print "The word is ", len(word), " letters long."

guess = []

for i in range(0, len(word)):

guess.append("_")

while guesses > 0 and won == False:

print " ".join(guess)

print "%d guesses left." % guesses

print "Letters guessed: ", ",".join(letters_guessed)

letter = raw_input("Pick a letter.\n>>>")

letters_guessed.append(letter)

while letter in word_array:

guess[word_array.index(letter)] = letter

word_array[word_array.index(letter)] = 0

if word == "".join(guess):

won = True

guesses -= 1

if won == True:

print "Congratulations! The word was %s." % word

print "You won!\n"

else:

print "Close! The word was %s." % word

print "Better luck next time.\n"

Python: Problem Set 1

This week’s problem set involved calculating credit card payments and interest rates over time. The objective comes with three sub-tasks: calculating payments over a fixed period, finding the amount required to pay debt in 12 months through exhaustive enumeration, and improving this second task using binary search.

concepts covered in lecture:

Exhaustive enumeration often the right solution
Break exits only the current loop
If the answer falls outside the range tested, answer won’t be found
E.g. range(0, 100) when answer is negative

Paying the Minimum

beginning_balance = 0
annual_interest_rate = 0
monthly_minimum_rate = 0
paid = 0

# don't forget to convert these from strings
beginning_balance = raw_input("What is your beginning balance?\n")
annual_interest_rate = raw_input("What is your annual interest rate as \
decimal?\n")
monthly_minimum_rate = raw_input("What is the monthly minimum rate as \
decimal?\n")

# really should use decimal not float
beginning_balance = float(beginning_balance)
annual_interest_rate = float(annual_interest_rate)
monthly_minimum_rate = float(monthly_minimum_rate)
paid = float(paid)

# calculate how much will be paid over 12 months
for i in range(1, 13):
print "Month: ", i
print "Beginning balance: $%.2f" % beginning_balance
monthly_minimum_payment = round(float(monthly_minimum_rate *
beginning_balance), 2)
print "Minimum monthly payment: $%.2f" % monthly_minimum_payment
# track how much was paid
paid += monthly_minimum_payment
principle_paid = round(float(monthly_minimum_rate * beginning_balance -
annual_interest_rate / 12 * beginning_balance), 2)
print "Principle paid: $%.2f" % principle_paid
# calculate new balance
beginning_balance = round(float(beginning_balance - principle_paid), 2)
print "Remaining balance: $%.2f" % beginning_balance

print "TOTAL"
print "Total amount paid: $", paid
print "Remaining balance: $", beginning_balance

beginning_balance = 0

annual_interest_rate = 0

monthly_minimum_rate = 0

paid = 0

# don't forget to convert these from strings

beginning_balance = raw_input("What is your beginning balance?\n")

annual_interest_rate = raw_input("What is your annual interest rate as \

decimal?\n")

monthly_minimum_rate = raw_input("What is the monthly minimum rate as \

decimal?\n")

# really should use decimal not float

beginning_balance = float(beginning_balance)

annual_interest_rate = float(annual_interest_rate)

monthly_minimum_rate = float(monthly_minimum_rate)

paid = float(paid)

# calculate how much will be paid over 12 months

for i in range(1, 13):

print "Month: ", i

print "Beginning balance: $%.2f" % beginning_balance

monthly_minimum_payment = round(float(monthly_minimum_rate *

beginning_balance), 2)

print "Minimum monthly payment: $%.2f" % monthly_minimum_payment

# track how much was paid

paid += monthly_minimum_payment

principle_paid = round(float(monthly_minimum_rate * beginning_balance -

annual_interest_rate / 12 * beginning_balance), 2)

print "Principle paid: $%.2f" % principle_paid

# calculate new balance

beginning_balance = round(float(beginning_balance - principle_paid), 2)

print "Remaining balance: $%.2f" % beginning_balance

print "TOTAL"

print "Total amount paid: $", paid

print "Remaining balance: $", beginning_balance

Paying off debt in 12 months

(brute force method)

# Write a program that calculates the minimum fixed monthly payment
# needed in order to pay off a debt within 12 months.
# Assume the interest is compounded monthly.
# The monthly payment must be a mutiple of $10 and same for every month
import math
import decimal

balance = raw_input("What is the total balance on your debt?\n")
balance = float(balance)
yearly_interest = raw_input("What is the interest rate as decimal?\n")
yearly_interest = float(yearly_interest)
monthly_interest = yearly_interest / 12
proposed_payment = 10

print balance, " ", type(balance)
print yearly_interest, " ", type(yearly_interest)
print monthly_interest, " ", type(monthly_interest)

balance_reset = balance
time = 0
paid_reset = 0

while balance > 0:
    balance = balance_reset
    paid = paid_reset
    for i in range(1, 13):
        balance = balance + balance * yearly_interest / 12
        print "Month: %d" % i
        print "Your balance: $%.2f" % balance
        print "Your payment: $%d" % proposed_payment
        balance = balance - proposed_payment
        time = i
        paid += proposed_payment
    proposed_payment += 10
    
print "Paying $%.2f per month will pay your debt in %d" % (proposed_payment - 
        10, time)
print "Final balance: $%.2f" % balance
print "TOTAL PAID: $%.2f" % paid

# Write a program that calculates the minimum fixed monthly payment

# needed in order to pay off a debt within 12 months.

# Assume the interest is compounded monthly.

# The monthly payment must be a mutiple of $10 and same for every month

import math

import decimal

balance = raw_input("What is the total balance on your debt?\n")

balance = float(balance)

yearly_interest = raw_input("What is the interest rate as decimal?\n")

yearly_interest = float(yearly_interest)

monthly_interest = yearly_interest / 12

proposed_payment = 10

print balance, " ", type(balance)

print yearly_interest, " ", type(yearly_interest)

print monthly_interest, " ", type(monthly_interest)

balance_reset = balance

time = 0

paid_reset = 0

while balance > 0:

balance = balance_reset

paid = paid_reset

for i in range(1, 13):

balance = balance + balance * yearly_interest / 12

print "Month: %d" % i

print "Your balance: $%.2f" % balance

print "Your payment: $%d" % proposed_payment

balance = balance - proposed_payment

time = i

paid += proposed_payment

proposed_payment += 10

print "Paying $%.2f per month will pay your debt in %d" % (proposed_payment -

10, time)

print "Final balance: $%.2f" % balance

print "TOTAL PAID: $%.2f" % paid

(binary search method)

# Write the same program with increments of $0.01.
# Find the monthly payment using bounds and bisection search.
# The monthly payment must be the same for every month.
import math
import decimal

balance = raw_input("What is the total balance on your debt?\n")
balance = float(balance)
yearly_interest = raw_input("What is the interest rate as decimal?\n")
yearly_interest = float(yearly_interest)
monthly_interest = yearly_interest / 12
proposed_min = round(balance / 12, 2)
proposed_max = round((balance * (1 + monthly_interest) ** 12) / 12)
proposed_payment = float(proposed_min + proposed_max / 2)

print balance, " ", type(balance)
print yearly_interest, " ", type(yearly_interest)
print monthly_interest, " ", type(monthly_interest)

balance_reset = balance
steps = 0
time = 0
paid_reset = 0

while  balance < -0.04 or balance > 0.04:
    balance = balance_reset
    paid = paid_reset
    steps += 1
    for i in range(1, 13):
        balance = balance + balance * monthly_interest
        #print "Month: %d" % i
        #print "Your balance: $%.2f" % balance
        #print "Your payment: $%.2f" % proposed_payment
        balance = balance - proposed_payment
        time = i
        paid += proposed_payment
    print "Beginning balance was: ", balance_reset
    print "Remaining balance was: ", balance
    print "Proposed payment was: ", proposed_payment
    if balance > 0.04:
        proposed_min = proposed_payment
        proposed_payment = (proposed_min + proposed_max) / 2
    else:
        proposed_max = proposed_payment
        proposed_payment = (proposed_min + proposed_max) / 2
    
print "Paying $%.2f per month will pay your debt in %d months." % (
    proposed_payment - 0.01, time)
print "Final balance: $%.2f" % balance
print "Number of iterations: ", steps
print "TOTAL PAID: $%.2f" % paid

# Write the same program with increments of $0.01.

# Find the monthly payment using bounds and bisection search.

# The monthly payment must be the same for every month.

import math

import decimal

balance = raw_input("What is the total balance on your debt?\n")

balance = float(balance)

yearly_interest = raw_input("What is the interest rate as decimal?\n")

yearly_interest = float(yearly_interest)

monthly_interest = yearly_interest / 12

proposed_min = round(balance / 12, 2)

proposed_max = round((balance * (1 + monthly_interest) ** 12) / 12)

proposed_payment = float(proposed_min + proposed_max / 2)

print balance, " ", type(balance)

print yearly_interest, " ", type(yearly_interest)

print monthly_interest, " ", type(monthly_interest)

balance_reset = balance

steps = 0

time = 0

paid_reset = 0

while balance < -0.04 or balance > 0.04:

balance = balance_reset

paid = paid_reset

steps += 1

for i in range(1, 13):

balance = balance + balance * monthly_interest

#print "Month: %d" % i

#print "Your balance: $%.2f" % balance

#print "Your payment: $%.2f" % proposed_payment

balance = balance - proposed_payment

time = i

paid += proposed_payment

print "Beginning balance was: ", balance_reset

print "Remaining balance was: ", balance

print "Proposed payment was: ", proposed_payment

if balance > 0.04:

proposed_min = proposed_payment

proposed_payment = (proposed_min + proposed_max) / 2

else:

proposed_max = proposed_payment

proposed_payment = (proposed_min + proposed_max) / 2

print "Paying $%.2f per month will pay your debt in %d months." % (

proposed_payment - 0.01, time)

print "Final balance: $%.2f" % balance

print "Number of iterations: ", steps

print "TOTAL PAID: $%.2f" % paid

If you made it this far, thank you for reading. I am aware I should be using decimal types, no floats, for much of the calculation here. I spent too much time trying to get decimal to work and failing, so I used float formatting and moved on.

Critiques and questions are appreciated.