conwayblue

# Problem Set 11: Simulating robots
# Name:conwayblue

import math
import pylab
import random
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)
        
    def __eq__(self, other):
        return self.getX() == other.getX() and self.getY() == other.getY()


# === Problems 1 and 2

class RectangularRoom(object):
    """
    A RectangularRoom represents a rectangular region containing clean or dirty
    tiles.

    A room has a width and a height and contains (width * height) tiles. At any
    particular time, each of these tiles is either clean or dirty.
    """
    def __init__(self, width, height):
        """
        Initializes a rectangular room with the specified width and height.
        Initially, no tiles in the room have been cleaned.

        width: an integer > 0
        height: an integer > 0
        """
        
        self.width = width
        self.height = height
        self.clean = []
        
        
    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
        """
        point = (int(pos.getX()), int(pos.getY()))
        if point not in self.clean:
            self.clean.append(point)
        
    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.clean
        
    def getNumTiles(self):
        """
        Return the total number of tiles in the room.

        returns: an integer
        """
        return self.width * self.height
        
    def getNumCleanedTiles(self):
        """
        Return the total number of clean tiles in the room.

        returns: an integer
        """
        return len(self.clean)
        
    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 (pos.getX() <= self.width and
                pos.getX() >- 0 and
                pos.getY() <= self.height and
                pos.getY() >= 0)


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)
        """
        # TODO: Your code goes here
        self.room = room
        self.speed = speed
        self.d = random.randint(0,360)
        self.p = room.getRandomPosition() 
    def getRobotPosition(self):
        """
        Return the position of the robot.

        returns: a Position object giving the robot's position.
        """
        # TODO: Your code goes here
        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.
        """
        # TODO: Your code goes here
        return self.d
    def setRobotPosition(self, position):
        """
        Set the position of the robot to POSITION.

        position: a Position object.
        """
        # TODO: Your code goes here
        self.p = position
    def setRobotDirection(self, direction):
        """
        Set the direction of the robot to DIRECTION.

        direction: integer representing an angle in degrees
        """
        # TODO: Your code goes here
        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.
        """
        # TODO: Your code goes here
        
        inroom = False
        while not inroom:
            newpos = self.p.getNewPosition(self.d,self.speed)
            if self.room.isPositionInRoom(newpos):
                inroom = True
            else:
                self.setRobotDirection(random.randint(0,360))
        self.setRobotPosition(newpos)
        self.setRobotDirection(self.d)
        self.room.cleanTileAtPosition(newpos)
    


# === Problem 3

def runSimulation(num_robots, speed, width, height, min_coverage, num_trials,
                  robot_type=Robot, visualize=False):
    """
    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)
    """
    # TODO: Your code goes
    
    results = []    
    for i in range(num_trials):
        room = RectangularRoom(width, height)
        robots = [robot_type(room,speed) for i in range(num_robots)]
        clean = 0
        tick = 0
        trial = []
        
        if visualize:
            anim = ps11_visualize.RobotVisualization(num_robots,width,height)
        
        while clean < min_coverage:
            clean = float(room.getNumCleanedTiles()) / float(room.getNumTiles())
            trial.append(clean)
            for bot in robots:
                tick += 1
                bot.updatePositionAndClean()
                if visualize:
                    anim.update(room,robots)
        #print tick
        if visualize:
            anim.done()
        results.append(trial)
    
    return results

    
    

# === 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
    
def avgTime(list_of_lists):
    total = 0
    for i in list_of_lists:
        total += len(i)
    avg = float(total) / float(len(list_of_lists))
    return avg  

# === Problem 4
def showPlot1(typebot=Robot):
    """
    Produces a plot showing dependence of cleaning time on room size.
    """
    # TODO: Your code goes here
    avgTimes = []
    sizes = [5,10,15,20,25]
    areas = [25,100,225,400,625]
    clean = 0.75
    sims = 1
    bots = 1
    speed = 1
    #typebot = Robot
    #typebot = RandomWalkRobot
    visualize = False
    
    for side in sizes:
        avgTimes.append(int(avgTime(runSimulation(
                                    bots,speed,side,side,
                                    clean,sims,typebot,visualize))))
    
    pylab.figure()
    pylab.plot(areas,avgTimes)
    pylab.ylabel('Number of steps')
    pylab.xlabel('Room Area')
    pylab.title('Avg time to clean 75% of given area with 1 robot at speed 1')
    pylab.show() 
    

def showPlot2(typebot=Robot):
    """
    Produces a plot showing dependence of cleaning time on number of robots.
    """
    # TODO: Your code goes here
    avgTimes = []
    side = 25
    clean = 0.75
    sims = 30
    speed = 1
    #typebot = Robot
    #typebot = RandomWalkRobot
    visualize = False
    
    for i in range(1,11):
        avgTimes.append(avgTime(runSimulation(i,speed,side,side,clean,
                                              sims,typebot,visualize)))
    
    pylab.figure()
    pylab.plot(range(1,11),avgTimes)
    pylab.xlabel('Number of robots')
    pylab.ylabel('Number of steps')
    pylab.title('Avg time for x number of robots to clean 75% of 25 x 25 room')
    pylab.show()

