Code Developed in CSCI-1100 Spring Semester 2016¶

open the file from the web with all the words in English
 
for each word in the file:
    for all positions l in the word
        if the letters at positions (l and l+1) are the same
           and the letters at positions (l+2 and l+3) are the same
           and the letters at positons  (l+4 and l+5) are the same then
            output word and increment the count

""" Find all words containing three consecutive pairs of double letters 
in a file of all English words located at:

        http://www.greenteapress.com/thinkpython/code/words.txt

**Modules used:**  :py:mod:`urllib` 

**Author**: Sibel Adali <adalis@rpi.edu>, Chuck Stewart <cvstewart@gmail.com>

**Returns:** All words matching condition and the count of found words

**Pseudo Code**::

   open the file from the web with all the words in English
    
   for each word in the file:
       for all positions l in the word
           if the letters at positions (l and l+1) are the same
              and the letters at positions (l+2 and l+3) are the same
              and the letters at positons  (l+4 and l+5) are the same then
               output word and increment the count

"""

import urllib

def has_three_double(word):
    """ Returns True if the word contains three consecutive pairs of
    double letters and False otherwise.         
    """
    for l in range(len(word)-5):
        if word[l] == word[l+1] and \
           word[l+2]==word[l+3] and \
           word[l+4]==word[l+5]:
            return True
    return False

# Comments that fit in a single line can be put in this format.
# Anything after a single pound sign is ignored.

# The main body of the program starts here

word_url = 'http://www.greenteapress.com/thinkpython/code/words.txt'
word_file = urllib.urlopen(word_url)

count = 0
for word in word_file:
    word = word.strip().strip('\n')
    if has_three_double(word):
        print word
        count = count + 1
        
if count == 0:
    print 'No words found'
elif count == 1:
    print "1 word found"
else:
    print count, 'words were found'

"""
Write a program to 
   read the dimensions of a rectangular prism,
   compute the surface area and volume, and
   print them.


"""

length = float(raw_input("Enter the length of the rectangular prism ==> "))
width = float(raw_input("Enter the width of the rectangular prism ==> "))
height = float(raw_input("Enter the height of the rectangular prism ==> "))

area = 2 * (length*width + length*height + width*height)
volume = length*width*height
print "Rectangular prism with length %.3f, width %.3f, height %.3f" %(length, width, height)
print "Area %.3f, Volume %.3f" %(area, volume)

name2 = "Rensselaer Polytechnic Institute"

##a -> 1,  e->a, 1->e
name2 = name2.replace("a","1")
name2 = name2.replace("e","a")
name2 = name2.replace("1","e")

print name2

word = 'Bring back the swarm'

word = word.title()
word = word.replace(" ", "")
word = "#" + word
print word


word = 'Bring back the swarm'

word = "#" + (word.title()).replace(" ","")
print word

"""
Write a program to 
   read radius of a circle in float
   compute its area and
   print it.


"""

import math

radius = raw_input("Radius ==> ")

radius = float(radius)
## or
## radius = float(raw_input("Radius ==> "))
area = math.pi * radius**2


print "The area of a circle is:", area
print "The area of a circle is: %.2f" %area

""" Author CS-1 Staff

    Purpose: This program reads radius and height 
    of a cylinder and outputs the area and volume.
    
"""
import math

# This is a comment
print "Computing the area and volume of a cylinder"
radius = float(raw_input("Enter radius ==> "))
height = float(raw_input("Enter height ==> "))

area = 2*math.pi*radius*height + 2*math.pi*radius**2
volume = math.pi*radius**2*height

print "Area is %.2f" % area
print "Volume is %.2f" %volume

""" Author CS-1 Staff

    Purpose: This program reads the lengths a and b
    of the sides of a right triangle and outputs the 
    hypotenuse.
    
"""
import math

print "Computing the hypotenuse of a right triangle"
a = float(raw_input("Enter side a ==> "))
b = float(raw_input("Enter side b ==> "))

c  = math.sqrt(a**2 + b**2)

print "Hypotenuse is %.2f" % c

'''
Demonstrate the writing and use of two functions that compute the area
of a circle and the surface area of a cylinder.
'''

import math

def area_circle(radius):
    return math.pi * radius ** 2

def area_cylinder(radius,height):
    circle_area = area_circle(radius)
    height_area = 2 * radius * math.pi * height
    return 2*circle_area + height_area

print 'The area of a circle of radius 1 is', area_circle(1)
r = 2
height = 10
print 'The surface area of a cylinder with radius', r
print 'and height', height, 'is', area_cylinder(r,height)

""" Author: CS1 Staff

    Simple program to demonstrate an if statement.
"""

name1 = "Dale"
height1 = int(raw_input("Enter the height of %s in cm ==> " %name1))
name2 = "Erin"
height2 = int(raw_input("Enter the height of %s in cm ==> " %name2,))
if height1 < height2:
    print "%s is taller" %name2
    max_height = height2
elif height1 > height2:
    print "%s is taller" %name1
    max_height = height1
else:
    print "%s and %s have the same height!" %(name1, name2)
    max_height = height1
    
print "The max height is %d" %max_height

from PIL import Image

filename = "chipmunk.jpg"
im = Image.open(filename)
print '\n' '********************'
print "Here's the information about", filename
print im.format, im.size, im.mode
im.show()


gray_im = im.convert('L')
scaled = gray_im.resize( (128,128) )
print "After converting to gray scale and resizing,"
print "the image information has changed to"
print scaled.format, scaled.size, scaled.mode


scaled.show()
scaled.save(filename + "_scaled.jpg")

from PIL import Image

im = Image.open("lego_movie.jpg")
w,h = im.size

## Crop out three columns from the image
## Note: the crop function returns a new image
part1 = im.crop((0,0,w/3,h))
part2 = im.crop((w/3,0,2*w/3,h))
part3 = im.crop((2*w/3,0,w,h))

## Create a new image
newim = Image.new("RGB",(w,h))

## Paste the image in different order
## Note: the paste function changes the image it is applied to
newim.paste(part3, (0,0))
newim.paste(part1, (w/3,0))
newim.paste(part2, (2*w/3,0))
newim.show()

