cmlilley

# 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):
        self.x = x
        self.y = y
        
    def __str__(self):
        return "x-coord=" + str(self.x) + " & y-coord=" + str(self.y)
        
    def getX(self):
        return self.x
        
    def getY(self):
        return self.y
        
    def convertPosToTile(self):
        tileX = int(self.x)
        tileY = int(self.y)
        self.tile = (tileX, tileY)
        
        return self.tile
        
    def getNewPosition(self, angle, speed):
        old_x, old_y = self.getX(), self.getY()
        # Compute the change in position
        delta_y = speed * math.cos(math.radians(angle))
        delta_x = speed * math.sin(math.radians(angle))
        # Add that to the existing position
        new_x = old_x + delta_x
        new_y = old_y + delta_y
        return Position(new_x, new_y)


# === Problems 1 and 2

class RectangularRoom(object):
    def __init__(self, width, height):
        self.w = width
        self.h = height
        
        self.cleantiles = []
        self.dirtytiles = []
        for w in range (width):
            for h in range (height):
                self.dirtytiles.append ((w,h))

    def __str__(self):
        return "This RectangularRoom contains the following dirty tiles: \n" + str(self.dirtytiles) + "\n And also the following clean tiles: \n" + str(self.cleantiles)
        
    def cleanTileAtPosition(self, tile):        
        if tile[0] >= self.w or tile[1] >= self.h:
            raise ValueError ("RectangularRoom.cleanTileAtPosition called with a position not in the room.")
        
        self.cleantiles.append (tile)
        self.dirtytiles.remove (tile)
        
    def isTileCleaned(self, m,n):
        tile = (m,n)
        return tile in self.cleantiles
        
    def getNumTiles(self):
        return int(self.w*self.h)
        
    def getNumCleanedTiles(self):
        return len(self.cleantiles)
        
    def getRandomPosition(self):
        return Position(random.triangular(0, self.w), random.triangular(0, self.h))
        
    def isPositionInRoom(self, pos):
        return (0 <= pos.x < (self.w)) and (0<= pos.y < (self.h))


class BaseRobot(object):
    def __init__(self, room, speed):
        self.speed = speed
        self.room = room
        self.d = random.randint(0,359)
        self.p = self.room.getRandomPosition()
        
        
    def getRobotPosition(self):
        return self.p
        
    def getRobotDirection(self):
        return self.d
        
    def setRobotPosition(self, position):
        self.p = position
        
    def setRobotDirection(self, direction):
        self.d = direction


class Robot(BaseRobot):
    def updatePositionAndClean(self):
        thinking = True
        while thinking:
            self.testp = self.p.getNewPosition(self.d, self.speed)
            if self.room.isPositionInRoom(self.testp) == True:
                thinking = False
            else: 
                self.d = random.randint(0,359)
        
        self.p = self.testp
        tile = self.testp.convertPosToTile()
        if not self.room.isTileCleaned(tile[0], tile[1]):
            self.room.cleanTileAtPosition(tile)
        
# === Problem 5

class RandomWalkRobot(BaseRobot):

    def updatePositionAndClean(self):

        thinking = True
        while thinking:
            self.d = random.randint(0,359)
            self.testp = self.p.getNewPosition(self.d, self.speed)
            if self.room.isPositionInRoom(self.testp) == True:
                thinking = False
        
        self.p = self.testp
        tile = self.testp.convertPosToTile()
        if not self.room.isTileCleaned(tile[0], tile[1]):
            self.room.cleanTileAtPosition(tile)


# === Problem 3

def runSimulation(num_robots, speed, width, height, min_coverage, num_trials,robot_type, visualize):
    iTrial = 0											#index of active trial, starts at 0
    trialsList = []
    incomplete = True
    
    while incomplete:
    	trialsList.append (runTrial (num_robots, speed, width, height, min_coverage, robot_type, visualize))
    	if iTrial+1 == num_trials:
    		incomplete = False
    	else:	
    		iTrial += 1
    return trialsList
        