def showPlot3(typebot=Robot):
    """
    Produces a plot showing dependence of cleaning time on room shape.
    """
    # TODO: Your code goes here
    rooms = [(20,20),(25,16),(40,10),(50,8),(80,5),(100,4)]
    clean = 0.75
    sims = 30
    speed = 1
    bots = 2
    #typebot = Robot
    #typebot = RandomWalkRobot
    visualize = False
    avgTimes = []
    ratios = []
    
    for room in rooms:
        ratios.append(float(room[0]) / room[1])
        avgTimes.append(avgTime(runSimulation(bots,speed,room[0],room[1],
                                              clean,sims,typebot,visualize)))
    pylab.figure()
    pylab.plot(ratios,avgTimes)
    pylab.xlabel('Ratio of room width / height')
    pylab.ylabel('Number of steps')
    pylab.title('Avg time for 2 robots to clean 75% of x-ratio room')
    pylab.show()
    

def showPlot4(typebot=Robot):
    """
    Produces a plot showing cleaning time vs. percentage cleaned, for
    each of 1-5 robots.
    """
    # TODO: Your code goes here
    sims = 3
    speed = 1
    side = 25
    #typebot = Robot
    #typebot = RandomWalkRobot
    visualize = False
    labels = []
    pylab.figure()
    
    for bots in range(1,6):
        run = runSimulation(bots,speed,side,side,1,sims,typebot,visualize)
        meanRun = computeMeans(run)
        label = '%d bots' % bots
        labels.append(label)        
        pylab.plot(meanRun*100,range(len(meanRun)), label=label)
        
    pylab.legend(labels)
    pylab.xlabel('Percent cleaned')
    pylab.ylabel('Number of steps')
    pylab.title('Time for x robots to clean x percent of room')
    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.
    """
    # TODO: Your code goes here
    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.
        """
        # TODO: Your code goes here
        
        
        
        inroom = False
        while not inroom:
            self.setRobotDirection(random.randint(0,360))
            newpos = self.p.getNewPosition(self.d,self.speed)
            if self.room.isPositionInRoom(newpos):
                inroom = True
            else:
                self.setRobotDirection(random.randint(0,360))
        self.setRobotPosition(newpos)
        self.setRobotDirection(self.d)
        self.room.cleanTileAtPosition(newpos)
        
# === Problem 6

def showPlot5():
    """
    Produces a plot comparing the two robot strategies.
    """
    # TODO: Your code goes here
    sims = 10
    speed = 1
    side = 20
    visualize = False
    types = (Robot,RandomWalkRobot)
    labels = []
    totalbots = 3
    pylab.figure()
    
    for bots in range(1,totalbots+1):
        for bot_type in types:
            run = runSimulation(bots,speed,side,side,0.75,sims,bot_type,visualize)
            meanRun = computeMeans(run)
            if bot_type == Robot:
                label = '%d Robot type' % (bots)
            else:
                label = '%d RandomWalkRobot' % (bots)                       
            labels.append(label)
            pylab.plot(meanRun*100,range(len(meanRun)),label=label)
            
    pylab.legend(labels)
    pylab.xlabel('Percent cleaned')
    pylab.ylabel('Number of steps')
    pylab.title('Time for x robots of x type to clean 75 percent of room')
    pylab.show()
            
            
            
    
    
    
    
    
    
    

# Backend code for PS10

import random
import string

# Global Constants
VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
HAND_SIZE = 30
SCRABBLE_LETTER_VALUES = {
    'a': 1, 'b': 3, 'c': 3, 'd': 2, 'e': 1, 'f': 4, 'g': 2, 'h': 4, 'i': 1,
    'j': 8, 'k': 5, 'l': 1, 'm': 3, 'n': 1, 'o': 1, 'p': 3, 'q': 10, 'r': 1,
    's': 1, 't': 1, 'u': 1, 'v': 4, 'w': 4, 'x': 8, 'y': 4, 'z': 10
}
HUMAN_SOLO = 0
HUMAN_VS_HUMAN = 1
HUMAN_VS_COMP = 2

WORDLIST_FILENAME = "words.txt"

def getFrequencyDict(sequence):
    """
    Given a sequence of letters, convert the sequence to a dictionary of
    letters -> frequencies. Used by containsLetters().

    returns: dictionary of letters -> frequencies
    """
    freq = {}
    for x in sequence:
        freq[x] = freq.get(x,0) + 1
    return freq