"""
This is a general program for practicing different loop
methods. The following are examples of:

1. Loops that count up or down, loops that end
  
   Loop block   
   Printing (print all on one line)
   Changing a list (make upper case)

   Accumulate a value
      Count by 1, 3 (print three in a line, check
      for three letters in a word, ending conditions?)
      Is it true that there are two consecutive repeated letters?
      
      Count all farmer's markets in Albany
      
2. Loops that are undeterministic

   Depends on an external condition 
      (while user does not say stop)
      
------ WE will continue with these the next time
   Depends on a complex condition 
      (while found or end of list, farmer's market)
   

3. Double loops

   Find all possible pairs of agents
   Find pairs of agents with the same first letter in their name


"""

months = ['jan', 'feb', 'mar', 'apr', 'may', 'jun', \
          'jul', 'aug', 'sep', 'oct', 'nov', 'dec']

agents = ['skye','may','fitz','simmons','caulson',\
          'hunter', 'mack', 'morse', 'triplett', \
          'hartley', 'deathlok', 'koenig', \
          'gonzales', 'fury']

word = 'bookkeeper'


i=0
while i< len(months):
    print "Month: %d is %s" %(i+1, months[i].capitalize() )
    i += 1

print months

print
print agents

## Capitalize the values in list "agents"

i=0
while i < len(agents):
    agents[i] = agents[i].capitalize()
    i += 1


## Check if capitalized
print
print agents


##Count how many agents have first names that start with S
##Accumulation of values

i = 0
cnt = 0
while i < len(agents):
    if agents[i][0] == 'S':
        cnt += 1
    i += 1

print "%d agents with first name starts with 'S'" %cnt

##Find if there any agents who name starts with F
##Print Yes if any agent with such name, No otherwise

i = 0
found = False
while i < len(agents):
    if agents[i][0] == 'F':
        found = True
    i += 1

if found:
    print 'Yes'
else:
    print 'No'


print
print "This is a loop that counts up to 7"
i = 0
while i < 7:
    i += 1
    print i
    
print 
print "This is a loop that counts 10 down to 1"
    
i=10
while i > 0:
    print i
    i -= 1
    
print
print "This is loop that counts by 2, starting with 1 and ending with 19"
i = 1
while i <= 20:
    print i
    i += 2
    

""" This program shows how to write a loop that ends
on a given user input. So, we must make sure that
while loop executes once initially and also that we 
set the conditions that would stop the loop manually
when the correct input is given.

"""




### write a loop that reads user input, until the 
### user types stop

finished = False
while not finished:
    cmd = raw_input("Enter a command (stop to stop) => ")
    if cmd == 'stop':
        finished = True

"""
Illustrating while loops with the CO2 example
"""


co2_levels = [ (2001, 320.03), (2003, 322.16), (2004, 328.07),\
               (2006, 323.91), (2008, 341.47), (2009, 348.92),\
               (2010, 357.29), (2011, 363.77), (2012, 361.51),\
               (2013, 382.47) ]

"""
First example, sum
"""
i=0
sum=0
while i< len(co2_levels):
    sum += co2_levels[i][1]
    i += 1

print
print "Total co2_levels is", sum

"""
Reverse order
"""
i=len(co2_levels)
while i > 0:
    i -= 1
    print "Year", co2_levels[i][0], \
          "CO2 levels:", co2_levels[i][1]
    
"""
Levels above 350
"""
print
i=0
num = 0
while i < len(co2_levels):
    if co2_levels[i][1] > 350:
        num += 1
    i += 1
print "%d years had CO2 levels greater than 350" % num

"""
Percent change
"""
print
i=1
num = 0
while i < len(co2_levels):
    percent = 100 * (co2_levels[i][1] - co2_levels[i-1][1]) / co2_levels[i-1][1]
    print "Percent change from %d to %d was %.2f" % (co2_levels[i-1][0], co2_levels[i][0], percent)
    i+=1

"""
Levels that went down
"""
print
i=1
num = 0
while i < len(co2_levels):
    if co2_levels[i][1] < co2_levels[i-1][1]:
        print "From %d to %d CO2 levels went down" % (co2_levels[i-1][0], co2_levels[i][0])
    i+=1

'''
Purpose:  Demonstrate the use of nested loops to find the two closest values in a list.
    This could also be implemented - probably better - using for loops.  The values
    are stored in a list L, but in practice it would be better to input them from the user.

Author: Chuck Stewart

Date:  March 3, 2016
'''

L = [34, 21, 12, 78, 28, 61 ]

#  Initialize two variables to hold information about the minimum.  The
#  first is a tuple holding the indices of the two closest values.  The
#  second is the minimum distance. These values are initialized from the
#  first two values in the list.
min_pair = (0,1)
min_dist = abs( L[0] - L[1] )

#  In order to test each possible pair of indices, the index of the first
#  component of the pair must start out 0.
i = 0
while i<len(L):
    #  The second index starts out at i+1 and runs through the end of
    #  the list.
    j=i+1
    while j < len(L):
        dist = abs(L[i]-L[j])
        
        #  If the distance between the current pair of points is less than
        #  the current minimum, we have a new minimum pair
        if dist < min_dist:
            min_pair = (i,j)
            min_dist = dist
        j += 1
       
    #  This is outside the inner while loop so that i is incremented after
    #  the inner while loop ends.
    i += 1 

closest_i = min_pair[0]
closest_j = min_pair[1]
print "Closest values are %d and %d at indices %d and %d."\
      %(L[closest_i], L[closest_j], closest_i, closest_j)

'''
Lecture 11 Example of a Random Walk

This code was started in class on March 7 and completed on March 10.
It simulates a random walk by turtle who in each time unit randomly
takes a step to the left or a step to the right until it falls off.

This is represented by creating a board of n spaces and starting the
turtle in space n/2.  A step to the left decreases the turtle
position.  A step to the right increases the turtle position.

The simulation is run with a delay between each step so we can watch
what is happening.  Without this delay, the board would print too
fast.
'''
import random
import sys
import time    # so that we can delay


def print_board( steps, n, turtle_pos):
    '''
    Print the board with the current turtle position on it.  This assumes the turtle
    position is at least 0 and less than n.
    '''
    board = '_' * turtle_pos + 'T' + '_'*(n-1-turtle_pos)
    print "%4d: %s" %(steps, board)
    
def take_step( n, turtle_pos ):
    '''
    Take a step, return turtle tuple with the new position, and False if
    turtle fell off
    '''
    ran_value = random.random()
    if ran_value < 0.5:
        '''  Step to the left '''
        turtle_pos -= 1
    else:
        ''' Step to the right '''
        turtle_pos += 1
    fell_off = turtle_pos < 0 or turtle_pos >= n    
    return (turtle_pos, fell_off)