def runTrial (num_robots, speed, width, height, min_coverage, robot_type, visualize):

    trialRoom = RectangularRoom(width, height)
    trialRoomSize = trialRoom.getNumTiles()
    trialSteps = []
    allRobots = []
    for i in range(num_robots):
        allRobots.append(robot_type(trialRoom, speed))
    dirty = True
    # Visualization Code:
    if visualize:
        anim = ps11_visualize.RobotVisualization(num_robots, width, height, .01)

    while dirty:
    	iRobot = 0	
        while iRobot != len(allRobots):
			allRobots[iRobot].updatePositionAndClean()
			iRobot += 1
        if visualize:
            anim.update(trialRoom, allRobots)
        numCleaned = trialRoom.getNumCleanedTiles()
        pctCleaned = float(numCleaned)/float(trialRoomSize)
        trialSteps.append(pctCleaned)
        if pctCleaned >= min_coverage:
            dirty = False
    if visualize:
        anim.done()
    return trialSteps
    

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

# === My Own Helper Function ===
def computeAvgLens(listList):
	"""Given a list of lists, returns the average length of the lists (as a proxy for time elapsed)"""
	tot = 0
	for i in range(len(listList)):
		tot += len(listList[i])
	avg = tot/len(listList)
	return avg


# === Problem 4
def showPlot1():
    """
    Produces a plot showing dependence of cleaning time on room size.
    """
    widths = [5, 10, 15, 20, 25]
    areas = [5**2, 10**2, 15**2, 20**2, 25**2]
    times = []
    for i in widths:
        times.append(computeAvgLens(runSimulation (1, 1.0, i, i, 0.75, 30, RandomWalkRobot, False)))
    
    
    pylab.figure()
    pylab.plot(areas, times, '-ro')
    pylab.axis([0, 650, 0, 3000])  #RandomWalkRobot needs 3 times as long
    pylab.ylabel ('time to clean')
    pylab.xlabel ('areas of room')
    pylab.title ('Room Area vs. 1 Robot Time To Clean')
    
    pylab.show()
# showPlot1()

def showPlot2():
    """
    Produces a plot showing dependence of cleaning time on number of robots.
    """
    number = [1,2,3,4,5,6,7,8,9,10]
    times = []
    for i in number:
        times.append(computeAvgLens(runSimulation (i, 1.0, 25, 25, 0.75, 30, Robot, False)))
    pylab.figure()
    pylab.plot(number, times, '-ro')
    pylab.axis([0, 11, 0, 1000]) 
    pylab.ylabel ('time to clean')
    pylab.xlabel ('number of robots')
    pylab.title ('# of Robots vs. Time To Clean 75% of 25x25 rm')
    
    pylab.show()
    
# showPlot2()

def showPlot3():
    """
    Produces a plot showing dependence of cleaning time on room shape.
    """
    widths = [20, 25, 40, 50, 80, 100]
    heights = [20, 16, 10, 8, 5, 4]
    ratios = [float(widths[i])/float(heights[i]) for i in range(len(widths))]
    times = []
    for i in range (len(widths)):
        times.append(computeAvgLens(runSimulation (1, 1.0, widths[i], heights[i], 0.75, 30, Robot, False)))
    pylab.figure()
    pylab.plot(ratios, times, '-ro')
    pylab.axis([0, 30, 580, 800]) 
    pylab.ylabel ('time to clean')
    pylab.xlabel ('ratio')
    pylab.title ('ratio of width to height vs. Time To Clean 75% of rm')
    
    pylab.show()
# showPlot3()

def showPlot4A():
    """
    Produces a plot showing dependence of cleaning time on required coverage.
    """
    coverages = [.50, .60, .70, .80, .90, .97, .98, .99, 1.0]
    times = []
    for i in coverages:
        times.append(computeAvgLens(runSimulation (5, 1.0, 25,25, i, 30, Robot, False)))
    pylab.figure()
    pylab.plot(coverages, times, '-ro')
    pylab.axis([0.45, 1.05, 0, 6000]) 
    pylab.ylabel ('time to clean (ticks)')
    pylab.xlabel ('required coverage (%)')
    pylab.title ('Coverage Requirements vs. Time To Clean for 1 robot')
    
    pylab.show()