def getWordScore(word):
    """
    Computes the score of a word (no bingo bonus is added).

    word: The word to score (a string).

    returns: score of the word.
    """
    score = 0
    for ch in word:
        score += SCRABBLE_LETTER_VALUES[ch]
    if len(word) == HAND_SIZE:
        score += 50
    return score

#
# Problem 2: Representing a Hand
#

class Hand(object):
    def __init__(self, handSize, initialHandDict = None):
        """
        Initialize a hand.

        handSize: The size of the hand

        postcondition: initializes a hand with random set of initial letters.
        """
        num_vowels = handSize / 3
        if initialHandDict is None:
            initialHandDict = {}
            for i in range(num_vowels):
                x = VOWELS[random.randrange(0,len(VOWELS))]
                initialHandDict[x] = initialHandDict.get(x, 0) + 1
            for i in range(num_vowels, handSize):
                x = CONSONANTS[random.randrange(0,len(CONSONANTS))]
                initialHandDict[x] = initialHandDict.get(x, 0) + 1
        self.initialSize = handSize
        self.handDict = initialHandDict
    def update(self, word):
        """
        Remove letters in word from this hand.

        word: The word (a string) to remove from the hand
        postcondition: Letters in word are removed from this hand
        
        """
        for letter in word:
            if self.handDict.get(letter,0) > 1:
                self.handDict[letter] -= 1
            else:
                del self.handDict[letter]
                            
            
        
    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
        """
        tempD = self.handDict.copy()

        for c in letters:
            if tempD.get(c,0) > 0:
                tempD[c] -= 1
            else:
                if tempD.get(c,0) == 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.
        """
        for c in self.handDict:
            if self.handDict.get(c,0) != 0:
                return False
        return True

        
    def __eq__(self, other):
        """
        Equality test, for testing purposes

        returns: True if this Hand contains the same number of each letter as
        the other Hand, False otherwise
        """
        return self.handDict == other.handDict
    
    def __str__(self):
        """
        Represent this hand as a string

        returns: a string representation of this hand
        """
        string = ''
        for letter in self.handDict.keys():
            for j in range(self.handDict[letter]):
                string = string + letter + ' '
        return string

#
# Problem 3: Representing a Player
#

class Player(object):
    """
    General class describing a player.
    Stores the player's ID number, hand, and score.
    """
    def __init__(self, idNum, hand):
        """
        Initialize a player instance.

        idNum: integer: 1 for player 1, 2 for player 2.  Used in informational
        displays in the GUI.

        hand: An object of type Hand.

        postcondition: This player object is initialized
        """
        self.points = 0.
        self.idNum = idNum
        self.hand = hand
    def getHand(self):
        """
        Return this player's hand.

        returns: the Hand object associated with this player.
        """
        return self.hand
    def addPoints(self, points):
        """
        Add points to this player's total score.

        points: the number of points to add to this player's score

        postcondition: this player's total score is increased by points
        """
        self.points += 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 0
        if self.getPoints() > other.getPoints():
            return 1
        else:
            return -1
        
    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
        """
        score = 0
        bestword = None
        
        for word in wordlist.getList():
            if self.getHand().containsLetters(word):
                wordscore = getWordScore(word)
                if wordscore > score:
                    score = wordscore
                    bestword = word
        return bestword
        
    def playHand(self, callback, wordlist):
        """
        Play a hand completely by passing chosen words to the callback
        function.
        """
        while callback(self.pickBestWord(wordlist)): pass

class HumanPlayer(Player):
    """
    A Human player class.
    No methods are needed because everything is taken care of by the GUI.
    """

class Wordlist(object):
    """
    A word list.
    """
    def __init__(self):
        """
        Initializes a Wordlist object.

        postcondition: words are read in from a file (WORDLIST_FILENAME, a
        global constant) and stored as a list.
        """
        inputFile = open(WORDLIST_FILENAME)
        try:
            self.wordlist = []
            for line in inputFile:
                self.wordlist.append(line.strip().lower())
        finally:
            inputFile.close()
    def containsWord(self, word):
        """
        Test whether this wordlist includes word

        word: The word to check (a string)

        returns: True if word is in this Wordlist, False if word is not in
        Wordlist
        """
        return word in self.wordlist
    def getList(self):
        return self.wordlist

class EndHand(Exception): pass

class Game(object):
    """
    Stores the state needed to play a round of the word game.
    """
    def __init__(self, mode, wordlist):
        """
        Initializes a game.

        mode: Can be one of three constant values - HUMAN_SOLO, HUMAN_VS_COMP,
        and HUMAN_VS_HUMAN

        postcondition: Initializes the players nd their hands.
        """
        hand = Hand(HAND_SIZE)
        hand2 = Hand(HAND_SIZE, hand.handDict.copy())
        if mode == HUMAN_SOLO:
            self.players = [HumanPlayer(1, hand)]
        elif mode == HUMAN_VS_COMP:
            self.players = [HumanPlayer(1, hand),
                            ComputerPlayer(2, hand2)]
        elif mode == HUMAN_VS_HUMAN:
            self.players = [HumanPlayer(1, hand),
                            HumanPlayer(2, hand2)]
        self.playerIndex = 0
        self.wordlist = wordlist
    def getCurrentPlayer(self):
        """
        Gets the Player object corresponding to the active player.

        returns: The active Player object.
        """
        return self.players[self.playerIndex]
    def nextPlayer(self):
        """
        Changes the game state so that the next player is the active player.

        postcondition: playerIndex is incremented
        """
        if self.playerIndex + 1 < len(self.players):
            self.playerIndex = self.playerIndex + 1
            return True
        else:
            return False
    def gameOver(self):
        """
        Determines if the game is over

        returns: True if the playerIndex >= the number of players, False
        otherwise
        """
        return self.playerIndex >= len(self.players)
    def tryWord(self, word):
        if word == '.':
            raise EndHand()
        player = self.getCurrentPlayer()
        hand = player.getHand()
        if self.wordlist.containsWord(word) and hand.containsLetters(word):
            points = getWordScore(word)
            player.addPoints(points)
            hand.update(word)
            if hand.isEmpty():
                raise EndHand()
            return points
        else:
            return None
    def getWinner(self):
        return max(self.players)
    def getNumPlayers(self):
        return len(self.players)
    def isTie(self):
        return len(self.players) > 1 and \
               self.players[0].getPoints() == self.players[1].getPoints()
    def __str__(self):
        """
        Convert this game object to a string

        returns: the concatenation of the string representation of the players
        """
        string = ''
        for player in self.players:
            string = string + str(player)
        return string

# 6.00 Problem Set 9
#
# Name: conwayblue


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


class Triangle(Shape):
    def __init__(self, base, height):
        """
        base: base of triangle
        height: height of 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 ' + str(self.base) + ' and height ' + str(self.height)
    def __eq__(self,other):
        """
        Two triangles are equal if the have the same base and same height
        other:  object to check for equality
        """
        return type(other) == Triangle and self.base == other.base and self.height == other.height