if __name__ == '__main__':
    '''  Read the input and check to make sure it is a positive integer '''
    n = raw_input('Enter the board size for the turtle walk => ')
    if not n.isdigit():
        print 'Need a positive number'
        sys.exit()
    n = int(n)
    print n
    
    '''  Initialize the turtle position in the middle and print the board. '''
    turtle_pos = (n-1)/2
    print_board( 0, n, turtle_pos )
    
    '''  Run one step at a time until the turtle falls off the board.  '''
    fell_off = False
    steps = 0
    while not fell_off:
        (turtle_pos, fell_off) = take_step( n, turtle_pos )
        steps += 1  
        if not fell_off:
            print_board( steps, n, turtle_pos )
            time.sleep(0.1)   # delay by the given number of seconds so we can see what is happening

    print 'The turtle fell off after', steps, ' steps.'

'''
Read a file of scores, with one score per line, and output them
in order from greatest to smallest.
'''
f = open('scores.txt')
scores_list = []
for line in f:
    score = int(line)
    scores_list.append( score )
    
scores_list.sort()

#  Reverse the list and then output it
scores_list = scores_list[::-1]
for i in range(len(scores_list)):
    print "%d: %3d" %(i,scores_list[i])

'''
# As an alternative to reversing the list we can
# index from the end of the list.
for i in range(len(scores_list)):
    print "%d: %3d" %(i, scores_list[-1-i])
'''

'''
Exercise from Lecture 13 on parsing a legos file and putting it into the form
we expected from HW 4.  

For example, if legos.txt has the following three lines:
2x1, 2
2x2, 6
   4x2  ,   3
   
Then at the end of the following, the legos list will be 
['2x1', '2x1', '2x2', '2x2', '2x2', '2x2', '2x2', '2x2', '4x2', '4x2', '4x2']

When we developed this in class, we added a bit of complexity and tested it as
we went.  This included making some mistakes.  At the end we have the following
completed solution.  Notice that the legos += ...  statement can be replaced
by the for loop that is commented out...
'''

lego_f = open('legos.txt')

legos = []
for line in lego_f:
    line = line.split(',')
    block = line[0].strip()
    count = int(line[1])
    '''
    for i in range(count):
        legos.append(block)
    '''
    legos += [block]*count
    
print legos

'''
Lecture 14
Spring 2016
Prof. Chuck Stewart

Here are two different solutions to the problem of counting the number
of occurrences of each integer in an input sequence of integers. These
are the implementations of two of the four solutions we came up with
in class.

I have rearranged the code into functions, with one function
implementing one solution.  Of course, if you were in class you noted
(and in many cases participated in) the development of the solutions,
involving several steps of writing the code, testing it, and refining
it.  What you see here is just the final product.
'''

def print_scores_v1( scores ):
    '''
    The first solution finds the minimum and maximum scores, and then
    counts each score in this range, only outputting the scores with
    non-zero counts.  This is short and easy to write, but it only
    works well when the scores are not widely distributed.  For
    example, if there were only two scores, 0 and 1,000,000, this
    would be a very slow solution.
    '''

    '''  Preliminary output.  Not necessary for the solution. '''
    print 'Min score', min(scores)
    print 'Max score', max(scores)
    print 'Length', len(scores)

    ''' Generate and print a count for each score '''
    print '\nVersion 1 output:'
    for score in range(min(scores), max(scores)+1 ):
        count = scores.count(score)
        if count > 0:
            print "%3d: %2d" %(score,count)


def print_scores_v2( scores ):
    '''
    The second solution is based on sorting.  In doing so, all values
    that are the same are adjacent to each other in the sorted list,
    making them much easier to count.  We start by making a copy of
    the list in case the user wanted to work with the original list.
    '''
    scores_c = scores[::]
    scores_c.sort()
    count = 1
    print '\nVersion 2 output:'
    for i in range(1,len(scores_c)):
        if scores_c[i-1] == scores_c[i]:  # seeing same score as the previous
            count += 1
        else:
            ''' The current score is not the same as the previous, so
                output the previous along with its count. '''
            print "%3d: %2d" %(scores_c[i-1],count)
            count = 1

    # Print count for last item in the list
    print "%3d: %2d" %(scores_c[-1],count)



if __name__ == "__main__":
    '''  Read in the scores, storing them in a list '''
    in_file = open('scores.txt')
    scores = []
    for line in in_file:
        scores.append( int(line) )

    print_scores_v1(scores)
    print_scores_v2(scores)
    
        

        

imdb_file = raw_input("Enter the name of the IMDB file ==> ").strip()
name_list = []
for line in open(imdb_file):
    words = line.strip().split('|')
    name = words[0].strip()

'''
Author: Chuck Stewart

Purpose: Using a list that keeps track of actors and the number of
movies they have been in, find the person who was in the most movies
listed in our data from the Internet Movie Database.  This
demonstrates a very slow --- O(N^2) --- solution to this problem.  A
dictionary-based solution and a solution based on sorting are both
faster.
'''
def insert_name_and_count( count_list, name ):
    i=0
    while i<len(count_list) and count_list[i][0] != name:
        i += 1
    if i == len(count_list):
        # name is not already in the list
        count_list.append( [name,1] )
    else:
        count_list[i][1] += 1
    
if __name__ == "__main__":
    imdb_file = raw_input("Enter the name of the IMDB file ==> ").strip()
    
    '''  Do the counting '''
    count_list = []
    for line in open(imdb_file):
        words = line.strip().split('|')
        name = words[0].strip()
        insert_name_and_count( count_list, name )
        
    ''' Find the max '''
    max_movies = count_list[0][1]
    max_name = count_list[0][0]
    for i in range(1,len(count_list)):
        if count_list[i][1] > max_movies:
            max_name = count_list[i][0]
            max_movies = count_list[i][1]
    
    ''' Print our answer  '''
    print '%s was involved in the most movies, %d' %(max_name, max_movies)
    

'''
Author: Chuck Stewart

Purpose: Using a dictionary that associates names with the number of
movies, find the person who was in the most movies listed in our data
from the Internet Movie Database.
'''

import time