# showPlot4A()


def showPlot4():
    """
    Produces a plot showing cleaning time vs. percentage cleaned, for
    each of 1-5 robots.
    """
    numRobots = [1,2,3,4,5]
    pcts = []
    for i in range (1,6):
        pcts.append (computeMeans(runSimulation (i, 1.0, 25, 25, 1.0, 10, Robot, False)))

    pylab.figure()
    pylab.plot(pcts[0], '-r', label='1 Robot')
    pylab.plot(pcts[1], '-b', label='2 Robots')
    pylab.plot(pcts[2], '-g', label='3 Robots')
    pylab.plot(pcts[3], '-c', label='4 Robots')
    pylab.plot(pcts[4], '-m', label='5 Robots')
    
    pylab.axis ([0, 6300, 0, 1.05]) 
    pylab.xlabel ('time to clean (ticks)')
    pylab.ylabel ('% of floor cleaned')
    pylab.title ('Completed Coverage vs. Time for 1-5 robots')
    pylab.legend() 
    
    pylab.show()
showPlot4()


# === Problem 6

def showPlot5():
    """
    Produces a plot comparing the two robot strategies.
    """
    
    pcts = computeMeans(runSimulation (1, 1.0, 15, 15, 1.0, 30, Robot, False))
    randomWalkPcts = computeMeans(runSimulation (1, 1.0, 15, 15, 1.0, 30, RandomWalkRobot, False))
    
    pylab.figure()
    pylab.plot(pcts, '-r')
    pylab.plot(randomWalkPcts, '-b')

    
    pylab.axis ([0, 7500, 0, 1.05]) 
    pylab.xlabel ('time to clean (ticks)')
    pylab.ylabel ('% of floor cleaned')
    pylab.title ('Coverage vs. Time, for Regular (red) vs RandomWalk (blue) robots')
    
    pylab.show()
# showPlot5()

### Final Comments: RandomWalk Robot averages about 2.5-3 times longer for most tasks, with high volatility between trials. 

# 6.00 Problem Set 12
#
# Name: CMLilley
# Collaborators: none
# Time:

import numpy
import random
import pylab
import copy

class NoChildException(Exception):

#
# PROBLEM 1
#

class SimpleVirus(object):

    def __init__(self, maxBirthProb, clearProb):
        self.maxBirthProb = maxBirthProb
        self.clearProb = clearProb
        
    def doesClear(self):
        return random.random() <= self.clearProb
    
    def reproduce(self, popDensity):        
        if random.random() <= self.maxBirthProb * (1 - popDensity):
        	return SimpleVirus(self.maxBirthProb, self.clearProb)
        else:
        	raise NoChildException()


class SimplePatient(object):
    def __init__(self, viruses, maxPop):
        self.viruses = viruses
        self.maxPop = maxPop

    def getTotalPop(self):
        return len(self.viruses)      

    def update(self):
        virIndex = copy.copy(self.viruses)  #shallow copy, so same items in each list
        for i in virIndex:
            if i.doesClear():
                self.viruses.remove(i)
        density = float(self.getTotalPop()) / float(self.maxPop)
        virIndex = copy.copy(self.viruses)  #shallow copy, so same items in each list
        for i in virIndex:
            try:
                self.viruses.append(i.reproduce(density))
            except NoChildException:
                pass    
        return self.getTotalPop()

#
# PROBLEM 2
#

def problem2():
    numViruses = 100
    maxTime = 300
    viruses = [SimpleVirus(0.1, 0.05) for i in range(numViruses)]
    
    patient = SimplePatient(viruses ,1000)
    time = 0
    popNums = []
    
    while time < maxTime:
        popNums.append(patient.update())
        time += 1

    pylab.figure()
    pylab.plot(popNums, '-r')
    pylab.axis([-5, 310, 350, 1010])
    pylab.ylabel ('Population Size')
    pylab.xlabel ('Time elapsed')
    pylab.title ('SimpleVirus population size over time, w/o drugs')
    
    pylab.show()
    
