About Me
No description provided.
Classes
|
Class status: Established
Role:
Student
|
.
0% complete
|
|
Class status: Established
Role:
Student
|
.
0% complete
|
|
Class status: Established
Role:
Student
|
.
82% complete
|
Submitted Assignments
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 23, HW 1
# 6.00 Problem Set 12
#
# Name: Joe Li
# Collaborators:
# Time: 7:00
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 with probability self.clearProb and otherwise returns
False.
"""
prob = random.random()
if prob < self.clearProb:
return True
else:
return False
def reproduce(self, popDensity):
"""
Stochastically determines whether this virus particle reproduces at a
time step. Called by the update() method in the SimplePatient and
Patient classes. The virus particle reproduces with probability
self.maxBirthProb * (1 - popDensity).
If this virus particle reproduces, then reproduce() creates and returns
the instance of the offspring SimpleVirus (which has the same
maxBirthProb and clearProb values as its parent).
popDensity: the population density (a float), defined as the current
virus population divided by the maximum population.
returns: a new instance of the SimpleVirus class representing the
offspring of this virus particle. The child should have the same
maxBirthProb and clearProb values as this virus. Raises a
NoChildException if this virus particle does not reproduce.
"""
chance = self.maxBirthProb * (1 - popDensity)
prob = random.random()
if prob < chance:
offspring = SimpleVirus(self.maxBirthProb, self.clearProb)
return offspring
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)
"""
health = []
# the list of viruses isn't cleared
offsprings = []
for v in self.viruses:
# append the virus which is able to reproduce to health
if not v.doesClear():
health.append(v)
popDensity = float(len(health))/float(self.maxPop)
assert 0 <= popDensity <=1,'wrong popDensity'
for v in health:
# append the offsprings the viruses reproduce to a list
try:
offsprings.append(v.reproduce(popDensity))
except NoChildException: pass
self.viruses = health + offsprings
# the new viruses list is both list health and list offspring
return len(self.viruses)
#
# PROBLEM 2
#
def problem2():
"""
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.
"""
v = []
pop = []
for i in range(100):
v.append(SimpleVirus(0.1, 0.05))
poorguy = SimplePatient(v, 1000)
for i in range(300):
pop.append(poorguy.update())
pylab.plot(pop)
pylab.xlabel('Time')
pylab.ylabel('Total virus population')
pylab.title('Simulation of viruses reproduction without drug')
pylab.show()
#
# 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.
"""
assert type(maxBirthProb) == type(clearProb) == type(mutProb) == float, 'wrong input type'
assert 0 <= maxBirthProb <= 1, 'maxBirthProb should be in [0,1]'
assert 0 <= clearProb <= 1, 'clearProb should be in [0,1]'
assert 0 <= mutProb <= 1, 'mutProb should be in [0,1]'
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.
"""
for drug in activeDrugs:
if not self.resistances[drug]:
raise NoChildException
chance = self.maxBirthProb * (1 - popDensity)
prob = random.random()
if prob < chance:
# reproduce
child_resistances = {}
for drug in self.resistances:
switch = random.random()
if switch < self.mutProb:
# mutate
child_resistances[drug] = not self.resistances[drug]
else:
# inherit
child_resistances[drug] = self.resistances[drug]
offspring = ResistantVirus(self.maxBirthProb, self.clearProb, child_resistances, self.mutProb)
return offspring
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.prescription = []
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.prescription:
self.prescription.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.prescription
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.
"""
resistpop = 0
for v in self.viruses:
resist_all = True
for drug in drugResist:
if not v.resistances[drug]:
resist_all = False
if resist_all == True:
resistpop += 1
return resistpop
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 list of 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)
"""
health = []
# the list of viruses isn't cleared
offsprings = []
for v in self.viruses:
# append the virus which is able to reproduce to health
if not v.doesClear():
health.append(v)
popDensity = float(len(health))/float(self.maxPop)
assert 0 <= popDensity <=1,'wrong popDensity'
for v in health:
# append the offsprings the viruses reproduce to a list
try:
offsprings.append(v.reproduce(popDensity, self.prescription))
except NoChildException: pass
self.viruses = health + offsprings
# the new viruses list is both list health and list offspring
return len(self.viruses)
#
# PROBLEM 4
#
def problem4():
"""
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
"""
v = []
pop = []
for i in range(100):
v.append(ResistantVirus(0.1, 0.05, {'guttagonol':False}, 0.005))
poorguy = Patient(v, 1000)
poorguy.addPrescription('guttagonol')
for i in range(150):
pop.append(poorguy.update())
pylab.plot(pop)
pylab.xlabel('Time')
pylab.ylabel('Total virus population')
pylab.title('Simulation of viruses reproduction with drug')
pylab.show()
#
# PROBLEM 5
#
def problem5():
"""
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).
"""
tot_trial = 100
delay = [300, 150, 75, 0]
for s in delay:
trial = 0
record = []
for test in range(tot_trial):
trial += 1
v = []
pop = []
for i in range(100):
v.append(ResistantVirus(0.1, 0.05, {'guttagonol':False}, 0.005))
poorguy = Patient(v, 1000)
# instiate patient
for i in range(s):
poorguy.update()
poorguy.addPrescription('guttagonol')
# take meds
for i in range(150):
poorguy.update()
record.append(poorguy.getTotalPop())
# record the final virus population
print 'delay: '+str(s)+' timesteps, Tiral: '+str(trial)
cured = 0
for result in record:
if result <= 50:
cured +=1
curerate = str(float(cured) / len(record) * 100.0) + '%'
pylab.figure()
pylab.hist(record, bins=20, label='Cure rate: '+curerate, facecolor='g')
pylab.legend()
pylab.title('Simulation of viruses reproduction with drug delay '+str(s)+' timesteps')
pylab.xlabel('Total virus population')
pylab.ylabel('Number of patients')
pylab.show()
#
# PROBLEM 6
#
def problem6():
"""
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 = [300, 150, 75, 0]
for s in delay:
trial = 0
record = []
for test in range(30):
trial += 1
v = []
pop = []
for i in range(100):
v.append(ResistantVirus(0.1, 0.05, {'guttagonol':False,'grimpex':False}, 0.005))
poorguy = Patient(v, 1000)
# initiate patient
for i in range(150):
poorguy.update()
poorguy.addPrescription('guttagonol')
# take meds 1
for i in range(s):
poorguy.update()
poorguy.addPrescription('grimpex')
# take meds 2
for i in range(150):
poorguy.update()
record.append(poorguy.getTotalPop())
# record the final virus population
print 'delay: '+str(s)+' timesteps, Tiral: '+str(trial)
cured = 0
for result in record:
if result <= 50:
cured +=1
curerate = str(float(cured) / len(record) * 100.0) + '%'
pylab.figure()
pylab.hist(record, bins=20, label='Cure rate: '+curerate, facecolor='g')
pylab.legend()
pylab.title('Simulation of viruses reproduction with delay '+str(s)+' timesteps between 2 drugs')
pylab.xlabel('Total virus population')
pylab.ylabel('Number of patients')
pylab.show()
#
# 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 = [300, 0]
t = {300:'Simulation of viruses population agianst time \n with a 300 time step delay between administering the 2 drugs',0:'Simulation of viruses population agianst time \n with drugs administered simultaneously'}
for s in delay:
v = []
pop = [] # total virus population
pop1 = [] # the population of guttagonol-resistant virus
pop2 = [] # the population of grimpex- resistant virus
popb = [] # the population of viruses that are resistant to both drugs
for i in range(100):
v.append(ResistantVirus(0.1, 0.05, {'guttagonol':False,'grimpex':False}, 0.005))
poorguy = Patient(v, 1000)
# initiate patient
for i in range(150):
pop.append(poorguy.update())
p1 = 0
p2 = 0
pb = 0
for v in poorguy.viruses:
if v.resistances['guttagonol']: p1 += 1
if v.resistances['grimpex']: p2 += 1
if v.resistances['guttagonol'] and v.resistances['grimpex']: pb += 1
pop1.append(p1)
pop2.append(p2)
popb.append(pb)
poorguy.addPrescription('guttagonol')
# take meds 1
for i in range(s):
pop.append(poorguy.update())
p1 = 0
p2 = 0
pb = 0
for v in poorguy.viruses:
if v.resistances['guttagonol']: p1 += 1
if v.resistances['grimpex']: p2 += 1
if v.resistances['guttagonol'] and v.resistances['grimpex']: pb += 1
pop1.append(p1)
pop2.append(p2)
popb.append(pb)
poorguy.addPrescription('grimpex')
# take meds 2
for i in range(150):
pop.append(poorguy.update())
p1 = 0
p2 = 0
pb = 0
for v in poorguy.viruses:
if v.resistances['guttagonol']: p1 += 1
if v.resistances['grimpex']: p2 += 1
if v.resistances['guttagonol'] and v.resistances['grimpex']: pb += 1
pop1.append(p1)
pop2.append(p2)
popb.append(pb)
pylab.figure()
pylab.plot(pop, label='total')
pylab.plot(pop1, label='guttagonol-resistant virus')
pylab.plot(pop2, label='grimpex- resistant virus')
pylab.plot(popb, label='resistant to both drugs')
pylab.legend(loc=0)
pylab.xlabel('Time')
pylab.ylabel('Virus population')
pylab.title(t[s])
pylab.show()
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 19, HW 1
# 6.00 Problem Set 12
#
# Name: Joe Li
# Collaborators:
# Time: 7:00
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 with probability self.clearProb and otherwise returns
False.
"""
prob = random.random()
if prob < self.clearProb:
return True
else:
return False
def reproduce(self, popDensity):
"""
Stochastically determines whether this virus particle reproduces at a
time step. Called by the update() method in the SimplePatient and
Patient classes. The virus particle reproduces with probability
self.maxBirthProb * (1 - popDensity).
If this virus particle reproduces, then reproduce() creates and returns
the instance of the offspring SimpleVirus (which has the same
maxBirthProb and clearProb values as its parent).
popDensity: the population density (a float), defined as the current
virus population divided by the maximum population.
returns: a new instance of the SimpleVirus class representing the
offspring of this virus particle. The child should have the same
maxBirthProb and clearProb values as this virus. Raises a
NoChildException if this virus particle does not reproduce.
"""
chance = self.maxBirthProb * (1 - popDensity)
prob = random.random()
if prob < chance:
offspring = SimpleVirus(self.maxBirthProb, self.clearProb)
return offspring
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)
"""
health = []
# the list of viruses isn't cleared
offsprings = []
for v in self.viruses:
# append the virus which is able to reproduce to health
if not v.doesClear():
health.append(v)
popDensity = float(len(health))/float(self.maxPop)
assert 0 <= popDensity <=1,'wrong popDensity'
for v in health:
# append the offsprings the viruses reproduce to a list
try:
offsprings.append(v.reproduce(popDensity))
except NoChildException: pass
self.viruses = health + offsprings
# the new viruses list is both list health and list offspring
return len(self.viruses)
#
# PROBLEM 2
#
def problem2():
"""
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.
"""
v = []
pop = []
for i in range(100):
v.append(SimpleVirus(0.1, 0.05))
poorguy = SimplePatient(v, 1000)
for i in range(300):
pop.append(poorguy.update())
pylab.plot(pop)
pylab.xlabel('Time')
pylab.ylabel('Total virus population')
pylab.title('Simulation of viruses reproduction without drug')
pylab.show()
#
# 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.
"""
assert type(maxBirthProb) == type(clearProb) == type(mutProb) == float, 'wrong input type'
assert 0 <= maxBirthProb <= 1, 'maxBirthProb should be in [0,1]'
assert 0 <= clearProb <= 1, 'clearProb should be in [0,1]'
assert 0 <= mutProb <= 1, 'mutProb should be in [0,1]'
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.
"""
for drug in activeDrugs:
if not self.resistances[drug]:
raise NoChildException
chance = self.maxBirthProb * (1 - popDensity)
prob = random.random()
if prob < chance:
# reproduce
child_resistances = {}
for drug in self.resistances:
switch = random.random()
if switch < self.mutProb:
# mutate
child_resistances[drug] = not self.resistances[drug]
else:
# inherit
child_resistances[drug] = self.resistances[drug]
offspring = ResistantVirus(self.maxBirthProb, self.clearProb, child_resistances, self.mutProb)
return offspring
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.prescription = []
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.prescription:
self.prescription.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.prescription
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.
"""
resistpop = 0
for v in self.viruses:
resist_all = True
for drug in drugResist:
if not v.resistances[drug]:
resist_all = False
if resist_all == True:
resistpop += 1
return resistpop
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 list of 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)
"""
health = []
# the list of viruses isn't cleared
offsprings = []
for v in self.viruses:
# append the virus which is able to reproduce to health
if not v.doesClear():
health.append(v)
popDensity = float(len(health))/float(self.maxPop)
assert 0 <= popDensity <=1,'wrong popDensity'
for v in health:
# append the offsprings the viruses reproduce to a list
try:
offsprings.append(v.reproduce(popDensity, self.prescription))
except NoChildException: pass
self.viruses = health + offsprings
# the new viruses list is both list health and list offspring
return len(self.viruses)
#
# PROBLEM 4
#
def problem4():
"""
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
"""
v = []
pop = []
for i in range(100):
v.append(ResistantVirus(0.1, 0.05, {'guttagonol':False}, 0.005))
poorguy = Patient(v, 1000)
poorguy.addPrescription('guttagonol')
for i in range(150):
pop.append(poorguy.update())
pylab.plot(pop)
pylab.xlabel('Time')
pylab.ylabel('Total virus population')
pylab.title('Simulation of viruses reproduction with drug')
pylab.show()
#
# PROBLEM 5
#
def problem5():
"""
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).
"""
tot_trial = 100
delay = [300, 150, 75, 0]
for s in delay:
trial = 0
record = []
for test in range(tot_trial):
trial += 1
v = []
pop = []
for i in range(100):
v.append(ResistantVirus(0.1, 0.05, {'guttagonol':False}, 0.005))
poorguy = Patient(v, 1000)
# instiate patient
for i in range(s):
poorguy.update()
poorguy.addPrescription('guttagonol')
# take meds
for i in range(150):
poorguy.update()
record.append(poorguy.getTotalPop())
# record the final virus population
print 'delay: '+str(s)+' timesteps, Tiral: '+str(trial)
cured = 0
for result in record:
if result <= 50:
cured +=1
curerate = str(float(cured) / len(record) * 100.0) + '%'
pylab.figure()
pylab.hist(record, bins=20, label='Cure rate: '+curerate, facecolor='g')
pylab.legend()
pylab.title('Simulation of viruses reproduction with drug delay '+str(s)+' timesteps')
pylab.xlabel('Total virus population')
pylab.ylabel('Number of patients')
pylab.show()
#
# PROBLEM 6
#
def problem6():
"""
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 = [300, 150, 75, 0]
for s in delay:
trial = 0
record = []
for test in range(30):
trial += 1
v = []
pop = []
for i in range(100):
v.append(ResistantVirus(0.1, 0.05, {'guttagonol':False,'grimpex':False}, 0.005))
poorguy = Patient(v, 1000)
# initiate patient
for i in range(150):
poorguy.update()
poorguy.addPrescription('guttagonol')
# take meds 1
for i in range(s):
poorguy.update()
poorguy.addPrescription('grimpex')
# take meds 2
for i in range(150):
poorguy.update()
record.append(poorguy.getTotalPop())
# record the final virus population
print 'delay: '+str(s)+' timesteps, Tiral: '+str(trial)
cured = 0
for result in record:
if result <= 50:
cured +=1
curerate = str(float(cured) / len(record) * 100.0) + '%'
pylab.figure()
pylab.hist(record, bins=20, label='Cure rate: '+curerate, facecolor='g')
pylab.legend()
pylab.title('Simulation of viruses reproduction with delay '+str(s)+' timesteps between 2 drugs')
pylab.xlabel('Total virus population')
pylab.ylabel('Number of patients')
pylab.show()
#
# 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 = [300, 0]
t = {300:'Simulation of viruses population agianst time \n with a 300 time step delay between administering the 2 drugs',0:'Simulation of viruses population agianst time \n with drugs administered simultaneously'}
for s in delay:
v = []
pop = [] # total virus population
pop1 = [] # the population of guttagonol-resistant virus
pop2 = [] # the population of grimpex- resistant virus
popb = [] # the population of viruses that are resistant to both drugs
for i in range(100):
v.append(ResistantVirus(0.1, 0.05, {'guttagonol':False,'grimpex':False}, 0.005))
poorguy = Patient(v, 1000)
# initiate patient
for i in range(150):
pop.append(poorguy.update())
p1 = 0
p2 = 0
pb = 0
for v in poorguy.viruses:
if v.resistances['guttagonol']: p1 += 1
if v.resistances['grimpex']: p2 += 1
if v.resistances['guttagonol'] and v.resistances['grimpex']: pb += 1
pop1.append(p1)
pop2.append(p2)
popb.append(pb)
poorguy.addPrescription('guttagonol')
# take meds 1
for i in range(s):
pop.append(poorguy.update())
p1 = 0
p2 = 0
pb = 0
for v in poorguy.viruses:
if v.resistances['guttagonol']: p1 += 1
if v.resistances['grimpex']: p2 += 1
if v.resistances['guttagonol'] and v.resistances['grimpex']: pb += 1
pop1.append(p1)
pop2.append(p2)
popb.append(pb)
poorguy.addPrescription('grimpex')
# take meds 2
for i in range(150):
pop.append(poorguy.update())
p1 = 0
p2 = 0
pb = 0
for v in poorguy.viruses:
if v.resistances['guttagonol']: p1 += 1
if v.resistances['grimpex']: p2 += 1
if v.resistances['guttagonol'] and v.resistances['grimpex']: pb += 1
pop1.append(p1)
pop2.append(p2)
popb.append(pb)
pylab.figure()
pylab.plot(pop, label='total')
pylab.plot(pop1, label='guttagonol-resistant virus')
pylab.plot(pop2, label='grimpex- resistant virus')
pylab.plot(popb, label='resistant to both drugs')
pylab.legend(loc=0)
pylab.xlabel('Time')
pylab.ylabel('Virus population')
pylab.title(t[s])
pylab.show()
Joe
1 year ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 18, HW 1
# Problem Set 10
# Name: Joe LI
# Time: 3:00
# 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 c in word:
if self.handDict.get(c, 0) != 0:
self.handDict[c] -= 1
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
"""
copy = self.handDict.copy()
for c in letters:
try:
copy[c] -= 1
if copy[c] < 0:
return False
except:
return False
return True
def isEmpty(self):
"""
Test if there are any more letters left in this hand.
returns: True if there are no letters remaining, False otherwise.
"""
for c in self.handDict:
if self.handDict.get(c, 0) != 0:
return False
return True
def __eq__(self, other):
"""
Equality test, for testing purposes
returns: True if this Hand contains the same number of each letter as
the other Hand, False otherwise
"""
for c in self.handDict:
if self.handDict[c] != other.handDict.get(c, 0):
return False
for c in other.handDict:
if c not in self.handDict:
return False
return True
def __str__(self):
"""
Represent this hand as a string
returns: a string representation of this hand
"""
string = ''
for letter in self.handDict.keys():
for j in range(self.handDict[letter]):
string = string + letter + ' '
return string
#
# Problem 3: Representing a Player
#
class Player(object):
"""
General class describing a player.
Stores the player's ID number, hand, and score.
"""
def __init__(self, idNum, hand):
"""
Initialize a player instance.
idNum: integer: 1 for player 1, 2 for player 2. Used in informational
displays in the GUI.
hand: An object of type Hand.
postcondition: This player object is initialized
"""
self.points = 0.
self.idNum = idNum
self.hand = hand
def getHand(self):
"""
Return this player's hand.
returns: the Hand object associated with this player.
"""
return self.hand
def addPoints(self, points):
"""
Add points to this player's total score.
points: the number of points to add to this player's score
postcondition: this player's total score is increased by points
"""
self.points += points
def getPoints(self):
"""
Return this player's total score.
returns: A float specifying this player's score
"""
return self.points
def getIdNum(self):
"""
Return this player's ID number (either 1 for player 1 or
2 for player 2).
returns: An integer specifying this player's ID number.
"""
return self.idNum
def __cmp__(self, other):
"""
Compare players by their scores.
returns: 1 if this player's score is greater than other player's score,
-1 if this player's score is less than other player's score, and 0 if
they're equal.
"""
if self.points > other.points:
return 1
elif self.points < other.points:
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
"""
points = {}
for word in wordlist.wordlist:
value = 0
for letter in word:
value += SCRABBLE_LETTER_VALUES[letter]
points[word] = value
highest = ''
for word in points:
if self.hand.containsLetters(word):
if highest == '' or points[word]>points[highest]:
highest = word
if highest != '':
return highest
return '.' # no word can be spelled with current hand
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
Joe
1 year ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 16, HW 1
# 6.00 Problem Set 9
#
# Name: Joe Li
# Time: 4:30
from string import *
class Shape(object):
def area(self):
raise AttributeException("Subclasses should override this method.")
class Square(Shape):
def __init__(self, h):
"""
h: length of side of the square
"""
self.side = float(h)
def area(self):
"""
Returns area of the square
"""
return self.side**2
def __str__(self):
return 'Square with side ' + str(self.side)
def __eq__(self, other):
"""
Two squares are equal if they have the same dimension.
other: object to check for equality
"""
return type(other) == Square and self.side == other.side
class Circle(Shape):
def __init__(self, radius):
"""
radius: radius of the circle
"""
self.radius = float(radius)
def area(self):
"""
Returns approximate area of the circle
"""
return 3.14159*(self.radius**2)
def __str__(self):
return 'Circle with radius ' + str(self.radius)
def __eq__(self, other):
"""
Two circles are equal if they have the same radius.
other: object to check for equality
"""
return type(other) == Circle and self.radius == other.radius
#
# Problem 1: Create the Triangle class
#
class Triangle(Shape):
def __init__(self, b, h):
"""
b: base of the triangle
h: height of the triangle
"""
self.base = float(b)
self.height = float(h)
def area(self):
"""
Return area of the triangle
"""
return self.base * self.height / 2
def __str__(self):
return 'Triangle with base ' + str(self.base)+' and height ' + str(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
#
## TO DO: Fill in the following code skeleton according to the
## specifications.
class ShapeSet:
def __init__(self):
"""
Initialize any needed variables
"""
self.shape = []
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 sh not in self.shape:
self.shape.append(sh)
def __iter__(self):
"""
Return an iterator that allows you to iterate over the set of
shapes, one shape at a time
"""
self.place = 0
return self
def next(self):
if self.place >= len(self.shape):
raise StopIteration
self.place += 1
return self.shape[self.place-1]
def __str__(self):
"""
Return the string representation for a set, which consists of
the string representation of each shape, categorized by type
(circles, then squares, then triangles)
"""
p=''
for shape in self.shape:
if type(shape) == Circle:
p += 'Circle with radius ' + str(shape.radius) + '\n'
for shape in self.shape:
if type(shape) == Square:
p += 'Square with side ' + str(shape.side) + '\n'
for shape in self.shape:
if type(shape) == Triangle:
p += 'Triangle with base ' + str(shape.base)+' and height ' + str(shape.height) + '\n'
return p
#
# 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
"""
candidate = []
result = 0
largest = []
for s in shapes:
if s.area() == result:
largest.append(s)
if s.area() > result:
result = s.area()
largest = [s]
largest=tuple(largest)
return largest
##ss = ShapeSet()
##ss.addShape(Triangle(1.2,2.5))
##ss.addShape(Circle(4))
##ss.addShape(Square(3.6))
##ss.addShape(Triangle(1.6,6.4))
##ss.addShape(Circle(2.2))
##largest = findLargest(ss)
##ss = ShapeSet()
##ss.addShape(Triangle(3,8))
##ss.addShape(Circle(1))
##ss.addShape(Triangle(4,6))
##largest = findLargest(ss)
##largest
##t = Triangle(6,6)
##c = Circle(1)
##ss = ShapeSet()
##ss.addShape(t)
##ss.addShape(c)
##largest = findLargest(ss)
#
# 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)
ss = ShapeSet()
for line in inputFile:
shape = line.strip().strip('1234567890,.')
par = line.strip().strip('abcdefghijklmnopqrstuvwxyz,')
if shape == 'circle':
c = Circle(float(par))
ss.addShape(c)
if shape == 'square':
s = Square(float(par))
ss.addShape(s)
if shape == 'triangle':
par = par.split(',')
t = Triangle(float(par[0]),float(par[1]))
ss.addShape(t)
return ss
filename = 'shapes.txt'
Joe
1 year ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 14, HW 1
problem 4 is really tough. I peeked someone else's code. I suggest read more about dynamic programming.
# 6.00 Problem Set 8
#
# Intelligent Course Advisor
#
# Name: Joe Li
# Time: 10:00
#
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)
d={}
for line in inputFile:
line = line.split(',')
subject = line[0]
value = int(line[1])
work = int(line[2].strip())
d[subject]=(value, work)
return d
# TODO: Instead of printing each line, modify the above to parse the name,
# value, and work of each subject and create a dictionary mapping the name
# to the (value, work).
subjects=loadSubjects(SUBJECT_FILENAME)
def printSubjects(subjects):
"""
Prints a string containing name, value, and work of each subject in
the dictionary of subjects and total value and work of all subjects
"""
totalVal, totalWork = 0,0
if len(subjects) == 0:
return 'Empty SubjectList'
res = 'Course\tValue\tWork\n======\t====\t=====\n'
subNames = subjects.keys()
subNames.sort()
for s in subNames:
val = subjects[s][VALUE]
work = subjects[s][WORK]
res = res + s + '\t' + str(val) + '\t' + str(work) + '\n'
totalVal += val
totalWork += work
res = res + '\nTotal Value:\t' + str(totalVal) +'\n'
res = res + 'Total Work:\t' + str(totalWork) + '\n'
print res
def cmpValue(subInfo1, subInfo2):
"""
Returns True if value in (value, work) tuple subInfo1 is GREATER than
value in (value, work) tuple in subInfo2
"""
val1 = subInfo1[VALUE]
val2 = subInfo2[VALUE]
return val1 > val2
def cmpWork(subInfo1, subInfo2):
"""
Returns True if work in (value, work) tuple subInfo1 is LESS than than work
in (value, work) tuple in subInfo2
"""
work1 = subInfo1[WORK]
work2 = subInfo2[WORK]
return work1 < work2
def cmpRatio(subInfo1, subInfo2):
"""
Returns True if value/work in (value, work) tuple subInfo1 is
GREATER than value/work in (value, work) tuple in subInfo2
"""
val1 = subInfo1[VALUE]
val2 = subInfo2[VALUE]
work1 = subInfo1[WORK]
work2 = subInfo2[WORK]
return float(val1) / work1 > float(val2) / work2
#
# Problem 2: Subject Selection By Greedy Optimization
#
def greedyAdvisor(subjects, maxWork, comparator):
"""
Returns a dictionary mapping subject name to (value, work) which includes
subjects selected by the algorithm, such that the total work of subjects in
the dictionary is not greater than maxWork. The subjects are chosen using
a greedy algorithm. The subjects dictionary should not be mutated.
subjects: dictionary mapping subject name to (value, work)
maxWork: int >= 0
comparator: function taking two tuples and returning a bool
returns: dictionary mapping subject name to (value, work)
"""
assert type(subjects) == dict, 'subjects should be dictionary'
assert type(maxWork) == int and maxWork >= 0, 'maxWork should be non-negative int'
work = 0
choice = {}
sub=subjects.copy()
while work < maxWork:
b = []
# b is a list which contains all the best sub in one travserse
for s in sub:
best = True
# assume such subject is the best one
if work + sub[s][WORK] <= maxWork:
# if work load exceeds limit after addition,
# then we don't even consider such subject
for others in sub:
if work + sub[others][WORK] <= maxWork:
# the other subjected must also under the work limit
# otherwise the best may not be found
# because the best may beyond the work limit
if best == True and comparator(sub[others], sub[s]):
# as soon as such subject turns out not the best
# then the comparason is saved
best = False
# if there is another subject better than such one
# such one cannot be the best, skip the following
if best == True:
# if such subject is the best one
choice[s] = sub[s]
# choose this subject
b.append(s)
# delete the subject from dictionary later
# otherwise it will be found again
work += choice[s][WORK]
if b != []:
# if there are best ones found
for d in b:
del sub[d]
# delete them all
else:
# if no best one found, which may be caused by work load limit,
# or there's nothing left in the sub
return choice
# jump out of the loop if work == maxWork
return choice
def bruteForceAdvisor(subjects, maxWork):
"""
Returns a dictionary mapping subject name to (value, work), which
represents the globally optimal selection of subjects using a brute force
algorithm.
subjects: dictionary mapping subject name to (value, work)
maxWork: int >= 0
returns: dictionary mapping subject name to (value, work)
"""
nameList = subjects.keys()
tupleList = subjects.values()
bestSubset, bestSubsetValue = \
bruteForceAdvisorHelper(tupleList, maxWork, 0, None, None, [], 0, 0)
outputSubjects = {}
for i in bestSubset:
outputSubjects[nameList[i]] = tupleList[i]
return outputSubjects
def bruteForceAdvisorHelper(subjects, maxWork, i, bestSubset, bestSubsetValue,
subset, subsetValue, subsetWork):
# Hit the end of the list.
if i >= len(subjects):
if bestSubset == None or subsetValue > bestSubsetValue:
# Found a new best.
return subset[:], subsetValue
else:
# Keep the current best.
return bestSubset, bestSubsetValue
else:
s = subjects[i]
# Try including subjects[i] in the current working subset.
if subsetWork + s[WORK] <= maxWork:
subset.append(i)
bestSubset, bestSubsetValue = bruteForceAdvisorHelper(subjects,
maxWork, i+1, bestSubset, bestSubsetValue, subset,
subsetValue + s[VALUE], subsetWork + s[WORK])
subset.pop()
bestSubset, bestSubsetValue = bruteForceAdvisorHelper(subjects,
maxWork, i+1, bestSubset, bestSubsetValue, subset,
subsetValue, subsetWork)
return bestSubset, bestSubsetValue
#
# Problem 3: Subject Selection By Brute Force
#
def bruteForceTime():
"""
Runs tests on bruteForceAdvisor and measures the time required to compute
an answer.
"""
for maxWork in range(9):
start_time = time.time()
bruteForceAdvisor(subjects, maxWork)
end_time = time.time()
time_used = round(end_time - start_time,3)
print 'maxWork:', maxWork, 'time:', time_used
# Problem 3 Observations
# ======================
#
# maxWork time_used(s)
# maxWork: 0 time: 0.001
# maxWork: 1 time: 0.004
# maxWork: 2 time: 0.015
# maxWork: 3 time: 0.058
# maxWork: 4 time: 0.193
# maxWork: 5 time: 0.689
# maxWork: 6 time: 2.008
# maxWork: 7 time: 6.106
# maxWork: 8 time: 16.679
#
# 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)
"""
name, v, w = extract(subjects)
subIndex = range(len(subjects))
workCap = range(maxWork+1)
A = {}
# A[(subIndex, workCap)]: int - given subjects in name[0:subIndex]
# and work load limit workCap, the best value we can get
B = {}
# B[(subIndex, workCap)]: list - all the subjects chosen to get the above value
for i in subIndex:
# set base case
A[(i, 0)] = 0
B[(i, 0)] = []
for j in workCap:
A[(0, j)] = 0
B[(0, j)] = []
for i in subIndex[1:]:
# base case excluded
for j in workCap[1:]:
if w[i] > j:
# if work load limit exeeds, don't take it
A[(i, j)] = A[(i - 1,j)]
B[(i, j)] = B[(i - 1,j)]
else:
if v[i] + A[(i - 1, j - w[i])] > A[(i - 1 ,j)]:
# if worth taking it, take it and store the choice to B
A[(i, j)] = v[i] + A[(i - 1, j - w[i])]
B[(i, j)] = B[(i - 1, j - w[i])]+[name[i]]
else:
# if not worth taking it, don't take it
A[(i, j)] = A[(i - 1, j)]
B[(i, j)] = B[(i - 1,j)]
output={}
for name in B[(len(subjects)-1,maxWork)]:
# to get the form as same as subjects
output[name] = (subjects[name][VALUE], subjects[name][WORK])
return output
def extract(subjects):
"""
input: type(subjects) == dict subjects[name] = (VALUE, WORK)
output: name[i] = name, value[i] = VALUE, work[i] = WORK
"""
name=[]
value=[]
work=[]
for j in subjects:
name.append(j)
value.append(subjects[j][VALUE])
work.append(subjects[j][WORK])
return name, value, work
#
# Problem 5: Performance Comparison
#
def dpTime():
"""
Runs tests on dpAdvisor and measures the time required to compute an
answer.
"""
for maxWork in range(8):
start_time = time.time()
dpAdvisor(subjects, maxWork)
end_time = time.time()
time_used = round(end_time - start_time,3)
print 'maxWork:', maxWork, 'time:', time_used
# Problem 5 Observations
# ======================
#
# maxWork: 0 time: 0.001
# maxWork: 1 time: 0.002
# maxWork: 2 time: 0.003
# maxWork: 3 time: 0.003
# maxWork: 4 time: 0.007
# maxWork: 5 time: 0.006
# maxWork: 6 time: 0.006
# maxWork: 7 time: 0.007
Joe
1 year ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 12, HW 1
1) T(n)=O(n): the function will recurse until i=1
2) T(n)=O(n): each loop is constant and there is about n loop
3) T(n)=O(n): each loop is constant and there is about n loop
4) T(n)=O(n): at first there is 2n, followed by a for loop with constant each loop, so it's still O(n)
#5)
def swap0([1], [2]):
assert type(s1) == list and type(s2) == list
tmp = s1[:]
# tmp = [1]
s1 = s2[:]
# tmp = [1], s1 = [2]
s2 = tmp
# tmp = [1], s1 = [2], s2 = [1]
return
# [2],[1]
#6)
def swap1([1], [2] ):
assert type([1]) == list and type([2] ) == list
return [2] , [1]
s1, s2 = swap1([1], [2])
print s1, s2
[2],[1]
#7)
def rev([1,2,3]):
assert type(s) == list
for i in range(0,1):
tmp = s[i] # tmp=1
s[i] = s[-(i+1)] # s=[3,2,3]
s[-(i+1)] = tmp # s=[3,2,1]
rev(s) print s # [3,2,1]
Joe
1 year ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 11, HW 1
Word games 2
Problem 4:
i copy the function which find subset from BTheMad, thanks!
this problem is really hard to comprehend what it is talking about.
then i watch lecture 11 in which the prof. said the problem set doesn't tell you everything and you have to do what you think is reasonable.
so i quit guessing what the problem want me to do, and just did what i think can solve the problem.
as required, i create the rearrangement_dict
whose key is a sorted string, and the value is a list, containing all valid word that can be spelled with the letter in the key
for example: {'aelpp':[apple,appel]}
suppose the given hand is {'a':1,'p':2,'l':1,'e':1}
both 'apple' and 'appel' are correct
first i turn the given hand to a sorted list [a,e,l,p,p]
then find each possible subset of it, turn it back to string and stor in a list.
'aelpp' is one of the subset. then find such value in the rearrangement_dict, and keep the highest score
# Problem Set 6: 6.00 Word Game
# Name: Joe Li
# Time: 8:30
#
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)
# -----------------------------------
def get_word_score(word, n):
"""
Returns the score for a word. Assumes the word is a
valid word.
The score for a word is the sum of the points for letters
in the word, plus 50 points if all n letters are used on
the first go.
Letters are scored as in Scrabble; A is worth 1, B is
worth 3, C is worth 3, D is worth 2, E is worth 1, and so on.
word: string (lowercase letters)
returns: int >= 0
"""
score=0
for letter in word:
score+=SCRABBLE_LETTER_VALUES[letter]
if len(word)==n:
score+=50
return score
#
# Make sure you understand how this function works and what it does!
#
def display_hand(hand):
"""
Displays the letters currently in the hand.
For example:
display_hand({'a':1, 'x':2, 'l':3, 'e':1})
Should print out something like:
a x x l l l e
The order of the letters is unimportant.
hand: dictionary (string -> int)
"""
for letter in hand.keys():
for j in range(hand[letter]):
print letter, # print all on the same line
print # print an empty line'
#
# Make sure you understand how this function works and what it does!
#
def deal_hand(n):
"""
Returns a random hand containing n lowercase letters.
At least n/3 the letters in the hand should be VOWELS.
Hands are represented as dictionaries. The keys are
letters and the values are the number of times the
particular letter is repeated in that hand.
n: int >= 0
returns: dictionary (string -> int)
"""
hand={}
num_vowels = n / 3
for i in range(num_vowels):
x = VOWELS[random.randrange(0,len(VOWELS))]
hand[x] = hand.get(x, 0) + 1
for i in range(num_vowels, n):
x = CONSONANTS[random.randrange(0,len(CONSONANTS))]
hand[x] = hand.get(x, 0) + 1
return hand
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)
"""
hand2=hand.copy()
for letter in word:
hand2[letter]-=1
return hand2
def is_valid_word(word, hand, points_dict):
"""
Returns True if word is in the word_list and is entirely
composed of letters in the hand. Otherwise, returns False.
Does not mutate hand or word_list.
word: string
hand: dictionary (string -> int)
word_list: list of lowercase strings
"""
if word not in points_dict: # if the word is not a actual word
return False
for letter in word:
if not letter in hand: # if the letter in word is not available
return False
hand2=update_hand(hand,word)
for i in hand2: # if the letter is available but not enough
if hand2.get(i)<0:
return False
return True
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 ...
#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(), points_dict,time_limit)
print
elif cmd == 'r':
play_hand(hand.copy(), points_dict,time_limit)
print
elif cmd == 'e':
break
else:
print "Invalid command."
#################################
# #
# Problem Set 6 Starts here #
# #
#################################
#
# Problem #1: How long?
# Problem #2: Time Limit
#
def play_hand(hand, points_dict, time_limit):
"""
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 # total score
current=hand.copy() # current hand
left=1
#time_limit=8
print 'Enter time limit, in seconds, for players: '+str(time_limit)
time_remain=time_limit
time_exceeds=False # if time_exceeds: break
while left!=0: # there is still letter left in hand
print 'Current Hand: ',
display_hand(current)
start_time = time.time() # time start
# word=str(raw_input('Enter word, or a . to indicate that you are finished: '))
word=pick_best_word_faster(current,points_dict)
print 'Enter word, or a . to indicate that you are finished: '+word
end_time = time.time() # time end
total_time = end_time - start_time
print 'It took %0.2f seconds to provide an answer.' % total_time
time_remain-=total_time
if time_remain<0: # time_exceeds
print 'Total time exceeds '+str(time_limit)+' seconds. You scored '+str(total)+' points.'
time_exceeds=True
break
print 'You have '+str(time_remain)+' seconds remaining.'
if word!='.': # test word
if is_valid_word(word,current,points_dict):
current=update_hand(current,word)
left=0 # reset left
for letter in current:
left+=current.get(letter) # letter left in hand
score=round(get_word_score(word,HAND_SIZE)/float(total_time),2)
total+=score
print word+' earned '+str(score)+' points. Total: '+str(total)+' points'
else: # word invalid
print 'Invalid word, please try again.'
else: # choose finished
left=0
if time_exceeds==False: # if not time_exceeds: print the total score
# if time_exeeds: have already break
print 'Total score: '+str(total)+' points.'
#
# Problem #3: Computer Player
#
def get_words_to_points(word_list):
"""
Return a dict that maps every word in word_list to its point value.
"""
points = {}
for word in word_list:
value=0
for letter in word:
value+=SCRABBLE_LETTER_VALUES[letter]
points[word]=value
return points
def pick_best_word(hand, points_dict):
"""
Return the highest scoring word from points_dict
that can be made with the given hand.
Return '.' if no words can be made with the given hand.
"""
highest=''
for word in points_dict:
if is_valid_word(word,hand,points_dict):
if highest=='' or points_dict[word]>points_dict[highest]:
highest=word
if highest!='':
return highest
return '.' # no word can be spelled with current hand
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) * 1
#
# Problem #4: Even Faster Computer Player
#
def sort_string(word):
"""
Return a string with the exact letter of input but in sorted order
word:string
"""
order=[]
for letter in word: # change a string to list
order.append(letter)
order.sort()
sorted_word='' # sort the list
for i in range(len(order)): # change the list back to string
sorted_word+=order[i]
return sorted_word
def get_word_rearrangements(word_list):
"""
Return a dictionary d
key: sorted string
value: a list of the word can be spelled with the letter in the sorted string
all of the word in word_list is included in this dict
"""
d={}
for word in word_list:
string=sort_string(word) # sort the letter of every word in word_list
if d.get(string)==None: # if the subset hasn't been created yet
d[string]=[word] # creat a list containing the subset
else: # if the subset has been created
d[string].append(word) # append the value with the new string
return d
def get_sets_recursive(word, word_list):
"""
Generate all possible string from a given letter list, without order changed
word: list
"""
# this function is written by BTheMad, thanks.
# i have been think this prolem all night
# i guess i'm just too stupid too figure it out
if len(word) > 0:
str_word = "".join(word)
if str_word not in word_list:
word_list.append(str_word)
for letter in word:
tmp_word = word[:]
tmp_word.remove(letter)
if len(tmp_word) > 0 and "".join(tmp_word) not in word_list:
get_sets_recursive(tmp_word, word_list)
return word_list
def pick_best_word_faster(hand,points_dict):
"""
Return the highest scoring word from points_dict
that can be made with the given hand.
Return '.' if no words can be made with the given hand.
"""
sorthand=[]
highest=''
for letter in hand.keys():
for j in range(hand[letter]):
sorthand.append(letter)
sorthand.sort() # make a sorted list of given hand
s=get_sets_recursive(sorthand,[]) # find every subset
for p in s:
if p in rearrange_dict:
for word in rearrange_dict[p]:
if is_valid_word(word,hand,points_dict):
if highest=='' or points_dict[word]>points_dict[highest]: # store the word with highest score
highest=word
if highest!='':
return highest
return '.' # no word can be spelled with current hand
#
# Problem #5: Algorithm Analysis
#
# algorithm of pick_best_word: O(n**2)
# 1.traverse all the words in word_list
# 2.check if the given hand can spell the word
# 3.if it can, keep the score untill find the higher score
#
# algorithm of pick_best_word_faster: O(n)
# 1.map every word in word_list to a ordered string
# 2.find every sorted subset of the given hand
# 3.for each subset, find out the word mapped to it, keep the highest score
#
# Build data structures used for entire session and play game
#
if __name__ == '__main__':
word_list = load_words()
points_dict=get_words_to_points(word_list)
rearrange_dict=get_word_rearrangements()
time_limit=get_time_limit(points_dict,1)
play_game(word_list)
Joe
1 year ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 9, HW 2
# Problem Set 5: Ghost
# Name: Joe Li
# Time: 3:30
#
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.
wordlist = load_words()
def ghost(wordlist):
print 'Welcome to Ghost!'
current=''
print 'Player 1 goes first.'
turn=1
player=1
valid=1
# if valid=1, this game continue
while valid==1:
if turn>1:
# the odd turn is player 1's turn, the even trun is player 2's turn
if turn%2==0:
player='2'
else:
player='1'
print 'Player '+player+'\'s turn.'
#this messege should only occur since 2nd turn
else:
#the 1st turn is player 1's turn
player='1'
print 'Current word fragment: '+current
letter=string.lower(raw_input('Player '+player+' says letter: '))
valid=0
passtest=0
# if passtest==0 after the test, means that no word begins with the current word
if letter in string.ascii_letters:
# make sure only one letter entered
current+=letter
for word in wordlist:
# check if there's a word start with the current word
if len(current)<=len(word):
if current==word[:len(current)]:
passtest=1
if passtest==1:
if len(current)>3:
# if len(current)>3, the current word can't be an actual word, else the player lose
if not current in wordlist:
# the current word isn't yet an actual word
valid=1
# game continue
turn+=1
else:
# the current word is an actual word
print 'Player '+player+' loses because \''+current+'\' is a word!'
if player==1:
print 'Player 2 wins!'
else:
print 'Player 1 win!'
else:
# if the len(current)<=3, then it doesn't matter
valid=1
turn+=1
else:
# fail the passtest
print 'Player '+player+' loses because no word begins with \''+current+'\'!'
if player=='1':
print 'Player 2 wins!'
else:
print 'Player 1 win!'
else:
# whatever entered is not a letter
print 'Please enter a letter.'
valid=1
ghost(wordlist)
Joe
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: Joe Li
# Time: 4:00
#
import random
import string
VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
HAND_SIZE = 7
SCRABBLE_LETTER_VALUES = {
'a': 1, 'b': 3, 'c': 3, 'd': 2, 'e': 1, 'f': 4, 'g': 2, 'h': 4, 'i': 1, 'j': 8, 'k': 5, 'l': 1, 'm': 3, 'n': 1, 'o': 1, 'p': 3, 'q': 10, 'r': 1, 's': 1, 't': 1, 'u': 1, 'v': 4, 'w': 4, 'x': 8, 'y': 4, 'z': 10
}
# -----------------------------------
# Helper code
# (you don't need to understand this helper code)
WORDLIST_FILENAME = "words.txt"
def load_words():
"""
Returns a list of valid words. Words are strings of lowercase letters.
Depending on the size of the word list, this function may
take a while to finish.
"""
print "Loading word list from file..."
# inFile: file
inFile = open(WORDLIST_FILENAME, 'r', 0)
# wordlist: list of strings
wordlist = []
for line in inFile:
wordlist.append(line.strip().lower())
print " ", len(wordlist), "words loaded."
return wordlist
def get_frequency_dict(sequence):
"""
Returns a dictionary where the keys are elements of the sequence
and the values are integer counts, for the number of times that
an element is repeated in the sequence.
sequence: string or list
return: dictionary
"""
# freqs: dictionary (element_type -> int)
freq = {}
for x in sequence:
freq[x] = freq.get(x,0) + 1
return freq
# (end of helper code)
# -----------------------------------
#
# Problem #1: Scoring a word
#
def get_word_score(word, n):
"""
Returns the score for a word. Assumes the word is a
valid word.
The score for a word is the sum of the points for letters
in the word, plus 50 points if all n letters are used on
the first go.
Letters are scored as in Scrabble; A is worth 1, B is
worth 3, C is worth 3, D is worth 2, E is worth 1, and so on.
word: string (lowercase letters)
returns: int >= 0
"""
score=0
for letter in word:
score+=SCRABBLE_LETTER_VALUES[letter]
if len(word)==n:
score+=50
return score
#
# Make sure you understand how this function works and what it does!
#
def display_hand(hand):
"""
Displays the letters currently in the hand.
For example:
display_hand({'a':1, 'x':2, 'l':3, 'e':1})
Should print out something like:
a x x l l l e
The order of the letters is unimportant.
hand: dictionary (string -> int)
"""
for letter in hand.keys():
for j in range(hand[letter]):
print letter, # print all on the same line
print # print an empty line
#
# Make sure you understand how this function works and what it does!
#
def deal_hand(n):
"""
Returns a random hand containing n lowercase letters.
At least n/3 the letters in the hand should be VOWELS.
Hands are represented as dictionaries. The keys are
letters and the values are the number of times the
particular letter is repeated in that hand.
n: int >= 0
returns: dictionary (string -> int)
"""
hand={}
num_vowels = n / 3
for i in range(num_vowels):
x = VOWELS[random.randrange(0,len(VOWELS))]
hand[x] = hand.get(x, 0) + 1
for i in range(num_vowels, n):
x = CONSONANTS[random.randrange(0,len(CONSONANTS))]
hand[x] = hand.get(x, 0) + 1
return hand
#
# Problem #2: Update a hand by removing letters
#
def update_hand(hand, word):
"""
Assumes that 'hand' has all the letters in word.
In other words, this assumes that however many times
a letter appears in 'word', 'hand' has at least as
many of that letter in it.
Updates the hand: uses up the letters in the given word
and returns the new hand, without those letters in it.
Has no side effects: does not mutate hand.
word: string
hand: dictionary (string -> int)
returns: dictionary (string -> int)
"""
hand2=hand.copy()
for letter in word:
hand2[letter]-=1
return hand2
#
# Problem #3: Test word validity
#
def is_valid_word(word, hand, word_list):
"""
Returns True if word is in the word_list and is entirely
composed of letters in the hand. Otherwise, returns False.
Does not mutate hand or word_list.
word: string
hand: dictionary (string -> int)
word_list: list of lowercase strings
"""
if word not in word_list:
return False
for letter in word:
if not letter in hand:
return False
hand2=update_hand(hand,word)
for i in hand2:
if hand2.get(i)<0:
return False
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
current=hand.copy()
left=1
while left!=0:
print 'Current Hand: ', display_hand(current)
word=str(raw_input('Enter word, or a . to indicate that you are finished: '))
if word!='.':
if is_valid_word(word,current,word_list):
current=update_hand(current,word)
left=0
for letter in current:
left+=current.get(letter)
score=get_word_score(word,HAND_SIZE)
total+=score
print word+' earned '+str(score)+' points. Total: '+str(total)+' points'
else:
print 'Invalid word, please try again.'
else:
left=0
print 'Total score: '+str(total)+' points.'
#
# 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 ...
#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)
Joe
1 year ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 7, HW 1
Simulating a retirement fund
# Problem Set 4
# Name: Joe Li
# Time: 4:15
#
# Problem 1
#
# Retirement fund
# End of year 1
# F[0] = salary*save*0.01
# End of year 2
# F[1] = F[0]*(1+0.01*growthRate)+salary*save*0.01
# End of year 3
# F[2] = F[1]*(1+0.01*growthRate)+salary*save*0.01
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 inte
ger 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.
"""
assert 0<=save<=100 and type(save)==int, 'save is an integer between 0 and 100, not '+str(save)
for r in growthRates:
assert 0<=r<=100 and type(r)==int, 'elements in growthRates is an integer between 0 and 100, not '+str(r)
# F(n,,,)is the size of retirement account at the end of nth year
def F(n, salary, save, growthRate):
if n==0:
return salary*save*0.01
else:
return F(n-1, salary, save, growthRate)*(1+0.01*growthRate)+F(0, salary, save, growthRate)
balance=[]
for n in range(0,years):
# append F[n] to list balance
balance.append(F(n,salary,save,growthRate))
return balance
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]
# TODO: Add more test cases here.
#
# Problem 2
#
def nestEggVariable(salary, save, growthRates):
"""
- salary: the amount of money you make each year.
- save: the percent of your salary to save in the investment account each
year (an integer between 0 and 100).
- growthRate: a list of the annual percent increases in your investment
account (integers between 0 and 100).
- return: a list of your retirement account value at the end of each year.
"""
assert 0<=save<=100 and type(save)==int, 'save is an integer between 0 and 100, not '+str(save)
for r in growthRates:
assert 0<=r<=100 and type(r)==int, 'elements in growthRates is an integer between 0 and 100, not '+str(r)
def F(n, salary, save, growthRates):
# F(n,,,) is the size of retirement account at the end of nth year
# it's a little bit different from the previous one
# now the argument 'growthRates' is a list
# the function will automatically choose the nth element in 'growthRates' to be the growthRate
if n==0:
return salary*save*0.01
else:
return F(n-1, salary, save, growthRates)*(1+0.01*growthRates[n])+F(0, salary, save, growthRates)
balance=[]
years=len(growthRates)
# The length of the last argument defines the number of years you plan to work
for n in range(0,years):
# append F[n] to list balance
balance.append(F(n,salary,save,growthRates))
return balance
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]
# TODO: Add more test cases here.
#
# Problem 3
#
def postRetirement(savings, growthRates, expenses):
"""
- savings: the initial amount of money in your savings account.
- growthRate: a list of the annual percent increases in your investment
account (an integer between 0 and 100).
- expenses: the amount of money you plan to spend each year during
retirement.
- return: a list of your retirement account value at the end of each year.
"""
for r in growthRates:
assert 0<=r<=100 and type(r)==int, 'elements in growthRates is an integer between 0 and 100, not '+str(r)
def F(n,savings,growthRates,expenses):
if n==0:
return savings*(1+0.01*growthRates[0])-expenses
else:
return F(n-1,savings,growthRates,expenses)*(1+0.01*growthRates[n])-expenses
# Retirement fund
# End of year 1
# F[0] = savings*(1+0.01*growthRates[0])-expenses
# End of year 2
# F[1] = F[0]*(1+0.01*growthRates[1])-expenses
# End of year 3
# F[2] = F[1]*(1+0.01*growthRates[2])-expenses
balance=[]
years=len(growthRates)
# The length of the last argument defines the number of years you plan to work
for n in range(0,years):
balance.append(F(n,savings,growthRates,expenses))
return balance
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]
# TODO: Add more test cases here.
#
# Problem 4
#
def findMaxExpenses(salary, save, preRetireGrowthRates, postRetireGrowthRates,epsilon):
"""
- salary: the amount of money you make each year.
- save: the percent of your salary to save in the investment account each
year (an integer between 0 and 100).
- preRetireGrowthRates: a list of annual growth percentages on investments
while you are still working.
- postRetireGrowthRates: a list of annual growth percentages on investments
while you are retired.
- epsilon: an upper bound on the absolute value of the amount remaining in
the investment fund at the end of retirement.
"""
assert 0<=save<=100 and type(save)==int, 'save is an integer between 0 and 100, not '+str(save)
for r in preRetireGrowthRates:
assert 0<=r<=100 and type(r)==int, 'elements in preRetireGrowthRates is an integer between 0 and 100, not '+str(r)
for r in postRetireGrowthRates:
assert 0<=r<=100 and type(r)==int, 'elements in postRetireGrowthRates is an integer between 0 and 100, not '+str(r)
savings=nestEggVariable(salary,save,preRetireGrowthRates) # get the savings from the result of the function in problem 2
savings=savings[-1] # only balance of the last year before retirement is needed
low=0
high=savings
expenses=(low+savings)/2.0
ctn=0
while abs(postRetirement(savings, postRetireGrowthRates, expenses)[-1])>epsilon:
# if the epsilon requirement isn't met
assert ctn<=100, 'Interation limit exeeds'
ctn+=1
if postRetirement(savings, postRetireGrowthRates, expenses)[-1]>0:
# if the expenses is too low
low=expenses # higher the lower bound
else:
# if the expenses is too high
high=expenses # lower the upper bound
expenses=(low+high)/2.0 #reassign expenses
print 'Interation',ctn,'expenses',expenses
return expenses
def testFindMaxExpenses():
salary = 10000
save = 10
preRetireGrowthRates = [3, 4, 5, 0, 3]
postRetireGrowthRates = [10, 5, 0, 5, 1]
epsilon = .01
expenses = findMaxExpenses(salary, save, preRetireGrowthRates,
postRetireGrowthRates, epsilon)
print expenses
# Output should have a value close to:
# 1229.95548986
# TODO: Add more test cases here.
Joe
1 year ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 5, HW 1
Matching strings: a biological perspective
# Problem Set 3 (Part I)
# Name: Joe Li
# Time: 2:00
#
from string import *
def countSubStringMatch(target,key):
count=0
index=0
while find(target,key,index)!=-1: # while searching the target from index and find a key
index=find(target,key,index)+1 # search from the next character
count+=1
return count
def countSubStringMatchRecursive (target, key):
target=target[find(target,key)+1:] # slice 'target'
if find(target,key)==-1: # if the substring doesn't contain the key
return 1 # the base case return 1 in order to count the last removed one
else:
recurse=countSubStringMatchRecursive(target,key) # recerse
return recurse+1 # count
# Problem Set 3 (Part II)
# Name: Joe Li
# Time 1:00
#
from string import *
def subStringMatchExact(target,key):
index=0
match=()
while find(target,key,index)!=-1:
index=find(target,key,index) # bind the position of found key to index
match+=(index,) # add to tuple
index+=1 # search from next character
return match
target1 = 'atgacatgcacaagtatgcat'
target2 = 'atgaatgcatggatgtaaatgcag'
key10 = 'a'
key11 = 'atg'
key12 = 'atgc'
key13 = 'atgca'
print subStringMatchExact(target1,key10)
print subStringMatchExact(target1,key11)
print subStringMatchExact(target1,key12)
print subStringMatchExact(target1,key13)
print subStringMatchExact(target2,key10)
print subStringMatchExact(target2,key11)
print subStringMatchExact(target2,key12)
print subStringMatchExact(target2,key13)
# Problem Set 3 (Part III)
# Name: Joe Li
# Time 0:30
#
from string import *
def subStringMatchExact(target,key):
index=0
match=()
while find(target,key,index)!=-1:
index=find(target,key,index) # bind the position of found key to index
match+=(index,) # add to tuple
index+=1 # search from next character
return match
def constrainedMatchPair(firstMatch,secondMatch,length):
filtered=()
for n in range(0,len(firstMatch)): # for every element in 1st & 2nd Match
for k in range(0,len(secondMatch)):
if firstMatch[n]+length+1==secondMatch[k]: # if n+m+1=k holds
filtered+=(firstMatch[n],) # add such n to result
return filtered
def subStringMatchOneSub(key,target):
"""search for all locations of key in target, with one substitution"""
allAnswers = ()
for miss in range(0,len(key)):
# miss picks location for missing element
# key1 and key2 are substrings to match
key1 = key[:miss]
key2 = key[miss+1:]
print 'breaking key',key,'into',key1,key2
# match1 and match2 are tuples of locations of start of matches
# for each substring in target
match1 = subStringMatchExact(target,key1)
match2 = subStringMatchExact(target,key2)
# when we get here, we have two tuples of start points
# need to filter pairs to decide which are correct
filtered = constrainedMatchPair(match1,match2,len(key1))
allAnswers = allAnswers + filtered
print 'match1',match1
print 'match2',match2
print 'possible matches for',key1,key2,'start at',filtered
return allAnswers
# Problem Set 3 (Part IV)
# Name: Joe Li
# Time 0:30
#
from string import *
def subStringMatchExact(target,key):
index=0
match=()
while find(target,key,index)!=-1:
index=find(target,key,index) # bind the position of found key to index
match+=(index,) # add to tuple
index+=1 # search from next character
return match
def constrainedMatchPair(firstMatch,secondMatch,length):
filtered=()
for n in range(0,len(firstMatch)): # for every element in 1st & 2nd Match
for k in range(0,len(secondMatch)):
if firstMatch[n]+length+1==secondMatch[k]: # if n+m+1=k holds
filtered+=(firstMatch[n],) # add such n to result
return filtered
def subStringMatchOneSub(key,target):
"""search for all locations of key in target, with one substitution"""
allAnswers = ()
for miss in range(0,len(key)):
# miss picks location for missing element
# key1 and key2 are substrings to match
key1 = key[:miss]
key2 = key[miss+1:]
print 'breaking key',key,'into',key1,key2
# match1 and match2 are tuples of locations of start of matches
# for each substring in target
match1 = subStringMatchExact(target,key1)
match2 = subStringMatchExact(target,key2)
# when we get here, we have two tuples of start points
# need to filter pairs to decide which are correct
filtered = constrainedMatchPair(match1,match2,len(key1))
allAnswers = allAnswers + filtered
print 'match1',match1
print 'match2',match2
print 'possible matches for',key1,key2,'start at',filtered
allAnswers=tuple(set(allAnswers))
return allAnswers
def subStringMatchExactlyOneSub(target,key):
exact=list(subStringMatchExact(target,key))
one=list(subStringMatchOneSub(key,target))
for index in range(0,len(exact)):
one.remove(exact[index]) #remove those elements occur in the 1st tuple from the 2nd tuple
return tuple(one)
Joe
1 year ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 3, HW 1
# Problem Set 2 (Part I)
# Name: Joe Li
# Time: 4:00
#
count=0 # the number of successive n McNuggets can be bought
n=1 # n start from 1
a=0 # make a,b,c,recognizable
b=0
c=0
while count!=6: # do as following untill count=6
while 6*a+9*b+20*c!=n: # test if n McNuggets can be bought with the combination abc. if test fail, do as following
if 6*a>n: # if a exceeds the limit
a=0 # reset a
b+=1 # try next b
elif 9*b>n: # if b exceeds the limit
a=0 # reset a
b=0 # reset b
c+=1 # try next c
elif 20*c>n: # if c excceds the limit
a=0 # reset a
b=0 # reset b
c=0 # reset c
count=0 # reset count
m=n # store last n cannot be bought to m
n+=1 # test next n
else: # if none of a,b,c exceeds the limit
a+=1 # try next a
else: # if pass the test
count+=1 # count plus 1
n+=1 # try the next n
a=0 # reset a
b=0 # reset b
c=0 # reset c
else: # if got 6 successive n McNuggets can be bought,
print 'Largest number of \
McNuggets that cannot \
be bought in exact \
quantity: <'+str(m)+'>' # print the last n cannot be bought
# Problem Set 2 (Part II)
# Name: Joe Li
# Time: 3:00
#
bestSoFar=0 # variable that keeps track of largest number of McNuggets that cannot be bought in exact quantity
package=(7,13,19) # variable that cantains package sizes
x=package[0]
y=package[1]
z=package[2]
for n in range(1,200): # test n from 1 to 199
m=1 # variable that remains 1 unless such n McNuggets can be bought with some combination
for c in range(0,n/z+2): # test c from 0 to n/z+1
for b in range(0,n/y+2): # test b from 0 to n/y+1
for a in range(0,n/x+2):# test a from 0 to n/x+1
if x*a+y*b+z*c==n:# if n McNuggets can be bought with such combination abc
m=0 # set m to 0
if m==1: # if m hasn't been set to 0 which means there's no combination with whitch n McNuggets can be bought
bestSoFar=n # assign such n to bestSoFar
print 'Given package sizes <'+str(x)+'>, \
<'+str(y)+'>, and <'+str(z)+'>, the largest \
number of McNuggets that cannot be bought \
in exact quantity is: <'+str(bestSoFar)+'>'
Joe
1 year ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 2, HW 1
Computing prime numbers, product of primes
#Problem Set 1 (PART I)
#Name Joe Li
#Time 4:30
#
x=3 # candidate
d=2 # divisor
count=1 # the number of prime has been found
while count!=1000: # do the following utill the 1000th prime has been found
while x%d==0: # while the remainder is zero, which means x is not a prime
x+=1 # test next x
d=2 # reset divisor
else: # while the remainder is not zero
if d==x-1: # and the divisor is the last one to test with, prime comfirmed
count+=1 # count
x+=1 # test next x
d=2 # reset divisor
else: # and the divisor is not the last one to test
d+=1 # test with next divisor
else: # 1000 primes have been found
print x-1 # print the last one (the 1000th prime)
#Problem Set 1 (PART II)
#Name Joe Li
#Time 0:10
#
from math import *
x=3 # candidate
d=2 # divisor
n=1 # the number of prime has been found
s=log(2) # the sum of log
while n!=1000: # do the following utill the nth prime has been found
while x%d==0: # while the remainder is zero, which means x is not a prime
x+=1 # test next x
d=2 # reset divisor
else: # while the remainder is not zero
if d==x-1: # and the divisor is the last one to test with, prime comfirmed
n+=1 # count
s+=log(x) # add to sum
x+=1 # test next x
d=2 # reset divisor
else: # and the divisor is not the last one to test
d+=1 # test with next divisor
else: # all the log of prime less than n have been added to sum
print s,x-1,s/(x-1) # print the sum, n, ratio
Joe
1 year ago
|
|
|
|
|