if __name__ == "__main__":
    imdb_file = raw_input("Enter the name of the IMDB file ==> ").strip()
    start_time = time.time()
    
    '''  Do the counting '''
    counts = {}
    for line in open(imdb_file):
        words = line.strip().split('|')
        name = words[0].strip()
        if name in counts:
            counts[name] += 1
        else:
            counts[name] = 1
        
    ''' Find the max '''
    max_movies = 0
    max_name = ''
    for name in counts.keys():
        if counts[name] > max_movies:
            max_name = name
            max_movies = counts[name]
    end_time = time.time()
    
    ''' Print our answer  '''
    print '%s was involved in the most movies, %d' %(max_name, max_movies)
    print 'Dictionary version took %1.2f seconds' %(end_time-start_time)
    
    

'''
Author: Chuck Stewart

Purpose: Here is a fast, list-based solution to our problem of finding
the busiest person in the internet movie database. It takes a
different approach, one involving sorting.
'''

import time
if __name__ == "__main__":
    imdb_file = raw_input("Enter the name of the IMDB file ==> ").strip()
    start_time = time.time()

    '''  Append each name '''
    names = []
    for line in open(imdb_file):
        words = line.strip().split('|')
        names.append( words[0].strip() )

    names.sort()

    '''
    Scan through the list, adding to a running counter when the name
    is the same as the previous.  When they are different check to see
    if a new max has been reached.  If so, then update the max and
    reset the counter to 1.  If not, just reset the counter.
    '''
    max_movies = 0
    max_name = ''
    current_count = 1
    for i in range(1,len(names)):
        if names[i] == names[i-1]:
            current_count += 1
        elif current_count > max_movies:
            max_movies = current_count
            max_name = names[i-1]
            current_count = 1
        else:
            current_count = 1

    '''
    Check the special case of the last actor being the busiest.
    '''
    if current_count > max_movies:
        max_movies = current_count
        max_name = names[-1]

    end_time = time.time()
    
    ''' Print our answer  '''
    print '%s was involved in the most movies, %d' %(max_name, max_movies)
    print 'List and sorting version took %1.2f seconds' %(end_time-start_time)

'''
Author:  Chuck Stewart

Purpose: Lecture 17 IDMB example of a dictionary associating a year
with the set of movies from that year and then using the dictionary to
find the year with the most movies.
'''

if __name__ == "__main__":
    ##  Form the dictionary
    imdb_file = raw_input("Enter the name of the IMDB file ==> ").strip()

    years_to_movies = {}
    for line in open(imdb_file):
        words = line.strip().split('|')
        movie_name = words[1].strip()
        year = int(words[2])

        #  Create an empty set entry if the year is new
        if year not in years_to_movies:
            years_to_movies[year] = set()

        #  Add the movie to the year
        years_to_movies[year].add(movie_name)
    
    # A little bit of extra printed information
    print 'Earliest year is', min(years_to_movies.keys())
    print 'Last year is', max(years_to_movies.keys())

    # Find the busiest year by keeping track of the maximum size set from
    # the dictionary and the year that had that maximum size.
    max_year = 0
    max_count = 0
    for y in years_to_movies.keys():
        count = len(years_to_movies[y])
        if count > max_count:
            max_year = y
            max_count = count

    print 'Year %d had max movies: %d' %(max_year, max_count)

'''
Author:  Chuck Stewart

Purpose: Lecture 17 IDMB example where two dictionaries are built, one
associating an actor with the set of movies they appear in and the
other associating a movie with the set of actors.  We can use this to
find actors that appeared together in a movie.
'''

if __name__ == "__main__":
    imdb_file = raw_input("Enter the name of the IMDB file ==> ").strip()
    actor_name = raw_input("Enter the name of an actor (last, first) ==> ").strip()

    #  Form the two dictionaries.
    actors_to_movies = {}
    movies_to_actors = {}
    for line in open(imdb_file):
        words = line.strip().split('|')
        actor = words[0].strip()
        movie = words[1].strip()

        #  Additions to the first dictionary
        if not actor in actors_to_movies:
            actors_to_movies[actor] = set()
        actors_to_movies[actor].add(movie)
    
        #  Additions to the second dictionary
        if not movie in movies_to_actors:
            movies_to_actors[movie] = set()
        movies_to_actors[movie].add(actor)

    # Let's evaluate the movies
    print "\n%s has been in %d movies" %(actor_name, len(actors_to_movies[actor]))
    print "Here they are:"
    movie_list = sorted(list(actors_to_movies[actor_name]))
    for i in range(len(movie_list)):
        print "\t%3d: %s" %(i+1, movie_list[i])

    #  Find other actors that this actor appeared with
    other_actors = set()
    for movie in actors_to_movies[actor_name]:
        other_actors |= movies_to_actors[movie]

    print '\n%d other actors appeared with %s' %(len(other_actors), actor_name)
    print 'Here they are:'
    actor_list = sorted(list(other_actors))
    for i in range(len(actor_list)):
        print "\t%3d: %s" %(i+1, actor_list[i])
    

""" Class example, a simple class of 2d objects 


"""

class Point2d(object):
    def __init__(self, x0, y0):
        """Initialize to make sure each point has an x, y value. """
        self.x = x0
        self.y = y0
        
    def length(self):
        """ Return the length of a point. """
        return (self.x**2 + self.y**2)**(0.5)
    
    def __str__(self):
        """ Returns the string representation of object. 
            Call as:
 
            str(x)
            print x  ##calls this function and prints the result string

        """
        return "(%d, %d)" %(self.x, self.y)
      
    def distance(self, other):
        """ Returns the distance between two points. """
        d = (self.x-other.x)**2 + (self.y-other.y)**2
        return d**(0.5)
      
    def __add__(self, other):
        """ Adds two points and returns a new point with the 
            addition of values. You can call this as:

            pt1.__add__(pt2)
            pt1+pt2
   
        """

        new = Point2d(self.x, self.y)
        new.x += other.x
        new.y += other.y
        return new
    
    def __sub__(self, other):
        """ Subtracts other from self, and returns a new point 
            containing the result. You can call this as:

            pt1.__sub__(pt2)
            pt1-pt2
   
        """
        new = Point2d(self.x, self.y)
        new.x -= other.x
        new.y -= other.y
        return new

if __name__ == "__main__":
    ##Test code here
    pt1 = Point2d(10, 20)
    pt2 = Point2d(3, 4)
    
    print pt1.x, pt1.y
    print pt2.x, pt2.y

    print pt1 ## calls the __str__ method
    print str(pt1) ## this is identical to the above call
    
    print "Length of pt1 is", pt1.length()
    print "Length of pt2 is", pt2.length()
    
    print "Distance between", pt1, "and", pt2, "is:", pt1.distance(pt2)
    print pt1  ##calls str
     
    pt3 = pt1+pt2
    print pt3

    print "Subtraction:", pt1-pt2
    print "Pt1:", pt1, "Pt2:", pt2
    print "Add/Subtract do not change the input objects"