# problem2()
#### Problem2 comments: pop stabilizes at about 500 in 50 ticks or so, because clearance rate now equals reproduction rate

#
# PROBLEM 3
#

class ResistantVirus(SimpleVirus):

    def __init__(self, maxBirthProb, clearProb, resistances, mutProb):
        SimpleVirus.__init__(self, maxBirthProb, clearProb)  # be sure to use parent __init__ method

        self.resistances = resistances
        self.mutProb = mutProb
        
    def getResistance(self, drug):
        return self.resistances[drug]
        
    def reproduce(self, popDensity, activeDrugs):
        resistable = [self.getResistance(i) for i in activeDrugs] 
        if False not in resistable:                                     # if it doesn't lack key resistance
            if random.random() <= self.maxBirthProb * (1 - popDensity): # and if allowed to reproduce by density
                newResistances = self.resistances.copy()    #make copy of resistances
                for i in newResistances:                    #iterate through them
                    if random.random() <= self.mutProb:     #and change if you hit mutProb
                        if newResistances[i] == True: 
                            newResistances[i] = False
                        else:
                            newResistances[i] = True
                return ResistantVirus(self.maxBirthProb, self.clearProb, newResistances, self.mutProb)
            else:
                raise NoChildException()
        else:
            raise NoChildException()
            
class Patient(SimplePatient):

    def __init__(self, viruses, maxPop):
        SimplePatient.__init__(self, viruses, maxPop)     
        self.activeDrugs = []
        
    def addPrescription(self, newDrug):
        if newDrug not in self.activeDrugs:
            self.activeDrugs.append(newDrug)

    def getPrescriptions(self):
        return self.activeDrugs
        
    def getResistPop(self, drugResist):
        resisters = copy.copy(self.viruses)
        for i in drugResist:            
            for v in self.viruses:
                if v.resistances[i] == False and v in resisters:
                    resisters.remove(v)
        return len(resisters)

    def update(self):
        virIndex = copy.copy(self.viruses)  #shallow copy, so same items in each list
        for i in virIndex:
            if i.doesClear():
                self.viruses.remove(i)
        density = float(self.getTotalPop()) / float(self.maxPop)
        virIndex = copy.copy(self.viruses)  #shallow copy, so same items in each list
        for i in virIndex:
            try:
                self.viruses.append(i.reproduce(density, self.activeDrugs))
            except NoChildException:
                pass
        return self.getTotalPop()
#
# PROBLEM 4
#

def problem4():
    numViruses = 100
    viruses = [ResistantVirus(0.1, 0.05, {'guttagonol':False}, .005) for i in xrange(numViruses)] # list comprehension
    patient = Patient(viruses,1000)
    time = 0
    timetodrug = 10
    timetoend = timetodrug + 150
    popNums = []
    resistNums = []
    while time <= timetodrug:
        popNums.append(patient.update())
        time += 1  
    patient.addPrescription('guttagonol')
    while time <= timetoend:
        popNums.append(patient.update())
        resistNums.append( patient.getResistPop(patient.getPrescriptions()) )
        time += 1
    pylab.figure()
    pylab.plot(popNums, '-r', label = 'Total Population')
    if resistNums[-1] > 0:
        pylab.plot(xrange(timetodrug+1,timetoend+1), resistNums, '-b', label = 'Resistant Population')
        pylab.legend()
    pylab.axis([-5, timetoend+5, -5, 600])
    pylab.ylabel ('Population Size')
    pylab.xlabel ('Time elapsed')
    pylab.title ('ResistantVirus pop over time, w/ Guttagonol added after ' + str(timetodrug) + ' ticks')
    pylab.axvline (x=timetodrug, linestyle = '--')
    
    print "Highest population of resistant bugs was: " + str(resistNums[-1])
    pylab.show()
