Code Developed in CSCI-1100 Fall Semester 2016¶

""" 

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".format((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 = list(range(k))
    random.shuffle(L)
    
    time_function( L, merge_sort_iterative )
    time_function( L, merge_sort_recursive )
    time_function( L, list.sort )

"""
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 == 0:
            info += " "*10+ "Depth: 0 (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 > 0:
            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.

        """
        ## 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")
            
        if depth <= self.depth:
            ## 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+1)
            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()

from tkinter import *

class MyApp(object):
    def __init__(self, parent):
        ## method internal to constructor method for creating buttons
        ## shortens the program code
        def new_button(parent, cmd, buttontext, packlocation):
            button = Button(parent, command=cmd)
            button.configure(text=buttontext)
            button.configure(width=button_width,
      	        padx=button_padx, pady=button_pady )
            button.pack(side=packlocation)
            return button

        #------ constants for controlling layout ------
        button_width = 10  
        button_padx = "2m" 
        button_pady = "1m" 
        buttons_frame_padx =  "3m" 
        buttons_frame_pady =  "2m" 
        buttons_frame_ipadx = "3m" 
        buttons_frame_ipady = "1m"
        # -------------- end constants ----------------
      
        #---------variables for controlling the function-----
        self.canvas_dimension = 600 ##Canvas will be a square
        self.wait_time = 8
        self.repetitions = 2
        #----------end of variables--------------------------
        
        self.myParent = parent
        self.main_frame = Frame(parent)
        self.main_frame.pack ()

        ## Two frames inside the main frame, one for the canvas
        ## on top and the second one for buttons in the bottom
        self.draw_frame = Frame(self.main_frame)
        self.draw_frame.pack(side=TOP)

        self.info_canvas = Canvas(self.draw_frame, height=20,
                                   width=self.canvas_dimension)
        self.info_canvas.pack(side=TOP)
        self.text_area = self.info_canvas.create_text(10,10,anchor='nw')
        self.info_canvas.itemconfigure(self.text_area,text="#circles = {:d}".format(self.repetitions))
        
        self.main_canvas = Canvas(self.draw_frame, \
                                  height=self.canvas_dimension,
                                  width=self.canvas_dimension)
        self.main_canvas.pack()
                                  
        self.button_frame = Frame(self.main_frame)
        self.button_frame.pack(side=BOTTOM)

        self.draw_button = new_button(self.button_frame,self.draw, 'Draw', LEFT)
        self.clear_button = new_button(self.button_frame,self.clear, 'Clear', LEFT)
        self.increase_button = new_button(self.button_frame,self.increase, 'Increase', LEFT) 
        self.reduce_button = new_button(self.button_frame,self.reduce, 'Reduce', LEFT)
        self.faster_button = new_button(self.button_frame,self.faster, 'Faster', LEFT) 
        self.slower_button = new_button(self.button_frame,self.slower, 'Slower', LEFT)
        self.quit_button = new_button(self.button_frame,self.quit, 'Quit', RIGHT)

    def clear(self):
        self.main_canvas.delete(ALL)

    def reduce(self):
        if self.repetitions > 1:
            self.repetitions //= 2
        self.put_info()

    def increase(self):
        if self.repetitions < 200:
            self.repetitions *= 2
        self.put_info()
        
    def faster(self):
        if self.wait_time > 1:
            self.wait_time //= 2    
            
    def slower(self):
        self.wait_time *= 2
        
    def put_info(self):
        ## Change the text field in the canvas
        self.info_canvas.itemconfigure(self.text_area,text="#circles = {:d}".format(self.repetitions))

    def draw(self):
        boundary_offset = 2
        max_radius = (self.canvas_dimension - 2*boundary_offset) // 2
        xc = self.canvas_dimension//2 + boundary_offset
        r = max_radius/self.repetitions
        inc = r
        for i in range(self.repetitions):
            self.main_canvas.create_oval((xc-r, xc-r, xc+r, xc+r))
            r += inc
            self.main_canvas.update() # Actually refresh the drawing on the canvas.
            # Pause execution.  This allows the eye to catch up
            self.main_canvas.after(self.wait_time)

    def quit(self):
        self.myParent.destroy()
        
if __name__ == "__main__":
    root = Tk()
    root.title("Drawing a circle") ##Give a title to the program
    myapp = MyApp(root)
    root.mainloop()

'''
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 the 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
    '''
    for i in range(1,len(v)):
        x = v[i]            # value to be inserted
        j = i-1             # first location down to consider
        while j >= 0 and v[j] > x:
            v[j+1] = v[j]   # move it over
            j -= 1          # consider the next value down
        v[j+1] = x          # insert in sorted position



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 = []
    
    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
    
    #  Append remainder of one of the lists.  Since either i1 == len(L1) or
    #  i2 == len(L2), only one of these will add to L
    L.extend( L1[i1:] )
    L.extend( L2[i2:] )
    return L

            

def merge_sort(v):
    '''
    Implementation of the merge sort algorithm.
    '''
    if len(v) <= 1:
        return
    
    '''
    Create list of lists
    '''
    lists = []
    for x in v:
        lists.append( [x] )
    
    '''
    Run merge until only one unmerged list.  Take the next two lists to be
    merged, merge them, and add the resulting list to the end of the list of lists.
    '''
    i = 0     # index of next "unmerged" list
    while i < len(lists)-1:
        lists.append( merge(lists[i],lists[i+1]) )
        i += 2
    v[:] = lists[-1]   # copy values in last list to each value in v







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)
    '''

    '''
    v0 = [ 0, 0, 9, 9.4, 9.6, 15, 21 ]
    v1 = [ 6, 12, 13, 145]
    print(v0)
    print(v1)
    print(merge(v1,v0))
    '''

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

'''
Professor Stewart's solution to the Lecture 20 problem of finding the indices
of the two smallest values in a list.
'''

import random
import time

def index_two_v1( values ):
    '''
    Store the values in a list of value,index pairs and sort, then
    return the indices associated with the first two values
    '''
    pairs = []
    for i in range(len(values)):
        pairs.append( (values[i],i) )
    pairs.sort()
    return pairs[0][1], pairs[1][1]   # indices of the values are in location 1 of each pair


def index_two_v2( values ):
    '''
    Keep track of the indices of the two smallest values as we scan
    through the list.
    '''
    if values[0] < values[1]:
        i0,i1 = 0,1
    else:
        i0,i1 = 1,0
    for i in range(2,len(values)):
        if values[i] < values[i1]:         # less than second smallestn
            if values[i] < values[i0]:     # less than the smallest too
                i0,i1 = i,i0               # new value is smallest, previous smallest is 2nd
            else:
                i1 = i                     # new 2nd smallest
    return i0,i1

if __name__ == "__main__":
    n = int(input("Enter the number of values to test ==> "))
    values = list(range(0,n))
    random.shuffle( values )

    s1 = time.time()
    (i0,i1) = index_two_v1(values)
    t1 = time.time() - s1
    print("Ver 1:  indices ({},{}); time {:.3f} seconds".format(i0,i1,t1))

    s2 = time.time()
    (j0,j1) = index_two_v2(values)
    t2 = time.time() - s2
    print("Ver 2:  indices ({},{}); time {:.3f} seconds".format(j0,j1,t2))

'''
Posting of Prof. Stewart's Lecture 16 solution to finding the number of times each individual
appears in the Internet Movie Database
'''

imdb_file = input("Enter the name of the IMDB file ==> ").strip()
counts = dict()
for line in open(imdb_file, encoding = "ISO-8859-1"):
    words = line.strip().split('|')
    name = words[0].strip()
    if name in counts:      # name is already a key in the dictionary
        counts[name] += 1   # we've seen one more instance of this name
    else:
        counts[name] = 1    # first time we have seen this individual
        
n = min(100,len(counts))
sorted_keys = sorted(counts.keys())[:n]   # keep the first n keys in lexicographic order

# Now output the first 100 names and counts
for name in sorted_keys:
    print("{}: {}".format(name, counts[name]))

'''
This is the solution to the problem of using sets to count the number
of individuals in the internet movie database.  Each line of input is
split and stripped to get the name and this name is added to the set. 

One important note.  In opening the file we need to specify the
encoding the text.  The default is what's known as utf-8, but this
only handles English characters well.  For the IMDB file, we need to
open with a more language-independent, international standard.  This
is 'ISO-8859-1'.

As we will use the time.time() function to measure how long our
computation takes.  This function tells the seconds since an "epoch",
which is 1/1/1970 on Unix-based systems (including Macs and Linux
machines) and 1/1/1601 on Windows machines.  By recording in the
software the time before the calculations start, the time when the
calculations end, and subtracting we get the elapsed time.
'''
import time

imdb_file = input("Enter the name of the IMDB file ==> ").strip()

start_time = time.time()

names = set()
for line in open(imdb_file, encoding = "ISO-8859-1"):
    words = line.strip().split('|')
    name = words[0].strip()
    names.add(name)

end_time = time.time()

print("Solution took {:.2f} seconds".format(end_time-start_time))

print("Number of unique names in the IMDB:", len(names))

#######
##  The rest of this code was written to test the code and then
##  commented out.
#######
'''
ordered_names = sorted(names)
for i in range(min(len(ordered_names),100)):
    print("{}: {}".format(i, ordered_names[i]))
'''

'''
for n in names:
    print('\t{}'.format(n))
'''

'''
This is the list-based solution to the problem of finding all people
named in the internet movide database.  Each line is split and
stripped to get the name and then the name is added to a list, but
only if it is not already there.

One important note.  In opening the file we need to specify the
encoding the text.  The default is what's known as utf-8, but this
only handles English characters well.  For the IMDB file, we need to
open with a more language-independent, international standard.  This
is 'ISO-8859-1'.

As we will use the time.time() function to measure how long our
computation takes.  This function tells the seconds since an "epoch",
which is 1/1/1970 on Unix-based systems (including Macs and Linux
machines) and 1/1/1601 on Windows machines.  By recording in the
software the time before the calculations start, the time when the
calculations end, and subtracting we get the elapsed time.
'''
import time

imdb_file = input("Enter the name of the IMDB file ==> ").strip()

start_time = time.time()

name_list = []
for line in open(imdb_file, encoding = "ISO-8859-1"):
    words = line.strip().split('|')
    name = words[0].strip()
    
    #  Add the name to the list if it is new
    if not name in name_list:
        name_list.append(name)
        if len(name_list) % 1000 == 0:
            end_time = time.time()
            print('After {} added, the last 1000 took {:.2f} seconds'.format(len(name_list), end_time-start_time))
            start_time = end_time
            

print("Number of unique names in the IMDB:", len(name_list))
for n in name_list:
    print('\t{}'.format(n))

'''
Here is an alternative list based solution - not covered in lecture -
where each name is added to the list without any checking for
duplicates. The list is then sorted and the number of distinct
individual is counted by scanning through the list and looking for
adjacent pairs of names that are different.

You will see that this solution is almost as fast as the set-based
solution, but the set-based solution is simpler and more natural to
write.

One important note.  In opening the file we need to specify the
encoding the text.  The default is what's known as utf-8, but this
only handles English characters well.  For the IMDB file, we need to
open with a more language-independent, international standard.  This
is 'ISO-8859-1'.

As we will use the time.time() function to measure how long our
computation takes.  This function tells the seconds since an "epoch",
which is 1/1/1970 on Unix-based systems (including Macs and Linux
machines) and 1/1/1601 on Windows machines.  By recording in the
software the time before the calculations start, the time when the
calculations end, and subtracting we get the elapsed time.
'''
import time

imdb_file = input("Enter the name of the IMDB file ==> ").strip()

start_time = time.time()

# Add all the names to the list
name_list = []
for line in open(imdb_file, encoding = "ISO-8859-1"):
    words = line.strip().split('|')
    name = words[0].strip()
    name_list.append(name)

# Sort the names.  After this all repeated names will be next to each
# other in the list.
name_list.sort()

# Count the distinct names by counting the number of adjacent pairs of
# names that are different.
count = 1
for i in range(1,len(name_list)):
    if name_list[i-1] != name_list[i]:
        count += 1

end_time = time.time()
print('Total time required {:2f} seconds'.format(end_time-start_time))
print("Number of unique names in the IMDB:", count)

'''
Professor Stewart's solution to building the list of legos from a
file.  Each line of this file contains the name of a lego and the
number of copies of that lego, separated by a comma.  For example,
2x1, 3
2x2, 2
'''
lego_name = input('Enter the name of the legos file: ').strip()
lego_list = []
for line in open(lego_name):
    line = line.split(',')
    lego = line[0].strip()   # get rid of extra space
    count = int(line[1])
    # Either of the following two lines work...
    # lego_list.extend( [lego]*count )
    lego_list = lego_list + [lego]*count
print(lego_list)

'''
Lecture 13 Practice Problem: Parse the yelp.txt data file to create a
list of lists of names and averages. This demonstrates parsing an
irregularly formatted file.  We have to know that the 0th entry on
each line and the 6th are the scores.

Prof. Stewart
'''

def yelp_averages( yelp_name ):
    averages = []
    for line in open(yelp_name):
        line = line.split('|')
        name = line[0]
        scores = line[6:]    # From entry 6 on are the scores

        if len(scores) == 0:
            # Handle the special case of an empty scores list
            averages.append( [ name, -1 ] )
        else:
            # Compute the average when there is at least one score
            sum_score = 0
            for s in scores:
                sum_score += int(s)
            avg = sum_score / len(scores)

    return averages

avgs = yelp_averages('yelp.txt')
print( avgs[0:3] )

'''
Find the two closest points from a list of tuples of points.  This
illustrates use of nested for loops.
Prof. Stewart
'''

import math

def dist( p, q ):
    '''
    Return the Euclidean distance between two points represented as a
    tuple of x,y locations.
    '''
    return math.sqrt( (p[0]-q[0])**2 + (p[1]-q[1])**2 )


# Here is a list of location tuples that we can use to test.
points = [ (1,5), (13.5, 9), (10, 5), (8, 2), (16,3) ]

'''
We will keep track of the minimum distance seen so far and the indices
of the two closest points.  We need to initialize the values of the
necessary variables based on the first pair of points.
'''
min_dist = dist( points[0], points[1]) 
min_i = 0
min_j = 1

'''
Loop i over all of the indices and then j starting from i+1.  We start
j here for two reasons: to avoid the case of i == j and to avoid
double testing since we don't have to test both pair i and j and pair
j and i --- they are the same distance.
'''
for i in range(len(points)):
    for j in range(i+1, len(points)):
        d = dist( points[i], points[j] )
        if d < min_dist:
            min_dist = d
            min_i = i
            min_j = j

print("Pair {},{} has min dist {:.2f}".format(min_i, min_j, min_dist))
        

'''
Given a list of the lists of temperature measurements at different
study sites, find the maximum average and the index of the site having
the maximum average.

Two solutions are given.  One solution computes the average for each
site (list within the outer list), stores the averages in a new list,
and then finds the max and its index from this list.  The second
solution keeps track of the max as the averages are being computed.

Prof. Stewart
'''

temps_at_sites = [ [ 12.12, 13.25, 11.17, 10.4],
                   [ 22.1, 29.3, 25.3, 20.2, 26.4, 24.3 ],
                   [ 18.3, 17.9, 24.3, 27.2, 21.7, 22.2 ],
                   [ 12.4, 12.5, 12.14, 14.4, 15.2 ] ]

'''
Solution 1:  Store the averages in a list and analyze this list to find the max.
'''
averages = []
for site in temps_at_sites:
    avg = sum(site) / len(site)
    averages.append(avg)
max_avg = max(averages)
max_i = averages.index(max_avg)
print("Solution 1: Maximum average of {:.2f} occurs at site {}".format(max_avg, max_i ))

'''
Solution 2: Keep track of the max avg and its index.  Initialize this
max index to be -1.  This essentially will mean that the max has not
been set yet, and so it will be set the first time through the loop.
'''
max_i = -1
max_avg = 0
for i in range(len(temps_at_sites)):
    avg = sum(temps_at_sites[i]) / len(temps_at_sites[i])
    if max_i == -1 or avg > max_avg:
        max_avg = avg
        max_i = i

print("Solution 2: Maximum average of {:.2f} occurs at site {}".format(max_avg, max_i) )

'''
Lecture 11 random walk example from Prof. Stewart's lecture.
Demonstrates the use of a random number generate as well as delays in
the processing so that the similuation can be observed at "human
speeds" rather than the rate at which the processing actually occurs.
'''
import random
import time

def print_platform( N, loc, step_num ):
    '''
    All values are positive integers
    1 <=  loc <= N
    '''
    print('{:4d}: '.format(step_num) + '_'*(loc-1) + 'X' + '_'*(N-loc))

def random_walk(N):
    '''
    Run the random walk for platform of N positions until the walker
    falls off one end or the other.
    N is a positive integer
    representing the number of steps on the platform
    '''
    loc = N // 2        # Start the walker in the center.
    steps = 0
    while 1 <= loc and loc <= N:
        print_platform( N, loc, steps )
        if random.randint(0,1) == 1:
            loc += 1    # Take a forward step
        else:
            loc -= 1    # Take a backward step
        time.sleep(0.1) # Pause the program for one-tenth of a second
        steps += 1
    if loc == 0:
        print("Fell off back")
    else:
        print("Fell off front")

'''
__name__ holds a string that names the main code or a separate module.
When the string is "__main__" this indicates that the file is the one
initially called by Python Otherwise, the string will be the file name
of the imported module.  This allows us to put test code into modules
that will not be run when the module is actually imported, but will be
run if the module itself is run.
'''
if __name__ == "__main__":
    N = int(input('Enter number of steps on the platform: '))
    random_walk(N)

'''
This code illustrate the various attempts to write a function that
capitalizes a list of strings, changing the list itself.
'''

def capitalize_list_v1( names ):
    '''
    Because names is an alias for the list referenced by animals when
    you change names to reference the list cap_names, you have not
    changed animals.  It still references the original list.
    '''
    cap_names = []
    for n in names:
        cap_names.append( n.capitalize() )
    names = cap_names

def capitalize_list_v2( names ):
    '''
    Here n aliases each string in the list.  (Remember, strings
    themselves can't be changed.)  The capitalize method creates a new
    string and n references that string.  The entry in the list does
    not change and still references the uncapitalized string.
    '''
    for n in names:
        n = n.capitalize()

def capitalize_list_v3( names ):
    '''
    This version, using a while loop, works correctly.  names[i] is an
    actual entry in the list and so when we change names[i] to
    reference the newly created string, we are changing the list itself.
    '''
    i = 0
    while i < len(names):
        names[i] = names[i].capitalize()
        i += 1

def capitalize_list_v4( names ):
    '''
    This version, using a for loop, works correctly for the same
    reason that v3 works correctly.  It is clearer and more compact
    than the while loop version and should be preferred.
    '''
    for i in range(len(names)):
        names[i] = names[i].capitalize()
        
animals = ['cat', 'monkey', 'hawk', 'tiger', 'parrot']
print(animals)
capitalize_list_v4(animals)
print(animals) 

'''
Author: Charles Stewart
Purpose:  These are the examples from Prof. Stewart's lecture working with
the co2_levels list.  They illustrate a number of small-scale problem-solving
approaches.
'''
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) ]

'''
The first example just prints the year and the CO2 levels together on one line:
'''
print('CO2 levels and years:')
i=0
while i< len(co2_levels):
    print( "Year", co2_levels[i][0], \
           "CO2 level:", co2_levels[i][1])
    i += 1

'''
Now here they are in reverse order.
'''
print('-------------')
print("Here are the same values printed in reverse order:")
i = len(co2_levels) - 1
while i >= 0:
    print( "Year", co2_levels[i][0], \
               "CO2 level:", co2_levels[i][1])
    i -= 1
    
'''
Next we average the co2 levels.  Note the importance of having a sum variable
(called sum_co2) that we initialize to 0 and add to as the loop proceeds.
'''
print('-------------')
sum_co2 = 0
i = 0
while i < len(co2_levels):
    sum_co2 += co2_levels[i][1]
    i += 1
print("Average co2_level {:0.1f}".format( sum_co2 / len(co2_levels)))

'''
Count number of levels greater than 350 ppm.  In this case we need to keep track
of the count of values.
'''
print('-------------')
count = 0
i = 0
while i < len(co2_levels):
    if co2_levels[i][1] > 350:
        count += 1
    i += 1
print("\n{} years saw CO2 levels above 350".format(count))

'''
Next we have the output of the measurement-to-measurement change.
Here we have to be careful with our indices because there are
len(co2_levels)-1 consecutive pairs of values to consider.  In this
case we start at i=1 (instead of 0) and end when i reaches the length
of the list.
'''
print('-------------')
i = 1
while i < len(co2_levels):
    curr = co2_levels[i][1]
    prev = co2_levels[i-1][1]
    pct_change = (curr-prev) / prev * 100
    print("Percent change of {} vs. {} is {:.1f}".format( co2_levels[i][0], co2_levels[i-1][0], pct_change))
    i += 1

'''
Finally, output the years for which the measurement dropped over the
previous measurement.  Just like in the previous example we need to be
careful with indices.  In this solution, however, we start with i and
end at len(co2_levels)-1.  Either of these methods of handling pairs
of indices is equally fine.  We just need to be careful to handle them
correctly.
'''
i = 0
while i < len(co2_levels)-1:
    if co2_levels[i+1][1] < co2_levels[i][1]:
        print("Dropped in year", co2_levels[i+1][0])
    i += 1
              

'''
Solutions to the second set of practice problems from Lecture 9
'''
months=['jan','feb','mar','apr','may','jun','jul','aug','sep','oct','nov','dec']
i = 1
while i < len(months):
    print("{}: {}".format(i,months[i]))
    i += 2
    
print()
print()

'''
This prints the 5 level evergreen tree.  Can you generalize to an arbitrary number
of levels
'''
i = 1
while i <= 9:
    print(' '*((9-i)//2) + '*'*i)
    i += 2
print(' '*3 + '*'*3)
print(' '*3 + '*'*3)
    

'''
Program to demonstrate the use of complex boolean expressions and if/elif/else
clauses. Determine whether a set of coordinates fall within a rectangle given
by the verticies (x0, y0), (x0, y1), (x1, y1), and (x1, y0)

Author: CS1 Staff
Date 9/19/2016
'''

'''
Initialize the rectangle
'''
x0 = 10
x1 = 16
y0 = 32
y1 = 45

'''
Get the target point
'''
x = input("x coordinate ==> ")
print(x)
x = float(x)
y = input("y coordinate ==> ")
print(y)
y = float(y)

'''
If the x coordinate matches x0 or x1 and we are within the y range, we are
on the boundary. Similarly, if the y coordinate matches y0 or y1 and we are 
within the x range, we are also on the boundary
'''
if ((x == x0 or x == x1) and (y0 <= y <= y1) or (y == y0 or y == y1) and (x0 <= x <= x1)):
    print("Point ({:.2f},{:.2f}) is on the boundary.".format(x, y))
elif (x0 < x < x1) and (y0 < y < y1):
    '''
    If we are not on the boundary, but we are in range in both x and y, 
    then we are inside the rectangle
    '''
    print("Point ({:.2f},{:.2f}) is inside the rectangle.".format(x, y))
else:
    '''
    If we are not on the boundary and we are not inside the rectangle, then
    we must be inside.
    '''
    print("Point ({:.2f},{:.2f}) is outside the rectangle.".format(x, y))

'''
Demonstration of how to define and call a function without a return. Note that
printer(7) causes the "Hello! " string to be printed 7 times and "Goodbye! " to
be printed 6 times. YOU DO NOT NEED TO print(printer(7)). It will cause "None" 
to be added as an additional line in your output.
'''
def printer(num):
    print(num * "Hello! ")
    print((num-1) * "Goodbye! ")
    
printer(7)

""" 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.request

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.

# The main body of the program starts here

"""
Assign the location of the words file and go get it.
"""
word_url = 'http://www.greenteapress.com/thinkpython/code/words.txt'
word_file = urllib.request.urlopen(word_url)

'''
Process each word in the file one by one, testing to see if it has
three consecutive doubles.  Print it and count it if it does.
'''
count = 0
for word in word_file:
    word = word.decode().strip()
    if has_three_double(word):
        print(word)
        count = count + 1

'''
After we've gone through all the words, output a final message based
on the number of words that were counted.
'''        
if count == 0:
    print('No words found')
elif count == 1:
    print("1 word found")
else:
    print(count, 'words were found')