""" Class for storing time. Time is reported on a military (24 hour) clock

"""

class Time(object):
    def __init__(self, hr, min, sec):
        pass
        
    def convert(self):
        pass
        
    def __str__(self):
        pass
    
    def __add__(self, other):
        pass
    
    def __sub__(self, other):
        pass


if __name__ == '__main__':
    pass

""" Class for storing time.

"""

class Time(object):
    def __init__(self, hr, min, sec):
        if hr > 24:
            hr = hr%24        
        self.seconds = hr*60*60 + min*60 + sec
        
    def convert(self):
        hr = self.seconds/3600
        min = (self.seconds - hr*3600)/60
        sec = self.seconds - hr*3600 - min*60
        return hr, min, sec
        
    def __str__(self):
        hr, min, sec = self.convert()
        return '%02d:%02d:%02d' \
               %(hr, min, sec)
    
    def __add__(self, other):
        total = self.seconds + other.seconds
        hr = total/3600
        min = (total - hr*3600)/60
        sec = total - hr*3600 - min*60
        return Time(hr, min, sec)
    
    def __sub__(self, other):
        total = self.seconds - other.seconds
        if total < 0:
            total += 24*3600
        hr = total/3600
        min = (total - hr*3600)/60
        sec = total - hr*3600 - min*60

        return Time(hr, min, sec)        

'''
Use the business class to manage a set of restaurants
and get user inputs on how to proceed.
'''

from lec19_business_class import Business
import webbrowser

def convert_input_to_restaurant(line):
    m = line.strip().split("|")
    return Business(m[0],m[1],m[2],m[3],m[4],m[5],m[6:])

def build_restaurant_list():
    restaurants = []
    f = open('yelp.txt')

    restaurants = []
    for line in f:
        restaurants.append(convert_input_to_restaurant(line))
    return restaurants
    

if __name__ == "__main__":
    
    restaurants = build_restaurant_list()
    num_restaurants = len(restaurants)

    while (True):
        #  Get the index of the restaurant and check it.
        print "Enter the index of the restaurant from 1 to %d or stop to end ==> " %num_restaurants,
        index = raw_input()
        print index
        if index == 'stop':
            break
        index = int(index)
        if index < 1 or index > num_restaurants:
            print "The index is out of range.  Sorry."
        else:
            print(restaurants[index-1])

###import points
from lec18_points import Point2d

class Business(object):
    def __init__(self, name, lat, lon, address, url, category, scores):
        self.name = name
        self.loc = Point2d(float(lon), float(lat))
        self.address = address
        self.url = url
        self.category = category

        ## convert scores into integer
        for i in range(len(scores)):
            scores[i] = int(scores[i])
        self.scores = scores
        
    def avgscore(self):
        if len(self.scores) < 3:
            return sum(self.scores)/float(len(self.scores))
        else:
            s = list(self.scores)
            s.sort() ## we do not want to change the actual ordering of scores
            return ( sum(s[1:-1])/float(len(s)-2) )
        
    
    def minscore(self):
        return min(self.scores)
    
    def maxscore(self):
        return max(self.scores)
        
    def __str__(self):
        return "%s (%s)\n\t%s\n\tLocation: %s\nAvg Score: %.1f (%d - %d)" \
               %(self.name, self.category, self.address, self.loc, self.avgscore(), self.minscore(), self.maxscore())
    

"""
Problem: Find the index of the two smallest values
We will also learn how to time running time of algorithms
using the time module

Algorithm:

     Idea 1:
     Make a copy of list
     Sort the copy
     Find the two smallest values (index 0,1)
     Find the index of these values**
     
     
     Idea 2:
     Initialize two smallest values to 0,1
     Then, iterate through list
     and remember the smallest two values
     and their index
     
     Idea 3:
     Make a list of value, index
     Sort the list
     Return the index for the first two
     
     Idea 4: (implement this yourself)
     Make a copy of list
     find min in copy
     find index of min in copy
     remove min from list copy
     find next min in copy
     find index of min in the next copy

"""

import random
import time

def smallest_two1(L):
    """ Assume n items in List L. 
    Complexity:  O(nlogn + 3n) =mostly costly element= O(nlogn)
        
    """
    
    L1 = list(L)  ### O(n): read and append to new list for n elements
    L1.sort()     ### O(nlogn): sorting: we will see this in sorting lecture
    min1,min2 = L1[0], L1[1]  ## O(1)
    i1 = L.index(min1)  ### O(n): compare against every element in worst case
    i2 = L.index(min2)  ### O(n): compare against every element in worst case
    if i2 == i1:
        i2 = L.index(min2, i1+1)
    return i1, i2

def smallest_two2(L):
    """ Assume n items in List L.
        Complexity: O(n)

    """
    if L[0] < L[1]:
        i1, i2 = 0,1
    else:
        i1, i2 = 1,0
    for i in range(2,len(L)):  ### O(n)
        if L[i] < L[i1]:
            i1, i2 = i, i1
        elif L[i] < L[i2]:
            i2 = i
    return i1, i2

def smallest_two3(L):
    """ Assume n items in List L.
        Complexity: O(n+nlog n) =mostly costly element= O(nlogn)
        Note: Compared 
        to smallest_two3, we are sorting a more complex list
              (list of 2-tuples). So efficiency will depend on the implementation
              of that sort

    """

    L1 = []
    for (i,val) in enumerate(L):  ## O(n): read and append each element
        L1.append( (val, i) )
    L1.sort()      ## O(nlogn): sorting, we will see why
    return L1[0][1], L1[1][1]

if __name__ == "__main__":
    print "Test cases"
    
    L = range(100000)
    random.shuffle(L)

    start = time.time()
    a,b = smallest_two1(L)
    end = time.time()
    print "smallest_two1 took %f seconds" %(end-start)

    start = time.time()
    a,b = smallest_two2(L)
    end = time.time()
    print "smallest_two2 took %f seconds" %(end-start)
   

    start = time.time()
    a,b = smallest_two3(L)
    end = time.time()
    print "smallest_two3 took %f seconds" %(end-start)

