Code Developed in CSCI-1100 Spring 2018¶
Lecture 1¶
Module: three_doubles — Finds three consecutive pairs of double letters¶
Code:
""" 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')
Lecture 3¶
Module: lec05_surface_and_area — Find the surface and area of a cylinder¶
Code:
pi = 3.14159
radius = input("Radius: ")
radius = float(radius)
height = input("Height: ")
height = float(height)
base_area = pi * radius ** 2
number = 7
volume = base_area * height * number
surface_area = 2 * base_area + 2 * pi * radius * height
print("volume is", volume, ", surface area is", surface_area)
Lecture 5¶
Module: lec05_surface_and_area — Find the surface and area of a cylinder¶
Code:
'''
This is a program to calculate the surface area and
volume of a cylinder given a radius and a height.
Radius and height are in float and are user inputs.
Sample Execution:
Enter radius (float) => 12
Enter height (float) => 10
Surface area is: 1658.76
Volume is: 4523.89
CS1
Wesley Turner
9/18/2017
'''
import math
def area_circle(radius):
'''
This function returns the area of a circle with a given radius.
radius is the input parameter
'''
area = math.pi * radius ** 2
return area
def area_cylinder(h, r):
'''
Give a height h and radius r, return the surface area of a cylinder.
'''
cap_area = 2 * area_circle(r)
rect_area = math.pi * 2 * r * h
return cap_area + rect_area
if __name__ == "__main__":
r = float(input("Enter radius (float) => "))
h = float(input("Enter height (float) => "))
print("Surface area is: {:.2f}".format(area_cylinder(h, r)))
print("Volume is: {:.2f}".format(h * area_circle(r)))
Lecture 6¶
Module: lec06_rectangle — Does a given point fall within a rectangle¶
Code:
'''
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/21/2017
'''
'''
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))
Lecture 7¶
Module: lec07_area — Set up a module for area calculations¶
Code:
'''
Lecture 7 - Area Module
Prof. Charles Stewart
We've gathered the code from our area calculations to form a module
that can be used by other programs.
'''
import math
def circle(radius):
''' Compute and return the area of a circle '''
return math.pi * radius**2
def cylinder(radius,height):
''' Compute and return the surface area of a cylinder '''
circle_area = circle(radius)
height_area = 2 * radius * math.pi * height
return 2*circle_area + height_area
def sphere(radius):
''' Compute and return the surface area of a sphere '''
return 4 * math.pi * radius**2
Module: lec08_use_area — Use the area module in a separate main¶
Code:
'''
Lecture 7 - Demonstrate the use of the area calculations
Prof. Charles Stewart
'''
import lec07_area
r = 6
h = 10
a1 = lec07_area.circle(r)
a2 = lec07_area.cylinder(r,h)
a3 = lec07_area.sphere(r)
print("Area circle {:.1f}".format(a1))
print("Surface area cylinder {:.1f}".format(a2))
print("Surface area sphere {:.1f}".format(a3))
Module: lec07_images_init — Image chipmunk example¶
Code:
'''
Lecture 7 - Our first image manipulation example
Prof. Stewart
Demonstrates opening images, accessing their properties, converting
them to gray scale, resizing them, displaying them and saving them to
new files.
'''
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)
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)im2.paste
scaled.show()
scaled.save(filename + "_scaled.jpg")
Lecture 9¶
Module: lec09_co2_percentages — CO2 percentages from class examples¶
Code:
'''
Demonstrate walking through a list calculating values between pairs of
values. In this instance we are calculating the percent change year-to-year
for CO2 concentration.
'''
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) ]
i=1
percent_change = []
while i< len(co2_levels):
percent_change.append((co2_levels[i][1] - co2_levels[i-1][1]) / co2_levels[i-1][1])
i += 1
print(percent_change)
Module: lec09_loop_variable_examples — Three examples of manipulating loop variables¶
Code:
'''
Two examples of manipulating loop variables. The first prints out every
other element of the list starting from the first element. The second uses the
loop variable to print out an evergreen tree.
'''
months=['jan','feb','mar','apr','may','jun','jul','aug','sep','oct','nov','dec']
i = 0
while i < len(months):
print(months[i])
i+= 2
'''
Now print out the evergreen.
'''
print()
i = 1
length = 9
while i < 10:
print((4 - i//2 )*" " + i*'*')
i+= 2
print(3*" "+3*'*')
print(3*" "+3*'*')
'''
Finally, let's let the user pick
an odd value > 3.
'''
print()
field = int(input("Enter an odd number greater than 3: "))
if field % 2 == 1 and field > 3:
j = 1
while j <= field:
print((field - j) // 2 * ' ', j * "*")
j += 2
j = 3
print((field - j) // 2 * ' ', j * "*")
print((field - j) // 2 * ' ', j * "*")
else:
print("{} is not an odd integer greater than 3.".format(field))
Module: lec09_nested_loop — Example of doubly nested loop¶
Code:
'''
Quick code snippet to demonstrate walking through a list operating on
all pairs of list elements without repeating matches and without operating
on the diagonals.
CS1
'''
L = [2, 21, 12, 8, 5, 31]
i = 0
dist = abs(L[0] - L[1])
indices = 0 ,1
while i < len(L):
j = i +1
while j < len(L):
test_dist = abs(L[i] - L[j])
if test_dist <= dist:
dist = test_dist
indices = i, j
j += 1
i += 1
print("Closest {} at {}.".format(dist, indices))
Lecture 10¶
Lecture 11¶
Module: Lec11_module — Example of defining test code in a module¶
Code:
'''
Demonstrate importing and using a 'homegrown' module. In this file
we are defining the Lec11_module code. Note that the code in the
if __name__ == "__main__":
block is executed when this file is run, but not when we import it
into Lec11_main. Either way the "addto" function remains available.
'''
def addto(val, increment):
return val + increment
if __name__ == "__main__":
# Put the main body of the program below this line
n = int(input("Enter a positive integer ==> "))
total = 0
i = 0
print(i,n)
while i < n:
print(i,n)
total = addto(total, i)
i += 1
print('Sum is', total)
Module: Lec11_main — Example of importing a module with test code¶
Code:
'''
Demonstrate importing and using a 'homegrown' module. In this file
we are importing the Lec11_module code. Note that the code in the
if __name__ == "__main__":
block is not executed, but we can read in and use the "addto" function.
'''
import Lec11_module
print(Lec11_module.addto(5,7))
Lecture 12¶
Module: Lec12_dist — Closest point example¶
Code:
'''
Two implementations of the closest point calculation, one using
an auxillary list and one not using an auxillary list.
'''
def distance(p1, p2):
'''
Calcalate the distance between two points.
'''
return ((p1[1] - p2[1])**2 + (p1[0]-p2[0])**2)**0.5
def closest_points_1(points):
'''
Calculate the closest distance between two points using a distance array
'''
dist = []
for i in range(len(points)):
for j in range(i+1, len(points)):
dist.append([distance(points[i], points[j]),i,j])
return min(dist)
def closest_points_2(points):
'''
Calculate the closest distance between two points without using a distance array
'''
small = distance(points[0], points[1])
i1 = 0
i2 = 1
for i in range(len(points)):
for j in range(i+1, len(points)):
dist = distance(points[i], points[j])
if dist < small:
small = dist
i1 = i
i2 = j
return small, i1, i2
points = [ (1,5), (13.5, 9), (10, 5), (8, 2), (16,3) ]
cp = closest_points_1(points)
print("Closest dist of {:.2f} occurs between {} and {}".format(cp[0], points[cp[1]], points[cp[2]]))
cp = closest_points_2(points)
print("Closest dist of {:.2f} occurs between {} and {}".format(cp[0], points[cp[1]], points[cp[2]]))
Module: Lec12_Workspace — For and while loop examples¶
Code:
'''
Calculate the distance betwee 2 x,y coordinates. This is used
later in the closest points calculation
'''
def dist(x, y):
return ((x[0] - y[0])**2 + (x[1] - y[1])**2)**0.5
'''
Two loops to demonstrate manipulation of
loop variables for "for" and "while" loops.
'''
n = int(input("N?: "))
print("For:")
for i in range(2, n, 2):
print(i)
print("\nWhile:")
i = 2
while i < n:
print(i)
i += 2
Lecture 13¶
Module: Lec13_avg — File example, reading and calculating scores¶
Code:
file_name = input("Enter the name of the scores file: ")
file_name = file_name.strip() # Elminate extra white space that the user may have typed
print(file_name)
num_scores = 0
sum_scores = 0
for s in open(file_name):
sum_scores += int(s)
num_scores += 1
print(int(s))
print("Average score is {:.1f}".format( sum_scores / num_scores ))
Module: Lec13_parse_legos — Parsing Practice from Lecture 13¶
Code:
'''
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)
Module: Lec13-parse-yelp — Parsing Practice from Lecture 13¶
Code:
'''
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] )
Lecture 14¶
Lecture 15¶
Module: Lec15_find_names_start — Starting point for IMDB example¶
Code:
'''
This is the start to the solution to the problem of find all people
named in the internet movide database.
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()
name_list = []
for line in open(imdb_file, encoding = "ISO-8859-1"):
words = line.strip().split('|')
name = words[0].strip()
Module: Lec15_find_names_list — Using lists to hold unique names¶
Code:
'''
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))
Module: lec15_find_names_list_sort — Faster list version using sorting¶
Code:
'''
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)
Module: Lec15_find_names_sets — Faster versions using sets¶
Code:
'''
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))
'''
Lecture 16¶
Module: Lec16_imdb — Find how many movies everyone was in¶
Code:
imdb_file = input("Enter the name of the IMDB file ==> ").strip()
count_list = []
for line in open(imdb_file, encoding = "ISO-8859-1"):
words = line.strip().split('|')
name = words[0].strip()
found = False
for pair in count_list:
if pair[0] == name:
pair[1] += 1
found = True
break
if not found:
new_pair = [name, 1]
count_list.append(new_pair)
for pair in count_list:
print("{} appeared in {} movies".format(pair[0], pair[1]))
Module: Lec16_imdb_sorted — Faster version using sorting¶
Code:
imdb_file = input("Enter the name of the IMDB file ==> ").strip()
count_list = []
for line in open(imdb_file, encoding = "ISO-8859-1"):
words = line.strip().split('|')
name = words[0].strip()
found = False
count_list.append(name)
count_list.sort()
index = 0
while index < len(count_list):
name = count_list[index]
count = count_list.count(name)
index += count
print("{} appeared in {} movies".format(name, count))
Module: Lec16_imdb_dict — Fastest version using dictionaries¶
Code:
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:
counts[name] += 1
else:
counts[name] = 1
names = sorted(counts)
limit = min(100, len(names))
for index in range(limit):
name = names[index]
print("{} appeared in {} movies".format(name, counts[name]))
Lecture 17¶
Module: Lec17_movie_actors_most_busy — Use sets to find unique movies.¶
Code:
'''
Short program to demonstrate using a set as a value within a dictionary.
For this example, we generate a movies dictionary where the keys are actor names
and the values are sets of movies with which they were associated. We then interrogate
the dictionary to find out who is the busiest actor in unique movies.
'''
imdb_file = input("Enter the name of the IMDB file ==> ").strip()
print(imdb_file)
'''
Generate the first dictionary by parsing the lines of the input file. Take
the actors name as the key and add the movie name into the set of movies
that the actor was associated with.
'''
movies = dict()
for line in open(imdb_file, encoding = "ISO-8859-1"):
words = line.strip().split('|')
name = words[0].strip()
movie = words[1].strip()
if name in movies:
movies[name].add(movie)
else:
movies[name] = set()
movies[name].add(movie)
'''
Now go through the dictionary and see how many actors appeared in only one
unique movie and which actor was busiest based on associations with unique
movies.
'''
singlets = 0
most = 0
for name in movies:
movie_ct = len(movies[name])
if movie_ct == 1:
singlets += 1
if movie_ct > most:
most = movie_ct
person = name
print("{} appears most often: {} times".format(person, most))
print("{} people appear once".format(singlets))
Module: Lec17_movie_actors_appearances — Demonstrate conversion between dictionaries¶
Code:
'''
Short program to demonstrate converting from one dictionary to another. For this
example, we start bt generating a movies dictionary where the keys are actor names
and the values are sets of movies with which they were associated. We turn that
into a second dictionary of occurrence frequency where the keys are a number
and the values are a list of the actors that have appeared in that number of movies
'''
imdb_file = input("Enter the name of the IMDB file ==> ").strip()
print(imdb_file)
'''
Generate the first dictionary by parsing the lines of the input file. Take
the actors name as the key and add the movie name into the set of movies
that the actor was associated with.
'''
movies = dict()
for line in open(imdb_file, encoding = "ISO-8859-1"):
words = line.strip().split('|')
name = words[0].strip()
movie = words[1].strip()
if name in movies:
movies[name].add(movie)
else:
movies[name] = set()
movies[name].add(movie)
'''
Now cycle through the movies dictionary to get the data for a new dictionary. This
time, for every actor, we calculate how many movies they were associated with by
taking the length of the set indicated by movies[name]. This length becomes a
key in the actors dictionary where everyone who is associated with length number of
movies is stored in a list.
'''
actors = dict()
for name in movies:
movie_ct = len(movies[name])
if movie_ct not in actors:
actors[movie_ct] = []
actors[movie_ct].append(name)
else:
actors[movie_ct].append(name)
'''
Sort the actors dictionary from highest (most number of movies) to lowest
(least number of movies). Print out the top 25 actors by number of movies
they are associated with.
'''
keys = sorted(actors, reverse=True)
i = 0
count = 0
while count < 25 and i < len(keys):
print(keys[i], actors[keys[i]])
count += len(actors[keys[i]])
i += 1
Lecture 18¶
Module: Lec18_point_class — A simple point class developed in lecture¶
Code:
from math import sqrt
'''
This module comntains a simple example of a Point2d class developed
during lecture
'''
class Point2d(object):
'''
Implement a point class
'''
def __init__( self, x0=0, y0=0):
'''
Initialization
'''
self.x = x0
self.y = y0
def __add__(self,other):
'''
Add two points
'''
return Point2d(self.x + other.x, self.y+other.y)
def magnitude(self):
'''
Distance from the origin
'''
return sqrt(self.x**2 + self.y**2)
def dist(self, o):
'''
Distance between 2 points
'''
return sqrt( (self.x-o.x)**2 + (self.y-o.y)**2 )
if __name__ == "__main__":
p = Point2d(0,4)
q = Point2d(5,10)
Point2d.__add__(p,q)
leng = Point2d.magnitude(q)
print("Magnitude {:.2f}".format( leng ))
print("Distance is {:.2f}".format( Point2d.dist(p,q)))
Module: Lec18_time — A simple time class using seconds since midnight¶
Code:
"""
Class for storing time. Time is maintained as seconds since midnight
"""
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)
Module: lec18_time_military_list — Code developed in class using a list to store H:M:S¶
Code:
"""
Class for storing time. Time is reported on a military (24 hour) clock. We
use a list to store hours minutes and seconds as list[0], list[1] and list[2]
explicitly
"""
class Time(object):
def __init__(self, hr=0, minute=0, sec=0):
self.time = [hr, minute, sec]
def convert(self):
pass
def __str__(self):
return "{:02d}:{:02d}:{:02d}".format(self.time[0],self.time[1],self.time[2])
def __add__(self, other):
new_hrs = self.time[0] + other.time[0]
new_mins = self.time[1] + other.time[1]
new_secs = self.time[2] + other.time[2]
add_minutes = new_secs // 60
new_secs = new_secs % 60
new_mins += add_minutes
add_hours = new_mins // 60
new_mins = new_mins % 60
new_hrs += add_hours
new_hrs = new_hrs % 24
return Time(new_hrs, new_mins, new_secs)
def __sub__(self, other):
seconds = self.time[2] + 60 * self.time[1] + 60*60*self.time[0]
other_seconds = other.time[2] + 60 * other.time[1] + 60*60*other.time[0]
new_seconds = max(0, seconds-other_seconds)
new_hrs = new_seconds // 3600
new_seconds = new_seconds % 3600
new_mins = new_seconds // 60
new_seconds = new_seconds % 60
return Time(new_hrs, new_mins, new_seconds)
if __name__ == '__main__':
t1 = Time()
print(str(t1))
t2 = Time(10, 29, 37)
print(str(t2))
t3 = Time(23, 59, 59)
print(str(t3))
print("{} + {} = {}".format(t3, t3, t3 + t3))
print("{} - {} = {}".format(t1, t2, t1 - t2))
print("{} - {} = {}".format(t2, t1, t2 - t1))
print("{} - {} = {}".format(t2, t3, t2 - t3))
print("{} - {} = {}".format(t3, t2, t3 - t2))
Module: lec18_time_military_list_better_sub — Same as previous with better subtraction¶
Code:
"""
Class for storing time. Time is reported on a military (24 hour) clock. We
use a list to store hours minutes and seconds as list[0], list[1] and list[2]
explicitly
"""
class Time(object):
def __init__(self, hr=0, minute=0, sec=0):
self.time = [hr, minute, sec]
def convert(self):
pass
def __str__(self):
return "{:02d}:{:02d}:{:02d}".format(self.time[0],self.time[1],self.time[2])
def __add__(self, other):
new_hrs = self.time[0] + other.time[0]
new_mins = self.time[1] + other.time[1]
new_secs = self.time[2] + other.time[2]
add_minutes = new_secs // 60
new_secs = new_secs % 60
new_mins += add_minutes
add_hours = new_mins // 60
new_mins = new_mins % 60
new_hrs += add_hours
new_hrs = new_hrs % 24
return Time(new_hrs, new_mins, new_secs)
def __sub__(self, other):
seconds = self.time[2] + 60 * self.time[1] + 60*60*self.time[0]
other_seconds = other.time[2] + 60 * other.time[1] + 60*60*other.time[0]
new_seconds = seconds-other_seconds
# if the subtraction makes us go negative, then add 24 hours to
# make it positive
if new_seconds < 0:
new_seconds += 3600 * 24
new_hrs = new_seconds // 3600
new_seconds = new_seconds % 3600
new_mins = new_seconds // 60
new_seconds = new_seconds % 60
return Time(new_hrs, new_mins, new_seconds)
if __name__ == '__main__':
t1 = Time()
print(str(t1))
t2 = Time(10, 29, 37)
print(str(t2))
t3 = Time(23, 59, 59)
print(str(t3))
print("{} + {} = {}".format(t3, t3, t3 + t3))
print("{} - {} = {}".format(t1, t2, t1 - t2))
print("{} - {} = {}".format(t2, t1, t2 - t1))
print("{} - {} = {}".format(t2, t3, t2 - t3))
print("{} - {} = {}".format(t3, t2, t3 - t2))
Lecture 19¶
Module: Restaurant — A start at the Restaurant class developed during lecture¶
Code:
'''
Lecture 19:
Implementation of a Restaurant class to represent restaurant data from
Yelp, which we originally worked with in Lab 5.
'''
from Lec18_point_class import Point2d
class Restaurant(object):
def __init__(self, name, lat, lon, address, url, category, scores):
'''
Initialize an object, including a name string, two floats to
store the latitude and longitude, a list of strings to
represent each line of an address, a string representing the
url, a string representing the category of restaurant, and a
list of scores.
'''
self.name = name
self.loc = Point2d(float(lon), float(lat))
self.address = address
self.url = url
self.category = category
self.reviews = scores
def __str__(self):
'''
Format the information about the restaurant as a multi-line string.
Rather than outputing the whole list of reviews, the average review
is output.
'''
s = ' Name: ' + self.name + '\n'
s += ' Lat/Long: ' + str(self.loc) + '\n'
s += ' Address: ' + self.address[0] + '\n'
for i in range(1,len(self.address)):
s += ' ' + self.address[i] + '\n'
s += ' Category: ' + self.category + '\n'
# s += 'Avg Review: {:.2f}'.format( self.average_review() ) + '\n'
return s
def is_in_city(self, city_name):
'''
Return True iff the restaurant is in the given city. This is
realized by testing the beginning of the last-line of the
address (a list), up until the ,
'''
my_city = self.address[-1].split(',')[0].strip()
return city_name == my_city
def average_review(self):
'''
Calculate and return the average rating. Return a -1 if there
are none.
'''
if len(self.reviews) == 0:
return -1
else:
return sum(self.reviews) / len(self.reviews)
def min_review(self):
'''
Return the minimum review, and -1 if there are no reviews
'''
pass
def max_review(self):
'''
Return the maximum review, and -1 if there are no reviews
'''
pass
def latitude(self):
'''
Return the latitude stored in the Point2d object
'''
return self.loc.y
def longitude(self):
'''
Return the longitude stored in the Point2d object
'''
return self.loc.x
if __name__ == "__main__":
"""
This is relatively minimal testing code for the Restaurant class.
Observe that when you import the Restaurant into the lecture 19
example programs, this code is not run.
"""
n = "Uncle Ricky's Bagel Heaven"
lat = 42.73
lon = -73.69
address = [ '1809 5th Ave', 'Troy, NY 12180']
url = "http://www.yelp.com/biz/uncle-rickys-bagel-heaven-troy"
rest_type = 'Bagels'
reviews = [ 5, 3, 5, 4, 3, 5, 4 ]
rest1 = Restaurant( n, lat, lon, address, url, rest_type, reviews )
n = "No Longer In Business"
lat = 42.74
lon = -73.7
address = [ '123 Nowhere Street', 'Troy, NY 12180']
url = "http://www.not_a_valid_url.biz/snafu"
rest_type = 'Concrete'
reviews = [ ]
rest2 = Restaurant( n, lat, lon, address, url, rest_type, reviews )
print("First restaurant:")
print("Name:", rest1.name)
print("Latitude:", rest1.latitude() )
print("Longitude:", rest1.longitude() )
print("Min review:", rest1.min_review() )
print("Max review:", rest1.max_review() )
print("\nSecond restaurant:")
print("Name:", rest2.name)
print("Latitude:", rest2.latitude() )
print("Longitude:", rest2.longitude() )
print("Min review:", rest2.min_review() )
print("Max review:", rest2.max_review() )
Lecture 20¶
Module: lec20_two_smallest_west_hall — Two versions of the two smallest code with timing¶
Code:
import random
import time
def index_two_v1( values ):
# O(N)
if values[1] < values[0]: # O(1)
lowest = values[1]
low = values[0]
index_lowest = 1
index_low = 0
else:
lowest = values[0]
low = values[1]
index_lowest = 0
index_low = 1
for i in range(2, len(values)): # N times the time of the inner part
if values[i] < lowest:
low = lowest
index_low = index_lowest
lowest = values[i]
index_lowest = i
elif values[i] < low:
low = values[i]
index_low = i
return index_lowest, index_low
def index_two_v2( values ):
# Generate a dictionary with values as keys and
# a list of indices as values
val_dict = dict()
for index in range(len(values)): # O(N)
if not values[index] in val_dict:
val_dict[values[index]] = []
val_dict[values[index]].append(index)
# sort the keys
sorted_keys = sorted(val_dict) #O(N log N)
# pick out the indices of the smallest keys
if len(val_dict[sorted_keys[0]]) > 1:
return val_dict[sorted_keys[0]][0], val_dict[sorted_keys[0]][1]
else:
return val_dict[sorted_keys[0]][0], val_dict[sorted_keys[1]][0]
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))
Module: lec20_two_smallest — An alternate version from a previous semester¶
Code:
import random
import time
def index_two_v1( values ):
if len(values) == 0:
return
if len(values) == 1:
return 0, 0
if values[0] > values[1]:
least = 1
next_least = 0
else:
least = 0
next_least = 1
for index in range(2, len(values)):
if values[index] < values[least]:
next_least = least
least = index
elif values[index] < values[next_least]:
next_least = index
return least, next_least
def index_two_v2( 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
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))
Lecture 21¶
Module: lec21_sorts — Multiple sorting routines¶
Code:
'''
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)):
j = i-1
x = v[i]
while j >= 0 and x < v[j]:
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 = []
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:])
L.extend(L2[i2:])
return L
def merge_sort(v):
'''
Implementation of the merge sort algorithm.
'''
if len(v) <= 1:
return
lists = []
for item in v:
lists.append([item])
i = 0
while i < len(lists)-1:
new_list = merge(lists[i], lists[i+1])
lists.append(new_list)
i += 2
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)
Module: lec21_test_sort — Multiple sorting routines¶
Code:
'''
Testing code for Computer Science 1, Lecture 21 on sorting. This
assumes that the sort functions are all in file lec21_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 lec21_sorts as sorts
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".format(t1-t0))
# print("Is correct?", v==known_v
print()
def generate_local_perm(v,max_shift):
'''
This function modifies a list so values are only a small amount
out of order. Each one 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(input("Enter the number of values ==> "))
print("----------")
print("Running on {:d} values".format(n))
print("----------")
v = list(range(n))
v1 = v[:]
random.shuffle(v1)
# generate_local_perm(v1, 10)
v2 = v1[:]
v3 = v1[:]
v4 = v1[:]
run_and_time("merge sort", sorts.merge_sort, v3, v ) # passing functions as an arg to a fcn
run_and_time("python sort", list.sort, v4, v )
run_and_time("selection sort", sorts.sel_sort, v1, v )
run_and_time("insertion sort", sorts.ins_sort, v2, v )
Lecture 22¶
Lecture 23¶
Module: lec23_flatten_list — Recursive routine to unflatten a list¶
Code:
def flatten(L):
result = []
for x in L:
if type(x) == list:
result.extend( flatten(x) )
else:
result.append(x)
return result
def flatten2(L):
if type(L) != list:
return [L]
else:
result = []
for x in L:
result.extend( flatten2(x) )
return result
if __name__ == "__main__":
v = [[1,5], 6, [[2]], [3, [7, 8, [9,10], [11,12] ]]]
print(v)
print(flatten(v))
print(flatten2(v))
'''
print(flatten2(2))
print(flatten(2))
'''
Module: lec23_merge_sort_rec — Recursive and iterative merge sort¶
Code:
"""
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.
"""
if len(L) == 1:
return L
length = len(L)
mid = length // 2
left = merge_sort_recursive(L[:mid])
right = merge_sort_recursive(L[mid:])
return merge(left, right)
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 )
Module: lec23_sierpinksi — Recursive fractal¶
Code:
"""
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()