# problem4()
"""PROBLEM 4 NOTES: If mutation begins immediately, without requiring presence of drug, then total
population falls quickly after drug introduced, stabilizes as resistant viruses become ever larger
part of population, then begins growing again as resistant viruses dominate. Only if drug introduced
by tick 10 or so is resistance usually prevented and virus wiped out.""" 

#
# PROBLEM 5
#
        
def problem5():
    numViruses = 100
    numSimulations = 30
    timetodrug = [0, 10, 25, 75, 150, 300]
    avgList = [] 
    # To cycle through the given configurations:
    for i in range (len(timetodrug)):
        drugtime = timetodrug[i]
    # To run N number of simulations with a given configuration:
        seriesList = []
        timetoend = drugtime + 150
        for n in range (numSimulations):
            viruses = [ResistantVirus(0.1, 0.05, {'guttagonol':False}, .005) for i in range(numViruses)]
            patient = Patient(viruses,1000)
            time = 0
            popNums = []
            while time <= drugtime:
                popNums.append(patient.update())
                time += 1
            patient.addPrescription('guttagonol')
            while time <= timetoend:
                popNums.append(patient.update())    # List for the simulation
                time += 1            
            seriesList.append(popNums[-1])  #list for that series/configuration. Saves only final population size.
        
        pylab.figure()
        pylab.hist (seriesList)
        pylab.yticks(range(10)) 
        pylab.ylabel ('Number of patients at final pop.')
        pylab.xlabel ('Final Population Size')
        titletext = 'ResistantVirus final pops, for treatment delay of ' + str(drugtime) + ' ticks.'
        pylab.title (titletext)
        print "Series complete, for " + str(drugtime) + " ticks of delay."
    pylab.show()

# problem5()
### PROBLEM 5 COMMENTS: No patients are cured at 150 or 300. For 75 ticks delay, 13% were cured. 
### For 25 ticks delay, 50-75% were cured (This proportion varied most across multiple runs. 
### For 10 delay, 80%. For 0 delay, all patients are cured. This corresponds to the length of 
### time the virus has in which to develop resistance. 

#
# PROBLEM 6
#

def problem6():
    numViruses = 100
    numSimulations = 100
    timetodrug = [0, 10, 25, 75, 150, 300]
    # To cycle through the given configurations:
    for i in range (len(timetodrug)):
        drugtime = timetodrug[i]
    # To run N number of simulations with a given configuration:
        seriesList = []
        timetoend = 150 + drugtime + 150
        for n in range (numSimulations):
            viruses = [ResistantVirus(0.1, 0.05, {'guttagonol':False, 'grimpex':False}, .005) for i in range(numViruses)]
            patient = Patient(viruses,1000)
            time = 0
            popNums = []  
            while time < 150:
                popNums.append(patient.update())
                time += 1
            patient.addPrescription('guttagonol')
            while time < drugtime + 150:
                popNums.append(patient.update())
                time += 1
            patient.addPrescription('grimpex')
            while time < timetoend:
                popNums.append(patient.update())    # List for the simulation
                time += 1
            seriesList.append(popNums[-1])  #list for that series/configuration. Saves only final population size.
            print "Total time elapsed this Simulation: " + str(time) + " ticks."
            
        pylab.figure()
        pylab.hist (seriesList)
        # pylab.yticks(range(20)) 
        pylab.ylabel ('Number of patients at final pop.')
        pylab.xlabel ('Final Population Size')
        titletext = 'Final pops, for delay of ' + str(drugtime) + ' ticks before 2nd drug.'
        pylab.title (titletext)
        print "Series complete, for " + str(drugtime) + " ticks of delay."
    pylab.show()
# problem6()