"""
Input: a sorted list and a value

Find the index of value if value is in list
of if it is not, return the index of where 
value would be inserted to keep the list sorted.

"""
import random
import time

def search(L,val):
    """ Linear search, each item has to be searched. """

    for i in range(len(L)):  ## O(n)
        if L[i] >= val:
            return i
    return len(L)-1


def binsearch(L, val):
    """ Binary search: always look at the middle value
    of a list, then look at the middle value of the remaining
    list. You can do this at most O(log n) times, where
    log is base 2.

    """
    
    low = 0
    high = len(L)-1
    while low != high:
        mid = (low+high)/2
        #print low, high, mid
        #raw_input()
        if L[mid] < val:
            low = mid+1
        else:
            high = mid
    return low
    

if __name__ == "__main__":
    
    print "Time tests"
    k = 500000
    L = range(k)
    loops = 100
    
    start = time.time()
    for i in range(loops):
        val = L[random.randrange(500000)] + 0.5
        val = k+1
        a = search(L, val)
    end = time.time()
    total = end-start
    print "Linear search took", total/loops, "seconds, value found at", a


    start = time.time()
    for i in range(1000*loops):
        val = L[random.randrange(500000)] + 0.5
        val = k+1
        a = binsearch(L,val)
    end = time.time()
    total = end-start
    print "Binary search took", total/(1000*loops), "seconds, value found at", a

'''
Testing code for Computer Science 1, Lecture 21 on sorting. This
assumes that the sort functions are all in file sorts.py, each taking
one list as its only argument, and that their names are sel_sort
ins_sort merge_sort

All tests are based on random permutations of integers.

. In most of our tests, these permutations are completely random,
  meaning that a value is equally likely to end up anywhere in the
  list.

. In the final test we will explore the implications of working
  with lists that are "almost sorted" by only moving values a small
  distance from the correct location.  You can see that insertion sort
  is very fast in this case by removing the # char in front of
  generate_local_perm
'''

import sorts_sol
import time
import random


def run_and_time(name, sort_fcn, v, known_v):
    '''
    Run the function passed as sort_fcn, timing its performance and
    double-checking if it correct.  The correctness check is probably
    not necessary.
    '''
    print "Testing " + name
    t0 = time.time()
    sort_fcn(v)
    t1 = time.time()
    print "Time: %.4f seconds" %(t1-t0)
    # print "Is correct?", v==known_v
    print


def run_and_time_python_sort(v):
    '''
    Run and time the Python list sort function on the list.
    '''
    print "Running Python's list sort function"
    t0 = time.time()
    v.sort()
    t1 = time.time()
    print "Time: %.4f seconds" %(t1-t0)
    print


def generate_local_perm(v,max_shift):
    '''
    Generate a local permutation by randomly moving each value up to
    max_shift locations in the list
    '''
    for i in range(len(v)):
        min_i = max(0,i-max_shift)
        max_i = min(len(v)-1, i+max_shift)
        new_i = random.randint( min_i, max_i )
        v[i], v[new_i] = v[new_i], v[i]


####################################################

if __name__ == '__main__':
    n = int(raw_input("Enter the number of values ==> "))
    print "----------"
    print "Running on %d values" %n
    print "----------"

    v = range(n)
    v1 = v[:]
    random.shuffle(v1)
    # generate_local_perm(v1, 10)
    v2 = v1[:]
    v3 = v1[:]
    v4 = v1[:]

    run_and_time("merge sort", sorts_sol.merge_sort, v3, v )   # passing functions as an arg to a fcn
    run_and_time_python_sort(v4 )
    run_and_time("selection sort", sorts_sol.sel_sort, v1, v )
    run_and_time("insertion sort", sorts_sol.ins_sort, v2, v )

'''
CS 1, Lecture 21

Implementation of a variety of sorting algorithms, including
.  Selection Sort,
.  Insertion Sort
.  Merge Sort
Details will be filled in during lecture.  

The main code gives tests for these functions.
'''

def sel_sort( v ):
    '''
    Sort based on teh O(N^2) selection sort algorithm.  The ideas is
    discussed in the text book.  Students are not responsible for
    knowing this algorithm.
    '''
    for i in range(0, len(v)-1):
        k = i
        for j in range(i+1,len(v)):
            if v[j] < v[k]:
                k = j
        v[i],v[k] = v[k],v[i]


def ins_sort( v ):
    '''
    The Insertion Sort algorithm
    '''
    #  Fill in here
    for i in range(1,len(v)):
        x = v[i]
        j = i-1
        while j >= 0 and v[j] > x:
            v[j+1] = v[j]
            j -= 1
        v[j+1] = x


def merge(L1,L2):
    '''
    Merge the contents of two lists, each of which is already sorted
    into a single sorted list.
    '''
    i1 = 0
    i2 = 0
    L = []

    '''
    Repeated choose the smallest remaining item from the lists until one
    list has no more items that have not been merged.
    '''
    while i1 < len(L1) and i2 < len(L2):
        if L1[i1] < L2[i2]:
            L.append( L1[i1] )
            i1 += 1
        else:
            L.append( L2[i2] )
            i2 += 1
    L.extend(L1[i1:])   #  copy remaining items from L1, if any
    L.extend(L2[i2:])   #  copy remaining items from L2, if any
    return L
            

def merge_sort(v):
    '''
    Implementation of the merge sort algorithm.
    '''
    if len(v) <= 1:
        return

    '''
    Start by creating the list of singleton lists '''
    lists = []
    for item in v:
        lists.append( [item] )
    # print 'Before', lists

    '''
    Merge the lists in pairs until there is one unmerged list remaining.
    A number of print statements, used to see what is happening, are here
    in the code but have been commented out.
    '''
    i = 0
    while i < len(lists)-1:
        # print '****** i =', i
        # print 'input', lists[i]
        # print 'input', lists[i+1]
        new_list = merge(lists[i], lists[i+1])
        lists.append( new_list )
        # print 'merged', new_list
        i += 2

    '''
    This is where I made a mistake in class.  I had v = lists[-1], but
    that makes v refer to a new list, and the reference is gone when the
    function ends.  Instead, by writing v[::], v still refers to the original
    list, but it is copied over.
    '''
    v[::] = lists[-1]


