class ShapeSet:
    def __init__(self):
        """
        Initialize any needed variables
        """
        self.items = []
        
    def addShape(self, sh):
        """
        Add shape sh to the set; no two shapes in the set may be
        identical
        sh: shape to be added
        """
        if sh not in self.items:
            self.items.append(sh)     
        
    def __iter__(self):
        """
        Return an iterator that allows you to iterate over the set of
        shapes, one shape at a time
        """
        self.place = 0
        return self
        
    def next(self):
        if self.place >= len(self.items):
            raise StopIteration
        self.place += 1
        return self.items[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)
        """
        s = ''
        for shape in self.items:
            if type(shape) == Circle:
                s += shape.__str__() + '\n'
        for shape in self.items:
            if type(shape) == Square:
                s += shape.__str__() + '\n'
        for shape in self.items:
            if type(shape) == Triangle:
                s += shape.__str__() + '\n'
        return s
        
        
#
# 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
    """
    ans = []
    temp = []

    for shape in shapes:
        temp.append(shape.area())
    for shape in shapes:
        if shape.area() == max(temp):
            ans.append(shape)

    return tuple(ans)


#
# 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()
    data = open(filename, 'r')
    for line in data:
        clean = line.strip().split(',')        
        if clean[0] == 'circle':
            ss.addShape(Circle(float(clean[1])))
        if clean[0] == 'square':
            ss.addShape(Square(float(clean[1])))
        if clean[0] == 'triangle':
            ss.addShape(Triangle(float(clean[1]),float(clean[-1])))
    return ss

# 1.1 True? - May not be best algo?
# 1.2 True  - If problem has optimal substructure and overlapping subproblems
# 1.3 False - Dynamic programming can find optimal solution
# 1.4 False - The class and instances of the class are both objects
# 1.5 True -  Each class can redefine parent class methods with their own.
# 1.6 False - Multi-branch trees?

# 2.0) ----------------
def findMedian(L):

  if len(L) == 0:  raise ValueError("Must have at least 1 item in the list")
  
  length = len(L)
  copy = sorted(L)
  mid = copy[length / 2]
  
  if length % 2 == 1:
      return mid
  else:
      return (mid + copy[length / 2-1]) / 2
      

# 3.0) -----------------------
# 16.0
# Circle with radius 4
# Circle with radius 8

# 4.1) -------------------------
# n - number of items
# pi = price of item i
# xi = 1 if taken; 0 if not taken
# wi = weight of item i
# C = maximum weight constraint

# 4.2) --------------------------
# 1) Formula one finds optimal solution given price
# 2_ Formula two add a weight constraint on formula one

# 5.0)
# If length of list is <= 1:  return list
# Else divide list in half and recursively return the sorted sublists
# Merge the sorted sublists