### PROBLEM 6 NOTES: There is considerable stochastic variability in results, so I was forced to 
### run 100 trials per configuration. At that sample size, a trend-line becomes clearer. Even at 0 
### ticks delay, there is a chance for enough viruses to acquire immunity to both drugs during the 
### first 150 ticks before either drug is introduced, so about 11% of patients remain infected. For 
### 10-150 ticks delay, cure rate gradually falls through 81 to 69 to 53 percent, then more abruptly 
### to 17, then 6. At this delay, we're guaranteeing that grimpex resistance develops fully before 
### grimpex is added. 



#
# PROBLEM 7
#
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. (Borrowed from a previous 6.00 assignment)
    """
    # Find length of longest list
    longest = 0
    for lst in list_of_lists:
        if len(lst) > longest:
           longest = len(lst)
    # Get totals
    tots = [0]*(longest)
    for lst in list_of_lists:
        for i in range(longest):
            if i < len(lst):
                tots[i] += lst[i]
            else:
                tots[i] += lst[-1]
    # Convert tots to an array to make averaging across each index easier
    tots = pylab.array(tots)
    # Compute means
    means = tots/float(len(list_of_lists))
    return means

def problem7():

    numViruses = 100
    numSimulations = 1
    timetodrug = [0, 300]
    avgList = []
    
    # To cycle through the given configurations:
    for i in range (len(timetodrug)):
        drugsdelay = timetodrug[i]
        timetoend = 150 + drugsdelay + 150
    
    # To run N number of simulations with a given configuration:
        seriesPops = []
        seriesResist = []
        seriesGutt = []
        seriesGrim = []
        
        for n in range (numSimulations):
            viruses = [ResistantVirus(0.1, 0.05, {'guttagonol':False, 'grimpex':False}, .005) for i in range(numViruses)]
            patient = Patient(viruses,1000)
            time = 0
            popNums = []
            guttResist = []
            grimResist = []
            bothResist = []
            
            while time < 150:
                popNums.append(patient.update())
                bothResist.append(patient.getResistPop(['guttagonol', 'grimpex']))
                guttResist.append(patient.getResistPop(['guttagonol',]))
                grimResist.append(patient.getResistPop(['grimpex',]))
                time += 1
            patient.addPrescription('guttagonol')
            while time < drugsdelay + 150:
                popNums.append(patient.update())
                bothResist.append(patient.getResistPop(['guttagonol', 'grimpex']))
                guttResist.append(patient.getResistPop(['guttagonol',]))
                grimResist.append(patient.getResistPop(['grimpex',]))
                time += 1
            patient.addPrescription('grimpex')
            while time < timetoend:
                popNums.append(patient.update())    # List for the simulation
                bothResist.append(patient.getResistPop(['guttagonol', 'grimpex']))
                guttResist.append(patient.getResistPop(['guttagonol',]))
                grimResist.append(patient.getResistPop(['grimpex',]))
                time += 1
            
            print "For this trial, total pop was " + str(popNums[-1]) + ", bothResist was " + str(bothResist[-1]) + ", guttResist was "  + str(guttResist[-1]) + ", and grimResist was "  + str(grimResist[-1])
            seriesPops.append(popNums)
            seriesResist.append(bothResist)
            seriesGutt.append(guttResist)
            seriesGrim.append(grimResist)
        
        popMeans = computeMeans(seriesPops)
        resistMeans = computeMeans(seriesResist)
        guttMeans = computeMeans(seriesGutt)
        grimMeans = computeMeans(seriesGrim)
        
        print "Series complete for delay of " + str(drugsdelay)
        
        pylab.figure()
        pylab.plot(popMeans, '-r', label = 'Total Pop')
        pylab.plot(resistMeans, '-b', label = 'Dual-Resistant Pop')
        pylab.plot(guttMeans, '-g', label = 'Guttagonol-Resistant')
        pylab.plot(grimMeans, '-y', label = 'Grimpex-Resistant')
            
        pylab.axis([-5, timetoend+5, -5, 700])
        pylab.ylabel ('Population Size')
        pylab.xlabel ('Time elapsed')
        pylab.title ('ResistantVirus pop: Guttagonol added @ 150, Grimpex @ ' + str(drugsdelay+150) + ' ticks')
        pylab.axvline (x=drugsdelay+150, linestyle = '--')
        pylab.axvline (x=150, linestyle = '--')
        pylab.legend()
    pylab.show()
problem7()

### PROBLEM 7 NOTES: Dual-Resistance is very rare in untreated patients, but not unheard of. It can 
### generally only arise in our model when a single-resistant population has time before treatment 
### to become established, and then become dominant. Dual-resistance can then emerge from that population. 

# Problem Set 1, part A
# Name: cmlilley
# Collaborators: none
# Time: lots

candidate = int(99)
successes = int(25)

import math

while successes < 1000 :     								#for all candidates before successes = 1000
	tester = int(math.sqrt(candidate)) + 1  				#setup your tester via the sqrt
	while tester > 1 :										#then, until tester = 1
		if candidate%tester == 0 :							#if tester divides cleanly,
			candidate = candidate + 2						#set next candidate and
			tester = 1										#bail out of this while loop
		elif candidate%tester != 0 :						#or if it doesn't divide cleanly
			if tester != 2 :									#and the tester is not yet 2
				tester = tester - 1									#then setup the next tester
			else :												#but if it doesn't divide and the tester is already 2
				candidate = candidate + 2							#then set the next candidate
				successes = successes + 1							#and declare a success
				tester = 1											#and bail out of this while loop
print (str(candidate-2) + ' is prime number ' + str(successes))	 #declare the results

# Problem Set 1, part B
# Name: cmlilley
# Collaborators: none
# Time: lots

candidate = int(3)
import math
sum = math.log(2)
n = int(raw_input ('Please enter the number we will use in our computation of the sum of the logs of the primes:   '))

while candidate < n :     								#for all candidates before candidate = n
	tester = int(math.sqrt(candidate)) + 1  				#setup your tester via the sqrt
	while tester > 1 :										#then, until tester = 1
		if candidate%tester == 0 :							#if tester divides cleanly,
			candidate = candidate + 2						#set next candidate and
			tester = 1										#bail out of this while loop
		elif candidate%tester != 0 :						#or if it doesn't divide cleanly
			if tester != 2 :									#and the tester is not yet 2
				tester = tester - 1									#then setup the next tester
			else :												#but if it doesn't divide and the tester is already 2
				sum = sum + math.log(candidate)						#calculate the log of the candidate and add to sum
				candidate = candidate + 2							#then set the next candidate
				tester = 1											#and bail out of this while loop
ratio = sum/n		
print ('The sum of the logs of primes below ' + str(n) + ' is ' + str(sum) + '.')
print ('The ratio of n to that sum is ' + str(ratio))

# Final Exam Answers for MIT OCW 6.0:

#1.1: False
#1.2: False - With adequately small inputs, an exponential algorithm can hypothetically take the same or less time. 
#1.3: True
#1.4: False
#1.5: False

#2: Figure 3 is first, then Figure 1, then Figure 2
#
#3: It could be only implemented if we could specify that e can only be a value greater than 0, or 
#    if we could return an exception for values of e less than 0. Without that additional 
#    specification, no, we can't implement it.
#    
#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"""
    
    L3 = []
    if len(L1) > len(L2):
        bigger = L1
        smaller = L2
    elif len(L2) > len(L1):
        bigger = L2
        smaller = L1
    else:
        for i in xrange ( max(len(L1), len(L2)) ):
            L3.append( L1[i] * L2[i] )
        return L3
    
    for i in xrange (len(smaller)):
        L3.append( bigger[i] * smaller[i] )
    for i in xrange (len(smaller), len(bigger)):
        L3.append (bigger[i])
    
    return L3
    
#5.1: d. Close to 0
#5.2: a. Smaller (With 20 sectors, the curve should be dramatically less complex)
#5.3: Complexity is polynomial, of degree x * y, where x is numSectors and y is sectorSize.
#5.4: B. removing volatility removes all price differentiation between stocks. The simply increase by bias.