if __name__ == "__main__":
    '''
    v =  [ 10, 5, 3, 2, -4 ]
    ins_sort(v)
    print v
    v = []
    ins_sort(v)
    print v
    v = [ 5, 6, 7, 6, 5, 5]
    ins_sort(v)
    print v
    '''

    '''
    v1 = [ 26, 35, 145]
    v0 = [ 0, 0, 9, 9, 9.4, 9.6, 15, 21 ]
    print v0
    print v1
    print merge(v0,v1)
    '''

    v = [ 9.1, 17.5, 9.8, 6.3, 12.4, 1.7 ]
    merge_sort(v)
    print v
        

'''
CS 1, Lecture 21

Implementation of a variety of sorting algorithms, including
.  Selection Sort,
.  Insertion Sort
.  Merge Sort
Details will be filled in during lecture.  

The main code gives tests for these functions.
'''

def sel_sort( v ):
    '''
    Sort based on teh O(N^2) selection sort algorithm.  The ideas is
    discussed in the text book.  Students are not responsible for
    knowing this algorithm.
    '''
    for i in range(0, len(v)-1):
        k = i
        for j in range(i+1,len(v)):
            if v[j] < v[k]:
                k = j
        v[i],v[k] = v[k],v[i]


def ins_sort( v ):
    '''
    The Insertion Sort algorithm
    '''
    #  Fill in here
    for i in range(1,len(v)):
        x = v[i]
        j = i-1
        while j >= 0 and v[j] > x:
            v[j+1] = v[j]
            j -= 1
        v[j+1] = x


def merge(L1,L2):
    '''
    Merge the contents of two lists, each of which is already sorted
    into a single sorted list.
    '''
    i1 = 0
    i2 = 0
    L = []

    '''
    Repeated choose the smallest remaining item from the lists until one
    list has no more items that have not been merged.
    '''
    while i1 < len(L1) and i2 < len(L2):
        if L1[i1] < L2[i2]:
            L.append( L1[i1] )
            i1 += 1
        else:
            L.append( L2[i2] )
            i2 += 1
    L.extend(L1[i1:])   #  copy remaining items from L1, if any
    L.extend(L2[i2:])   #  copy remaining items from L2, if any
    return L
            

def merge_sort(v):
    '''
    Implementation of the merge sort algorithm.
    '''
    if len(v) <= 1:
        return

    '''
    Start by creating the list of singleton lists '''
    lists = []
    for item in v:
        lists.append( [item] )
    # print 'Before', lists

    '''
    Merge the lists in pairs until there is one unmerged list remaining.
    A number of print statements, used to see what is happening, are here
    in the code but have been commented out.
    '''
    i = 0
    while i < len(lists)-1:
        # print '****** i =', i
        # print 'input', lists[i]
        # print 'input', lists[i+1]
        new_list = merge(lists[i], lists[i+1])
        lists.append( new_list )
        # print 'merged', new_list
        i += 2

    '''
    This is where I made a mistake in class.  I had v = lists[-1], but
    that makes v refer to a new list, and the reference is gone when the
    function ends.  Instead, by writing v[::], v still refers to the original
    list, but it is copied over.
    '''
    v[::] = lists[-1]


















if __name__ == "__main__":
    '''
    v =  [ 10, 5, 3, 2, -4 ]
    ins_sort(v)
    print v
    v = []
    ins_sort(v)
    print v
    v = [ 5, 6, 7, 6, 5, 5]
    ins_sort(v)
    print v
    '''

    '''
    v1 = [ 26, 35, 145]
    v0 = [ 0, 0, 9, 9, 9.4, 9.6, 15, 21 ]
    print v0
    print v1
    print merge(v0,v1)
    '''

    v = [ 9.1, 17.5, 9.8, 6.3, 12.4, 1.7 ]
    merge_sort(v)
    print v
        

"""
Recursion: Example functions

Basis/Stopping condition:
    Define when your function should stop 
    calling itself recursively

Inductive/Recursive step:
    Define how the function can compute its
    output by calling itself recursively and then
    use the result.

Example:

Recursive step:

factorial(n) =  factorial(n-1)*n

If you had the correct output for  factorial(n-1), 
you can multiply it with n to find the correct output.

"""

def blast(n):
    if n <= 0: ##basis step
        print "Blast off!"
    else: ## recursive step
        print n
        blast(n-1)
        print n
                

def factorial(n):
    if n == 1:  
        return 1
    else:
        x = factorial(n-1)
        return x*n

def factorial_iterative(n):
    """Many recursive functions can be written without recursion. """
    x = 1
    for i in range(n+1):
        x *= i
    return x


def fib(n):
    """Fibonacci sequence: Even though it is defined recursively
       this function would be much more efficient to write without
       recursion.

    """
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)


if __name__ == "__main__":
    ##Testing code here.
    val = int(raw_input("Number => "))
    print "Factorial of %d is %d" %(val, factorial(val))

    for i in range(10):
        print "fib(%d) = %d" %(i, fib(i))

"""
Example program shows the use of recursion to create fractals, 
in this case, the Sierpinski Triangle. See function:

draw_triangles

for the recursion. The rest is TkInter program allowing the
user to change properties of the Sierpinski triangle drawn.

"""


from Tkinter import *
import math