#6.0) 
def cmpGuess(guess):    
    answer = 701
    
    if guess == answer:
        return 0
    if guess < answer:
        return -1
    if guess > answer:
        return 1    

def findNumber(maxVal=1000):   
    low = 0
    high = maxVal
    guess = (low + high) / 2

    while cmpGuess(guess) != 0:        
        if cmpGuess(guess) == -1:            
            low = guess            
        else:            
            high = guess
        guess = (low + high) / 2
        
    return guess

# Problem Set 5: Ghost
# Name: conwayblue

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."
    print '-'*30
    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.

# TO DO: your code begins here!



def ghost(wordlist):    
    print "Welcome to Ghost!"
    print "Player 1 goes first"
    running = True
    wordFrag = ''
    player = 1
    
    
    while running:
        print 'The current word fragment is: ', wordFrag
        print 'Player %s, enter a letter: ' % player
        wordFrag += raw_input()

        if is_valid_word(wordFrag, wordlist) == False:
            running = False
        if is_valid_word(wordFrag, wordlist) == True:
            player = which_player(player)
            
            
    print "Word: '%s' is an illegal play, Player %s loses" % (wordFrag, player)
    print "Congratulations Player %s, You Win!" % which_player(player)
    print '-'*30
    ghost(wordlist)

        
def is_valid_word(wordFrag, wordlist):    
    length = len(wordFrag)
    templist = []

    for word in wordlist:
        if word[:length] == wordFrag:
            templist.append(word)            
    
    if len(templist) > 1:
        if len(wordFrag) > 3 and wordFrag in templist:
            return False
        else:
            return True        
    return False
           
 
def which_player(player):
    if player == 1:
        return 2
    return 1    
    


if __name__ == '__main__':
    wordlist = load_words()
    ghost(wordlist)
    

# Problem Set 5: 6.00 Word Game
# Name: conwayblue



import random
import string

VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
HAND_SIZE = 9

SCRABBLE_LETTER_VALUES = {'a': 1, 'b': 3, 'c': 3, 'd': 2, 'e': 1, 'f': 4, 'g': 2, 'h': 4, 'i': 1, 'j': 8, 'k': 5, 'l': 1, 'm': 3, 'n': 1, 'o': 1, 'p': 3, 'q': 10, 'r': 1, 's': 1, 't': 1, 'u': 1, 'v': 4, 'w': 4, 'x': 8, 'y': 4, 'z': 10}


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

WORDLIST_FILENAME = "words.txt"

def load_words():
    """
    Returns a list of valid words. Words are strings of lowercase letters.
    
    Depending on the size of the word list, this function may
    take a while to finish.
    """
    print "Loading word list from file..."
    # inFile: file
    inFile = open(WORDLIST_FILENAME, 'r', 0)
    # wordlist: list of strings
    wordlist = []
    for line in inFile:
        wordlist.append(line.strip().lower())
    print "  ", len(wordlist), "words loaded."
    return wordlist

def get_frequency_dict(sequence):
    """
    Returns a dictionary where the keys are elements of the sequence
    and the values are integer counts, for the number of times that
    an element is repeated in the sequence.

    sequence: string or list
    return: dictionary
    """
    # freqs: dictionary (element_type -> int)
    freq = {}
    for x in sequence:
        freq[x] = freq.get(x,0) + 1
    return freq


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

#
# Problem #1: Scoring a word-----------------------------------------------------------
#
def get_word_score(word, n):
    """
    Returns the score for a word. Assumes the word is a
    valid word.

    The score for a word is the sum of the points for letters
    in the word, plus 50 points if all n letters are used on
    the first go.

    Letters are scored as in Scrabble; A is worth 1, B is
    worth 3, C is worth 3, D is worth 2, E is worth 1, and so on.

    word: string (lowercase letters)
    returns: int >= 0
    """
    score = 0
    for letter in word:
        score += SCRABBLE_LETTER_VALUES[letter]
    if len(word) == n:
        score += 50
    return score
    

#
# Make sure you understand how this function works and what it does!
#
def display_hand(hand):
    """
    Displays the letters currently in the hand.

    For example:
       display_hand({'a':1, 'x':2, 'l':3, 'e':1})
    Should print out something like:
       a x x l l l e
    The order of the letters is unimportant.

    hand: dictionary (string -> int)
    """
    for letter in hand.keys():
        for j in range(hand[letter]):
            print letter,              # print all on the same line
    print                              # print an empty line

