About Me
No description provided.
Classes
|
Class status: Established
Role:
Student
|
.
100% complete
|
Submitted Assignments
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 24, HW 1
# Problem 1:
# 1.1: True
# 1.2: True
# 1.3: True
# 1.4: False
# 1.5: False
# Problem 2:
# Figure 1--> 2nd Diagram
# Figure 2--> 3rd Diagram
# Figure 3--> 1st Diagram
# Problem 3:
# Yes it can be implemented if y equals the squareroot of the mean of the expression x-e
# and x+e. Although negative floats would cause an error.
# Problem 4:
def f(L1, L2):
"""
L1 and L2 are lists of integers
returns the element-wise product of L1 and L2.
If the lists are of different length, it uses 1
for the missing coefficients.
E.g., if L1 = [2, 2, 3] and L2 = [7, 5, 6, 7]
it returns [14, 10, 18, 7]
side effects: none
"""
newL1 = L1[:]
newL2 = L2[:]
L3 = []
if len(L1) > len(L2):
for length in range(len(L1) - len(L2)):
newL2.append(1)
if len(L1) < len(L2):
for length in range(len(L2) - len(L1)):
newL1.append(1)
for i in range(len(newL1)):
L3.append(newL1[i]*newL2[i])
return L3
# Problem 5:
# 5.1: D Close to Zero
# 5.2: C About the same
# 5.3: generateMarket iteself is linear O(n) where n is the number of
# numSectors. But the function also calls gerateSector which is also
# of complexity O(s) where s is the size of the sector. So generateMarket
# should be O(n*s) or O(n**2), Quadradtic
# 5.4: B
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 23, HW 1
Problem 2:
The population levels out to around 500 viruses after 50 to 100 time steps.
Problem 4:
I observed that the population of viruses quickly declined as the non-drug resistant viruses were prevented from reproducing. Conversely the drug resistant viruses continued to reproduce until the total population of viruses were resistant to Guttagonol.
Problem 5:
The proportion of patients in remission greatly improved when treatment wasn't delayed. Remission differed as greatly as ~0.1% to 100% of the patients.
The histogram keeps track of the population at the end of the treatment time. By that time all the viruses left would be resistant to whatever drugs were being used.
Problem 6:
The proportion of patients in remission also greatly improved when the drugs were introduced closer to each other. The percent in Remission at the end of the test was 1%, 10%, 30%, 78%.
Problem 7:
The reason is because when there is a delay between the drugs it gives time for the viruses to adapt resistance to each drug separately.
Problem 8:
A way to model the fact that patients often forget to take their medication would be to create a function that removes the drug from the patients list of prescriptions allowing resistant and non-resistant viruses to reproduce. This would be decided at each time step whether or not the patient would remember to take their medication based on a probability.
# 6.00 Problem Set 12
#
# Name:
# Collaborators:
# Time:
import copy
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 = float(maxBirthProb)
self.clearProb = float(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.
"""
clearance = random.random()
if clearance <= 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.
"""
if random.random() <= self.maxBirthProb * (1 - popDensity):
return SimpleVirus(self.maxBirthProb, self.clearProb)
else:
raise NoChildException()
class SimplePatient(object):
"""
Representation of a simplified patient. The patient does not take any drugs
and his/her virus populations have no drug resistance.
"""
def __init__(self, viruses, maxPop):
"""
Initialization function, saves the viruses and maxPop parameters as
attributes.
viruses: the list representing the virus population (a list of
SimpleVirus instances)
maxPop: the maximum virus population for this patient (an integer)
"""
self.viruses = viruses
self.maxPop = maxPop
def getTotalPop(self):
"""
Gets the current total virus population.
returns: The total virus population (an integer)
"""
return len(self.viruses)
def update(self):
"""
Update the state of the virus population in this patient for a single
time step. update() should execute the following steps in this order:
- Determine whether each virus particle survives and updates the list
of virus particles accordingly.
- The current population density is calculated. This population density
value is used until the next call to update()
- Determine whether each virus particle should reproduce and add
offspring virus particles to the list of viruses in this patient.
returns: the total virus population at the end of the update (an
integer)
"""
updateViruses = []
for virus in self.viruses:
if not virus.doesClear():
updateViruses.append(virus)
popDensity = self.getTotalPop()/float(self.maxPop)
try: updateViruses.append(virus.reproduce(popDensity))
except NoChildException: pass
self.viruses = updateViruses
return self.getTotalPop()
#
# 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.
"""
maxBirthProb = 0.1
clearProb = 0.05
maxPop = 1000
virusList = []
timesteps = []
totalViruses = []
ctr = 0
for i in range(0,100):
virusList.append(SimpleVirus(maxBirthProb, clearProb))
patient = SimplePatient(virusList, maxPop)
for t in range(0,300):
totalViruses.append(patient.update())
timesteps.append(ctr)
ctr += 1
pylab.figure()
pylab.plot(timesteps, totalViruses)
pylab.ylabel('Viruses')
pylab.xlabel('Timesteps')
pylab.title('Total virus population over time')
# Testing Problem 2
#problem2()
#
# PROBLEM 3
#
class ResistantVirus(SimpleVirus):
"""
Representation of a virus which can have drug resistance.
"""
def __init__(self, maxBirthProb, clearProb, resistances, mutProb):
"""
Initialize a ResistantVirus instance, saves all parameters as attributes
of the instance.
maxBirthProb: Maximum reproduction probability (a float between 0-1)
clearProb: Maximum clearance probability (a float between 0-1).
resistances: A dictionary of drug names (strings) mapping to the state
of this virus particle's resistance (either True or False) to each drug.
e.g. {'guttagonol':False, 'grimpex',False}, means that this virus
particle is resistant to neither guttagonol nor grimpex.
mutProb: Mutation probability for this virus particle (a float). This is
the probability of the offspring acquiring or losing resistance to a drug.
"""
self.maxBirthProb = float(maxBirthProb)
self.clearProb = float(clearProb)
self.resistances = resistances
self.mutProb = float(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.
"""
reproduce = False
if activeDrugs == []:
reproduce = True
for drug in activeDrugs:
if self.getResistance(drug):
reproduce = True
elif not self.getResistance(drug):
reproduce = False
break
if reproduce == True:
if random.random() <= self.maxBirthProb * (1 - popDensity):
new_resistances = copy.copy(self.resistances)
for drug in new_resistances.keys():
if random.random() <= self.mutProb:
if new_resistances[drug] == True:
new_resistances[drug] = False
else: new_resistances[drug] = True
return ResistantVirus(self.maxBirthProb, self.clearProb, new_resistances, self.mutProb)
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.prescriptions = []
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.getPrescriptions():
self.prescriptions.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.prescriptions
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 virus in self.viruses:
resist = False
for drug in drugResist:
if not virus.getResistance(drug):
resist = False
break
else: resist = True
if resist == 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 listof drugs being administered should be accounted for in the
determination of whether each virus particle reproduces.
returns: the total virus population at the end of the update (an
integer)
"""
updateViruses = []
for virus in self.viruses:
if not virus.doesClear():
updateViruses.append(virus)
self.viruses = updateViruses
popDensity = self.getTotalPop()/float(self.maxPop)
for virus in self.viruses:
try: self.viruses.append(virus.reproduce(popDensity,self.getPrescriptions()))
except NoChildException: pass
self.viruses = updateViruses
return self.getTotalPop()
#
# 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
"""
maxBirthProb = 0.1
clearProb = 0.05
maxPop = 1000
resistances = {'guttagonol':False, 'grimpex':False}
mutProb = 0.005
virusList = []
timesteps = []
totalViruses = []
ctr = 0
virusResist = []
for i in range(0,100):
virusList.append(ResistantVirus(maxBirthProb, clearProb, resistances, mutProb))
patient = Patient(virusList, maxPop)
for t in range(0,300):
totalViruses.append(patient.update())
virusResist.append(patient.getResistPop(patient.getPrescriptions()))
timesteps.append(ctr)
ctr += 1
if t == 150:
patient.addPrescription('guttagonol')
pylab.figure()
pylab.plot(timesteps, totalViruses, label='Total Viruses')
pylab.plot(timesteps, virusResist, label='Guttagonol Resistant')
pylab.axis([-5, 305, -5, 800])
pylab.axvline (x=150, linestyle = '--', label='Guttagonol Introduced')
pylab.legend(loc=2)
pylab.ylabel('Viruses')
pylab.xlabel('Timesteps')
pylab.title('Total virus population over time')
# Testing Problem 4
#problem4()
#
# 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).
"""
maxBirthProb = 0.1
clearProb = 0.05
maxPop = 1000
resistances = {'guttagonol':False}
mutProb = 0.005
delay = [300,150,75,0]
virusList = []
for i in xrange(0,100):
virusList.append(ResistantVirus(maxBirthProb, clearProb, resistances, mutProb))
trials = 100
for steps in delay:
totalViruses = []
for trial in range(trials):
print steps, trial
patient = Patient(virusList, maxPop)
for t in xrange(steps):
patient.update()
patient.addPrescription('guttagonol')
for c in xrange(150):
patient.update()
totalViruses.append(patient.getTotalPop())
pylab.figure()
pylab.hist(totalViruses)
pylab.ylabel('Number of Patients')
pylab.xlabel('Final Total Virus Population')
pylab.title('Total virus populations after a delay in treatment of %d timesteps (%d Trials)' % (steps, trials))
# Testing Problem 5
#problem5()
#
# 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).
"""
maxBirthProb = 0.1
clearProb = 0.05
maxPop = 1000
resistances = {'guttagonol':False, 'grimpex':False}
mutProb = 0.005
delay = [300,150,75,0]
virusList = []
for i in xrange(100):
virusList.append(ResistantVirus(maxBirthProb, clearProb, resistances, mutProb))
trials = 100
for steps in delay:
totalViruses = []
for trial in xrange(trials):
print steps, trial
patient = Patient(virusList, maxPop)
for a in xrange(150):
patient.update()
patient.addPrescription('guttagonol')
for b in xrange(steps):
patient.update()
patient.addPrescription('grimpex')
for c in xrange(150):
patient.update()
totalViruses.append(patient.getTotalPop())
pylab.figure()
pylab.hist(totalViruses)
pylab.ylabel('Number of Patients')
pylab.xlabel('Total Virus Population at the end of treatment')
pylab.title('Total virus populations after a delay in treatment of %d timesteps between drugs (%d Trials)' % (steps, trials))
# Testing Problem 6
#problem6()
#
# 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.
"""
maxBirthProb = 0.1
clearProb = 0.05
maxPop = 1000
resistances = {'guttagonol':False, 'grimpex':False}
mutProb = 0.005
treatment = [300,0]
virusList = []
for i in xrange(100):
virusList.append(ResistantVirus(maxBirthProb, clearProb, resistances, mutProb))
for delay in treatment:
patient = Patient(virusList, maxPop)
timesteps = []
totalViruses = []
guttagonolResist = []
grimpexResist = []
totalResist = []
ctr = 0
for trial in xrange(300+delay):
totalViruses.append(patient.update())
guttagonolResist.append(patient.getResistPop(['guttagonol']))
grimpexResist.append(patient.getResistPop(['grimpex']))
totalResist.append(patient.getResistPop(patient.getPrescriptions()))
timesteps.append(ctr)
ctr += 1
if trial == 150:
patient.addPrescription('guttagonol')
if trial == 150+delay:
patient.addPrescription('grimpex')
pylab.figure()
pylab.plot(timesteps, totalViruses, label='Viruses')
pylab.plot(timesteps, totalResist, label='Total Resistant')
pylab.plot(timesteps, guttagonolResist, label='Guttagonol Resistant')
pylab.plot(timesteps, grimpexResist, label='Grimpex Resist')
pylab.legend(loc=2)
pylab.axis([-5, 300+delay, -5, 800])
pylab.axvline (x=delay+150, linestyle = '--')
pylab.axvline (x=150, linestyle = '--')
pylab.ylabel('Population Size')
pylab.xlabel('Timesteps')
pylab.title('Total virus population over time and Drug Resistance')
#Testing Problem 7:
problem7()
pylab.show()
tuckertuck
8 months ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 19, HW 1
# Problem Set 11: Simulating robots
# Name:
# Collaborators:
# Time:
import math, random, pylab
import ps11_visualize
# === Provided classes
class Position(object):
"""
A Position represents a location in a two-dimensional room.
"""
def __init__(self, x, y):
"""
Initializes a position with coordinates (x, y).
x: a real number indicating the x-coordinate
y: a real number indicating the y-coordinate
"""
self.x = x
self.y = y
def getX(self):
return self.x
def getY(self):
return self.y
def getNewPosition(self, angle, speed):
"""
Computes and returns the new Position after a single clock-tick has
passed, with this object as the current position, and with the
specified angle and speed.
Does NOT test whether the returned position fits inside the room.
angle: integer representing angle in degrees, 0 <= angle < 360
speed: positive float representing speed
Returns: a Position object representing the new position.
"""
old_x, old_y = self.getX(), self.getY()
# Compute the change in position
delta_y = speed * math.cos(math.radians(angle))
delta_x = speed * math.sin(math.radians(angle))
# Add that to the existing position
new_x = old_x + delta_x
new_y = old_y + delta_y
return Position(new_x, new_y)
# === Problems 1 and 2
class RectangularRoom(object):
"""
A RectangularRoom represents a rectangular region containing clean or dirty
tiles.
A room has a width and a height and contains (width * height) tiles. At any
particular time, each of these tiles is either clean or dirty.
"""
def __init__(self, width, height):
"""
Initializes a rectangular room with the specified width and height.
Initially, no tiles in the room have been cleaned.
width: an integer > 0
height: an integer > 0
"""
self.width = int(width)
self.height = int(height)
self.tiles = []
self.cleaned = []
for h in range(0,height):
for w in range(0,width):
self.tiles.append((w,h))
def cleanTileAtPosition(self, pos):
"""
Mark the tile under the position POS as cleaned.
Assumes that POS represents a valid position inside this room.
pos: a Position
"""
self.cleaned.append((int(pos.getX()),int(pos.getY())))
def isTileCleaned(self, m, n):
"""
Return True if the tile (m, n) has been cleaned.
Assumes that (m, n) represents a valid tile inside the room.
m: an integer
n: an integer
returns: True if (m, n) is cleaned, False otherwise
"""
return (m,n) in self.cleaned
def getNumTiles(self):
"""
Return the total number of tiles in the room.
returns: an integer
"""
return len(self.tiles)
def getNumCleanedTiles(self):
"""
Return the total number of clean tiles in the room.
returns: an integer
"""
return len(self.cleaned)
def getRandomPosition(self):
"""
Return a random position inside the room.
returns: a Position object.
"""
return Position(random.randint(0,self.width),random.randint(0,self.height))
def isPositionInRoom(self, pos):
"""
Return True if POS is inside the room.
pos: a Position object.
returns: True if POS is in the room, False otherwise.
"""
return 0 <= pos.getX() < self.width and 0 <= pos.getY() < self.height
class BaseRobot(object):
"""
Represents a robot cleaning a particular room.
At all times the robot has a particular position and direction in
the room. The robot also has a fixed speed.
Subclasses of BaseRobot should provide movement strategies by
implementing updatePositionAndClean(), which simulates a single
time-step.
"""
def __init__(self, room, speed):
"""
Initializes a Robot with the given speed in the specified
room. The robot initially has a random direction d and a
random position p in the room.
The direction d is an integer satisfying 0 <= d < 360; it
specifies an angle in degrees.
p is a Position object giving the robot's position.
room: a RectangularRoom object.
speed: a float (speed > 0)
"""
self.room = room
self.speed = float(speed)
self.p = self.room.getRandomPosition()
self.d = random.randint(0,359)
def getRobotPosition(self):
"""
Return the position of the robot.
returns: a Position object giving the robot's position.
"""
return self.p
def getRobotDirection(self):
"""
Return the direction of the robot.
returns: an integer d giving the direction of the robot as an angle in
degrees, 0 <= d < 360.
"""
return self.d
def setRobotPosition(self, position):
"""
Set the position of the robot to POSITION.
position: a Position object.
"""
self.p = position
def setRobotDirection(self, direction):
"""
Set the direction of the robot to DIRECTION.
direction: integer representing an angle in degrees
"""
self.d = direction
class Robot(BaseRobot):
"""
A Robot is a BaseRobot with the standard movement strategy.
At each time-step, a Robot attempts to move in its current
direction; when it hits a wall, it chooses a new direction
randomly.
"""
def updatePositionAndClean(self):
"""
Simulate the passage of a single time-step.
Move the robot to a new position and mark the tile it is on as having
been cleaned.
"""
moving = True
while moving:
new_p = self.p.getNewPosition(self.d,self.speed)
if self.room.isPositionInRoom(new_p):
self.setRobotPosition(new_p)
#print new_p.getX(), new_p.getY()
if not self.room.isTileCleaned(int(new_p.getX()),int(new_p.getY())):
self.room.cleanTileAtPosition(new_p)
#print 'cleaned'
moving = False
else:
#print 'new direction'
self.setRobotDirection(random.randint(0,359))
continue
# Testing Problem 1 and 2
##room = RectangularRoom(5,5)
##robby = Robot(room,1)
##robby.updatePositionAndClean()
##robby.updatePositionAndClean()
##robby.updatePositionAndClean()
##print room.getNumCleanedTiles()/float(room.getNumTiles())
# === Problem 3
def runSimulation(num_robots, speed, width, height, min_coverage, num_trials,
robot_type, visualize):
"""
Runs NUM_TRIALS trials of the simulation and returns a list of
lists, one per trial. The list for a trial has an element for each
timestep of that trial, the value of which is the percentage of
the room that is clean after that timestep. Each trial stops when
MIN_COVERAGE of the room is clean.
The simulation is run with NUM_ROBOTS robots of type ROBOT_TYPE,
each with speed SPEED, in a room of dimensions WIDTH x HEIGHT.
Visualization is turned on when boolean VISUALIZE is set to True.
num_robots: an int (num_robots > 0)
speed: a float (speed > 0)
width: an int (width > 0)
height: an int (height > 0)
min_coverage: a float (0 <= min_coverage <= 1.0)
num_trials: an int (num_trials > 0)
robot_type: class of robot to be instantiated (e.g. Robot or
RandomWalkRobot)
visualize: a boolean (True to turn on visualization)
"""
results = []
for i in xrange(0,num_trials):
coverage = 0
trial = []
robots = []
room = RectangularRoom(width,height)
for n in xrange(0,num_robots):
robots.append(robot_type(room, speed))
if visualize:
anim = ps11_visualize.RobotVisualization(num_robots, width, height)
# Simulate a trial
while coverage < min_coverage:
for robot in robots:
robot.updatePositionAndClean()
if visualize:
anim.update(room, robots)
coverage = room.getNumCleanedTiles()/float(room.getNumTiles())
trial.append(coverage)
if visualize:
anim.done()
results.append(trial)
return results
# Testing Problem 3
#avg = runSimulation(1, 1.0, 5, 5, 1.0, 5, Robot, True)
# === Provided function
def computeMeans(list_of_lists):
"""
Returns a list as long as the longest list in LIST_OF_LISTS, where
the value at index i is the average of the values at index i in
all of LIST_OF_LISTS' lists.
Lists shorter than the longest list are padded with their final
value to be the same length.
"""
# Find length of longest list
longest = 0
for lst in list_of_lists:
if len(lst) > longest:
longest = len(lst)
# Get totals
tots = [0]*(longest)
for lst in list_of_lists:
for i in range(longest):
if i < len(lst):
tots[i] += lst[i]
else:
tots[i] += lst[-1]
# Convert tots to an array to make averaging across each index easier
tots = pylab.array(tots)
# Compute means
means = tots/float(len(list_of_lists))
return means
# === Problem 4
def showPlot1():
"""
Produces a plot showing dependence of cleaning time on room size.
"""
num_robots = 1
speed = 1.0
min_coverage = 0.75
num_trials = 100
robot_type = Robot
visualize = False
rooms = [5,10,15,20,25]
means = []
area = []
for i in range(len(rooms)):
width = rooms[i]
height = rooms[i]
sim = runSimulation(num_robots, speed, width, height, min_coverage, num_trials, robot_type, visualize)
avg = plotHelper(sim)
area.append(width*height)
means.append(avg)
pylab.figure()
pylab.plot(area, means)
pylab.ylabel('Timesteps')
pylab.xlabel('Room area')
pylab.title('Time to clean %d percent of a square room of various areas with %d robots (%d trials)' % (min_coverage*100, num_robots, num_trials))
def showPlot2():
"""
Produces a plot showing dependence of cleaning time on number of robots.
"""
num_robots = range(1,11)
speed = 1.0
min_coverage = 0.75
num_trials = 100
robot_type = Robot
visualize = False
width, height = (25, 25)
means = []
for bot in num_robots:
sim = runSimulation(bot, speed, width, height, min_coverage, num_trials, robot_type, visualize)
avg = plotHelper(sim)
means.append(avg)
pylab.figure()
pylab.plot(num_robots, means)
pylab.ylabel('Timesteps')
pylab.xlabel('Number of Robots')
pylab.title('Time to clean %d percent of a 25x25 room with multiple robots (%d trials)' % (min_coverage*100, num_trials))
def showPlot3():
"""
Produces a plot showing dependence of cleaning time on room shape.
"""
num_robots = 2
speed = 1.0
min_coverage = 0.75
num_trials = 100
robot_type = Robot
visualize = False
rooms = [(20,20),(25,16),(40,10),(50,8),(80,5),(100,4)]
means = []
ratio = []
for i in range(len(rooms)):
width, height = rooms[i]
sim = runSimulation(num_robots, speed, width, height, min_coverage, num_trials, robot_type, visualize)
avg = plotHelper(sim)
ratio.append(width/float(height))
means.append(avg)
pylab.figure()
pylab.plot(ratio, means)
pylab.axis([0,25,0, 400])
pylab.ylabel('Timesteps')
pylab.xlabel('Ratio of Width to Height')
pylab.title('Time to clean %d percent of a rectangular room with %d robots (%d trials)' % (min_coverage*100, num_robots, num_trials))
def showPlot4():
"""
Produces a plot showing cleaning time vs. percentage cleaned, for
each of 1-5 robots.
"""
num_robots = range(1,6)
speed = 1.0
min_coverage = [0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0]
num_trials = 10
robot_type = Robot
visualize = False
width, height = (25, 25)
pylab.figure()
for bot in num_robots:
means = []
for percent in min_coverage:
sim = runSimulation(bot, speed, width, height, percent, num_trials, robot_type, visualize)
avg = plotHelper(sim)
means.append(avg)
pylab.plot(min_coverage, means, label='%d robots' % bot)
pylab.legend(loc=2)
pylab.ylabel('Timesteps')
pylab.xlabel('Minimum Coverage')
pylab.title('Time to clean a 25x25 room with 1 to 5 robots (%d trials)' % num_trials)
# Testing Problem 4
def plotHelper(list_of_lists):
"""
Returns the average length of all the lists of lists.
"""
listCounter = 0
for list in list_of_lists:
listCounter += len(list)
return listCounter/float(len(list_of_lists))
showPlot1()
showPlot2()
showPlot3()
showPlot4()
pylab.show()
# === Problem 5
class RandomWalkRobot(BaseRobot):
"""
A RandomWalkRobot is a robot with the "random walk" movement
strategy: it chooses a new direction at random after each
time-step.
"""
def updatePositionAndClean(self):
"""
Simulate the passage of a single time-step.
Move the robot to a new position and mark the tile it is on as having
been cleaned.
"""
moving = True
while moving:
new_p = self.p.getNewPosition(self.d,self.speed)
if self.room.isPositionInRoom(new_p):
self.setRobotPosition(new_p)
if not self.room.isTileCleaned(int(new_p.getX()),int(new_p.getY())):
self.room.cleanTileAtPosition(new_p)
moving = False
self.setRobotDirection(random.randint(0,359))
# Testing Problem 5
#avg = runSimulation(3, 1.0, 5, 5, 0.8, 1, RandomWalkRobot, True)
# === Problem 6
def showPlot5():
"""
Produces a plot comparing the two robot strategies.
"""
num_robots = 3
speed = 1.0
min_coverage = 0.75
num_trials = 100
robot_type = [Robot, RandomWalkRobot]
visualize = False
rooms = [5,10,15,20,25]
pylab.figure()
for botType in robot_type:
means = []
area = []
for i in range(len(rooms)):
width = rooms[i]
height = rooms[i]
sim = runSimulation(num_robots, speed, width, height, min_coverage, num_trials, botType, visualize)
avg = plotHelper(sim)
area.append(width*height)
means.append(avg)
if botType is Robot:
label = 'Robot'
else: label = 'RandomWalkRobot'
pylab.plot(area, means, label=label)
pylab.legend(loc=2)
pylab.ylabel('Timesteps')
pylab.xlabel('Area')
pylab.title('Performance comparison of Robot and RandomWalkRobot clearing %d percent of various size rooms (%d trials)' % (min_coverage*100, num_trials))
pylab.show()
#Testing Problem 6
#showPlot5()
# Observations for Problem 6:
# RobotWalkRandom() is always slower than Robot(), the difference in performance is more obvious
# with 1 robot and a large room and high minimum coverage.
tuckertuck
8 months ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 18, HW 1
Probably like this project the least.
Never felt confident that I was writing the code correctly. But the program did work in the end.
# 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
"""
freq = getFrequencyDict(word)
newhand = {}
for char in self.handDict:
newhand[char] = self.handDict[char]-freq.get(char,0)
self.handDict = newhand
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
"""
freq = getFrequencyDict(letters)
for letter in letters:
if freq[letter] > self.handDict.get(letter, 0):
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.
"""
emptyTest = self.handDict.values()
for i in emptyTest:
if i != 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
"""
if self.handDict == other.handDict:
return True
return False
def __str__(self):
"""
Represent this hand as a string
returns: a string representation of this hand
"""
string = ''
for letter in self.handDict.keys():
for j in range(self.handDict[letter]):
string = string + letter + ' '
return string
#
# Problem 3: Representing a Player
#
class Player(object):
"""
General class describing a player.
Stores the player's ID number, hand, and score.
"""
def __init__(self, idNum, hand):
"""
Initialize a player instance.
idNum: integer: 1 for player 1, 2 for player 2. Used in informational
displays in the GUI.
hand: An object of type Hand.
postcondition: This player object is initialized
"""
self.points = 0.
self.idNum = idNum
self.hand = hand
def getHand(self):
"""
Return this player's hand.
returns: the Hand object associated with this player.
"""
return self.hand
def addPoints(self, points):
"""
Add points to this player's total score.
points: the number of points to add to this player's score
postcondition: this player's total score is increased by points
"""
self.points += points
def getPoints(self):
"""
Return this player's total score.
returns: A float specifying this player's score
"""
return self.points
def getIdNum(self):
"""
Return this player's ID number (either 1 for player 1 or
2 for player 2).
returns: An integer specifying this player's ID number.
"""
return self.idNum
def __cmp__(self, other):
"""
Compare players by their scores.
returns: 1 if this player's score is greater than other player's score,
-1 if this player's score is less than other player's score, and 0 if
they're equal.
"""
if self.getPoints() > other.getPoints():
return 1
elif self.getPoints < other.getPoints():
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
"""
ans = False
best = False
wordScore = 0
wordList = wordlist.getList()
currentHand = getFrequencyDict(str(self.getHand()))
for word in wordList:
word_freq = getFrequencyDict(word)
for letter in word_freq:
if letter in currentHand and word_freq[letter] <= currentHand[letter]:
ans = True
continue
else:
ans = False
break
if ans == True:
new_score = getWordScore(word)
if new_score > wordScore:
wordScore = new_score
best_word = word
best = True
if best == True:
return best_word
else: return '.'
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
tuckertuck
8 months ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 17, HW 1
For 1.1:
When we made the greedy algorithm based on the ratio between value and work, my implementation for a majority of the cases produced the optimal solution. In the few cases where it was sub-optimal it was only off by 1-2 value units.
And since it's complexity was O(n) it was more efficient than the Dynamic programming algorithm when the work constraint was high, because Dynamic programming complexity increases as the number of solutions increase.
For Problem 6:
Is it me, or is the solution they posted to problem 6 incorrect?
I tried implementing it with my own version of cmpGuess() that followed the specification and I had to change if cmpGuess(s[mid]) == -1: from -1 to 1 to get it to work properly.
And as far as I can tell using the while loop is the same complexity as the recursive implementation if I am not mistaken — O(log(n)).
Is one version superior to the other?
# Problem 1:
# 1.1: True --> Inorrect
# 1.2: True --> Correct
# 1.3: False --> Correct
# 1.4: False --> Correct
# 1.5: True --> Correct
# 1.6: False --> Correct
# Problem 2: --> Correct
def findMedian(L):
"""Finds median of L.
L: a non-empty list of floats
Returns:
If L has an odd number of elements, returns the median
element of L. For example, if L is the list
[15.0, 5.3, 18.2], returns 15.0.
If L has an even number of elements, returns the average
of the two median elements. For example, if L is the
list [1.0, 2.0, 3.0, 4.0], returns 2.5.
If the list is empty, raises a ValueError exception.
Side effects: none.
"""
if L == []: raise ValueError, 'List is empty'
sortL = sorted(L[:])
length = len(sortL)
median = length/2
if length%2 == 1:
return sortL[median]
else:
return (sortL[median-1]+sortL[median])/2.0
# Problem 3: --> Correct
# The code prints:
# 16.0
# Circle with radius 4
# Circle with radius 8
# Problem 4:
# 4.1: --> Correct
# n = total items
# pi = value of item i
# xi = whether item is selected or not 1/0
# wi = weight of item i
# C = the constraint, in this case the total weight
# 4.2: --> Correctish
# Formula 1: the highest sum of the total value of selected items from i = 1 to n
# Formula 2: within the constraint of the sum of weights of the selected items from
# i = 1 to n being less than or equal to the constraint C.
# Problem 5: --> Incorrect, I hate writing pseudocode!
# Take a list, L split it in half until you can compare each list entry individually.
# then merge the lists back together in order.
# Problem 6: --> I think it is correct, but implemented with a while loop instead of recursively
def findNumber(maxVal):
"""
Assumes that maxVal is a positive integer.
Returns a number, num, such that cmpGuess(num) == 0.
"""
lowGuess = 0
highGuess = maxVal
guess = (highGuess+lowGuess)/2
correct = cmpGuess(guess)
while correct != 0:
if correct == 1:
highGuess = guess
guess = (highGuess+lowGuess)/2
correct = cmpGuess(guess)
else:
lowGuess = guess
guess = (highGuess+lowGuess)/2
correct = cmpGuess(guess)
return guess
tuckertuck
9 months ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 16, HW 1
# 6.00 Problem Set 9
#
# Name:
# Collaborators:
# Time:
from string import *
class Shape(object):
def area(self):
raise AttributeException("Subclasses should override this method.")
class Square(Shape):
def __init__(self, h):
"""
h: length of side of the square
"""
self.side = float(h)
def area(self):
"""
Returns area of the square
"""
return self.side**2
def __str__(self):
return 'Square with side ' + str(self.side)
def __eq__(self, other):
"""
Two squares are equal if they have the same dimension.
other: object to check for equality
"""
return type(other) == Square and self.side == other.side
class Circle(Shape):
def __init__(self, radius):
"""
radius: radius of the circle
"""
self.radius = float(radius)
def area(self):
"""
Returns approximate area of the circle
"""
return 3.14159*(self.radius**2)
def __str__(self):
return 'Circle with radius ' + str(self.radius)
def __eq__(self, other):
"""
Two circles are equal if they have the same radius.
other: object to check for equality
"""
return type(other) == Circle and self.radius == other.radius
#
# Problem 1: Create the Triangle class
#
## TO DO: Implement the `Triangle` class, which also extends `Shape`.
class Triangle(Shape):
def __init__(self, base, height):
"""
base: base of the triangle
height: height of the triangle
"""
self.base = float(base)
self.height = float(height)
def area(self):
"""
Returns area of the triangle.
"""
return 0.5*self.base*self.height
def __str__(self):
return 'Triangle with base %0.1f and height %0.1f' % (self.base, self.height)
def __eq__(self, other):
"""
Two triangles are equal if they have the same base and height
"""
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(object):
def __init__(self):
"""
Initialize any needed variables
"""
self.shSet = {}
self.place = None
def valueList(self):
return self.shSet.values()
def addShape(self, sh):
"""
Add shape sh to the set; no two shapes in the set may be
identical
sh: shape to be added
"""
valueList = self.shSet.values()
added = False
for i in valueList:
#print i, sh, added
if self.shSet == {}:
break
if i == sh:
added = True
print 'The', sh, 'has already been added!'
break
if added == False:
self.shSet[(type(sh),sh)] = 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):
valueList = self.shSet.values()
#print valueList
if self.place >= len(self.shSet):
raise StopIteration
self.place += 1
return valueList[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)
"""
circleList = []
squareList = []
triangleList = []
for i, j in self.shSet:
if i == Circle:
circleList.append(str(j))
if i == Square:
squareList.append(str(j))
if i == Triangle:
triangleList.append(str(j))
return '\n'.join(circleList+squareList+triangleList)
#
# 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
"""
largestShape = ()
shapeArea = []
for shape in shapes:
area = shape.area()
shapeArea.append((area,shape))
sortedArea = sorted(shapeArea, reverse=True)
largestShape += (sortedArea[0][1],)
for i in range(1,len(sortedArea)-1):
if (sortedArea[i][0]) == (sortedArea[i-1][0]):
largestShape += (sortedArea[i][1],)
return largestShape
#
# 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
"""
ss = ShapeSet()
inputFile = open(filename)
for line in inputFile:
l = line.strip() # strips line break
l = l.split(',') # strips commas and converts into a list
name = lower(l[0])
dim1 = l[1]
dim2 = l[-1]
if name == 'circle':
shape = Circle(dim1)
elif name == 'square':
shape = Square(dim1)
elif name == 'triangle':
shape = Triangle(dim1, dim2)
else: raise ValueError('supported shape not found: ' + name)
ss.addShape(shape)
return ss
#
# Problem 2 Test:
#
ss = ShapeSet()
c1 = Circle(2)
s1 = Square(4)
s2 = Square(1)
t1 = Triangle(1,1)
c2 = Circle(2)
s3 = Square(4)
c3 = Circle(5)
t2 = Triangle(1,1)
ss.addShape(c1)
ss.addShape(s1)
ss.addShape(s2)
ss.addShape(t1)
ss.addShape(c2)
ss.addShape(s3)
ss.addShape(c3)
ss.addShape(t2)
ss.addShape(c1)
print ss
#
# Problem 3 Test:
#
##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))
##
##ss.addShape(Triangle(3,8))
##ss.addShape(Circle(1))
##ss.addShape(Triangle(4,6))
##
##t = Triangle(6,6)
##c = Circle(1)
##ss = ShapeSet()
##ss.addShape(t)
##ss.addShape(c)
##
##print ss
##largest = findLargest(ss)
##for e in largest: print e, 'has the largest area'
#
# Problem 4 Test:
#
ss = readShapesFromFile("shapes.txt")
print ss
tuckertuck
9 months ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 14, HW 1
Problem 4 was really hard.
It was easy to get the dynamic programming sample from the lecture to return the proper value but to get it to return the dictionary was challenging.
# 6.00 Problem Set 8
#
# Intelligent Course Advisor
#
# Name:
# Collaborators:
# Time:
#
import time
SUBJECT_FILENAME = "subjects.txt"
VALUE, WORK = 0, 1
#
# Problem 1: Building A Subject Dictionary
#
def loadSubjects(filename):
"""
Returns a dictionary mapping subject name to (value, work), where the name
is a string and the value and work are integers. The subject information is
read from the file named by the string filename. Each line of the file
contains a string of the form "name,value,work".
returns: dictionary mapping subject name to (value, work)
"""
# The following sample code reads lines from the specified file and prints
# each one.
subjects = {}
inputFile = open(filename)
for line in inputFile:
#print line
l = line.strip() # strips line break
l = l.split(',') # strips commas and converts into a list
name = l[0]
value = int(l[1])
work = int(l[2])
subjects[name] = (value, work)
return subjects
# TODO: Instead of printing each line, modify the above to parse the name,
# value, and work of each subject and create a dictionary mapping the name
# to the (value, work).
def printSubjects(subjects):
"""
Prints a string containing name, value, and work of each subject in
the dictionary of subjects and total value and work of all subjects
"""
totalVal, totalWork = 0,0
if len(subjects) == 0:
return 'Empty SubjectList'
res = 'Course\tValue\tWork\n======\t====\t=====\n'
subNames = subjects.keys()
subNames.sort()
for s in subNames:
val = subjects[s][VALUE]
work = subjects[s][WORK]
res = res + s + '\t' + str(val) + '\t' + str(work) + '\n'
totalVal += val
totalWork += work
res = res + '\nTotal Value:\t' + str(totalVal) +'\n'
res = res + 'Total Work:\t' + str(totalWork) + '\n'
print res
def printValue(subjects):
"""
Prints a string containing total value and work of all subjects
"""
totalVal, totalWork = 0,0
if len(subjects) == 0:
return 'Empty SubjectList'
res = ''
subNames = subjects.keys()
for s in subNames:
val = subjects[s][VALUE]
work = subjects[s][WORK]
totalVal += val
totalWork += work
res = res + 'Total Value: ' + str(totalVal)
res = res + ' Total Work: ' + str(totalWork)
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)
"""
# performs a selection sort on the list of the subjects.keys()
assert type(maxWork) == int and maxWork >= 0
outputSubjects = {}
nameList = subjects.keys()
sortedList = nameList[:]
sumWork = 0
for i in range(len(sortedList) - 1):
minIndx = i
subInfo1 = subjects[sortedList[i]]
j = i + 1
while j < len(sortedList):
subInfo2 = subjects[sortedList[j]]
if not comparator(subInfo1, subInfo2):
minIndx = j
subInfo1 = subjects[sortedList[j]]
j += 1
temp = sortedList[i]
sortedList[i] = sortedList[minIndx]
sortedList[minIndx] = temp
#selects the best answers by the amount of maxWork remaining
for best in sortedList:
work = subjects[best][WORK]
if work + sumWork <= maxWork:
outputSubjects[best] = subjects[best]
sumWork += work
if sumWork == maxWork: break
return outputSubjects
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.
"""
maxWork = [1,2,3,4,5,6,7,8,9,10]
for work in maxWork:
start_time = time.time()
bruteForceAdvisor(SUBJECTS, work)
end_time = time.time()
total_time = end_time - start_time
print 'It took %0.3f seconds to complete bruteForceAdvisor for maxWork = %s' % (total_time, work)
# Problem 3 Observations
# ======================
#
# It took 0.002 seconds to complete bruteForceAdvisor for maxWork = 1
# It took 0.007 seconds to complete bruteForceAdvisor for maxWork = 2
# It took 0.026 seconds to complete bruteForceAdvisor for maxWork = 3
# It took 0.095 seconds to complete bruteForceAdvisor for maxWork = 4
# It took 0.306 seconds to complete bruteForceAdvisor for maxWork = 5
# It took 0.995 seconds to complete bruteForceAdvisor for maxWork = 6
# It took 2.875 seconds to complete bruteForceAdvisor for maxWork = 7
# It took 8.130 seconds to complete bruteForceAdvisor for maxWork = 8
# It took 21.928 seconds to complete bruteForceAdvisor for maxWork = 9
# It took 56.926 seconds to complete bruteForceAdvisor for maxWork = 10
# It took 143.230 seconds to complete bruteForceAdvisor for maxWork = 11
# It took 351.753 seconds to complete bruteForceAdvisor for maxWork = 12
# It took 832.148 seconds to complete bruteForceAdvisor for maxWork = 13
# A reasonable amount of time would be less than a minute so 10 hours or less
#
# Problem 4: Subject Selection By Dynamic Programming
#
def dpAdvisor(subjects, maxWork):
"""
Returns a dictionary mapping subject name to (value, work) that contains a
set of subjects that provides the maximum value without exceeding maxWork.
subjects: dictionary mapping subject name to (value, work)
maxWork: int >= 0
returns: dictionary mapping subject name to (value, work)
"""
nameList = subjects.keys()
tupleList = subjects.values()
i = len(nameList) - 1
outputSubjects = {}
memo = {}
bestSubjectsValue, bestSubjectsIndex = dpHelper(tupleList, i, maxWork, memo, ())
for index in bestSubjectsIndex:
outputSubjects[nameList[index]] = tupleList[index]
return outputSubjects
def dpHelper(tupleList, i, maxWork, memo, subjectsIndex):
try: return memo[(i, maxWork)][0], memo[(i, maxWork)][1]
except KeyError:
if i == 0:
if tupleList[i][WORK] <= maxWork:
# if there is room for the last course to be added
# then it adds the index number of the course to tuple.
subjectsIndex += (i,)
memo[(i, maxWork)] = tupleList[i][VALUE], subjectsIndex
return tupleList[i][VALUE], subjectsIndex
else:
memo[(i, maxWork)] = 0, subjectsIndex
return 0, subjectsIndex
without_value, without_i = dpHelper(tupleList, i-1, maxWork, memo, subjectsIndex)
if tupleList[i][WORK] > maxWork:
memo[(i, maxWork)] = without_value, without_i
return without_value, without_i
else:
with_value, with_i = dpHelper(tupleList, i-1, maxWork - tupleList[i][WORK], memo, subjectsIndex)
with_value += tupleList[i][VALUE]
bestSubjectsValue = max(with_value, without_value)
# conditional decides whether the course was added or not.
# if the course was added then it adds the index number of the course
# to the tuple.
if with_value == bestSubjectsValue:
subjectsIndex = with_i + (i,)
memo[(i, maxWork)] = bestSubjectsValue, subjectsIndex
else:
subjectsIndex = without_i
memo[(i, maxWork)] = bestSubjectsValue, subjectsIndex
return bestSubjectsValue, subjectsIndex
#
# Problem 5: Performance Comparison
#
def dpTime():
"""
Runs tests on dpAdvisor and measures the time required to compute an
answer.
"""
maxWork = [1,2,3,4,5,6,7,8,9,10,20,25,50,100,200,300,400,500]
for work in maxWork:
start_time = time.time()
dpAdvisor(SUBJECTS, work)
end_time = time.time()
total_time = end_time - start_time
print 'It took %0.3f seconds to complete dpAdvisor for maxWork = %s' % (total_time, work)
def greedyTime():
maxWork = [1,2,3,4,5,6,7,8,9,10,20,25,50,100,200,300,400,500]
for work in maxWork:
start_time = time.time()
greedyAdvisor(SUBJECTS, work, cmpRatio)
end_time = time.time()
total_time = end_time - start_time
print 'It took %0.3f seconds to complete dpAdvisor for maxWork = %s' % (total_time, work)
# Problem 5 Observations
# ======================
#
# TODO: write here your observations regarding dpAdvisor's performance and
# how its performance compares to that of bruteForceAdvisor.
#
# Greedy
# It took 0.058 seconds to complete dpAdvisor for maxWork = 1
# It took 0.058 seconds to complete dpAdvisor for maxWork = 2
# It took 0.059 seconds to complete dpAdvisor for maxWork = 3
# It took 0.057 seconds to complete dpAdvisor for maxWork = 4
# It took 0.055 seconds to complete dpAdvisor for maxWork = 5
# It took 0.057 seconds to complete dpAdvisor for maxWork = 6
# It took 0.057 seconds to complete dpAdvisor for maxWork = 7
# It took 0.057 seconds to complete dpAdvisor for maxWork = 8
# It took 0.056 seconds to complete dpAdvisor for maxWork = 9
# It took 0.057 seconds to complete dpAdvisor for maxWork = 10
# It took 0.057 seconds to complete dpAdvisor for maxWork = 20
# It took 0.057 seconds to complete dpAdvisor for maxWork = 25
# It took 0.058 seconds to complete dpAdvisor for maxWork = 50
# It took 0.058 seconds to complete dpAdvisor for maxWork = 100
# It took 0.057 seconds to complete dpAdvisor for maxWork = 200
# It took 0.057 seconds to complete dpAdvisor for maxWork = 300
# It took 0.056 seconds to complete dpAdvisor for maxWork = 400
# It took 0.056 seconds to complete dpAdvisor for maxWork = 500
#
# Dynamic Programming
# It took 0.002 seconds to complete dpAdvisor for maxWork = 1
# It took 0.003 seconds to complete dpAdvisor for maxWork = 2
# It took 0.003 seconds to complete dpAdvisor for maxWork = 3
# It took 0.005 seconds to complete dpAdvisor for maxWork = 4
# It took 0.006 seconds to complete dpAdvisor for maxWork = 5
# It took 0.006 seconds to complete dpAdvisor for maxWork = 6
# It took 0.008 seconds to complete dpAdvisor for maxWork = 7
# It took 0.009 seconds to complete dpAdvisor for maxWork = 8
# It took 0.010 seconds to complete dpAdvisor for maxWork = 9
# It took 0.010 seconds to complete dpAdvisor for maxWork = 10
# It took 0.023 seconds to complete dpAdvisor for maxWork = 20
# It took 0.024 seconds to complete dpAdvisor for maxWork = 21
# It took 0.029 seconds to complete dpAdvisor for maxWork = 25
# It took 0.067 seconds to complete dpAdvisor for maxWork = 50
# It took 0.144 seconds to complete dpAdvisor for maxWork = 100
# It took 0.316 seconds to complete dpAdvisor for maxWork = 200
# It took 0.491 seconds to complete dpAdvisor for maxWork = 300
# It took 0.700 seconds to complete dpAdvisor for maxWork = 400
# It took 0.921 seconds to complete dpAdvisor for maxWork = 500
#
# The performance of dpAdvisor increases slowly as maxWork increases because
# as maxWork increases the total number of solutions increases and since the
# complexity is O(ns) where n is number of subjects and s is the number of
# solutions.
#
# bruteForceAdvisor grows exponentially and isn't workable past maxWork > 10
# I'm guessing the complexity is O(2**ns) as the size of the solution grows
# when maxWork increases
#
# greedyAdvisor complexity is O(n) where n is the number of entries in subjects.
# The time it takes to solve doesn't change when maxWork changes. the comparator
# cmpRatio gives the correct answer most of the time, but not always.
#
# dpAdvisor is faster than greedyAdvisor when maxWork < 50
# dpAdvisor is faster than bruteForceAdvisor when maxWork > 1
#
if __name__ == '__main__':
SUBJECTS = loadSubjects('subjects.txt')
maxWork = 30
#
# Testing Problem 2
#
##print 'Greedy By Value'
##printSubjects(greedyAdvisor(SUBJECTS, maxWork, cmpValue))
##print 'Greedy By Work'
##printSubjects(greedyAdvisor(SUBJECTS, maxWork, cmpWork))
##print 'Greedy By Ratio'
##printSubjects(greedyAdvisor(SUBJECTS, maxWork, cmpRatio))
##if maxWork <= 10:
## print 'Brute Force'
## printSubjects(bruteForceAdvisor(SUBJECTS, maxWork))
#
# Testing Problem 4
#
##print 'Dynamic Programming'
printSubjects(dpAdvisor(SUBJECTS, maxWork))
##for work in range(1,60):
## print 'Greedy By Ratio'
## printValue(greedyAdvisor(SUBJECTS, work, cmpRatio))
## print 'Dynamic Programming'
## printValue(dpAdvisor(SUBJECTS, work))
## print
#
# Testing Problem 5
#
##print 'Greedy'
##greedyTime()
##print
##print 'Brute Force'
##bruteForceTime()
##print
##print 'Dynamic Programming'
##dpTime()
tuckertuck
9 months ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 12, HW 1
#
# Problem 1: What is the computational complexity of fact0()?
#
def fact0(i):
assert type(i) == int and i >= 0
if i == 0 or i == 1:
return 1
return i * fact0(i-1)
#
# The complexity of fact0 is O(n) or Linear where n = i.
# The function recurs once for every i and then returns i - 1 until it hits
# the base case.
#
#
# Problem 2: What is the computational complexity of fact1()?
#
def fact1(i):
assert type(i) == int and i >= 0
res = 1
while i > 1:
res = res * i
i -= 1
return res
#
# The complexity of fact1 is O(n) or Linear where n = i - 1.
# The function iterates from i to i > 1.
#
#
# Problem 3: What is the computational complexity of MakeSet()?
#
def makeSet(s):
assert type(s) == str
res = ''
for c in s:
if not c in res:
res = res + c
return res
#
# The complexity of MakeSet is O(n) or Linear where n = len(s).
# The function iterates through the string s and decides whether or not to add
# the character, c to res, before finally returning the value of res, which is
# the unique characters in the string.
#
#
# Problem 3: What is the computational complexity of intersect()?
#
def intersect(s1, s2):
assert type(s1) == str and type(s2) == str
s1 = makeSet(s1)
s2 = makeSet(s2)
res = ''
for e in s1:
print e
if e in s2:
print res
res = res + e
return res
#
# The complexity of intersect is O(n) or Linear where n = len(s1).
# The function iterates through the string s1 and checks whether the character,
# e is also in s2. If it is then it saves the character to res and finally
# returns all characters that are the same in both words.
#
#
# Problem 5: Present a hand simulation of the following code:
#
def swap0(s1, s2):
assert type(s1) == list and type(s2) == list
tmp = s1[:]
s1 = s2[:]
s2 = tmp
return
s1 = [1]
s2 = [2]
swap0(s1, s2)
print s1, s2
#
# __main__
# s1 --> [1]
# s2 --> [2]
# swap0(s1, s2)
#
# __swap0__
# tmp --> [1]
# s1 --> [2]
# s2 --> [1]
# s1 = [2], s2 = [1]
#
# __main__
# s1 = [1], s2 = [2]
# print [1], [2]
#
#
# Problem 6: Present a hand simulation of the following code:
#
def swap1(s1, s2):
assert type(s1) == list and type(s2) == list
return s2, s1
s1 = [1]
s2 = [2]
s1, s2 = swap1(s1, s2)
print s1, s2
#
# __main__
# s1 --> [1]
# s2 --> [2]
# swap1(s1, s2)
#
# __swap1__
# return s2, s1
#
# __main__
# s1, s2 --> s2, s1
# s1 = [2], s2 = [1]
# print [2], [1]
#
#
# Problem 7: Present a hand simulation of the following code:
#
def rev(s):
assert type(s) == list
for i in range(len(s)/2):
tmp = s[i]
s[i] = s[-(i+1)]
s[-(i+1)] = tmp
s = [1,2,3]
rev(s)
print s
#
# __main__
# s --> [1,2,3]
# rev(s)
#
# __rev__
# for i in range(0,1)
# for i is 0
# tmp --> s[0] --> 1
# s[0] --> s[-1] --> 3
# s[-1] --> 3
# for i is 1
# tmp --> s[1] --> 2
# s[1] --> s[-2] --> 2
# s[-2] --> 2
#
# __main__
# print [3,2,1]
#
tuckertuck
9 months ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 11, HW 1
Problem 5:
The complexity of pick_best_word is O(n^2) or Quadratic.
You have to iterate the length of the word_list and then the length of each word. Since there are 83667 words in the list, then you need to iterate 83667 * len(word) which is anywhere from 2 to 7 letters long.
It took my computer typically 0.34 seconds to find a word.
The complexity of pick_best_word_faster is O(2^n) or Exponential.
While the algorithm is more complex, it is only limited by the maximum times you have to iterate through the Hand. Since there are 7 letters maximum in the hand then it only needs to make 2^7 or 128 steps.
It took my computer typically 0.001 seconds to find a word
# 6.00 Problem Set 6
#
# The 6.00 Word Game
# Name: tuckertuck
# Time: 9:00
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)
# -----------------------------------
#
# Scoring a word
#
def get_word_score(word, n):
"""
Returns the score for a word. Assumes the word is a
valid word.
The score for a word is the sum of the points for letters
in the word, plus 50 points if all n letters are used on
the first go.
Letters are scored as in Scrabble; A is worth 1, B is
worth 3, C is worth 3, D is worth 2, E is worth 1, and so on.
word: string (lowercase letters)
returns: int >= 0
"""
score = 0
for letter in word:
score += SCRABBLE_LETTER_VALUES[letter.lower()]
if len(word) == n:
score += 50
return score
#
# Make sure you understand how this function works and what it does!
#
def display_hand(hand):
"""
Displays the letters currently in the hand.
For example:
display_hand({'a':1, 'x':2, 'l':3, 'e':1})
Should print out something like:
a x x l l l e
The order of the letters is unimportant.
hand: dictionary (string -> int)
"""
for letter in hand.keys():
for j in range(hand[letter]):
print letter, # print all on the same line
print # print an empty line
#
# Make sure you understand how this function works and what it does!
#
def deal_hand(n):
"""
Returns a random hand containing n lowercase letters.
At least n/3 the letters in the hand should be VOWELS.
Hands are represented as dictionaries. The keys are
letters and the values are the number of times the
particular letter is repeated in that hand.
n: int >= 0
returns: dictionary (string -> int)
"""
hand={}
num_vowels = n / 3
for i in range(num_vowels):
x = VOWELS[random.randrange(0,len(VOWELS))]
hand[x] = hand.get(x, 0) + 1
for i in range(num_vowels, n):
x = CONSONANTS[random.randrange(0,len(CONSONANTS))]
hand[x] = hand.get(x, 0) + 1
#hand = {'g':1,'o':1,'l':1,'d':1,'e':1,'s':1,'t':1}
return hand
#
# 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.
word: string
hand: dictionary (string -> int)
returns: dictionary (string -> int)
"""
freq = get_frequency_dict(word)
newhand = {}
for char in hand:
newhand[char] = hand[char]-freq.get(char,0)
return newhand
#return dict( ( c, hand[c] - freq.get(c,0) ) for c in hand )
#
# Test word validity
#
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
"""
freq = get_frequency_dict(word)
for letter in word:
if freq[letter] > hand.get(letter, 0):
return False
return word in points_dict
# Problem 1 & 2: Computing Time
#
# Playing a hand
#
def play_hand(hand, word_list, clock):
"""
Allows the user to play the given hand, as follows:
* The hand is displayed.
* The user may input a word.
* An invalid word is rejected, and a message is displayed asking
the user to choose another word.
* When a valid word is entered, it uses up letters from the hand.
* After every valid word: the score for that word is displayed,
the remaining letters in the hand are displayed, and the user
is asked to input another word.
* The sum of the word scores is displayed when the hand finishes.
* The hand finishes when there are no more unused letters.
The user can also finish playing the hand by inputing a single
period (the string '.') instead of a word.
hand: dictionary (string -> int)
word_list: list of lowercase strings
"""
total = 0
update_clock = clock
initial_handlen = sum(hand.values())
while sum(hand.values()) > 0:
print
print 'Current Hand:',
display_hand(hand)
start_time = time.time()
## userWord = raw_input('Enter word, or a . to indicate that you are finished: ') # Human Player
## userWord = pick_best_word(hand, points_dict) # Computer Player
userWord = pick_best_word_faster(hand, rearrange_dict) # Even Faster Computer Player
if userWord == '.':
break
else:
isValid = is_valid_word(userWord, hand, points_dict)
if not isValid:
print 'Invalid word, please try again.'
else:
end_time = time.time()
total_time = (end_time - start_time)#*(1+time_limit)
update_clock -= total_time
print 'It took %0.3f seconds to provide an answer.' % total_time
if update_clock >= 0:
if total_time == 0: points = get_word_score(userWord, initial_handlen)
else: points = get_word_score(userWord, initial_handlen)/(1+total_time)
#print total_time
total += points
print 'You have %0.2f seconds remaining.' % update_clock
print '%s earned %0.2f points. Total: %0.2f points.' % (userWord, points, total)
hand = update_hand(hand, userWord)
else:
print 'Total time exceeds %s seconds. You scored %0.2f points.' % (clock, total)
break
print 'Total score: %0.2f points.' % total
#
# 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.
"""
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':
#chess_clock = int(raw_input('Enter time limit, in seconds, for players: '))
chess_clock = time_limit
hand = deal_hand(HAND_SIZE)
play_hand(hand.copy(), word_list, chess_clock)
print
elif cmd == 'r':
play_hand(hand.copy(), word_list, chess_clock)
print
elif cmd == 'e':
break
else:
print "Invalid command."
#
# Problem #3: Computer Player
#
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.
"""
#print hand
ans = False
best = False
score = 0
for word in points_dict:
word_freq = get_frequency_dict(word)
#print word
for letter in word_freq:
#print letter
if letter in hand and word_freq[letter] <= hand[letter]:
ans = True
continue
else:
ans = False
break
if ans == True:
#print word
new_score = points_dict[word]
if new_score > score:
score = new_score
best_word = word
best = True
if best == True:
#print best_word
return best_word
else: return '.'
def get_words_to_points(word_list):
"""
Return a dict that maps every word in word_list to its point value.
"""
points_dict = {}
for word in word_list:
points_dict[word] = get_word_score(word, HAND_SIZE)
return points_dict
def get_time_limit(points_dict, k):
"""
Return the time limit for the computer player as a function of the
multiplier k.
points_dict should be the same dictionary that is created by
get_words_to_points.
"""
start_time = time.time()
# Do some computation. The only purpose of the computation is so we can
# figure out how long your computer takes to perform a known task.
for word in points_dict:
get_frequency_dict(word)
get_word_score(word, HAND_SIZE)
end_time = time.time()
return (end_time - start_time) * k
#
# Problem #4: Even Faster Computer Player
#
def pick_best_word_faster(hand, rearrange_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.
Uses a binary counter to map whether a letter is part of the subset or not
"""
ans = False
best = False
score = 0
sorted_hand = sort_dic(hand)
#print sorted_hand
if sorted_hand in rearrange_dict:
#print points_dict[rearrange_dict[sorted_hand]]
return rearrange_dict[sorted_hand]
elif len(sorted_hand) > 1:
## Binary represents whether letter gets used in the hand.
for a in range(2):
for b in range(2):
for c in range(2):
for d in range(2):
for e in range(2):
for f in range(2):
for g in range(2):
binary = (g,f,e,d,c,b,a)
dic = dict(zip(sorted_hand,binary))
#print dic
sorted_dic = sort_dic(dic)
#print binary, sorted_dic
#print sorted_hand
if sorted_dic in rearrange_dict:
word = rearrange_dict[sorted_dic]
#print word
new_score = points_dict[word]
if new_score > score:
score = new_score
best_word = word
best = True
if best == True:
#print best_word
return best_word
else: return '.'
def sort_dic(hand):
"""
Returns Tuple of alphabetized letters in a given Dictionary of value >= 1
"""
l = []
for letter in hand.keys():
for j in range(hand[letter]):
l.append(letter)
sorted_tuple = tuple(sorted(l))
return sorted_tuple
def get_word_rearrangements(word_list):
rearrange_dict = {}
for word in word_list:
dorw = tuple(sorted(word))
#print dorw, word
rearrange_dict[dorw] = word
return rearrange_dict
#
# Build data structures used for entire session and play game
#
if __name__ == '__main__':
word_list = load_words()
rearrange_dict = get_word_rearrangements(word_list)
points_dict = get_words_to_points(word_list)
time_limit = get_time_limit(points_dict, 2)
play_game(word_list)
tuckertuck
9 months ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 8, HW 1
Problem 1
1.1 False -> Correct
1.2 False -> Correct
1.3 False -> Correct
1.3 False -> Correct
1.5 False -> Correct
1.6 True -> Correct
1.7 True -> Correct
Problem 2
2.1 Yes -> Correct
2.2 Yes -> Incorrect
Problem 3
3.1 6 -> Correct
3.2 Returns the sum of the digits in the number x -> Correct
Problem 5
I don't know how to write pseudo code
Problem 7 -> Correct
Yes
Problem 9 -> Incorrect
Takes an integer and returns a string of that integer
#Problem 4 -> Kind of correct
def first_N(n):
squares = []
for x in range(1,n*2,2):
squares.append(x*x)
print tuple(squares)
#Problem 6 -> Correct
def findSide():
"""asks the user to enter the area of a rectangle and the length of one side of the rectangle. Returns a floating point number that is the length of the adjacent side."""
height = 0.0
area = float(raw_input('Enter the area of a rectangle: '))
length = float(raw_input('Enter the length of one side: '))
if length == 0:
return height
else: height = area/length
return height
#Problem 8 -> Correct, but forgot to divide num by 6, 9, 20 so is inefficient.
def f(num):
a = 6
b = 9
c = 20
for x in range(0,num+1):
for y in range(0,num+1):
for z in range(0,num+1):
if a*x + b*y + c*z == num:
return True
return False
tuckertuck
10 months ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 9, HW 2
This was one of my favourite problem sets so far.
# Problem Set 5: Ghost
# Name: tuckertuck
# Collaborators:
# Time: 2 hours
#
import random
# -----------------------------------
# Helper code
# (you don't need to understand this helper code)
import string
WORDLIST_FILENAME = "words.txt"
def load_words():
"""
Returns a list of valid words. Words are strings of lowercase letters.
Depending on the size of the word list, this function may
take a while to finish.
"""
print "Loading word list from file..."
# inFile: file
inFile = open(WORDLIST_FILENAME, 'r', 0)
# wordlist: list of strings
wordlist = []
for line in inFile:
wordlist.append(line.strip().lower())
print " ", len(wordlist), "words loaded."
return wordlist
def get_frequency_dict(sequence):
"""
Returns a dictionary where the keys are elements of the sequence
and the values are integer counts, for the number of times that
an element is repeated in the sequence.
sequence: string or list
return: dictionary
"""
# freqs: dictionary (element_type -> int)
freq = {}
for x in sequence:
freq[x] = freq.get(x,0) + 1
return freq
# (end of helper code)
# -----------------------------------
# Actually load the dictionary of words and point to it with
# the wordlist variable so that it can be accessed from anywhere
# in the program.
def is_valid_fragment(word, wordlist, low, high):
"""
Returns True if the word fragment is a fragment of a word in wordlist.
Performs a binary search to locate the fragment within the list of words.
"""
word = word.lower()
guess = (low+high)/2
if wordlist[guess].find(word) == 0:
#print wordlist[guess], low, high
return True
if low + 1 == high:
#print wordlist[guess], low, high
return False
if word < wordlist[guess]:
#print wordlist[guess], low, high
return is_valid_fragment(word, wordlist, low, guess)
else:
#print wordlist[guess], low, high
return is_valid_fragment(word, wordlist, guess, high)
def is_word(word, wordlist):
"""
Returns True if the word fragment is a completed word in wordlist
4 letters or more in length.
"""
word = word.lower()
if len(word) > 3 and word in wordlist:
return True
return False
def alt_player(currentPlayer):
if currentPlayer == 1:
return 2
else: return 1
def ghost(wordlist):
"""
Allows two players to play a game of Ghost
* Displays current word fragment
* Asks to input letter
* If letter is valid adds it to the word fragment
* If word fragment is valid players take turns
* Player loses if they complete a word over 3 letters or creates and invalid word fragment
wordlist: list of lowercase strings
"""
## Initialize Game
currentPlayer = 1
word = ''
lossCondition = 0
print
print 'Welcome to Ghost!'
print 'Player', currentPlayer ,'goes first.'
## Game Loop
while True:
print "Current word fragment: '" + word.upper() + "'"
letter = raw_input('Player ' + str(currentPlayer) + ' says letter: ')
if letter == '':
print 'Invalid letter, please choose again.'
continue
if letter in string.ascii_letters:
word += letter
else:
print 'Invalid letter, please choose again.'
continue
# Checks if word fragment is valid
if not is_valid_fragment(word, wordlist, 0, len(wordlist)):
lossCondition = 1
break
# Checks if word fragment is complete word 4 letters or more
if is_word(word, wordlist):
lossCondition = 0
break
# Alternates Players
currentPlayer = alt_player(currentPlayer)
print
print 'Player '+ str(currentPlayer)+"'s turn"
## Win/Loss Conditions
if lossCondition == 1:
print
print "Current word fragment: '" + word.upper() + "'"
print "Player " + str(currentPlayer) + " loses because no word begins with '"+ word.upper()+"'!"
print "Player " + str(alt_player(currentPlayer)) + " wins!"
elif lossCondition == 0:
print
print "Current word fragment: '" + word.upper() + "'"
print "Player " + str(currentPlayer) + " loses because '"+ word.upper()+"' is a word!"
print "Player " + str(alt_player(currentPlayer)) + " wins!"
## Replay Game Loop
while True:
print
replay = raw_input('Do you want to play again? Y/N: ').upper()
if replay == 'Y':
return ghost(wordlist)
elif replay == 'N':
print 'Thanks for playing, Goodbye!'
break
else:
print 'Invalid choice, please choose again'
#
# Build data structures used for entire session and play game
#
if __name__ == '__main__':
wordlist = load_words()
ghost(wordlist)
tuckertuck
10 months ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 9, HW 1
I realize now that I didn't need to do a binary search for checking if the word was in the word list.
But it was good practice for me since I'm still getting used to writing recursive algorithms.
# Problem Set 5: 6.00 Word Game
# Name: tuckertuck
# Collaborators:
# Time: 1 day
#
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
"""
scoreUpdate = 0
if len(word) > 0:
for letter in word:
scoreUpdate += SCRABBLE_LETTER_VALUES[letter]
if len(word) >= 7 and n >= 7:
scoreUpdate += 50
return scoreUpdate
else: return scoreUpdate
#
# 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)
"""
newHand = hand.copy()
for letter in word:
if letter in hand:
newHand[letter] -= 1
if newHand[letter] == 0:
del newHand[letter]
return newHand
#
# 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
"""
def in_list(word, word_list, ctr):
low = 0
high = len(word_list)
guess = (low+high)/2
if word == word_list[guess]:
#print word_list[guess], '==', wordCandidate
return True
while ctr < 20:
if word < word_list[guess]:
#print word_list[guess]
ctr += 1
return in_list(word, word_list[:guess],ctr)
else:
#print word_list[guess]
ctr += 1
return in_list(word, word_list[guess:],ctr)
return False
def in_hand(word, hand):
checkHand = hand.copy()
for letter in word:
if letter not in checkHand:
return False
if letter in checkHand:
checkHand[letter] -= 1
#print hand
if checkHand[letter] < 0:
return False
return True
#print 'check1', str(check1), 'check2', str(check2)
if in_hand(word, hand) and in_list(word, word_list, 0): return True
else: return False
#
# 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
"""
score = 0
totalScore = 0
while True:
print 'Current Hand:',
display_hand(hand)
word = str(raw_input('Enter word, or a . to indicate that you are finished:'))
#print word.isalpha()
if word == '.':
break
elif not word.isalpha():
print 'Invalid word, please try again.'
continue
word = word.lower()
if is_valid_word(word, hand, word_list):
score = get_word_score(word, len(word))
totalScore += score
print word, 'earned', score, 'points. Total:', totalScore, 'points'
hand = update_hand(hand, word)
else:
print 'Invalid word, please try again.'
print 'Total score:', totalScore, '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.
"""
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)
tuckertuck
10 months ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 7, HW 1
First project in a while where I understood everything the entire time, haha
# Problem Set 4
# Name: tuckertuck
# Collaborators: None
# Time: 2:00
#
# Problem 1
#
def nestEggFixed(salary, save, growthRate, years):
"""
- salary: the amount of money you make each year.
- save: the percent of your salary to save in the investment account each
year (an integer between 0 and 100).
- growthRate: the annual percent increase in your investment account (an
integer between 0 and 100).
- years: the number of years to work.
- return: a list whose values are the size of your retirement account at
the end of each year.
"""
savings = []
for n in range(0,years):
if n == 0:
fund = salary * save * 0.01
savings.append(fund)
else:
fund = savings[-1] * (1 + 0.01 * growthRate) + salary * save * 0.01
savings.append(fund)
return savings
def testNestEggFixed():
salary = 10000
save = 10
growthRate = 15
years = 5
savingsRecord = nestEggFixed(salary, save, growthRate, years)
print savingsRecord
# Output should have values close to:
# [1000.0, 2150.0, 3472.5, 4993.375, 6742.3812499999995]
salary = 10000
save = 10
growthRate = 15
years = 1
savingsRecord = nestEggFixed(salary, save, growthRate, years)
print savingsRecord
#
# 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.
"""
account = []
for n in range(0,len(growthRates)):
if n == 0:
fund = salary * save * 0.01
account.append(fund)
else:
fund = account[n-1] * (1 + 0.01 * growthRates[n]) + salary * save * 0.01
account.append(fund)
return account
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.
"""
balance = []
for n in range(0,len(growthRates)):
if n == 0:
fund = savings * (1 + 0.01 * growthRates[n]) - expenses
balance.append(fund)
else:
fund = balance[n-1] * (1 + 0.01 * growthRates[n]) - expenses
balance.append(fund)
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.
"""
minExpense = 0
retirementFund = nestEggVariable(salary, save, preRetireGrowthRates)[-1]
maxExpense = retirementFund
expensesGuess = (minExpense + maxExpense)/2.0
expensesTest = postRetirement(retirementFund, postRetireGrowthRates, expensesGuess)[-1]
while abs(expensesTest) > epsilon:
if expensesTest < epsilon:
maxExpense = expensesGuess
else:
minExpense = expensesGuess
expensesGuess = (minExpense + maxExpense)/2.0
expensesTest = postRetirement(retirementFund, postRetireGrowthRates, expensesGuess)[-1]
return expensesGuess
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.
tuckertuck
10 months ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 5, HW 1
The recursive function was really making me mad, Still didn't quite get it as I couldn't get it to return the proper statement that I wanted.
from string import *
# this is a code file that you can use as a template for submitting your
# solutions
# these are some example strings for use in testing your code
# target strings
target1 = 'atgacatgcacaagtatgcat'
target2 = 'atgaatgcatggatgtaaatgcag'
# key strings
key10 = 'a'
key11 = 'atg'
key12 = 'atgc'
key13 = 'atgca'
### the following procedure you will use in Problem 3
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 1
def countSubStringMatch(target,key):
"""counts number of times key appears withing the target"""
count = 0
for i in range(0,len(target)):
sequence = find(target,key,i,i+len(key))
if sequence != -1:
count += 1
print key, 'occurs', count, 'times in the string', target
def countSubStringMatchRecursive(target,key, count = 0):
"""Counts the number of times a key appears within the target"""
index = rfind(target,key)
if index != -1:
count += 1
countSubStringMatchRecursive(target[:-len(target)+index],key,count)
else:
print key, 'occurs', count, 'times'
# Problem 2
def subStringMatchExact(target,key):
"""returns tuple with locations where key appears within target"""
startPoint = []
for i in range(0,len(target)):
sequence = find(target,key,i,i+len(key))
if sequence != -1:
startPoint.append(sequence)
return tuple(startPoint)
# Problem 3
def constrainedMatchPair(firstMatch,secondMatch,length):
"""returns a tuple of locations in firstMatch + length + 1 == secondMatch"""
matchPair = []
for k in secondMatch:
for n in firstMatch:
if n + length + 1 == k:
matchPair.append(n)
elif n + length == k and firstMatch[-1] == k and len(secondMatch) == len(firstMatch):
matchPair.append(n)
return tuple(matchPair)
# Problem 4
def subStringMatchExactlyOneSub(target,key):
""" returns all locations of key in target, with exactly one substitution"""
exact = subStringMatchExact(target,key)
oneSub = subStringMatchOneSub(key,target)
exactlyOneSub = list(oneSub)
for match in exact:
for one in oneSub:
if match == one:
exactlyOneSub.remove(match)
return tuple(exactlyOneSub)
tuckertuck
10 months ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 3, HW 1
This was hard for me to figure out until I watched the fourth lecture. I still don't think I understand exactly how I made it work, but I'm pretty sure it works, heh.
##6a + 9b + 20c = n
##
##n | a b c n | a b c n | a b c
##——————————————————————————————————————————————-------------
##50 5 0 1 56 6 0 1 62 7 0 1
##51 7 1 0 57 8 1 0 63 9 1 0
##52 2 0 2 58 3 0 2 64 4 0 2
##53 4 1 1 59 5 1 1 65 6 1 1
##54 9 0 0 60 10 0 0
##55 1 1 2 61 2 1 2
##
##This theorem is true because when six consecutive numbers are solvable every number afterwards is solvable by adding another six to the previous totals.
# Problem Set 2 (Problem 3)
# tuckertuck
# time = 4:00
BestSoFar = 0
packages = (9,6,20)
count = 0
def BruteForceNuggets(n,(x,y,z)):
for a in range(0, n + 1):
for b in range(0, n - (a * x) + 1):
c = (n - (b * y) - (a * x)) / z
if c >= 0:
#print (x*a),'+',(y*b),'+',(z*c),'=',n
if (a * x) + (b * y) + (c * z) == n:
return True
return False
for n in range(1, 200):
if not BruteForceNuggets(n,packages):
BestSoFar = n
print BestSoFar,
count = 0
count += 1
print count
sortPackage = sorted(packages)
if count > sortPackage[0]:
break
print 'Largest number of McNuggets that cannot be bought in exact quantity:',BestSoFar
# Problem Set 2 (Problem 4)
# tuckertuck
bestSoFar = 0 # variable that keeps track of largest number
# of McNuggets that cannot be bought in exact quantity
packages = (13,16,25) # variable that contains package sizes
count = 0
def BruteForceNuggets(n,(x,y,z)):
for a in range(0, n + 1):
for b in range(0, n - (a * x) + 1):
c = (n - (b * y) - (a * x)) / z
if c >= 0:
#print (x*a),'+',(y*b),'+',(z*c),'=',n
if (a * x) + (b * y) + (c * z) == n:
return True
return False
for n in range(1, 200):
if not BruteForceNuggets(n,packages):
BestSoFar = n
#print BestSoFar
count = 0
count += 1
#print count,
sortPackage = sorted(packages)
if count > sortPackage[0]:
break
print "Given package sizes", packages[0], packages[1], "and", packages[2], "the largest number of McNuggets that cannot be bought in exact quantity is:", BestSoFar
tuckertuck
11 months ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 2, HW 1
Creates a tuple up to the Nth prime number. It checks the remainder from dividing the candidate for prime against all the other numbers in the tuple, stopping when the divisor**2 is greater than the candidate and moving on to the next number.
# Problem Set 1
# tuckertuck
# Time = 4 days
prime_candidate = 1
count = 1
primes = (2,)
total = raw_input('nth prime number: ')
if str.isdigit(total):
total = int(total)
while count < total:
prime_candidate += 2 # generates odd numbers
for i in primes[0:]:
if prime_candidate%i == 0 and prime_candidate == i:
continue
elif prime_candidate%i == 0 and prime_candidate != i:
break
elif i*i < prime_candidate and prime_candidate%i != 0: #stops checking when i**2 is greater than prime_candidate for efficiency
continue
else: #prime_candiate is prime if it doesn't meet the other conditions of the seive and added to tuple
primes += (prime_candidate,)
count += 1
break
print 'the', total,'nth prime number is', primes[total-1]
else:
print 'please use a positive integer'
# Problem Set 2
# tuckertuck
# Time = 1 hour
from math import *
prime_candidate = 1
count = 1
primes = (2,)
total = raw_input('nth prime number: ')
if str.isdigit(total):
total = int(total)
while count < total:
prime_candidate += 2 #generates odd numbers
for i in primes[0:]:
if prime_candidate%i == 0 and prime_candidate == i:
continue
elif prime_candidate%i == 0 and prime_candidate != i:
break
elif i*i < prime_candidate and prime_candidate%i != 0:
continue
else: #prime_candiate is prime and added to list
primes += (prime_candidate,)
count += 1
break
print 'the', total,'nth prime number is', primes[total-1]
n = primes[total-1]
log_sum = 0
for i in primes[0:total]:
log_sum += log(i)
ratio = log_sum/n
print 'The sum of the logs up to',total,'is:', log_sum
print 'The ratio of the sum to n is:', ratio
else:
print 'please use a positive integer'
tuckertuck
11 months ago
|
|
|
|
|