class MyApp(object):
    def __init__(self, parent):
        ##Function local to init to simplify repetitive button creation process
        def put_button(parent, name, functionname, placement):
            newbutton = Button(parent, text=name, command=functionname)
            newbutton.pack(side=placement)
            newbutton.configure(width=button_width,\
                                padx=button_padx, pady=button_pady )
            return newbutton
        
        ## constants used  in the initialization
        button_width = 10
        button_padx = "3m"
        button_pady = "3m"

        ## variables used in the program
        self.maxlevel = 6
        self.size = 600  #3**self.maxlevel
        self.maxy = int(self.size*math.sqrt(3)/2)
        self.stopped = False
        self.depth = 2
        self.wait_time = 1
        self.parent = parent
        
        ## interface elements
        ## all frames
        self.main_frame = Frame(parent)
        self.main_frame.pack()
        self.top_frame = Frame(self.main_frame)
        self.top_frame.pack(side=TOP)
        self.bottom_frame = Frame(self.main_frame)
        self.bottom_frame.pack(side=BOTTOM)

        ## canvases: top for info, buttom for drawing Triangles
        self.infocanvas = Canvas(self.top_frame, \
                                 width=self.size, height=30)
        self.infocanvas.pack(side=TOP)
        self.text_area = self.infocanvas.create_text(30,10,anchor='nw')
        self.canvas = Canvas(self.top_frame, \
                             width=self.size, height=self.maxy)
        self.canvas.pack(side=BOTTOM)

        ## buttons: for controlling the program
        self.drawbutton = put_button(self.bottom_frame, 'Draw', self.draw, LEFT)
        self.clearbutton = put_button(self.bottom_frame, 'Clear', self.clear, LEFT)
        self.fasterbutton = put_button(self.bottom_frame, \
                                         "Faster", self.faster, LEFT)
        self.slowerbutton = put_button(self.bottom_frame, \
                                         "Slower", self.slower, LEFT)
        self.increasebutton = put_button(self.bottom_frame, \
                                         "Depth+1", self.increase, LEFT)
        self.decreasebutton = put_button(self.bottom_frame, \
                                         "Depth-1", self.decrease, LEFT)
        self.quitbutton = put_button(self.bottom_frame, \
                                     "Quit", self.quit, RIGHT)
        ## display settings for the program on the info canvas
        self.put_info()

    def put_info(self):
        """ Function for displaying the settings for the program, 
            depth and wait time for the animation effect.

        """
        
        info = "Wait time: %d ms" %(self.wait_time)
        if self.depth == self.maxlevel+3:
            info += " "*10+ "Depth: %d (max level reached)" %self.depth 
        elif self.depth <= 2:
            info += " "*10+ "Depth: 2 (min level reached)"
        else:
            info += " "*10+ "Depth: %d" %self.depth
        self.infocanvas.itemconfigure(self.text_area, text=info)

    def clear(self):
        """ Clear the drawing (used in self.clearbutton). """
        self.canvas.delete("all")
        
    def faster(self):
        """ Make the animation faster (used in self.fasterbutton). """
        self.wait_time /= 2
        if self.wait_time <= 0:
            self.wait_time = 1
        self.put_info()

    def slower(self):
        """ Make the animation slower (used in self.slowerbutton). """
        self.wait_time *= 2
        self.put_info()
        
    def increase(self):
        """ Increases the depth for recursion (used in self.fasterbutton). """
        if self.depth < self.maxlevel+3: 
            self.depth += 1
            self.put_info()
        
    def decrease(self):
        """ Decreases the depth for recursion (used in self.slowerbutton). """
        if self.depth > 2:
            self.depth -= 1
            self.put_info()
            
    def draw(self):
        """ Clear the canvas and draws the Sierpinksi triangles (used in self.drawbutton). """
        padding = 20 ##just leave some space off the corners
        if not self.stopped:
            self.clear()
            self.draw_triangles(0+padding,self.maxy-padding,self.size-2*padding, 1)
            
    def draw_triangles(self, x, y, length, depth):
        """ Draws two triangles: one with x,y as the bottom left corner,
            in red and a second inverted one inside between the midpoints
            of the outside triangle, in white.

        """
        if depth <= self.depth:
            ## Triangle 1: Outside Triangle
            mid = length/2
            self.canvas.create_polygon(x, y, \
                                       x+length, y, \
                                       x+mid, y-math.sqrt(3)*mid,\
                                       fill = "red")
            
            ## Triangle 2: Inside Triangle
            leftmid = ( x+(mid)/2, y-(math.sqrt(3)*mid)/2 )
            rightmid = (  x+(length+mid)/2, y-(math.sqrt(3)*mid)/2 )
            bottommid = ( x+mid, y )
            
            self.canvas.create_polygon( leftmid[0], leftmid[1], \
                                        rightmid[0], rightmid[1], \
                                        bottommid[0], bottommid[1], \
                                        fill = "white" )
            self.draw_triangles(x, y, length/2, depth+1)
            self.draw_triangles(leftmid[0], leftmid[1], length/2, depth)
            self.draw_triangles(x+length/2, y, length/2, depth+1)
            ## Add animation effect
            self.canvas.update()
            self.canvas.after(self.wait_time)
            
    def quit(self):
        self.stopped = True
        self.parent.destroy()

if __name__ == "__main__":
    root = Tk()
    root.title("Recursion Example with Sierpinski Triangles")
    myApp = MyApp(root)
    root.mainloop()

""" 

We rewrite merge_sort using recursion and compare to the 
iterative version. The recursive version is natural to write 
and does not require a list/loop to maintain sublists. As a 
result, it is slightly more efficient.


"""

import time
import random


def time_function(L, func):
    """ Illustrates how you can send a function as an argument
    to another function as well. Runs the function called func,
    and returns the time.

    """

    L1 = list(L)
    start = time.time()
    func(L1)
    end = time.time()
    print "Method: %s took %f seconds" \
          %((func.__name__).ljust(20), end-start)


def merge(L1, L2):
    """ Assume L1 and L2 are sorted.
    Create a new list L that is the merged
    version of L1&L2.
    
    This is the efficient version of merge
    that does not modify the input lists, as pop 
    is costly, even though it is a constant time operation.

    """
    
    L = []
    i = 0
    j = 0
    while i < len(L1) and j < len(L2):
        if L1[i] < L2[j]:
            val = L1[i]
            L.append( val )
            i += 1
        else:
            val = L2[j]
            L.append( val )
            j += 1
    ## at this point, either L1 or L2 has run out of values
    ## add all the remaining values to the end of L.
    L.extend(L1[i:]) 
    L.extend(L2[j:])
    return L


    
def merge_sort_iterative(L):
    """ Complexity: O(n* log n)
        See earlier version of this code for explanation.

    """

    L1 = []
    for val in L:
        L1.append( [val] )
    
    while len(L1) > 1:
        L2 = []
        for i in range(0, len(L1)-1, 2):
            Lmerged = merge( L1[i], L1[i+1] )
            L2.append( Lmerged )
            
        if len(L1)%2 == 1:
            L2.append( L1[-1] )
        L1 = L2
    return L1[0]


def merge_sort_recursive(L):
    """ Complexity: O(n logn)
        The function calls itself recursively logn times,
        and each time about n elements are merged.

    """

    numitems = len(L)
    if numitems <= 1:
        return L
    else:
        mid = numitems/2
        L1 = merge_sort_recursive( L[:mid] )
        L2 = merge_sort_recursive( L[mid:] )
        return merge(L1, L2)

if __name__ == "__main__":
    ##Testing code
    k = 100000
    L = range(k)
    random.shuffle(L)
    
    time_function( L, merge_sort_iterative )
    time_function( L, merge_sort_recursive )
    time_function( L, list.sort )