About Me
No description provided.
Classes
|
Class status: Established
Role:
Student
|
.
88% complete
|
Submitted Assignments
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 23, HW 1
# 6.00 Problem Set 12
#
# Name:
# Collaborators:
# Time:
import numpy
import random
import pylab
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.
"""
#
# 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).
"""
self.maxBirthProb = maxBirthProb
self.clearProb = clearProb
def doesClear(self):
"""
Stochastically determines whether this virus is cleared from the
patient's body at a time step.
returns: Using a random number generator (random.random()), this method
returns True if random.random() < self.clearProb and returns
False otherwise.
"""
return random.random() <= self.clearProb
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.
"""
if random.random() <= self.maxBirthProb * (1 - popDensity):
return SimpleVirus(self.maxBirthProb, self.clearProb)
else:
raise 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)
"""
self.viruses = viruses
self.maxPop = maxPop
def getTotalPop(self):
"""
Gets the current total virus population.
returns: The total virus population (an integer)
"""
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)
"""
for particle in self.viruses:
if particle.doesClear():
self.viruses.remove(particle)
self.popDensity = self.getTotalPop()/float(self.maxPop)
for survived in self.viruses:
try:
self.viruses.append(survived.reproduce(self.popDensity))
except:
pass
return self.getTotalPop()
#
# PROBLEM 2
#
def problem2(time_steps):
"""
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.
"""
total_pop = [100]
viruses = []
for num in range(100):
viruses.append(SimpleVirus(0.1, 0.05))
patient = SimplePatient(viruses, 1000)
ctr = 0
while ctr < time_steps:
total_pop.append(patient.update())
ctr += 1
pylab.figure()
pylab.plot(total_pop, 'r-')
pylab.axis([1, time_steps, 1, 1000])
pylab.ylabel('Virus Population')
pylab.xlabel('Time (Hours)')
pylab.title('Virus Population Over Time')
pylab.show()
##problem2(500)
#
# PROBLEM 3
#
class ResistantVirus(SimpleVirus):
"""
Representation of a virus which can have drug resistance.
"""
def __init__(self, maxBirthProb, clearProb, resistances, mutProb):
"""
Initialize a ResistantVirus 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).
resistances: A dictionary of drug names (strings) mapping to the state
of this virus particle's resistance (either True or False) to each drug.
e.g. {'guttagonol':False, 'grimpex':False}, means that this virus
particle is resistant to neither guttagonol nor grimpex.
mutProb: Mutation probability for this virus particle (a float). This is
the probability of the offspring acquiring or losing resistance to a drug.
"""
self.maxBirthProb = maxBirthProb
self.clearProb = clearProb
self.resistances = resistances
self.mutProb = mutProb
def getResistance(self, drug):
"""
Get the state of this virus particle's resistance to a drug. This method
is called by getResistPop() in Patient to determine how many virus
particles have resistance to a drug.
drug: the drug (a string).
returns: True if this virus instance is resistant to the drug, False
otherwise.
"""
return self.resistances[drug]
def reproduce(self, popDensity, activeDrugs):
"""
Stochastically determines whether this virus particle reproduces at a
time step. Called by the update() method in the Patient class.
If the virus particle is not resistant to any drug in activeDrugs,
then it does not reproduce. Otherwise, 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 ResistantVirus (which has the same
maxBirthProb and clearProb values as its parent).
For each drug resistance trait of the virus (i.e. each key of
self.resistances), the offspring has probability 1-mutProb of
inheriting that resistance trait from the parent, and probability
mutProb of switching that resistance trait in the offspring.
For example, if a virus particle is resistant to guttagonol but not
grimpex, and `self.mutProb` is 0.1, then there is a 10% chance that
that the offspring will lose resistance to guttagonol and a 90%
chance that the offspring will be resistant to guttagonol.
There is also a 10% chance that the offspring will gain resistance to
grimpex and a 90% chance that the offspring will not be resistant to
grimpex.
popDensity: the population density (a float), defined as the current
virus population divided by the maximum population
activeDrugs: a list of the drug names acting on this virus particle
(a list of strings).
returns: a new instance of the ResistantVirus 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.
"""
if len(activeDrugs) == 0:
return self.reproduceReg(popDensity)
else:
for drug in activeDrugs:
if self.getResistance(drug):
return self.reproduceReg(popDensity)
raise NoChildException()
def reproduceReg(self, popDensity):
"""
returns: a new instance of the ResistantVirus class representing the
offspring of this virus particle. The child has the same
maxBirthProb and clearProb values as this virus. Raises a
NoChildException if this virus particle does not reproduce.
"""
if random.random() <= self.maxBirthProb * (1 - popDensity):
self.temp = {}
for drug in self.resistances:
if random.random() <= self.mutProb:
self.temp[drug] = not self.resistances[drug]
else:
self.temp[drug] = self.resistances[drug]
return ResistantVirus(self.maxBirthProb, self.clearProb, self.temp, self.mutProb)
else:
raise NoChildException()
class Patient(SimplePatient):
"""
Representation of a patient. The patient is able to take drugs and his/her
virus population can acquire resistance to the drugs he/she takes.
"""
def __init__(self, viruses, maxPop):
"""
Initialization function, saves the viruses and maxPop parameters as
attributes. Also initializes the list of drugs being administered
(which should initially include no drugs).
viruses: the list representing the virus population (a list of
SimpleVirus instances)
maxPop: the maximum virus population for this patient (an integer)
"""
self.viruses = viruses
self.maxPop = maxPop
self.activeDrugs = []
def addPrescription(self, newDrug):
"""
Administer a drug to this patient. After a prescription is added, the
drug acts on the virus population for all subsequent time steps. If the
newDrug is already prescribed to this patient, the method has no effect.
newDrug: The name of the drug to administer to the patient (a string).
postcondition: list of drugs being administered to a patient is updated
"""
if newDrug not in self.activeDrugs:
self.activeDrugs.append(newDrug)
def getPrescriptions(self):
"""
Returns the drugs that are being administered to this patient.
returns: The list of drug names (strings) being administered to this
patient.
"""
return self.activeDrugs
def getResistPop(self, drugResist):
"""
Get the population of virus particles resistant to the drugs listed in
drugResist.
drugResist: Which drug resistances to include in the population (a list
of strings - e.g. ['guttagonol'] or ['guttagonol', 'grimpex'])
returns: the population of viruses (an integer) with resistances to all
drugs in the drugResist list.
"""
self.resistPop = 0
for virus in self.viruses:
self.chk = 0
for drug in drugResist:
if virus.getResistance(drug):
self.chk += 1
if self.chk == len(drugResist):
self.resistPop += 1
return self.resistPop
def getSelectResistPop(self, drug_1, drug_2):
"""
Get the population of virus particles that are resistant to drug_1, but not drug_2
returns: the population of viruses resistant to drug_1, but not drug_2
drug_1 and drug_2: strings
"""
self.selectResistPop = 0
for virus in self.viruses:
if virus.getResistance(drug_1):
if not virus.getResistance(drug_2):
self.selectResistPop += 1
return self.selectResistPop
def update(self):
"""
Update the state of the virus population in this patient for a single
time step. update() should execute these actions in order:
- Determine whether each virus particle survives and update 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.
The listof drugs being administered should be accounted for in the
determination of whether each virus particle reproduces.
returns: the total virus population at the end of the update (an
integer)
"""
for particle in self.viruses:
if particle.doesClear():
self.viruses.remove(particle)
self.popDensity = self.getTotalPop()/float(self.maxPop)
for survived in self.viruses:
try:
self.viruses.append(survived.reproduce(self.popDensity, self.activeDrugs))
except:
pass
return self.getTotalPop()
#
# PROBLEM 4
#
def problem4(time_steps):
"""
Runs simulations and plots graphs for problem 4.
Instantiates a patient, runs a simulation for 150 timesteps, adds
guttagonol, and runs the simulation for an additional 150 timesteps.
total virus population vs. time, and guttagonol-resistant virus population
vs. time are plotted
"""
total_pop = [100]
total_pop_wdrug = []
resistant_pop = [0]
viruses = []
resistances = {'guttagonol':False}
for num in range(100):
viruses.append(ResistantVirus(0.1, 0.05, resistances, .005))
patient = Patient(viruses, 1000)
total_pop, resistant_pop = runResistantUpdates(time_steps, total_pop, resistant_pop, patient)
patient.addPrescription('guttagonol')
total_pop_wdrug.append(total_pop[-1])
total_pop_wdrug, resistant_pop = runResistantUpdates(time_steps, total_pop_wdrug, resistant_pop, patient)
pylab.figure()
pylab.plot(range(0, time_steps + 1), total_pop, 'r-', range(0, 2*time_steps + 1), resistant_pop, 'bo',\
range(time_steps, 2*time_steps + 1), total_pop_wdrug, 'g-')
pylab.legend(('Normal Population Behaviour Without Drug', 'Drug Resistant Population',\
'Population Behaviour After Administering Drug'), loc = 9)
pylab.axis([1, 2*time_steps, 1, 800])
pylab.ylabel('Virus Population')
pylab.xlabel('Time (Hours)')
pylab.title('Virus Population Over Time')
pylab.show()
def runResistantUpdates(time_steps, current_state_pop, resistant_pop, patient):
"""
performs update() using ResistantVirus and Patient
time_steps: number of updates to perform
current_state_pop: a list representing the number of viri in some current state
at each time step
resistant_pop: a list of the total resistant population at each time step
patient: an object of type Patient
"""
drugResist = ['guttagonol']
ctr = 0
while ctr < time_steps:
current_state_pop.append(patient.update())
resistant_pop.append(patient.getResistPop(drugResist))
ctr += 1
return current_state_pop, resistant_pop
##problem4(300)
#
# PROBLEM 5
#
def problem5(number_of_simulations):
"""
Runs simulations and make histograms for problem 5.
Runs multiple simulations to show the relationship between delayed treatment
and patient outcome.
Histograms of final total virus populations are displayed for delays of 300,
150, 75, 0 timesteps (followed by an additional 150 timesteps of
simulation).
"""
delay_list = [300, 150, 75, 35, 0]
pop_dict = {}
for delay in delay_list:
pop_temp_dict = {}
ctr = 0
while ctr < number_of_simulations:
pop_temp_dict[delay, ctr] = runSimulation(delay, 150)
ctr += 1
pop_dict[delay] = pop_temp_dict.values()
for delay in delay_list:
pylab.figure()
pylab.hist(pop_dict[delay], label = 'delay = ' + str(delay))
pylab.legend()
pylab.show()
def runSimulation(time_steps_1, time_steps_2):
"""
Runs simulations of drug administration for a variety of delay times
"""
total_pop = [100]
total_pop_wdrug = []
resistant_pop = [0]
viruses = []
resistances = {'guttagonol':False}
for num in range(100):
viruses.append(ResistantVirus(0.1, 0.05, resistances, .005))
patient = Patient(viruses, 1000)
total_pop, resistant_pop = runResistantUpdates(time_steps_1, total_pop, resistant_pop, patient)
patient.addPrescription('guttagonol')
total_pop_wdrug.append(total_pop[-1])
total_pop_wdrug, resistant_pop = runResistantUpdates(time_steps_2, total_pop_wdrug, resistant_pop, patient)
return total_pop_wdrug[-1]
##problem5(100)
#
# PROBLEM 6
#
def problem6(number_of_simulations):
"""
Runs simulations and make histograms for problem 6.
Runs multiple simulations to show the relationship between administration
of multiple drugs and patient outcome.
Histograms of final total virus populations are displayed for lag times of
150, 75, 0 timesteps between adding drugs (followed by an additional 150
timesteps of simulation).
"""
delay_list = [300, 150, 75, 35, 0]
pop_dict = {}
for delay in delay_list:
pop_temp_dict = {}
ctr = 0
while ctr < number_of_simulations:
pop_temp_dict[delay, ctr] = runSimulation2(150, delay)
ctr += 1
pop_dict[delay] = pop_temp_dict.values()
for delay in delay_list:
pylab.figure()
pylab.hist(pop_dict[delay], label = 'delay = ' + str(delay))
pylab.legend()
pylab.show()
def runResistantUpdates2(time_steps, current_state_pop, resistant_pop, patient):
"""
performs update() using ResistantVirus and Patient
time_steps: number of updates to perform
current_state_pop: a list representing the number of viri in some current state
at each time step
resistant_pop: a list of the total resistant population at each time step
patient: an object of type Patient
"""
drugResist = ['guttagonol', 'grimpex']
ctr = 0
while ctr < time_steps:
current_state_pop.append(patient.update())
resistant_pop.append(patient.getResistPop(drugResist))
ctr += 1
return current_state_pop, resistant_pop
def runSimulation2(time_steps_1, time_steps_2):
"""
Runs simulations of drug administration for a variety of delay times
"""
total_pop = [100]
total_pop_wdrug_1 = []
total_pop_wdrug_2 = []
resistant_pop = [0]
viruses = []
resistances = {'guttagonol':False, 'grimpex':False}
for num in range(100):
viruses.append(ResistantVirus(0.1, 0.05, resistances, .005))
patient = Patient(viruses, 1000)
total_pop, resistant_pop = runResistantUpdates2(time_steps_1, total_pop, resistant_pop, patient)
patient.addPrescription('guttagonol')
total_pop_wdrug_1.append(total_pop[-1])
total_pop_wdrug_1, resistant_pop = runResistantUpdates2(time_steps_2, total_pop_wdrug_1, resistant_pop, patient)
patient.addPrescription('grimpex')
total_pop_wdrug_2.append(total_pop_wdrug_1[-1])
total_pop_wdrug_2, resistant_pop = runResistantUpdates2(time_steps_1, total_pop_wdrug_2, resistant_pop, patient)
## pylab.figure()
## pylab.plot(range(0, time_steps_1 + 1), total_pop, 'r-', range(0, 2*time_steps_1 + 1 + time_steps_2), resistant_pop, 'bo', \
## range(time_steps_1, time_steps_1 + time_steps_2 + 1), total_pop_wdrug_1, 'g-',\
## range(time_steps_1 + time_steps_2, 2*time_steps_1 + 1 + time_steps_2), total_pop_wdrug_2, 'm-')
## pylab.legend(('Normal Population Behaviour Without Drug', 'Drug Resistant Population', 'Population Behaviour After Administering Drug 1',\
## 'Population Behaviour After Administering Drug 2'), loc = 9)
## pylab.axis([1, 2*time_steps_1 + 1 + time_steps_2, 1, 800])
## pylab.ylabel('Virus Population')
## pylab.xlabel('Time (Hours)')
## pylab.title('Virus Population Over Time')
## pylab.show()
return total_pop_wdrug_2[-1]
##runSimulation2(150, 0)
##problem6(50)
#
# PROBLEM 7
#
def problem7():
"""
Run simulations and plot graphs examining the relationship between
administration of multiple drugs and patient outcome.
Plots of total and drug-resistant viruses vs. time are made for a
simulation with a 300 time step delay between administering the 2 drugs and
a simulations for which drugs are administered simultaneously.
"""
delay_list = [300, 0]
pop_dict = {}
for delay in delay_list:
pop_dict[delay] = runSimulation3(150, delay)
for delay in delay_list:
pylab.figure()
pylab.plot(range(0, 151), pop_dict[delay][0], 'r-', range(0, 301 + delay), pop_dict[delay][3], 'bo',\
range(150, 151 + delay), pop_dict[delay][1], 'g-',\
range(150 + delay, 301 + delay), pop_dict[delay][2], 'm-',\
range(0, 301 + delay), pop_dict[delay][5], 'c^',\
range(0, 301 + delay), pop_dict[delay][4], 'kv')
pylab.legend(('Normal Population Behaviour Without Drug', 'Drug Resistant Population', 'Population Behaviour After Administering Drug 1',\
'Population Behaviour After Administering Drug 2', 'Guttagonol Resistant Population', 'Grimpex Resistant Population'), loc = 9)
pylab.axis([1, 301 + delay, 1, 800])
pylab.ylabel('Virus Population')
pylab.xlabel('Time (Hours)')
pylab.title('Virus Population Over Time, Delay = ' + str(delay))
pylab.show()
def runResistantUpdates3(time_steps, current_state_pop, resistant_pop, resistant_gutt_pop, resistant_grim_pop, patient):
"""
performs update() using ResistantVirus and Patient
time_steps: number of updates to perform
current_state_pop: a list representing the number of viri in some current state
at each time step
resistant_pop: a list of the total resistant population at each time step
patient: an object of type Patient
"""
drugResist = ['guttagonol', 'grimpex']
ctr = 0
while ctr < time_steps:
current_state_pop.append(patient.update())
resistant_pop.append(patient.getResistPop(drugResist))
resistant_gutt_pop.append(patient.getSelectResistPop(drugResist[0], drugResist[1]))
resistant_grim_pop.append(patient.getSelectResistPop(drugResist[1], drugResist[0]))
ctr += 1
return current_state_pop, resistant_pop, resistant_gutt_pop, resistant_grim_pop
def runSimulation3(time_steps_1, time_steps_2):
"""
Runs simulations of drug administration for a variety of delay times
"""
total_pop = [100]
total_pop_wdrug_1 = []
total_pop_wdrug_2 = []
resistant_pop = [0]
resistant_grim_pop = [0]
resistant_gutt_pop = [0]
viruses = []
resistances = {'guttagonol':False, 'grimpex':False}
for num in range(100):
viruses.append(ResistantVirus(0.1, 0.05, resistances, .005))
patient = Patient(viruses, 1000)
total_pop, resistant_pop, resistant_gutt_pop, resistant_grim_pop =\
runResistantUpdates3(time_steps_1, total_pop, resistant_pop, resistant_gutt_pop, resistant_grim_pop, patient)
patient.addPrescription('guttagonol')
total_pop_wdrug_1.append(total_pop[-1])
total_pop_wdrug_1, resistant_pop, resistant_gutt_pop, resistant_grim_pop =\
runResistantUpdates3(time_steps_2, total_pop_wdrug_1, resistant_pop, resistant_gutt_pop, resistant_grim_pop, patient)
patient.addPrescription('grimpex')
total_pop_wdrug_2.append(total_pop_wdrug_1[-1])
total_pop_wdrug_2, resistant_pop, resistant_gutt_pop, resistant_grim_pop =\
runResistantUpdates3(time_steps_1, total_pop_wdrug_2, resistant_pop, resistant_gutt_pop, resistant_grim_pop, patient)
## pylab.figure()
## pylab.plot(range(0, time_steps_1 + 1), total_pop, 'r-', range(0, 2*time_steps_1 + 1 + time_steps_2), resistant_pop, 'bo',\
## range(time_steps_1, time_steps_1 + time_steps_2 + 1), total_pop_wdrug_1, 'g-',\
## range(time_steps_1 + time_steps_2, 2*time_steps_1 + 1 + time_steps_2), total_pop_wdrug_2, 'm-',\
## range(0, 2*time_steps_1 + 1 + time_steps_2), resistant_gutt_pop, 'c^',\
## range(0, 2*time_steps_1 + 1 + time_steps_2), resistant_grim_pop, 'kv')
## pylab.legend(('Normal Population Behaviour Without Drug', 'Drug Resistant Population', 'Population Behaviour After Administering Drug 1',\
## 'Population Behaviour After Administering Drug 2', 'Guttagonol Resistant Population', 'Grimpex Resistant Population'), loc = 9)
## pylab.axis([1, 2*time_steps_1 + 1 + time_steps_2, 1, 800])
## pylab.ylabel('Virus Population')
## pylab.xlabel('Time (Hours)')
## pylab.title('Virus Population Over Time')
## pylab.show()
return total_pop, total_pop_wdrug_1, total_pop_wdrug_2, resistant_pop, resistant_gutt_pop, resistant_grim_pop
##problem7()
##runSimulation3(150, 0)
##runSimulation3(150, 300)
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 19, HW 1
# Problem Set 11: Simulating robots
# Name:
# Collaborators:
# Time:
import math
import random
import pylab
##import time
##import ps11_visualize_amended
# === Provided classes
class Position(object):
"""
A Position represents a location in a two-dimensional room.
"""
def __init__(self, x, y):
"""
Initializes a position with coordinates (x, y).
x: a real number indicating the x-coordinate
y: a real number indicating the y-coordinate
"""
self.x = x
self.y = y
def getX(self):
return self.x
def getY(self):
return self.y
def getNewPosition(self, angle, speed):
"""
Computes and returns the new Position after a single clock-tick has
passed, with this object as the current position, and with the
specified angle and speed.
Does NOT test whether the returned position fits inside the room.
angle: integer representing angle in degrees, 0 <= angle < 360
speed: positive float representing speed
Returns: a Position object representing the new position.
"""
old_x, old_y = self.getX(), self.getY()
# Compute the change in position
delta_y = speed * math.sin(math.radians(angle))
delta_x = speed * math.cos(math.radians(angle))
# Add that to the existing position
new_x = old_x + delta_x
new_y = old_y + delta_y
# returns two floats
return new_x, new_y
# === Problems 1 and 2
class RectangularRoom(object):
"""
A RectangularRoom represents a rectangular region containing clean or dirty
tiles.
A room has a width and a height and contains (width * height) tiles. At any
particular time, each of these tiles is either clean or dirty.
"""
def __init__(self, width, height):
"""
Initializes a rectangular room with the specified width and height.
Initially, no tiles in the room have been cleaned.
width: an integer > 0
height: an integer > 0
"""
self.width = width
self.height = height
# represent the state of the floor using a dictionary. If dirty value = 0, clean = 1
self.cleanDict = {}
for fat in range(width):
for tall in range(height):
self.cleanDict[fat, tall] = 0
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 object
"""
self.cleanDict[pos] = 1
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.cleanDict[int(m), int(n)] == 1
def getNumTiles(self):
"""
Return the total number of tiles in the room.
returns: an integer
"""
return self.width*self.height
def getNumCleanedTiles(self):
"""
Return the total number of clean tiles in the room.
returns: an integer
"""
return sum(self.cleanDict.values())
def getRandomPosition(self):
"""
Return a random position inside the room.
returns: a Position object.
"""
return random.choice(self.cleanDict.keys())
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 pos in self.cleanDict
##a = RectangularRoom(5,5)
class BaseRobot(object):
"""
Represents a robot cleaning a particular room.
At all times the robot has a particular position and direction in
the room. The robot also has a fixed speed.
Subclasses of BaseRobot should provide movement strategies by
implementing updatePositionAndClean(), which simulates a single
time-step.
"""
def __init__(self, room, speed):
"""
Initializes a Robot with the given speed in the specified
room. The robot initially has a random direction d and a
random position p in the room.
The direction d is an integer satisfying 0 <= d < 360; it
specifies an angle in degrees.
p is a Position object giving the robot's position.
room: a RectangularRoom object.
speed: a float (speed > 0)
"""
self.room = room
self.speed = float(speed)
self.direction = random.randint(0, 359)
self.position = self.room.getRandomPosition()
def getRobotPosition(self):
"""
Return the position of the robot.
returns: a Position object giving the robot's position.
"""
return self.position
def getRobotDirection(self):
"""
Return the direction of the robot.
returns: an integer d giving the direction of the robot as an angle in
degrees, 0 <= d < 360.
"""
return self.direction
def setRobotPosition(self, position):
"""
Set the position of the robot to POSITION.
position: a Position object.
"""
self.position = position
def setRobotDirection(self, direction):
"""
Set the direction of the robot to DIRECTION.
direction: integer representing an angle in degrees
"""
self.direction = direction
##b = BaseRobot(a, 1)
class Robot(BaseRobot):
"""
A Robot is a BaseRobot with the standard movement strategy.
At each time-step, a Robot attempts to move in its current
direction; when it hits a wall, it chooses a new direction
randomly.
"""
def updatePositionAndClean(self):
"""
Simulate the passage of a single time-step.
Move the robot to a new position and mark the tile it is on as having
been cleaned.
"""
# get new position
self.new_x, self.new_y = Position(self.getRobotPosition()[0], self.getRobotPosition()[1]).getNewPosition(self.getRobotDirection(), self.speed)
# checking for negative establishes left and bottom boundaries
if self.new_x < 0 or self.new_y < 0:
# if the new position is out of the room, change direction and do it again
self.direction = random.randint(0, 359)
self.updatePositionAndClean()
# if it's in the room clean it. int rounds down to whole number.
elif self.room.isPositionInRoom((int(self.new_x), int(self.new_y))):
self.setRobotPosition((self.new_x, self.new_y)) # position must be kept as float, otherwise distance will keep being reset
self.room.cleanTileAtPosition((int(self.new_x), int(self.new_y))) # coordinates are integers. must keep with convention.
else:
# if the new position is out of the room, change direction and do it again
self.direction = random.randint(0, 359)
self.updatePositionAndClean()
##c = Robot(a, 1)
# === Problem 3
def runSimulation(num_robots, width, height, speed, min_coverage, num_trials,
robot_type, visualize):
"""
Runs NUM_TRIALS trials of the simulation and returns a list of
lists, one per trial. The list for a trial has an element for each
timestep of that trial, the value of which is the percentage of
the room that is clean after that timestep. Each trial stops when
MIN_COVERAGE of the room is clean.
The simulation is run with NUM_ROBOTS robots of type ROBOT_TYPE,
each with speed SPEED, in a room of dimensions WIDTH x HEIGHT.
Visualization is turned on when boolean VISUALIZE is set to True.
num_robots: an int (num_robots > 0)
speed: a float (speed > 0)
width: an int (width > 0)
height: an int (height > 0)
min_coverage: a float (0 <= min_coverage <= 1.0)
num_trials: an int (num_trials > 0)
robot_type: class of robot to be instantiated (e.g. Robot or
RandomWalkRobot)
visualize: a boolean (True to turn on visualization)
"""
anim = None
robotDict = {}
simlist = []
trial = 0
while trial < num_trials:
room = RectangularRoom(width, height)
# create a dictionary of numbered robots of length num_robots.
# a list of variables would not work for this task. The variables were
# cleared when passed to runtrial
for ronum in range(num_robots):
robotDict[ronum] = robot_type(room, speed)
if visualize:
anim = ps11_visualize_amended.RobotVisualization(num_robots, width, height)
# append the trial's resultant list to simlist
simlist.append(runtrial(room, robotDict, min_coverage, anim, visualize))
trial += 1 # go to next trial
if visualize:
anim.done()
return simlist
def runtrial(room, robotDict, min_coverage, anim, visualize):
"""Returns the list for one trial run"""
triallist = []
percentclean = 0
totaltiles = room.getNumTiles()
while percentclean < min_coverage:
# run num_robots simultaneously in time step
for robot in robotDict:
robotDict[robot].updatePositionAndClean()
percentclean = round(float(room.getNumCleanedTiles())/totaltiles, 2)
triallist.append(percentclean)
robots = robotDict.values()
if visualize:
anim.update(room, robots)
return triallist
##d = runSimulation(5, 20, 20, 1, .9, 1, Robot, True)
# === Provided function
def computeMeans(list_of_lists):
"""
Returns a list as long as the longest list in LIST_OF_LISTS, where
the value at index i is the average of the values at index i in
all of LIST_OF_LISTS' lists.
Lists shorter than the longest list are padded with their final
value to be the same length.
"""
# Find length of longest list
longest = 0
for lst in list_of_lists:
if len(lst) > longest:
longest = len(lst)
# Get totals
tots = [0]*(longest)
for lst in list_of_lists:
for i in range(longest):
if i < len(lst):
tots[i] += lst[i]
else:
tots[i] += lst[-1]
# Convert tots to an array to make averaging across each index easier
tots = pylab.array(tots)
# Compute means
means = tots/float(len(list_of_lists))
return means
##q = [[ 0.11, 0.22, 0.33],[ 0.11, 0.198, 0.308, 0.396, 0.44 ],[ 0.11, 0.22, 0.33, 0.418, 0.488, 0.536, 0.536, 0.536, 0.536, 0.56 ]]
##p = computeMeans(q)
# === Helper Function
def avgTrialTime(simulation):
"""Returns the average number of time steps (an integer) for a simulation"""
# get the number of trials run
num_lists = float(len(simulation))
total_length = 0
# get the total number of time steps from one trial
for result in simulation:
total_length += len(result)
# return the average number of time steps per trial
return round(total_length/num_lists, 2)
# === Problem 4
def showPlot1():
"""
Produces a plot showing dependence of cleaning time on room size.
"""
roomside = [5, 10, 15, 20, 25]
lengthlist = []
roomarea = []
for side in roomside:
tempsim = runSimulation(3, side, side, 1, .75, 20, Robot, False)
roomarea.append(side*side)
lengthlist.append(avgTrialTime(tempsim))
pylab.figure()
pylab.plot(roomarea, lengthlist)
pylab.axis([25, 650, 0, 350])
pylab.ylabel('Cleaning Time')
pylab.xlabel('Room Area')
pylab.title('Average Time to Clean 75% of Various Room Sizes with 3 Robots')
pylab.show()
##showPlot1()
def showPlot2():
"""
Produces a plot showing dependence of cleaning time on number of robots.
"""
robotlist = list(range(1, 11))
lengthlist = []
for robot in robotlist:
tempsim = runSimulation(robot, 25, 25, 1, .75, 20, Robot, False)
lengthlist.append(avgTrialTime(tempsim))
pylab.figure()
pylab.plot(robotlist,lengthlist, 'ro')
pylab.axis([1, 10, 0, 1000])
pylab.ylabel('Cleaning Time')
pylab.xlabel('Number of Robots')
pylab.title('Average Time to Clean 75% of a 25x25 Room with 1-10 Robots')
pylab.show()
##showPlot2()
def showPlot3():
"""
Produces a plot showing dependence of cleaning time on room shape.
"""
widthlist = [20, 25, 40, 50, 80, 100]
roomlist = []
lengthlist = []
for width in widthlist:
roomlist.append((width, 400/width))
for room in roomlist:
tempsim = runSimulation(2, room[0], room[1], 1, .75, 50, Robot, False)
lengthlist.append(avgTrialTime(tempsim))
pylab.figure()
pylab.plot(widthlist,lengthlist)
pylab.axis([20, 100, 250, 400])
pylab.ylabel('Cleaning Time')
pylab.xlabel('Room Width')
pylab.title('Average Time to Clean 75% of a Various Room Shapes with Same Area using 2 Robots')
pylab.show()
##showPlot3()
def showPlot4():
"""
Produces a plot showing cleaning time vs. percentage cleaned, for
each of 1-5 robots.
"""
lengthDict = {}
x = [25, 40, 55, 70, 85]
for robot in range(1, 6):
templength = []
for coverage in x:
tempsim = runSimulation(robot, 25, 25, 1, coverage/100.0, 20, Robot, False)
templength.append(avgTrialTime(tempsim))
lengthDict[robot] = templength
pylab.figure()
pylab.plot(x, lengthDict[1], 'r', x, lengthDict[2], 'b', x, lengthDict[3], 'g', \
x, lengthDict[4], 'k', x, lengthDict[5], 'y')
pylab.legend(('1 robot', '2 robots', '3 robots', '4 robots', '5 robots'), loc = 2)
pylab.axis([20, 90, 0, 1275])
pylab.ylabel('Mean Cleaning Time')
pylab.xlabel('Percent Cleaned')
pylab.title('Average Time to Clean Various Percentages of a 25x25 Room with 1-5 Robots')
pylab.show()
##showPlot4()
# === Problem 5
class RandomWalkRobot(BaseRobot):
"""
A RandomWalkRobot is a robot with the "random walk" movement
strategy: it chooses a new direction at random after each
time-step.
"""
def updatePositionAndClean(self):
"""
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. Choose a new random direction after each move.
"""
# get new position
self.new_x, self.new_y = Position(self.getRobotPosition()[0], self.getRobotPosition()[1])\
.getNewPosition(self.getRobotDirection(), self.speed)
# checking for negative establishes left and bottom boundaries
if self.new_x < 0 or self.new_y < 0:
# if the new position is out of the room, change direction and do it again
self.direction = random.randint(0, 359)
self.updatePositionAndClean()
# if it's in the room clean it. int rounds down to whole number.
elif self.room.isPositionInRoom((int(self.new_x), int(self.new_y))):
self.setRobotPosition((self.new_x, self.new_y)) # position must be kept as float, otherwise distance will keep being reset
self.room.cleanTileAtPosition((int(self.new_x), int(self.new_y))) # coordinates are integers. must keep with convention.
self.direction = random.randint(0, 359) # choose a random direction after cleaning
else:
# if the new position is out of the room, change direction and do it again
self.direction = random.randint(0, 359)
self.updatePositionAndClean()
##e = runSimulation(1, 20, 20, 1, .9, 1, RandomWalkRobot, True)
# === Problem 6
def showPlot5():
"""
Produces a plot comparing the two robot strategies. Shows the average time
to clean 75% of a 20x20 room as a function of number of robots.
It seems as though the most telling comparison is between the two approaches
is to between time and robot density. For a fixed room area, robot density
translates to number of robots.
RandomWalk is inferior, because it has too much repetition.
"""
robotlist = list(range(1, 11))
lengthlistReg = []
lengthlistRandom = []
for robot in robotlist:
tempsimReg = runSimulation(robot, 20, 20, 1, .75, 20, Robot, False)
tempsimRandom = runSimulation(robot, 20, 20, 1, .75, 20, RandomWalkRobot, False)
lengthlistReg.append(avgTrialTime(tempsimReg))
lengthlistRandom.append(avgTrialTime(tempsimRandom))
pylab.figure()
pylab.plot(robotlist,lengthlistReg, 'ro', robotlist,lengthlistRandom, 'bo')
pylab.axis([1, 10, 0, 1700])
pylab.legend(('NormalWalk' ,'RandomWalk'), loc = 1)
pylab.ylabel('Cleaning Time')
pylab.xlabel('Number of Robots')
pylab.title('Average Time to Clean 75% of a 20x20 Room with 1-10 Robots')
pylab.show()
##showPlot5()
ps_11_visualize_amended
# Problem Set 11:
# Visualization code for simulated robots.
#
# See the problem set for instructions on how to use this code.
import math
import time
from Tkinter import *
class RobotVisualization:
def __init__(self, num_robots, width, height, delay = 0.2):
"Initializes a visualization with the specified parameters."
# Number of seconds to pause after each frame
self.delay = delay
self.max_dim = max(width, height)
self.width = width
self.height = height
self.num_robots = num_robots
# Initialize a drawing surface
self.master = Tk()
self.w = Canvas(self.master, width=500, height=500)
self.w.pack()
self.master.update()
# Draw a backing and lines
x1, y1 = self._map_coords(0, 0)
x2, y2 = self._map_coords(width, height)
self.w.create_rectangle(x1, y1, x2, y2, fill = "white")
# Draw gray squares for dirty tiles
self.tiles = {}
for i in range(width):
for j in range(height):
x1, y1 = self._map_coords(i, j)
x2, y2 = self._map_coords(i + 1, j + 1)
self.tiles[(i, j)] = self.w.create_rectangle(x1, y1, x2, y2,
fill = "gray")
# Draw gridlines
for i in range(width + 1):
x1, y1 = self._map_coords(i, 0)
x2, y2 = self._map_coords(i, height)
self.w.create_line(x1, y1, x2, y2)
for i in range(height + 1):
x1, y1 = self._map_coords(0, i)
x2, y2 = self._map_coords(width, i)
self.w.create_line(x1, y1, x2, y2)
# Draw some status text
self.robots = None
self.text = self.w.create_text(25, 0, anchor=NW,
text=self._status_string(0, 0))
self.time = 0
self.master.update()
def _status_string(self, time, num_clean_tiles):
"Returns an appropriate status string to print."
percent_clean = 100 * num_clean_tiles / (self.width * self.height)
return "Time: %04d; %d tiles (%d%%) cleaned" % \
(time, num_clean_tiles, percent_clean)
def _map_coords(self, x, y):
"Maps grid positions to window positions (in pixels)."
return (250 + 450 * ((x - self.width / 2.0) / self.max_dim),
250 + 450 * ((self.height / 2.0 - y) / self.max_dim))
def _draw_robot(self, position, direction):
"Returns a polygon representing a robot with the specified parameters."
x, y = position[0], position[1]
d1 = direction + 165
d2 = direction - 165
x1, y1 = self._map_coords(x, y)
x2, y2 = self._map_coords(x + 0.6 * math.sin(math.radians(d1)),
y + 0.6 * math.cos(math.radians(d1)))
x3, y3 = self._map_coords(x + 0.6 * math.sin(math.radians(d2)),
y + 0.6 * math.cos(math.radians(d2)))
return self.w.create_polygon([x1, y1, x2, y2, x3, y3], fill="red")
def update(self, room, robots):
"Redraws the visualization with the specified room and robot state."
# Removes a gray square for any tiles have been cleaned.
for i in range(self.width):
for j in range(self.height):
if room.isTileCleaned(i, j):
self.w.delete(self.tiles[(i, j)])
# Delete all existing robots.
if self.robots:
for robot in self.robots:
self.w.delete(robot)
self.master.update_idletasks()
# Draw new robots
self.robots = []
for robot in robots:
pos = robot.getRobotPosition()
x, y = pos[0], pos[1]
x1, y1 = self._map_coords(x - 0.08, y - 0.08)
x2, y2 = self._map_coords(x + 0.08, y + 0.08)
self.robots.append(self.w.create_oval(x1, y1, x2, y2,
fill = "black"))
self.robots.append(
self._draw_robot(robot.getRobotPosition(), robot.getRobotDirection()))
# Update text
self.w.delete(self.text)
self.time += 1
self.text = self.w.create_text(
25, 0, anchor=NW,
text=self._status_string(self.time, room.getNumCleanedTiles()))
self.master.update()
time.sleep(self.delay)
def done(self):
"Indicate that the animation is done so that we allow the user to close the window."
mainloop()
mrphud
1 year ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 18, HW 1
# Backend code for PS10
import random
import string
# Global Constants
VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
HAND_SIZE = 30
SCRABBLE_LETTER_VALUES = {'a': 1, 'b': 3, 'c': 3, 'd': 2, 'e': 1, 'f': 4,
'g': 2, 'h': 4, 'i': 1, 'j': 8, 'k': 5, 'l': 1,
'm': 3, 'n': 1, 'o': 1, 'p': 3, 'q': 10, 'r': 1,
's': 1, 't': 1, 'u': 1, 'v': 4, 'w': 4, 'x': 8,
'y': 4, 'z': 10}
HUMAN_SOLO = 0
HUMAN_VS_HUMAN = 1
HUMAN_VS_COMP = 2
WORDLIST_FILENAME = "words.txt"
def getFrequencyDict(sequence):
"""
Given a sequence of letters, convert the sequence to a dictionary of
letters -> frequencies. Used by containsLetters().
returns: dictionary of letters -> frequencies
"""
freq = {}
for x in sequence:
freq[x] = freq.get(x,0) + 1
return freq
def getWordScore(word):
"""
Computes the score of a word (no bingo bonus is added).
word: The word to score (a string).
returns: score of the word.
"""
score = 0
for ch in word:
score += SCRABBLE_LETTER_VALUES[ch]
if len(word) == HAND_SIZE:
score += 50
return score
#
# Problem 2: Representing a Hand
#
class Hand(object):
def __init__(self, handSize, initialHandDict = None):
"""
Initialize a hand.
handSize: The size of the hand
postcondition: initializes a hand with random set of initial letters.
"""
num_vowels = handSize / 3
if initialHandDict is None:
initialHandDict = {}
for i in range(num_vowels):
x = VOWELS[random.randrange(0,len(VOWELS))]
initialHandDict[x] = initialHandDict.get(x, 0) + 1
for i in range(num_vowels, handSize):
x = CONSONANTS[random.randrange(0,len(CONSONANTS))]
initialHandDict[x] = initialHandDict.get(x, 0) + 1
self.initialSize = handSize
self.handDict = initialHandDict
def update(self, word):
"""
Remove letters in word from this hand.
word: The word (a string) to remove from the hand
postcondition: Letters in word are removed from this hand
"""
for letter in word: # goes through the word
if self.handDict[letter] > 1: # if the number of letters in hand is > 1
self.handDict[letter] = self.handDict.pop(letter) - 1 # the number is reduced by 1
else:
self.handDict.pop(letter) # if less than one, the key:value pair is removed
# pop(key, default = error) removes the key:value pair and displays the value
return self.handDict
def containsLetters(self, letters):
"""
Test if this hand contains the characters required to make the input
string (letters)
returns: True if the hand contains the characters to make up letters,
False otherwise
"""
self.testDict = 0
self.tempDict = self.handDict.copy()
for letter in letters:
if self.tempDict.get(letter, 0) > 0:
self.tempDict[letter] = self.tempDict.pop(letter) - 1
self.testDict += 1
if self.testDict != len(letters):
return False
else:
return True
def isEmpty(self):
"""
Test if there are any more letters left in this hand.
returns: True if there are no letters remaining, False otherwise.
"""
return len(self.handDict) == 0
def __eq__(self, other):
"""
Equality test, for testing purposes
returns: True if this Hand contains the same number of each letter as
the other Hand, False otherwise
"""
return other.handDict == self.handDict
def __str__(self):
"""
Represent this hand as a string
returns: a string representation of this hand
"""
string = ''
for letter in self.handDict.keys():
for j in range(self.handDict[letter]):
string = string + letter + ' '
return string
#
# Problem 3: Representing a Player
#
class Player(object):
"""
General class describing a player.
Stores the player's ID number, hand, and score.
"""
def __init__(self, idNum, hand):
"""
Initialize a player instance.
idNum: integer: 1 for player 1, 2 for player 2. Used in informational
displays in the GUI.
hand: An object of type Hand.
postcondition: This player object is initialized
"""
self.points = 0.
self.idNum = idNum
self.hand = hand
def getHand(self):
"""
Return this player's hand.
returns: the Hand object associated with this player.
"""
return self.hand
def addPoints(self, points):
"""
Add points to this player's total score.
points: the number of points to add to this player's score
postcondition: this player's total score is increased by points
"""
self.points = self.points + points
return self.points
def getPoints(self):
"""
Return this player's total score.
returns: A float specifying this player's score
"""
return self.points
def getIdNum(self):
"""
Return this player's ID number (either 1 for player 1 or
2 for player 2).
returns: An integer specifying this player's ID number.
"""
return self.idNum
def __cmp__(self, other):
"""
Compare players by their scores.
returns: 1 if this player's score is greater than other player's score,
-1 if this player's score is less than other player's score, and 0 if
they're equal.
"""
self.sign = self.getPoints() - other.getPoints()
if self.sign > 0:
return 1
if self.sign < 0:
return -1
else:
return 0
def __str__(self):
"""
Represent this player as a string
returns: a string representation of this player
"""
return 'Player %d\n\nScore: %.2f\n' % \
(self.getIdNum(), self.getPoints())
#
# Problem 4: Representing a Computer Player
#
class ComputerPlayer(Player):
"""
A computer player class.
Does everything a Player does, but can also pick a word using the
PickBestWord method.
"""
def pickBestWord(self, wordlist):
"""
Pick the best word available to the computer player.
returns: The best word (a string), given the computer player's hand and
the wordlist
"""
self.goodwords = []
self.bestword = None
self.bestvalue = 0
for word in wordlist.getList():
if self.hand.containsLetters(word):
self.goodwords.append(word)
for word in self.goodwords:
self.points = getWordScore(word)
if self.points > self.bestvalue:
self.bestvalue = self.points
self.bestword = word
if self.bestword == None:
return '.'
else:
return self.bestword
def playHand(self, callback, wordlist):
"""
Play a hand completely by passing chosen words to the callback
function.
"""
while callback(self.pickBestWord(wordlist)): pass
class HumanPlayer(Player):
"""
A Human player class.
No methods are needed because everything is taken care of by the GUI.
"""
class Wordlist(object):
"""
A word list.
"""
def __init__(self):
"""
Initializes a Wordlist object.
postcondition: words are read in from a file (WORDLIST_FILENAME, a
global constant) and stored as a list.
"""
inputFile = open(WORDLIST_FILENAME)
try:
self.wordlist = []
for line in inputFile:
self.wordlist.append(line.strip().lower())
finally:
inputFile.close()
def containsWord(self, word):
"""
Test whether this wordlist includes word
word: The word to check (a string)
returns: True if word is in this Wordlist, False if word is not in
Wordlist
"""
return word in self.wordlist
def getList(self):
return self.wordlist
class EndHand(Exception): pass
class Game(object):
"""
Stores the state needed to play a round of the word game.
"""
def __init__(self, mode, wordlist):
"""
Initializes a game.
mode: Can be one of three constant values - HUMAN_SOLO, HUMAN_VS_COMP,
and HUMAN_VS_HUMAN
postcondition: Initializes the players nd their hands.
"""
hand = Hand(HAND_SIZE)
hand2 = Hand(HAND_SIZE, hand.handDict.copy())
if mode == HUMAN_SOLO:
self.players = [HumanPlayer(1, hand)]
elif mode == HUMAN_VS_COMP:
self.players = [HumanPlayer(1, hand),
ComputerPlayer(2, hand2)]
elif mode == HUMAN_VS_HUMAN:
self.players = [HumanPlayer(1, hand),
HumanPlayer(2, hand2)]
self.playerIndex = 0
self.wordlist = wordlist
def getCurrentPlayer(self):
"""
Gets the Player object corresponding to the active player.
returns: The active Player object.
"""
return self.players[self.playerIndex]
def nextPlayer(self):
"""
Changes the game state so that the next player is the active player.
postcondition: playerIndex is incremented
"""
if self.playerIndex + 1 < len(self.players):
self.playerIndex = self.playerIndex + 1
return True
else:
return False
def gameOver(self):
"""
Determines if the game is over
returns: True if the playerIndex >= the number of players, False
otherwise
"""
return self.playerIndex >= len(self.players)
def tryWord(self, word):
if word == '.':
raise EndHand()
player = self.getCurrentPlayer()
hand = player.getHand()
if self.wordlist.containsWord(word) and hand.containsLetters(word):
points = getWordScore(word)
player.addPoints(points)
hand.update(word)
if hand.isEmpty():
raise EndHand()
return points
else:
return None
def getWinner(self):
return max(self.players)
def getNumPlayers(self):
return len(self.players)
def isTie(self):
return len(self.players) > 1 and \
self.players[0].getPoints() == self.players[1].getPoints()
def __str__(self):
"""
Convert this game object to a string
returns: the concatenation of the string representation of the players
"""
string = ''
for player in self.players:
string = string + str(player)
return string
mrphud
1 year ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 12, HW 1
#Problem Set 7
# 1) What is the computational complexity of fact0? Explain your answer.
# def fact0(i):
# assert type(i) == int and i >= 0
# if i == 0 or i == 1:
# return 1
# return i * fact0(i-1)
# Constant + f(n-1) = 2*Constant + f(n-2) = n*Constant = linear
# The computational complexity of this recursive function is O(n), where
# n is the input of the function. The function must be called n times in
# order to get to the base case.
# 2) What is the computational complexity of fact1? Explain your answer.
# def fact1(i):
# assert type(i) == int and i >= 0
# res = 1
# while i > 1:
# res = res * i
# i -= 1
# return res
# a + n*b = linear
# The computational complexity of this function is still O(n), where n is
# the input i of the function. This function just uses a while loop to count
# down until base case.
# 3) What is the computational complexity of makeSet? Explain your answer.
# def makeSet(s):
# assert type(s) == str
# res = ''
# for c in s:
# if not c in res:
# res = res + c
# return res
# a + b*n + c = a' + b*n = linear
# The computational complexity of this function should be O(n), where n
# is the length of s. This function passes through the string s and adds
# letters missing from res to res.
# 4) What is the computational complexity of intersect? Explain your answer.
# def intersect(s1, s2):
# assert type(s1) == str and type(s2) == str
# s1 = makeSet(s1)
# s2 = makeSet(s2)
# res = ''
# for e in s1:
# if e in s2:
# res = res + e
# return res
# a + (a' + b*n) + (a'' + b*m) + c*n = d + n*e = linear
# The computational complexity of intersect should be ~O(n), where n
# is the length of s1 and m the length of s2. This function calls two previous
# functions of O(n) and then searches through n to combine the like terms.
# 5) Present a hand simulation of the code below. Describe the value to which each
# identifier is bound after each step of the computation. Note that “s1” and “s2” exist
# in more than one scope.
def swap0(s1, s2):
assert type(s1) == list and type(s2) == list # Checks to see that s1 & s2 are lists
tmp = s1[:] # tmp points to a copy of s1
s1 = s2[:] # s1 now points to a copy of s2
s2 = tmp # s2 points to the same list as tmp
return # returns None. The swap is only done locally
s1 = [1]
s2 = [2]
swap0(s1, s2) # This does nothing
print s1, s2 # prints s1 = [1] and s2 = [2]
# 6) Present a hand simulation of the following code:
def swap1(s1, s2):
assert type(s1) == list and type(s2) == list
return s2, s1 # Returns the inputs, but switched assignment
s1 = [1]
s2 = [2]
s1, s2 = swap1(s1, s2) # The swap is now done globally
print s1, s2 # This will print [2] [1]
# 7) Present a hand simulation of the following code:
def rev(s):
assert type(s) == list
for i in range(len(s)/2): # Scans the list in range 0 to len(s)/2. 1 in this case.
tmp = s[i] # points local variable (tmp) to s[i]
s[i] = s[-(i+1)] # points global s[i] to s[-(i+1)] at end of list
s[-(i+1)] = tmp # points global s[-(i+1)] to original s[i]
s = [1,2,3]
rev(s) # reverses the list s. The function is switching pointer assignments.
print s # prints [3, 2, 1]
mrphud
1 year ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 14, HW 1
# 6.00 Problem Set 8
#
# Intelligent Course Advisor
#
# Name:
# Collaborators:
# Time:
#
import time
SUBJECT_FILENAME = "subjects.txt"
VALUE, WORK = 0, 1
#
# Problem 1: Building A Subject Dictionary
#
def loadSubjects(filename):
"""
Returns a dictionary mapping subject name to (value, work), where the name
is a string and the value and work are integers. The subject information is
read from the file named by the string filename. Each line of the file
contains a string of the form "name,value,work".
returns: dictionary mapping subject name to (value, work)
"""
# The following sample code reads lines from the specified file and prints
# each one.
inputFile = open(filename)
subjectDict = {}
for line in inputFile:
templist = []
templist += line.strip().split(',')
subjectDict[templist[0]] = (int(templist[1]),int(templist[2]))
return subjectDict
def printSubjects(subjects):
"""
Prints a string containing name, value, and work of each subject in
the dictionary of subjects and total value and work of all subjects
"""
totalVal, totalWork = 0,0
if len(subjects) == 0:
return 'Empty SubjectList'
res = 'Course\tValue\tWork\n======\t====\t=====\n'
subNames = subjects.keys()
subNames.sort()
for s in subNames:
val = subjects[s][VALUE]
work = subjects[s][WORK]
res = res + s + '\t' + str(val) + '\t' + str(work) + '\n'
totalVal += val
totalWork += work
res = res + '\nTotal Value:\t' + str(totalVal) +'\n'
res = res + 'Total Work:\t' + str(totalWork) + '\n'
print res
def cmpValue(subInfo1, subInfo2):
"""
Returns True if value in (value, work) tuple subInfo1 is GREATER than
value in (value, work) tuple in subInfo2
"""
val1 = subInfo1[VALUE]
val2 = subInfo2[VALUE]
return val1 > val2
def cmpWork(subInfo1, subInfo2):
"""
Returns True if work in (value, work) tuple subInfo1 is LESS than than work
in (value, work) tuple in subInfo2
"""
work1 = subInfo1[WORK]
work2 = subInfo2[WORK]
return work1 < work2
def cmpRatio(subInfo1, subInfo2):
"""
Returns True if value/work in (value, work) tuple subInfo1 is
GREATER than value/work in (value, work) tuple in subInfo2
"""
val1 = subInfo1[VALUE]
val2 = subInfo2[VALUE]
work1 = subInfo1[WORK]
work2 = subInfo2[WORK]
return float(val1) / work1 > float(val2) / work2
#
# Problem 2: Subject Selection By Greedy Optimization
#
def greedyAdvisor(subjects, maxWork, comparator):
"""
Returns a dictionary mapping subject name to (value, work) which includes
subjects selected by the algorithm, such that the total work of subjects in
the dictionary is not greater than maxWork. The subjects are chosen using
a greedy algorithm. The subjects dictionary should not be mutated.
subjects: dictionary mapping subject name to (value, work)
maxWork: int >= 0
comparator: function taking two tuples and returning a boolean
returns: dictionary mapping subject name to (value, work)
"""
temp_dict = subjects.copy()
select_dict = {}
totalWork = 0
while totalWork < maxWork:
best = temp_dict.keys()[-1]
for i in temp_dict:
if comparator(temp_dict[i], temp_dict[best]):
best = i
if totalWork + temp_dict[best][WORK] <= maxWork:
select_dict[best] = temp_dict.pop(best)
totalWork += select_dict[best][WORK]
else:
break
return select_dict
def bruteForceAdvisor(subjects, maxWork):
"""
Returns a dictionary mapping subject name to (value, work), which
represents the globally optimal selection of subjects using a brute force
algorithm.
subjects: dictionary mapping subject name to (value, work)
maxWork: int >= 0
returns: dictionary mapping subject name to (value, work)
"""
nameList = subjects.keys()
tupleList = subjects.values()
bestSubset, bestSubsetValue = \
bruteForceAdvisorHelper(tupleList, maxWork, 0, None, None, [], 0, 0)
outputSubjects = {}
for i in bestSubset:
outputSubjects[nameList[i]] = tupleList[i]
return outputSubjects
def bruteForceAdvisorHelper(subjects, maxWork, i, bestSubset, bestSubsetValue,
subset, subsetValue, subsetWork):
# Hit the end of the list.
if i >= len(subjects):
if bestSubset == None or subsetValue > bestSubsetValue:
# Found a new best.
return subset[:], subsetValue
else:
# Keep the current best.
return bestSubset, bestSubsetValue
else:
s = subjects[i]
# Try including subjects[i] in the current working subset.
if subsetWork + s[WORK] <= maxWork:
subset.append(i)
bestSubset, bestSubsetValue = bruteForceAdvisorHelper(subjects,
maxWork, i+1, bestSubset, bestSubsetValue, subset,
subsetValue + s[VALUE], subsetWork + s[WORK])
subset.pop()
bestSubset, bestSubsetValue = bruteForceAdvisorHelper(subjects,
maxWork, i+1, bestSubset, bestSubsetValue, subset,
subsetValue, subsetWork)
return bestSubset, bestSubsetValue
#
# Problem 3: Subject Selection By Brute Force
#
def bruteForceTime(maxWork):
"""
Runs tests on bruteForceAdvisor and measures the time required to compute
an answer.
"""
start_time = time.time()
bruteForceAdvisor(subjects, maxWork)
end_time = time.time()
total_time = end_time - start_time
return total_time
# Problem 3 Observations
# ======================
#
# The order of bruteForceAdvisor is clearly exponential in maxWork.
#
# Problem 4: Subject Selection By Dynamic Programming
#
def dpAdvisor(subjects, maxWork):
"""
Returns a dictionary mapping subject name to (value, work) that contains a
set of subjects that provides the maximum value without exceeding maxWork.
subjects: dictionary mapping subject name to (value, work)
maxWork: int >= 0
returns: dictionary mapping subject name to (value, work)
"""
nameList = subjects.keys()
tupleList = subjects.values()
optimal_value, optimal_tuple = dpAdvisorHelper(maxWork, len(subjects)-1, nameList, tupleList, (), {})
optimal_dict = {}
for i in optimal_tuple:
optimal_dict[i] = subjects[i]
return optimal_dict
def dpAdvisorHelper(maxWork, index, nameList, tupleList, best_tuple, memo):
"""
Returns a dictionary mapping subject name to (value, work) that contains a
set of subjects that provides the maximum value without exceeding maxWork.
subjects: dictionary mapping subject name to (value, work)
maxWork: int >= 0
returns: dictionary mapping subject name to (value, work)"""
#try and return the stored solution
try:
return memo[(index, maxWork)][0], memo[(index, maxWork)][1]
except KeyError:
# base case returns nothing if won't fit or the items if it does.
if index == 0:
if tupleList[index][WORK] <= maxWork:
best_tuple += (nameList[index],)
memo[(index, maxWork)] = (tupleList[index][VALUE], best_tuple)
return tupleList[index][VALUE], best_tuple
else:
memo[(index, maxWork)] = (0, best_tuple)
return 0, best_tuple
# if the course won't fit then skip it.
without_value, without_tuple = dpAdvisorHelper(maxWork, index-1, nameList, tupleList, best_tuple, memo)
if tupleList[index][WORK] > maxWork:
memo[(index, maxWork)] = (without_value, without_tuple)
return without_value, without_tuple
# if the course will fit then choose the better value of adding the item or skipping it.
else:
with_value, with_tuple = dpAdvisorHelper(maxWork - tupleList[index][WORK], index-1, nameList, tupleList, best_tuple, memo)
total_with_value = with_value + tupleList[index][VALUE]
if total_with_value > without_value:
best_tuple = with_tuple + (nameList[index],)
memo[(index, maxWork)] = (total_with_value, best_tuple)
return total_with_value, best_tuple
else:
return without_value, without_tuple
#
# Problem 5: Performance Comparison
#
def dpTime(maxWork):
"""
Runs tests on dpAdvisor and measures the time required to compute an
answer.
"""
start_time = time.time()
dpAdvisor(subjects, maxWork)
end_time = time.time()
total_time = end_time - start_time
return total_time
# Problem 5 Observations
# ======================
#
# TODO: write here your observations regarding dpAdvisor's performance and
# how its performance compares to that of bruteForceAdvisor.
subjects = loadSubjects(SUBJECT_FILENAME)
smallset = {'6.00':(16, 8),'1.00':(7,7), '6.01':(5,3), '15.01':(9,6)}
mrphud
1 year ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 16, HW 1
# 6.00 Problem Set 9
#
# Name: Delphi
# Collaborators:
# Time:
from string import *
SUBJECT_FILENAME = "shapes.txt"
class Shape(object):
def area(self):
raise AttributeException("Subclasses should override this method.")
class Square(Shape):
def __init__(self, h):
"""
h: length of side of the square
"""
self.side = float(h)
def area(self):
"""
Returns area of the square
"""
return self.side**2
def __str__(self):
return 'Square with side ' + str(self.side)
def __eq__(self, other):
"""
Two squares are equal if they have the same dimension.
other: object to check for equality
"""
return type(other) == Square and self.side == other.side
class Circle(Shape):
def __init__(self, radius):
"""
radius: radius of the circle
"""
self.radius = float(radius)
def area(self):
"""
Returns approximate area of the circle
"""
return 3.14159*(self.radius**2)
def __str__(self):
return 'Circle with radius ' + str(self.radius)
def __eq__(self, other):
"""
Two circles are equal if they have the same radius.
other: object to check for equality
"""
return type(other) == Circle and self.radius == other.radius
#
# Problem 1: Create the Triangle class
#
class Triangle(Shape):
def __init__(self, base, height):
"""
base: length of triangle base
height: length of triangle height
"""
self.base = float(base)
self.height = float(height)
def area(self):
"""
Returns area of the triangle
"""
return self.base*self.height/2
def __str__(self):
return 'Triangle with base %s and height %s' % (self.base, self.height)
def __eq__(self, other):
"""
Two triangles are equal if they have the same base and height.
other: object to check for equality
"""
return type(other) == Triangle and self.base == other.base and self.height == other.height
#
# Problem 2: Create the ShapeSet class
#
class ShapeSet():
# make sure you use type ShapeSet() when initializing the class. ShapeSet without () won't work.
def __init__(self):
"""
Initialize any needed variables
"""
self.shape = []
self.place = None
def addShape(self, sh):
"""
Add shape sh to the set; no two shapes in the set may be
identical
sh: shape to be added
"""
if type(sh) == Circle or type(sh) == Triangle or type(sh) == Square:
if sh in self.shape:
raise ValueError('Duplicate Entry')
self.shape.append(sh)
else:
raise TypeError('This is not a valid shape')
def __iter__(self):
"""
Return an iterator that allows you to iterate over the set of
shapes, one shape at a time
"""
# This method is called first when using an iterator type
# self.place = 0 resets self.place before self is returned. If not reset, self.place would
# be greater than len(self.shape) and StopIteration would be raised before next() can do anything.
self.place = 0
return self
def next(self):
"""
Returns the object at current location and moves to next object. Allows you to move
to the next object in the list.
"""
# next() is called at each increment of the iterator
if self.place >=len(self.shape):
raise StopIteration
self.place += 1
return self.shape[self.place-1]
def __str__(self, sh):
"""
Return the string representation for a set, which consists of
the string representation of each shape, categorized by type
(circles, then squares, then triangles)
"""
# __str__ in this context is used to print items from self.shape or self.place
return sh
#
# Problem 3: Find the largest shapes in a ShapeSet
#
def findLargest(shapes):
"""
Returns a tuple containing the elements of ShapeSet with the largest area.
shapes: ShapeSet
"""
epsilon = .01
largest = [None]
for i in shapes:
if largest[0] == None:
largest = [i]
else:
sign = i.area() - largest[0].area()
if sign < 0:
pass
else:
if sign < epsilon:
largest.append(i)
if sign > epsilon:
largest = [i]
return tuple(largest)
#
# Problem 4: Read shapes from a file into a ShapeSet
#
def readShapesFromFile(filename):
"""
Retrieves shape information from the given file.
Creates and returns a ShapeSet with the shapes found.
filename: string
"""
inputFile = open(filename)
shapes = ShapeSet()
for line in inputFile:
templist = []
templist += line.strip().split(',')
if len(templist) > 2:
shapes.addShape(Triangle(float(templist[1]), float(templist[2])))
if templist[0] == 'square':
shapes.addShape(Square(float(templist[1])))
else:
shapes.addShape(Circle(float(templist[1])))
return shapes
a = ShapeSet()
b = Circle(1)
c = Square(5)
d = Triangle(4,5)
e = Triangle(5,4)
a.addShape(b)
a.addShape(c)
a.addShape(d)
a.addShape(e)
g = findLargest(a)
k = readShapesFromFile(SUBJECT_FILENAME)
h = findLargest(k)
mrphud
1 year ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 11, HW 1
# 6.00 Problem Set 6
#
# The 6.00 Word Game
#
import random
import string
import time
VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
HAND_SIZE = 7
SCRABBLE_LETTER_VALUES = {'a': 1, 'b': 3, 'c': 3, 'd': 2, 'e': 1, 'f': 4,
'g': 2, 'h': 4, 'i': 1, 'j': 8, 'k': 5, 'l': 1,
'm': 3, 'n': 1, 'o': 1, 'p': 3, 'q': 10, 'r': 1,
's': 1, 't': 1, 'u': 1, 'v': 4, 'w': 4, 'x': 8,
'y': 4, 'z': 10}
# -----------------------------------
# Helper code
# (you don't need to understand this helper code)
WORDLIST_FILENAME = "words.txt"
def load_words():
"""
Returns a list of valid words. Words are strings of lowercase letters.
Depending on the size of the word list, this function may
take a while to finish.
"""
print "Loading word list from file..."
# inFile: file
inFile = open(WORDLIST_FILENAME, 'r', 0)
# wordlist: list of strings
wordlist = []
for line in inFile:
wordlist.append(line.strip().lower())
print " ", len(wordlist), "words loaded."
return wordlist
def get_frequency_dict(sequence):
"""
Returns a dictionary where the keys are elements of the sequence
and the values are integer counts, for the number of times that
an element is repeated in the sequence.
sequence: string or list
return: dictionary
"""
# freqs: dictionary (element_type -> int)
freq = {}
for x in sequence:
freq[x] = freq.get(x,0) + 1
return freq
# (end of helper code)
# -----------------------------------
#
# Problem #1: Scoring a word
#
def get_word_score(word, n):
"""
Returns the score for a word. Assumes the word is a
valid word.
The score for a word is the sum of the points for letters
in the word, plus 50 points if all n letters are used on
the first go.
Letters are scored as in Scrabble; A is worth 1, B is
worth 3, C is worth 3, D is worth 2, E is worth 1, and so on.
word: string (lowercase letters)
returns: int >= 0
"""
score = 0
for letter in word:
score += SCRABBLE_LETTER_VALUES[letter.lower()]
if len(word) == n:
score += 50
return score
#
# Make sure you understand how this function works and what it does!
#
def display_hand(hand):
"""
Displays the letters currently in the hand.
For example:
display_hand({'a':1, 'x':2, 'l':3, 'e':1})
Should print out something like:
a x x l l l e
The order of the letters is unimportant.
hand: dictionary (string -> int)
"""
for letter in hand.keys():
for j in range(hand[letter]):
print letter, # print all on the same line
print # print an empty line
#
# Make sure you understand how this function works and what it does!
#
def deal_hand(n):
"""
Returns a random hand containing n lowercase letters.
At least n/3 the letters in the hand should be VOWELS.
Hands are represented as dictionaries. The keys are
letters and the values are the number of times the
particular letter is repeated in that hand.
n: int >= 0
returns: dictionary (string -> int)
"""
hand={}
num_vowels = n / 3
for i in range(num_vowels):
x = VOWELS[random.randrange(0,len(VOWELS))]
hand[x] = hand.get(x, 0) + 1
for i in range(num_vowels, n):
x = CONSONANTS[random.randrange(0,len(CONSONANTS))]
hand[x] = hand.get(x, 0) + 1
return hand
#
# Problem #2: Update a hand by removing letters
# My function
def update_hand(hand, word):
"""
Assumes that 'hand' has all the letters in word.
In other words, this assumes that however many times
a letter appears in 'word', 'hand' has at least as
many of that letter in it.
Updates the hand: uses up the letters in the given word
and returns the new hand, without those letters in it.
Has no side effects: does not mutate hand.
word: string
hand: dictionary (string -> int)
returns: dictionary (string -> int)
"""
for letter in word: # goes through the word
if hand[letter] > 1: # if the number of letters in hand is > 1
hand[letter] = hand.pop(letter) - 1 # the number is reduced by 1
else:
hand.pop(letter) # if less than one, the key:value pair is removed
# pop(key, default = error) removes the key:value pair and displays the value
return hand
# Their function didn't work with my setup. It only reduced the value(key). It didn't remove
# the key completly. The presence of 'key':0 sent my program into an infinite loop.
##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.
##
## word: string
## hand: dictionary (string -> int)
## returns: dictionary (string -> int)
## """
## freq = get_frequency_dict(word)
## newhand = {}
## for char in hand:
## newhand[char] = hand[char]-freq.get(char,0)
## return newhand
## #return dict( ( c, hand[c] - freq.get(c,0) ) for c in hand )
#
# Problem #3: Test word validity
#
def is_valid_word(word, hand, points_dictionary):
"""
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
"""
freq = get_frequency_dict(word)
for letter in word:
if freq[letter] > hand.get(letter, 0):
return False
return word in points_dictionary
#
# Problem #4: Playing a hand
#
##def play_hand(hand, points_dict):
## """
## Allows the user to play the given hand, as follows:
##
## * The hand is displayed.
##
## * The user may input a word.
##
## * 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
## """
## total_time = 0
## total = 0
## initial_handlen = sum(hand.values())
## while sum(hand.values()) > 0:
## print 'Current Hand:',
## display_hand(hand)
## start_time = time.time() # time to start counting
## good_words = find_all_words(hand, points_dict)
## userWord = pick_best_word(good_words)
## if userWord == '.':
## break
## else:
## isValid = is_valid_word(userWord, hand, points_dict)
## if not isValid:
## print 'Invalid word, please try again.'
## else:
## end_time = time.time() # time to end counting
## time_spent = end_time - start_time
## total_time += time_spent
## try:
## points = round(get_word_score(userWord, initial_handlen)/time_spent, 2)
## except: # just in case the entry time is near 0 seconds
## time_spent = 0.1 # This error pathway sets a minimum time
## print 'It took less than %0.2f seconds to provide an answer' % (time_spent)
## print 'You are too fast. Let\'s say it took at least %0.2f seconds to answer' % (total_time)
## print 'It took %0.2f seconds to provide an answer' % (time_spent)
## # The %0.2f tells python to insert the variable total_time as a floating point
## # that is rounded to the second decimal (hundreths place)
## time_left = time_clock(total_time, time_limit)
## if time_left > 0:
## total += points
## print '%s earned %0.2f points. Total: %0.2f points' % (userWord, points, total)
## print 'You have %0.2f seconds remaining' % (time_left)
## hand = update_hand(hand, userWord)
## else:
## print '%s earned %0.2f points, but ...' % (userWord, points)
## print 'Total time exceeds %s seconds.' % (time_limit)
## break
## print 'Total score: %s points.' % total
#
# Problem #5: Playing a game
# Make sure you understand how this code works!
#
def play_game(points_dictionary):
"""
Allow the user to play an arbitrary number of hands.
* Asks the user to input 'n' or 'r' or 'e'.
* If the user inputs 'n', let the user play a new (random) hand.
When done playing the hand, ask the 'n' or 'e' question again.
* If the user inputs 'r', let the user play the last hand again.
* If the user inputs 'e', exit the game.
* If the user inputs anything else, ask them again.
"""
hand = deal_hand(HAND_SIZE) # random init
while True:
cmd = raw_input('Enter n to deal a new hand, r to replay the last hand, or e to end game: ')
if cmd == 'n':
hand = deal_hand(HAND_SIZE)
play_hand(hand.copy(), points_dictionary)
print
elif cmd == 'r':
play_hand(hand.copy(), points_dictionary)
print
elif cmd == 'e':
break
else:
print "Invalid command."
#
## Problem # 6. Functions used for Problem set 6.
#
def hand_convert_to_list(hand):
""" Converts the dictionary 'hand' into a list of keys*frequency"""
keylist = hand.keys()
number_of_letters = hand_length_count(hand)
temp_dict = hand.copy()
check = False
while not check:
for key in keylist:
if temp_dict[key] > 1:
keylist.append(key)
temp_dict[key] = temp_dict.pop(key) - 1
if len(keylist) == number_of_letters:
check = True
return keylist
def hand_length_count(hand):
"""returns the total number of letters in scrabble dictionary"""
number_of_letters = 0
for letter in hand:
number_of_letters += hand[letter]
return number_of_letters
def find_all_words(hand, points_dict):
"""Return the highest scoring words from points_dict that
can be made with the given hand"""
ctr = sum(hand.values())
good_words = {}
while ctr > 1:
for word in points_dict:
if len(word) == ctr and word_compare(hand, word):
good_words[word] = points_dict[word]
ctr -= 1
if len(good_words) != 0:
return good_words
else:
return '.'
def choose_best_words(good_words):
"""Returns a sub-dictionary of the highest scoring words from find_all_words"""
if good_words == '.':
return '.'
highest = 0
best_words = {}
for word in good_words:
if good_words[word] >= highest:
highest = good_words[word]
best_words[word] = highest
return best_words
def pick_best_word(good_words):
"""Returns highest scoring word from find_all_words"""
if good_words == '.':
return '.'
highest = 0
for word in good_words:
if good_words[word] >= highest:
highest = good_words[word]
best_word = word
return best_word
def get_words_to_points(word_list):
"""Return a dictionary that maps every word in word_list to its point value"""
points_dict = {}
for word in word_list:
points_dict[word] = get_word_score(word, 10)
return points_dict
def word_compare(hand, key):
"""Returns True if key can be made by letters in hand. Returns False otherwise"""
handlist = hand_convert_to_list(hand)
keylist = list(key)
for letter in keylist:
if letter in handlist:
handlist.remove(letter)
else:
return False
return True
def get_time_limit(points_dict, k):
"""Return the time limit for the computer player as a function of the multiplier k.
points_dict should be the same dictionary that is created by get_words_to_points."""
start_time = time.time()
# Do some computation. the only purpose of the computation is so we can figure out
# how long your computer takes to perform a known task.
for word in points_dict:
get_frequency_dict(word)
get_word_score(word, HAND_SIZE)
end_time = time.time()
return (end_time - start_time)*k
def time_clock(time_spent, time_limit):
""" Sets a time limit to a round."""
time_left = time_limit - time_spent
if time_left < 0:
time_left = 0
return time_left
#
## Problem 7. Even Faster Computer Player
#
def rearrange_words(word_list):
""" Returns a dictionary of all words in word_list linked to the sorted letters in the word"""
rearrange_dict = {}
for word in word_list:
rearrangedlist = sorted(word)
rearrangedstring = ''.join(rearrangedlist)
rearrange_dict[rearrangedstring] = word
return rearrange_dict
def get_rearranged_to_points(rearrange_dict):
"""Return a dictionary that maps every sorted string in rearrange_dict to its point value"""
rearrange_points_dict = {}
for sortedstring in rearrange_dict:
rearrange_points_dict[sortedstring] = get_word_score(sortedstring, 10)
return rearrange_points_dict
def play_hand(hand, rearrange_points):
"""
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
"""
total_time = 0
total = 0
initial_handlen = sum(hand.values())
while sum(hand.values()) > 0:
print 'Current Hand:',
display_hand(hand)
start_time = time.time() # time to start counting
userWord = pick_best_word(find_all_words_faster(hand, rearrange_points))
if userWord == '.':
break
else:
isValid = is_valid_word(userWord, hand, rearrange_points)
if not isValid:
print 'Invalid word, please try again.'
else:
end_time = time.time() # time to end counting
time_spent = end_time - start_time
total_time += time_spent
try:
points = round(get_word_score(userWord, initial_handlen)/time_spent, 2)
except: # just in case the entry time is near 0 seconds
time_spent = 0.01 # This error pathway sets a minimum time
print 'It took less than %0.2f seconds to provide an answer' % (time_spent)
print 'You are too fast. Let\'s say it took at least %0.2f seconds to answer' % (time_spent)
points = round(get_word_score(userWord, initial_handlen)/time_spent, 2)
print 'It took %0.2f seconds to provide an answer' % (time_spent)
# The %0.2f tells python to insert the variable total_time as a floating point
# that is rounded to the second decimal (hundreths place)
time_left = time_clock(total_time, time_limit)
if time_left > 0:
total += points
print '%s earned %0.2f points. Total: %0.2f points' % (rearrange_dict[userWord], points, total)
print 'You have %0.2f seconds remaining' % (time_left)
hand = update_hand(hand, userWord)
else:
print '%s earned %0.2f points, but ...' % (userWord, points)
print 'Total time exceeds %s seconds.' % (time_limit)
break
print 'Total score: %s points.' % total
def find_all_words_faster(hand, rearranged_points):
"""Retruns all words that can be made with hand"""
good_words = {}
sortedhandlist = sorted(hand_convert_to_string(hand))
sortedhandstring = ''.join(sortedhandlist)
for word in rearrange_points:
if word in sortedhandstring:
good_words[word] = rearrange_points[word]
if len(good_words) != 0:
return good_words
else:
return '.'
def hand_convert_to_string(hand):
"""Converts the dictionary 'hand' into srtring"""
keylist = hand_convert_to_list(hand)
keyliststring = ''.join(keylist)
return keyliststring
#
# Build data structures used for entire session and play game
#
if __name__ == '__main__':
word_list = load_words()
points_dict = get_words_to_points(word_list)
rearrange_dict = rearrange_words(word_list)
rearrange_points = get_rearranged_to_points(rearrange_dict)
time_limit = get_time_limit(points_dict, k = 1)
play_game(rearrange_points)
#
## Problem #8. Algorithm Analysis
#
# The differences between find_all_words and find_all_words_faster is that find_all_words
# uses a function called word_compare and checks that the len(word) is the same for
# a particular search. word_compare compares letter for letter two words.
# find_all_words_faster only uses a word in dictionary statement which should be O(len(word_list)).
# word_compare is O(len(hand)), because it must go through hand. find_all_words also searches through
# word_list. Because, it also compares word length it must go through ~len(hand) times.
# Thus, the order of find_all_word is O(len(hand)^2*len(wordlist)). Then find_all_words is
# approximately 7*7 = 49 times slower, which is consistent with observed word submission times.
# On a side note. If the ctr feature in find_all_words is removed, the average time to find
# good_words increases by ~0.08 seconds. This may be small, but is consistent.
mrphud
1 year ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 9, HW 2
# Problem Set 5: Ghost
# Name:
# Collaborators:
# Time:
#
import random
# -----------------------------------
# Helper code
# (you don't need to understand this helper code)
import string
WORDLIST_FILENAME = "words.txt"
def load_words():
"""
Returns a list of valid words. Words are strings of lowercase letters.
Depending on the size of the word list, this function may
take a while to finish.
"""
print "Loading word list from file..."
# inFile: file
inFile = open(WORDLIST_FILENAME, 'r', 0)
# wordlist: list of strings
wordlist = []
for line in inFile:
wordlist.append(line.strip().lower())
print " ", len(wordlist), "words loaded."
return wordlist
def get_frequency_dict(sequence):
"""
Returns a dictionary where the keys are elements of the sequence
and the values are integer counts, for the number of times that
an element is repeated in the sequence.
sequence: string or list
return: dictionary
"""
# freqs: dictionary (element_type -> int)
freq = {}
for x in sequence:
freq[x] = freq.get(x,0) + 1
return freq
# (end of helper code)
# -----------------------------------
# Actually load the dictionary of words and point to it with
# the wordlist variable so that it can be accessed from anywhere
# in the program.
def is_word(word, word_list):
"""
Returns True if word is in the word_list. Otherwise, returns False.
Does not mutate word_list.
word: string
hand: dictionary (string -> int)
word_list: list of lowercase strings
"""
return word in word_list
def play_letter(fragment, player):
"""displays the current word fragment and prompts the player to enter
the next word"""
check = False
while not check:
print ''
print 'Current word fragment: %s' % (fragment)
turn = raw_input('Player %i says letter: ' % (player))
test = turn in string.ascii_letters
if test == True and len(turn) == 1:
turn = string.lower(turn)
fragment += turn
check = True
else:
print ''
print turn, 'is not valid'
print 'enter a letter'
return fragment
def is_valid_fragment(fragment, word_list):
for word in word_list:
indx = word.find(fragment)
if indx != -1:
if indx == 0:
return True
return False
def update_player(player):
if player is 1:
player = 2
else:
player = 1
return player
def game_over_word(player, fragment):
print 'Player %s loses, %s is a word' % (player, fragment)
if player == 1:
print 'Player 2 wins!'
else:
print 'Player 1 wins!'
def game_over_fragment(player, fragment):
if player == 1:
print 'Player 1 loses!'
player = 2
else:
print 'Player 2 loses!'
player = 1
print 'There is no word that starts with %s' % (fragment)
print 'Player %s wins!' % (player)
def play_again():
while True:
ask = raw_input('Would you like to play again? (y/n): ')
if ask == 'y':
return True
elif ask == 'n':
break
else:
print 'invalid command'
def play_game(word_list):
"""Runs the game Ghost"""
print 'Welcome to Ghost'
print 'Player 1 goes first.'
frag = ''
player = 1
while True:
frag = play_letter(frag, player)
test1 = is_word(frag, word_list)
test2 = is_valid_fragment(frag, word_list)
if test1 == True:
game_over_word(player, frag)
break
elif test2 == False:
game_over_fragment(player, frag)
break
player = update_player(player)
print ''
print 'GAME OVER - Thanks for playing'
print ''
ask = play_again()
if ask == True:
play_game(word_list)
if __name__ == '__main__':
word_list = load_words()
play_game(word_list)
mrphud
1 year ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 9, HW 1
# Problem Set 5: 6.00 Word Game
# Name: Jordan
# Collaborators: None
# Time: Lots
#
import random
import string
VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
HAND_SIZE = 7
SCRABBLE_LETTER_VALUES = {'a': 1, 'b': 3, 'c': 3, 'd': 2, 'e': 1, 'f': 4, 'g': 2,
'h': 4, 'i': 1, 'j': 8, 'k': 5, 'l': 1, 'm': 3, 'n': 1,
'o': 1, 'p': 3, 'q': 10, 'r': 1, 's': 1, 't': 1, 'u': 1,
'v': 4, 'w': 4, 'x': 8, 'y': 4, 'z': 10}
# -----------------------------------
# Helper code
# (you don't need to understand this helper code)
WORDLIST_FILENAME = "words.txt"
def load_words():
"""
Returns a list of valid words. Words are strings of lowercase letters.
Depending on the size of the word list, this function may
take a while to finish.
"""
print "Loading word list from file..."
# inFile: file
inFile = open(WORDLIST_FILENAME, 'r', 0)
# wordlist: list of strings
wordlist = []
for line in inFile:
wordlist.append(line.strip().lower())
print " ", len(wordlist), "words loaded."
return wordlist
def get_frequency_dict(sequence):
"""
Returns a dictionary where the keys are elements of the sequence
and the values are integer counts, for the number of times that
an element is repeated in the sequence.
sequence: string or list
return: dictionary
"""
# freqs: dictionary (element_type -> int)
freq = {}
for x in sequence:
freq[x] = freq.get(x,0) + 1
return freq
# (end of helper code)
# -----------------------------------
#
# Problem #1: Scoring a word
# Takes a word of n letters or less and adds the associated values
# listed in SCRABBLE_LETTER_VALUES
def get_word_score(word, n):
"""
Returns the score for a word. Assumes the word is a
valid word.
The score for a word is the sum of the points for letters
in the word, plus 50 points if all n letters are used on
the first go.
Letters are scored as in Scrabble; A is worth 1, B is
worth 3, C is worth 3, D is worth 2, E is worth 1, and so on.
word: string (lowercase letters)
returns: int >= 0
"""
# The assert statement below makes use of the string formatting operator %
# To find out more see http://www.python.org/doc/current/lib/module-string.html
assert len(word) <= n, 'There is no way this word came from %s letters.' % (n)
score = 0
ctr = 0
while ctr < len(word):
score += SCRABBLE_LETTER_VALUES[word[ctr]]
ctr += 1
#print score, ctr
if len(word) == n:
score += 50
return score
#
# Make sure you understand how this function works and what it does!
#
def display_hand(hand):
"""
Displays the letters currently in the hand.
For example:
display_hand({'a':1, 'x':2, 'l':3, 'e':1})
Should print out something like:
a x x l l l e
The order of the letters is unimportant.
hand: dictionary (string -> int)
"""
for letter in hand.keys():
for j in range(hand[letter]):
# uses range(value) to determine number of times to print key
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 # uses dictionary get() method
# get(key, default = None). Here 0 is supplied as default.
# If value already exists, the last assignment adds 1 to it.
for i in range(num_vowels, n):
x = CONSONANTS[random.randrange(0,len(CONSONANTS))]
hand[x] = hand.get(x, 0) + 1
return hand
#
# Problem #2: Update a hand by removing letters
#
def update_hand(hand, word):
"""
Assumes that 'hand' has all the letters in word.
In other words, this assumes that however many times
a letter appears in 'word', 'hand' has at least as
many of that letter in it.
Updates the hand: uses up the letters in the given word
and returns the new hand, without those letters in it.
Has no side effects: does not mutate hand.
word: string
hand: dictionary (string -> int)
returns: dictionary (string -> int)
"""
for letter in word: # goes through the word
if hand[letter] > 1: # if the number of letters in hand is > 1
hand[letter] = hand.pop(letter) - 1 # the number is reduced by 1
else:
hand.pop(letter) # if less than one, the key:value pair is removed
# pop(key, default = error) removes the key:value pair and displays the value
return hand
#
# Problem #3: Test word validity
#
def is_valid_word(word, hand, word_list):
"""
Returns True if word is in the word_list and is entirely
composed of letters in the hand. Otherwise, returns False.
Does not mutate hand or word_list.
word: string
hand: dictionary (string -> int)
word_list: list of lowercase strings
"""
# temp_dict = hand points temp_dict to exact dictionary as hand.
# We must not do this or else we will mutate hand.
test_dict = 0
temp_dict = hand.copy() # This notation produces a copy of hand
for letter in word:
if temp_dict.get(letter, 0) > 0:
temp_dict[letter] = temp_dict.pop(letter) - 1
test_dict += 1
# The 'in' operator searches the list for 'word'
test = word in word_list
# Below is another way to search using a for loop.
#present = False
#ctr = 0
#while ctr < len(word_list):
# if word == word_list[ctr]:
# present = True
# break
# else:
# ctr += 1
# clearly the 'in' operator is cleaner.
if test_dict != len(word) or test == False:
return False
else:
return True
#
# Problem #4: Playing a hand
#
def play_hand(hand, word_list):
"""
Allows the user to play the given hand, as follows:
* The hand is displayed.
* The user may input a word.
* An invalid word is rejected, and a message is displayed asking
the user to choose another word.
* When a valid word is entered, it uses up letters from the hand.
* After every valid word: the score for that word and the total
score so far are displayed, the remaining letters in the hand
are displayed, and the user is asked to input another word.
* The sum of the word scores is displayed when the hand finishes.
* The hand finishes when there are no more unused letters.
The user can also finish playing the hand by inputing a single
period (the string '.') instead of a word.
* The final score is displayed.
hand: dictionary (string -> int)
word_list: list of lowercase strings
"""
total = 0
ctr = 0
numoflett = sum(hand.values())
while True:
if len(hand) == 0:
break
print ''
print 'Current Hand:'
display_hand(hand)
print ''
word = str(raw_input('Enter word or .. to end hand: '))
word_check = True
while word_check:
if word == '..':
break
elif is_valid_word(word, hand, word_list) == False:
print word, 'is not a valid word.'
word = str(raw_input('enter new word or .. to quit: '))
else:
word_check = False
if word == '..':
break
new_score = get_word_score(word, numoflett)
print word, 'earned', new_score, 'points'
total += new_score
print 'Total score:', total
hand = update_hand(hand, word)
ctr =+ 1
print 'Total score:', total
#print "play_hand not implemented."
#
# 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 ...
##print "play_game not implemented." # delete this once you've completed Problem #4
##play_hand(deal_hand(HAND_SIZE), word_list) # delete this once you've completed Problem #4
## uncomment the following block of code once you've completed Problem #4
hand = deal_hand(HAND_SIZE) # random init
while True:
cmd = raw_input('Enter n to deal a new hand, r to replay the last hand, or e to end game: ')
if cmd == 'n':
hand = deal_hand(HAND_SIZE)
play_hand(hand.copy(), word_list)
print
elif cmd == 'r':
play_hand(hand.copy(), word_list)
print
elif cmd == 'e':
break
else:
print "Invalid command."
#
# Build data structures used for entire session and play game
#
if __name__ == '__main__':
word_list = load_words()
play_game(word_list)
mrphud
1 year ago
|
|
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 7, HW 1
##Problem #1
#The following function implements a savings model with fixed growthrate
#and retirement contribution.
def nestEggFixed(salary, save, growthRate, years):
"""
- salary: the amount of money you make each year.
- save: the percent of your salary to save in the investment account each
year (an integer between 0 and 100).
- growthRate: the annual percent increase in your investment account (an
integer between 0 and 100).
- years: the number of years to work.
- return: a list whose values are the size of your retirement account at
the end of each year.
"""
retirement = [salary*save*0.01,] #initiate the retirement fund
time = 1 #set the ctr and add variable
new = 0
while time < years:
#time < years because we must have a salary to grow interest
new = retirement[-1]*(1 + 0.01*growthRate) + retirement[0]
retirement.append(new) #computes end of year gain and
time += 1 #adds it to retirment. Start next year
return retirement #return list of growth
def testNestEggFixed():
salary = 10000
save = 10
growthRate = 15
years = 5
savingsRecord = nestEggFixed(salary, save, growthRate, years)
print savingsRecord
# Output should have values close to:
# [1000.0, 2150.0, 3472.5, 4993.375, 6742.3812499999995]
##Problem #2
#The following function implements a savings model with variable growthrate
def nestEggVariable(salary, save, growthRates):
"""
- salary: the amount of money you make each year.
- save: the percent of your salary to save in the investment account each
year (an integer between 0 and 100).
- growthRate: a list of the annual percent increases in your investment
account (integers between 0 and 100).
- return: a list of your retirement account value at the end of each year.
"""
years = len(growthRates)
retirement = [salary*save*0.01,]
for annual in range(1,years):
#it starts at year one, because money can't be added until a salary is earned.
new = retirement[-1]*(1 + 0.01*growthRates[annual]) + retirement[0]
retirement.append(new)
return retirement
def testNestEggVariable():
salary = 10000
save = 10
growthRates = [3, 4, 5, 0, 3]
savingsRecord = nestEggVariable(salary, save, growthRates)
print savingsRecord
# Output should have values close to:
# [1000.0, 2040.0, 3142.0, 4142.0, 5266.2600000000002]
#This shows there is more than one way to skin a cat.
def nestEggVariable2(salary, save, growthRates):
"""
- salary: the amount of money you make each year.
- save: the percent of your salary to save in the investment account each
year (an integer between 0 and 100).
- growthRate: a list of the annual percent increases in your investment
account (integers between 0 and 100).
- return: a list of your retirement account value at the end of each year.
"""
retirement = [salary*save*0.01,] #initiate the retirement fund
years = len(growthRates)
time = 1 #set the ctr
while time < years:
#time must be < years since indexing for lists starts at zero.
new = retirement[-1]*(1 + 0.01*growthRates[time]) + retirement[0]
retirement.append(new) #computes end of year gain and
time += 1 #adds it to retirment. Start next year
return retirement #return list of growth
def testNestEggVariable2():
salary = 10000
save = 10
growthRates = [3, 4, 5, 0, 3]
savingsRecord = nestEggVariable2(salary, save, growthRates)
print savingsRecord
# Output should have values close to:
# [1000.0, 2040.0, 3142.0, 4142.0, 5266.2600000000002]
##Problem #3
#The following function now removes additions to retirement and incorporates constant expenses
def postRetirement(savings, growthRates, expenses):
"""
- savings: the initial amount of money in your savings account.
- growthRate: a list of the annual percent increases in your investment
account (an integer between 0 and 100).
- expenses: the amount of money you plan to spend each year during
retirement.
- return: a list of your retirement account value at the end of each year.
"""
years = len(growthRates) #This function is basically the same from problem #2
retirement = [savings,]
for annual in range(0,years):
new = retirement[-1]*(1 + 0.01*growthRates[annual]) - expenses
retirement.append(new)
return retirement
def testPostRetirement():
savings = 100000
growthRates = [10, 5, 0, 5, 1]
expenses = 30000
savingsRecord = postRetirement(savings, growthRates, expenses)
print savingsRecord
# Output should have values close to:
# [80000.000000000015, 54000.000000000015, 24000.000000000015,
# -4799.9999999999854, -34847.999999999985]
##Problem #4
#Now we try a method that leaves us with zero retirement money upon passing
#This will make use of successive approximation.
def findMaxExpenses(salary, save, preRetireGrowthRates, postRetireGrowthRates,
epsilon):
"""
- salary: the amount of money you make each year.
- save: the percent of your salary to save in the investment account each
year (an integer between 0 and 100).
- preRetireGrowthRates: a list of annual growth percentages on investments
while you are still working.
- postRetireGrowthRates: a list of annual growth percentages on investments
while you are retired.
- epsilon: an upper bound on the absolute value of the amount remaining in
the investment fund at the end of retirement.
"""
retirement = nestEggVariable(salary, save, preRetireGrowthRates)
#This will yield the total money accrued before retirement
ctr = 0 #setting variables for the calculation
high = retirement[-1]
low = 0
expense = (high + low)/2.0 #initial guess
while ctr < 100: #max number of iterations
downturn = postRetirement(retirement[-1], postRetireGrowthRates, expense)
#downturn is the result to check
#print high, '', low, '', expense, '', downturn[-1], '', ctr
if downturn[-1] < 0: #if less than zero we are spending too much
high = expense #therefore reduce the high and check again
expense = (high + low)/2.0
ctr += 1
elif downturn[-1] > 0 and (downturn[-1] - 0) < epsilon:
return expense
#if downturn is positive and has a change less than epsilon we have converged
else: #otherwise we are not spending as much as we can.
low = expense
expense = (high + low)/2.0
ctr += 1
print 'Error: The calculation did not converge' #Just in case
print 'Try reducing the range or increasing the number of iterations'
def testFindMaxExpenses():
salary = 10000
save = 10
preRetireGrowthRates = [3, 4, 5, 0, 3]
postRetireGrowthRates = [10, 5, 0, 5, 1]
epsilon = .001
expenses = findMaxExpenses(salary, save, preRetireGrowthRates,
postRetireGrowthRates, epsilon)
print expenses
# Output should have a value close to:
# 1229.95548986
mrphud
1 year ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 5, HW 1
from string import *
##Problem #1
#We will define a function that returns all instances and appearances of a key string within a target string
#The """string""" provides the user with a short description of the function
def countSubStringMatch(target, key):
"""Returns the locations where the key (string) exists and number of occurances in the target (string)"""
search = True #Setting the state variables
locations = ()
place = 0
while search == True:
result = find(target, key, place) #The find function returns where in the string the key appears
if result != -1 and result != 0: #testing to see if it appears anywhere
locations += (result,) #If id does, add it to the tuple and shift the search
place = result + 1 #starting point
elif result == -1 and locations == (): #NOTE: find returns 0 if you search for an empty string ('') in any target
print key, 'does not exist in', target #or result == 0: can be added to remove the case whe
search = False
elif result == -1 and locations != ():
print 'There are', len(locations), 'places where', key, 'exists.'
print 'They are', locations
search = False
# The recursive function below will only count the number of occurances
def countSubStringMatchRecursive(target, key):
"""Returns the locations where the key (string) exists in the target (string)"""
result = find(target, key) #state variable every time the function is called.
if result != -1: #test for base case:
target = target[result + 1:] #if not then shorten the target string and do it again
return 1 + countSubStringMatchRecursive(target, key) #return 1 + the result of the next iteration
else: #the recursive 'nesting' in the return allows you to 'count' without a counting variable
return 0 #use return 0 vs. None because you can't mix 1
#(the integer result from the above return) with the 'type' None
##Problem #2
#This will modify the first function to return only the tuple with mactched locations
def subStringMatchExact(target, key):
"""Returns the locations where the key (string) exists"""
search = True #Setting the state variables
locations = ()
place = 0
while search == True:
result = find(target, key, place) #The find function returns where in the string the key appears
if result != -1: #testing to see if it appears anywhere. Can add "and result != 0" to remove '' search
locations += (result,) #If id does, add it to the tuple and shift the search
place = result + 1 #starting point
else:
search = False #if result == -1, end the loop and return locations
return locations
##Problem #3
#This will define a function that returns all places where
def constrainedMatchPair(firstMatch, secondMatch, length):
"""returns tuple satisfying the conditions firstMatch + length + 1 = secondMatch"""
replica = () #initializes the tuple variable 'replica'
for i in firstMatch: #sets the value in firstMatch
for j in secondMatch: #scans the values in secondMatch such that
if 1 + length + i == j: #they satisfy this contition
replica += (i,) #if they do, add it to replica. Otherwise continue the loop
return replica #returns the values that satisfy the if statement.
mrphud
1 year ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 3, HW 1
##Problem #1
#We wish to show there are solutions to the eq 6a + 9b + 20c = n
#where n is 50 - 55
n = range(50,56) #create the list for which to check
for i in n: #search the list by setting n
for a in range(0,11): #for some n search a
for b in range(0,8): #for some n, a search b
for c in range(0,4): #for some n, a, b search c
if 6*a + 9*b + 20*c == i: #test if this is true. If yes print. If not do the try the next c
print 'we have a solution!'
print a,b,c, 'yields', i
##Problem #2
#Here we chose to show that if 50 - 55 can be made in exact quantity then so can
#any number greater than 55
newset = range(56,66) #adptation of previous program. simply new set of numbers to check
for i in newset:
for a in range(0,15):
for b in range(0,15):
for c in range(0,5):
if 6*a + 9*b + 20*c == i:
print 'we have a solution!'
print a,b,c, 'yields', i
##Problem 3
#This program will search for the largest value that cannot be made
#in exact quantity
highnum = range(1,50) #range of numbers to check
good = (6,) #initiates the tuple of values that can be found
duds = () #initiates the tuple of values that can't be found
for i in highnum:
for a in range(0,50/6 + 1):
for b in range(0,50/9 + 1):
for c in range(0,50/20 + 1):
if 6*a + 9*b + 20*c == i and i != good[-1]: #search for numbers that can be found and
good += (i,) #put them in good. i != good[-1] checks if
#the value is already in good
n = 1
b = 0 #This added code takes what is not in good and puts it in duds.
while n < 50:
if n != good[b]: #check if it is not in good
duds += (n,) #and put it in dud
n += 1
else:
b += 1 #b is meant to check if there is double counting. it is redundant now that
n += 1 #i != good[-1] is checked
print 'The largest number of McNuggets that cannot be bought in exact quantity is: ' + str(duds[-1])
##Problem #4
#This adaptation performs a search for vaules less than 200 that cannot be found by combinations of 3 separate package sizes
#This is a generalized form of the previous code.
pck1 = input('Enter the smallest of the packages: ')
pck2 = input('Enter the medium of the packages: ')
pck3 = input('Enter the largest of the packages: ')
package = (pck1, pck2, pck3)
print 'The package quantities you chose were', package
good1 = (pck1,)
duds1 = ()
limit = range(1,201)
for i in limit:
for a in range(0, 200/pck1 + 2):
for b in range(0, 200/pck2 + 2):
for c in range(0, 200/pck3 + 2):
if pck1*a + pck2*b + pck3*c == i and i != good1[-1]:
good1 += (i,)
n = 1
b = 0
while n < 201:
if n != good1[b]:
duds1 += (n,)
n += 1
else:
b += 1
n += 1
print 'Given package', package, 'the largest quantity of McNuggets, less that 200, that cannot be bought is: ', duds1[-1]
mrphud
1 year ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 2, HW 1
##Problem #1
#This program computes and prints prime numbers
#The first part generate odd numbers > 1
num = 2
odds = ()
while num < 10000:
if num%2 == 0:
num = num + 1
else:
odds += (num,)
num = num + 1
#The second part is meant to test the subset odds and sort primes into
#the tuple "primes'
primes = (2,) #These are the state variables that start the loop
prime = True
for i in odds: #Here I want to run through all of the numbers in odds
for g in primes: #and divide each odd by all the numbers in the primes list
if i%g ==0:
prime = False #If the test finds the number not to be prime it marks it false
if prime == True: #If the number is prime it will test if the lenght of primes is < 1000
if len(primes) < 1000: #If not it will add the number to primes, if yes it will break the loop
primes += (i,)
else:
break
else:
prime = True #This will reset the prime variable
print 'The 1000th prime is: %d' % primes[-1]
##Problem #2
from math import *
n = input('Please enter the number of primes you wish to sum: ')
num = 2
odds = ()
while num < 10*n:
if num%2 == 0:
num = num + 1
else:
odds += (num,)
num = num + 1
#The second part is meant to test the subset odds and sort primes into
#the tuple "primes'
primes = (2,)
logprimes = (log(2),)
prime = True
for i in odds:
for g in primes:
if i%g ==0:
prime = False
if prime == True: #If the number is prime it will test if the lenght of primes is < n
if len(primes) < n: #If not it will add the number to primes, if yes it will break the loop
primes += (i,)
logprimes += (log(i),)
else:
break
else:
prime = True
sumlogprimes = sum(logprimes[0:-1]) #I wish to comput the sum of log(prime) and the ratio
ratio = sumlogprimes/primes[-1] #of n to the sum of log(prime)
print 'The prime to which you chose to sum is: %d' % primes[-2]
print 'The prime you wish to compare it to is: %d' % primes[-1]
print 'The sum of log(prime) is: ' + str(sumlogprimes)
print 'The ratio of the sum log(prime) to N is: ' + str(ratio)
mrphud
1 year ago
|
|
|
|
|