#
# Make sure you understand how this function works and what it does!
#
def deal_hand(n):
    """
    Returns a random hand containing n lowercase letters.
    At least n/3 the letters in the hand should be VOWELS.

    Hands are represented as dictionaries. The keys are
    letters and the values are the number of times the
    particular letter is repeated in that hand.

    n: int >= 0
    returns: dictionary (string -> int)
    """
    hand={}
    num_vowels = n / 3
    
    for i in range(num_vowels):
        x = VOWELS[random.randrange(0,len(VOWELS))]
        hand[x] = hand.get(x, 0) + 1
        
    for i in range(num_vowels, n):    
        x = CONSONANTS[random.randrange(0,len(CONSONANTS))]
        hand[x] = hand.get(x, 0) + 1
        
    return hand

#
# Problem #2: Update a hand by removing letters
#
def update_hand(hand, word):
    """
    Assumes that 'hand' has all the letters in word.
    In other words, this assumes that however many times
    a letter appears in 'word', 'hand' has at least as
    many of that letter in it. 

    Updates the hand: uses up the letters in the given word
    and returns the new hand, without those letters in it.

    Has no side effects: does not mutate hand.

    word: string
    hand: dictionary (string -> int)    
    returns: dictionary (string -> int)
    """

    newhand = hand.copy()

    for letter in word:
        if newhand[letter] > 1:
            newhand[letter] -= 1
        else:
            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
    """
    # TO DO ...

    handcopy = hand.copy()  

    if word not in word_list:
        return False
    
    for letter in word:        
        if letter not in handcopy:
            return False
        
        handcopy[letter] -= 1                
        if handcopy[letter] == -1:
            return False
        
    for each in handcopy.values():
        if each >= 0:
            return True
        
#
# Problem #4: Playing a hand
#
def play_hand(hand, word_list):
    """
    Allows the user to play the given hand, as follows:

    * The hand is displayed.
    
    * The user may input a word.

    * An invalid word is rejected, and a message is displayed asking
      the user to choose another word.

    * When a valid word is entered, it uses up letters from the hand.

    * After every valid word: the score for that word and the total
      score so far are displayed, the remaining letters in the hand 
      are displayed, and the user is asked to input another word.

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

    * The hand finishes when there are no more unused letters.
      The user can also finish playing the hand by inputing a single
      period (the string '.') instead of a word.

    * The final score is displayed.

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

    total = 0
    
    while len(hand) > 0:
        display = display_hand(hand)
        print "Your current hand is: ", display
        word = raw_input("Enter a word or enter a period (.) to stop the game:  ")

        if word == '.':
            break
        else:
            if is_valid_word(word, hand, word_list) == False:
                print 'Invalid word'
            else:
                hand = update_hand(hand,word)
                wordscore = get_word_score(word,HAND_SIZE)
                total += wordscore
                print word, ':', 'Word Score:', wordscore, 'Total Score:', total

    print 'Total Score', total
                
                
    

#
# Problem #5: Playing a game
# Make sure you understand how this code works!
# 
def play_game(word_list):
    """
    Allow the user to play an arbitrary number of hands.

    * Asks the user to input 'n' or 'r' or 'e'.

    * If the user inputs 'n', let the user play a new (random) hand.
      When done playing the hand, ask the 'n' or 'e' question again.

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

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

    * If the user inputs anything else, ask them again.
    """
    # TO DO ...

    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)

#1.1) - False - recursion can go to infinity?
#1.2) - False - as tangent gets close to zero it is not reliable
#1.3) - False - dictionaries are mutable:  dict[key] = somevalue
#1.4) - False - beware of equality comparison of floats
#1.5) - False - for small values of n iteration may be faster?
#1.6) - False - not necessarily for short programs
#1.7) - True

#2.1) Yes
#2.2) ?

#3.1) 6


#3.2) """Recursive function.  Input positive interger.  Returns sum of int"""



#4)---------   

def first_N(n):    
    answer = []
    i = 1    
    while len(answer) < n:
        if i**2 % 2 != 0:
            answer.append(i**2)
            i += 1
        else:
            i += 1
    return answer




#5)
#def(guess,check):
#	for a in range of guess(....):
#		if checkfunction(a) == check
#			return answer


#6)
def findSide():
    side1 = float(raw_input("Enter side 1 length: "))
    area = float(raw_input("Enter the area of the rectangle: "))
    side2 = area / side1
    return side2


#7) Yes.  List is not modified

#8) 
def nuggets(n):
    for a in range(0, n/20 + 1):
        for b in range(0, n/9 + 1):
            for c in range(0, n/6 + 1):
                total = 20*a + 9*b + 6*c

                if total == n:
                    return (a, b, c)
    return (None,None,None)

#9) reverses the string
	

# Problem Set 4
# Name: 
# Collaborators: 
# Time: 

#
# 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.
    """
    # TODO: Your code here.

    #return a list [total acct size, this year]

    counter = 0
    f = [salary*save*0.01]

    while counter + 1 < years:
        f.append(f[counter] * (1 + 0.01*growthRate) + f[0])
        counter += 1
    return f


def testNestEggFixed():
    salary     = 10000
    save       = 10
    growthRate = 15
    years      = 5
    savingsRecord = nestEggFixed(salary, save, growthRate, years)
    print savingsRecord
    # Output should have values close to:
    # [1000.0, 2150.0, 3472.5, 4993.375, 6742.3812499999995]

    # TODO: Add more test cases here.

#
# Problem 2------------------------------------------------------------------------
#

def nestEggVariable(salary, save, growthRates):
    """
    - salary: the amount of money you make each year.
    - save: the percent of your salary to save in the investment account each
      year (an integer between 0 and 100).
    - growthRate: a list of the annual percent increases in your investment
      account (integers between 0 and 100).
    - return: a list of your retirement account value at the end of each year.
    """
    # TODO: Your code here.    
     
    counter = 0
    f = [salary*save*0.01]

    while counter + 1 < len(growthRates):
        f.append(f[counter] * (1 + 0.01 * growthRates[counter+1]) + f[0])
        counter += 1
    return f
    

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.
    """
    # TODO: Your code here.

    counter = 0
    f = [savings * (1 + 0.01*growthRates[0]) - expenses]

    while counter + 1 < len(growthRates):
        f.append(f[counter] * (1 + 0.01 * growthRates[counter+1]) - expenses)
        counter += 1
    return f
        

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.
    """
    # TODO: Your code here.

    savings = nestEggVariable(salary,save,preRetireGrowthRates)[-1]
    lowGuess = 0
    highGuess = savings
    expenses = (lowGuess + highGuess) / 2.0
    dead = postRetirement(savings,postRetireGrowthRates,expenses)[-1]
    counter = 1

    while abs(dead) > epsilon and counter <= 100:
        if dead > epsilon:  #if money left, expenses were to low
            lowGuess = expenses
        else:
            highGuess = expenses
        expenses = (lowGuess + highGuess) / 2.0
        dead = postRetirement(savings,postRetireGrowthRates,expenses)[-1]
        counter += 1
    return expenses
        
        
    
def testFindMaxExpenses():
    
    salary                = 10000
    save                  = 10
    preRetireGrowthRates  = [3, 4, 5, 0, 3]
    postRetireGrowthRates = [10, 5, 0, 5, 1]
    epsilon               = .01
    expenses = findMaxExpenses(salary, save, preRetireGrowthRates,
                               postRetireGrowthRates, epsilon)
    print expenses
    # Output should have a value close to:
    # 1229.95548986

    # TODO: Add more test cases here.

#Problem Set 3
#Name: conwayblue


from string import *

target1 = 'atgacatgcacaagtatgcat'
target2 = 'atgaatgcatggatgtaaatgcag'

key10 = 'a'
key11 = 'atg'
key12 = 'atgc'
key13 = 'atgca'

#Problem 1 - Iterative----------------------------------------------

def countSubStringMatch(target,key):
    """Counts the number of key strings in target string - Incremental"""
    
    count = 0       #Initialize count
    position = -1   #Initialize position at -1 to start at index 0
    
    while True:               
        position = find(target,key,position+1)  #Find index of 1st key in target   
        if position == -1:                      #Test if None
            break        
        count += 1                              #Increase count
    return count

#Problem 1 - Recursive-----------------------------------------------

def countSubStringMatchRecursive(target,key):
    """Counts the number of key strings in target string - Recursive"""

    count = 0                                   #Initialize count
    position = find(target,key)                 #Find initial 

    if position == -1:                          #Test if None
        return count
    else:
        count += 1                              #Increase count
        return count + countSubStringMatchRecursive(target[position+1:],key)  #Add count to count from recursion at last position + 1

#Problem 1a - Recursive-----------------------------------------------

def countSubStringMatchRecursive2(target,key):
    """Counts the number of key strings in target string - Recursive"""
    
    if find(target,key) == -1: return 0
    return 1 + countSubStringMatchRecursive(target[find(target,key)+1:],key)

#Problem 2 --------------------------------------------------------------

def subStringMatchExact(target,key):
    """Returns a tuple of index locations of each key in target"""

    answers = []
    position = -1

    while True:
        position = find(target,key,position+1)
        if position == -1:
            break
        answers.append(position)
    return tuple(answers)

#Problem 3---------------------------------------------------------------

def constrainedMatchPair(firstMatch,secondMatch,length):
    """Returns a tuple of indexes from firstMatch that are possible matches given indexes of secondMatch and length of key"""

    ##firstIndex + length + 1 = secondIndex
    ##secondIndex - firstIndex - length = 1
   
    n = []    
    for firstIndex in firstMatch:
        for secondIndex in secondMatch:
            if secondIndex - firstIndex - length == 1:
                n.append(firstIndex)
    return tuple(n)


#function from problem sheet-

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
        print "------------------------------------"
    return allAnswers


#Problem 4-----------------------------------------------------------------

def subStringMatchExactlyOneSub(target,key):
    """Returns indexes of key matches missing exactly one letter only"""

    exactMatch = subStringMatchExact(target,key)      #indexes of exact matches
    subMatch = subStringMatchOneSub(key,target)       #indexes of exact matches and one sub matches
    
    answer = []

    for each in subMatch:
        if each  not in exactMatch:
            answer.append(each)
    return tuple(answer)

    


    

#Problem Set 2 (Part 1)
#Name: conwayblue

#Problem 1-------------------------------------------------------


def nuggets(totalNuggets):
    """needs total number of nuggets"""

    for pack20 in range(0, totalNuggets / 20 + 1):
        for pack9 in range(0, totalNuggets / 9 + 1):
            for pack6 in range(0,totalNuggets / 6 + 1):
                
                totalNuggetsCalc = 20*pack20 + 9*pack9 + 6*pack6
                if totalNuggetsCalc == totalNuggets and pack6 > -1:
                    return (pack6, pack9, pack20)
    return(None, None, None)
     

def mcdonalds():
    """will ask how many total nuggets"""
    
    totalNuggets = int(raw_input("How many total nuggets do you want? "))
    pack6, pack9, pack20 = nuggets(totalNuggets)

    if pack6 == None:
        print "You can't buy that many nuggets"
    else:
        print "You could buy", pack6, "six packs"
        print "You could buy", pack9, "nine packs"
        print "You could buy", pack20, "twenty packs"


#Problem 2--------------------------------------------------
        

def nuggetrange(startnumber):
    """needs a number and will give you the possible number packs for the next 6"""

    for each in range(startnumber, startnumber+7):
        pack6, pack9, pack20 = nuggets(each)
        if pack6 == None:
            print "You can\'t have", each, "nuggets dummy!"
        else:
            print "For", each, "nuggets you need", pack6, "six packs", pack9, "nine packs", pack20, "twenty packs"


#Problem 3---------------------------------------------------


def maxNonNugget():

    notNuggetFriendly = []

    for nuggetCount in range(0,50):

        packList = nuggets(nuggetCount)

        if packList[0] == None:

            notNuggetFriendly.append(nuggetCount)


    print "Largest number of McNuggets that cannot be bought in exact quantity: ", notNuggetFriendly[-1]
            
        
#Problem 4--------------------------------------------------------

def crazyNugget():
    
    packages = (6,9,20)
    notNuggetFriendly = 0
    foundRow = 0

    for totalNuggets in range(0,200):
        
        friendly = False

        for a in range(0, totalNuggets + 1):
            for b in range(0, totalNuggets + 1):
                for c  in range(0, totalNuggets + 1):
                    runningCalc = (a * packages[0]) + (b * packages[1]) + (c * packages[2])
                    if runningCalc == totalNuggets:
                        friendly = True

        if friendly:
            foundRow += 1
            if foundRow == packages[0]:
                break
        else:
            foundRow = 0
            notNuggetFriendly = totalNuggets

    print "Given sizes %s, %s, and %s, the largest number of nuggets than can't be purchased is %s" % (packages[0], packages[1], packages[2], notNuggetFriendly)



                



    

    

##Problem Set 1
##Name: Audie Swan
##Collaborators:  me, myself, and I
##Time:  took me forever man!




##Problem 1 -

##Write a program that computes and prints the 1000th prime number


import math

primeList = [2]
primeCandidate = 3
divisor = 3
whichPrime = input("Which prime would you like to find, enter 1000 for Problem set 1 answer: ")



while len(primeList) < whichPrime:

    if divisor == primeCandidate:
        primeList.append(primeCandidate)
        primeCandidate += 2
        divisor = 3

    if primeCandidate % divisor != 0:
        divisor += 1

    else:
        primeCandidate += 2
        divisor = 3
        
print primeList.pop()




##Problem 2 - Sum of log of primes




primeList = [2]
primeCandidate = 3
divisor = 3
maxNumber = input("Enter a maximum number, n, to calculate the sum of the log of all primes less than that number: ")
logPrimeSum = 0

while primeCandidate < maxNumber:

    if divisor == primeCandidate:
        primeList.append(primeCandidate)
        primeCandidate += 2
        divisor = 3

    if primeCandidate % divisor != 0:
        divisor += 1

    else:
        primeCandidate += 2
        divisor = 3


for eachPrime in primeList:

    logPrime = math.log(eachPrime)
    logPrimeSum += logPrime

print "The max number is", maxNumber    
print "The sum of log of primes up to", maxNumber, "is", logPrimeSum
print "logPrimeSum / maxNumber is", logPrimeSum / maxNumber

# Problem Set 0
# Name: conwayblue
# !python

# Request first and last names then prints both.

firstName = raw_input("Yo dog, What\'s your first name? ")
lastName = raw_input("...and your last? ")

print firstName, lastName