Practice Final Exam Solutions
Exam Solutions
Problem 1 Lists (20 Points)
The company DataScrambler.com has hired you to write a function called interleave_lists, which has the following header: def interleave_lists(list1, list2).
The interleave_lists function is passed two lists of integers (list1 and list2), and should return a new list of integers that interleaves the elements (numbers) from list1 and list2. The result of interleaving list1 and list2 is simply a list of integers that contains (in order) alternating elements (numbers) from list1 and list2 (starting with a number from list1). If one of the lists passed in to the function is longer than the other, then any remaining numbers from the longer list which are not already included in the interleaved list are simply added (in order) to the end of the result.
For the examples we give below, say we have the following three lists:
first = [1, 2, 3, 4, 5, 6, 7]
second = [10, 20, 30, 40]
third = [100]
Calling: interleave_lists(first, second)
should return this list: [1, 10, 2, 20, 3, 30, 4, 40, 5, 6, 7]
Note that the interleaved lists that is returned starts with the value 1 from the list first, then 10 from the list second, then 2 from the list first, then 20 from the list second, and so on. Since the list first is longer than the list second, after the values 1, 2, 3 and 4 from the list first have been interleaved with the values 10, 20, 30 and 40 from the list second, the remaining elements of the lists first (5, 6, 7) are simply added to the end of the resulting interleaved list.
Here are two additional examples of what should be returned from your interleave_list function: Calling: interleave_lists(second, third)
should return this list: [10, 100, 20, 30, 40]
And calling: interleave_lists(third, first)
should return this list: [100, 1, 2, 3, 4, 5, 6, 7]
If one of the lists passed into your function is an “empty” list ([]), you should still perform an interleaving, but the empty list will contribute nothing to the result. If you are passed two empty lists, your function should return an empty list.
Write your interleave_lists function below. Note that for this problem you don't need to write a complete program – you just need to implement the interleave_lists function. Feel free to define any additional functions that you would like to help you solve this problem.
# Starter code
def interleave_lists(list1, list2):
# Solution code
def interleave_lists(list1, list2):
result = []
# Determine which list is shorter
min_length = min(len(list1), len(list2))
# Loop over the length of shorter list, appending elements from list1 and list2
# on to the result list in an interleaved pattern.
for i in range(min_length):
result.append(list1[i])
result.append(list2[i])
# Create the remainder by slicing the elements from the longer list that were
# not added to the result
if len(list1) > len(list2):
remainder = list1[min_length:]
else:
remainder = list2[min_length:]
# Add the remaining elements from the longer list to the result
result.extend(remainder)
return result
Problem 2 Strings (20 Points)
Computers have gotten very good at correcting our writing mistakes. One form of such correction is making sure that sentences we write are properly capitalized. For example, given a string that contains some text, we want to make sure that the first letter of every sentence is capitalized and all other letters are lower case.
For example, consider the string: 'almost done with finals? yah!!! ** so HAPPY. have a GoOd BrEaK!'
The properly capitalized version of this string would be: 'Almost done with finals? Yah!!! ** So happy. Have a good break!'
To implement this functionality, your job is to write a function fix_capitalization that takes a string name str as its argument and returns a new string which is the properly capitalized version of the original string passed in.
The rules for proper capitalization are as follows:
- The first letter of the string is capitalized (upper case).
- The first letter after each end-of-sentence punctuation mark should be capitalized. For our purposes, we'll consider period ('.'), exclamation point ('!') and question mark ('?') as the only three characters that can be used as punctuation to end sentences, so you should not consider any other end-of-sentence punctuation.
- All letters that are not capitalized (according to the rules above) should be lower case.
- Characters which are not letters should remain unchanged.
For example, if you call:
fix_capitalization("STANFORD ROCKS!!")
your function should return the string: "Stanford rocks!!".
Similarly, if you call:
fix_capitalization("*almost done!! * that's AwESoME?! yes, IT IS.")
your function should return: "*Almost done!! * That's awesome?! Yes, it is."
As you can see above, we make the first letter at the beginning of the string or after a punctuation mark upper case even when there are (an arbitrary number of) intervening non-letter characters (such as "almost done!!" and " that's" in the second example above, which are properly capitalized as "Almost done!!" and " That's", respectively, regardless of the intervening non-letter characters).
In writing your solution, you should keep in mind that you do not need to write a complete program. All you need is the definition of the function fix_capitalization that returns the desired result. You may write any additional functions that may help you solve this problem, but you are not required to decompose your solution. Write your solution to this problem on the next page.
# Starter code
def fix_capitalization(str):
# Solution code
def fix_capitalization(str):
# Start with an empty result string that we will build up.
result = ''
# next_cap keeps track of whether next letter in input string should
# be capitalized. Note that the first letter must be capitalized.
next_cap = True
for i in range(len(str)):
ch = str[i]
# If we have a letter, check to see if it should be capitalized or not
if ch.isalpha():
if next_cap:
ch = ch.upper()
next_cap = False
else:
ch = ch.lower()
# If we didn't have letter, see if it's end-of-sentence punctuation
# mark (in which case we should capitalize the next letter).
elif ch == '.' or ch == '!' or ch == '?':
next_cap = True
# Add the character to the result we are building up
result += ch
return result
Problem 3 Graphics (25 Points)
To get more artistic with your programming, you decide to write a function called draw_sketch that is passed a graphics canvas and draws a simple line sketch “artwork” on that canvas. Your function should first asking the user (on the console) for the “Number of lines in the drawing:”. You can assume the user will always enter a positive integer value. You should then create a drawing on the canvas which is produced by drawing lines with randomly determined starting and ending points, where the ending point of each line in the drawing becomes the starting point for the subsequent line, so all the lines in the drawing are connected. The starting/ending points for each line can appear anywhere on the canvas, which has size (in pixels) specified by the constants CANVAS_WIDTH and CANVAS_HEIGHT. Figure 1 below shows an example of an output of this program where the user asked for 5 lines in the drawing.
Note that there is also a colored circle (both the fill and outline of the circle are colored) centered at the end point of each line in the drawing. This is to add more artistic flair to the drawing. The colors used for the circles are determined by the constant COLORS, which is a list of color names (strings), as shown below.
COLORS = ['red', 'orange', 'yellow', 'green', 'blue', 'violet']
The colors for the circles you draw should cycle through the COLORS list, starting with the color red for the starting point of the first line, then the color orange for the starting point of the second line (which is also the ending point of the first line), and so on. After drawing a circle that is violet, the next circle drawn should be red again, since the colors are being cycled through. Each colored circle should appear underneath the two lines that are connected at that point in the drawing, though it is fine if the circle appears in front of lines that came earlier in the drawing. The radius (in pixels) of the circle is determined by the constant RADIUS.
Two additional program runs are shown in Figure 2 and Figure 3 below, which have 8 and 12 lines, respectively, to show the cycling of colors in the circles. Note that while the endpoints of all the lines should appear on the graphics canvas, it is fine if the circles drawn get clipped if they are too close to the edge of the canvas.
Write your function draw_sketch below. Note that for this problem you can assume that there is a main function that has already created a canvas with the dimensions CANVAS_WIDTH and CANVAS_HEIGHT, and is passing that canvas to your draw_sketch function. So, you just need to implement the draw_sketch function. Feel free to define any additional functions that you would like to help you solve this problem.
# Starter code
import tkinter
import random
CANVAS_WIDTH = 500 # Width of drawing canvas in pixels
CANVAS_HEIGHT = 300 # Height of drawing canvas in pixels
COLORS = ['red', 'orange', 'yellow', 'green', 'blue', 'violet']
RADIUS = 5
def main():
canvas = make_canvas(CANVAS_WIDTH, CANVAS_HEIGHT) # Assume make_canvas exists
draw_sketch(canvas)
tkinter.mainloop()
# You should implement the draw_sketch function below
def draw_sketch(canvas):
# Solution code
def draw_sketch(canvas):
num_colors = len(COLORS)
num_lines = int(input('Number of lines in drawing: '))
# Determine starting point for first line
start_x = random.randint(0, CANVAS_WIDTH)
start_y = random.randint(0, CANVAS_HEIGHT)
centered_circle(canvas, start_x, start_y, COLORS[0])
# Draw the lines
for i in range(num_lines):
end_x = random.randint(0, CANVAS_WIDTH)
end_y = random.randint(0, CANVAS_HEIGHT)
# Use i + 1 to determine color for circle since starting point
# of first line already used the first color
centered_circle(canvas, end_x, end_y, COLORS[(i + 1) % num_colors])
canvas.create_line(start_x, start_y, end_x, end_y)
# The ending point of this line becomes starting point of next line
start_x = end_x
start_y = end_y
# Draws a circle centered at point (x, y) with the given color
def centered_circle(canvas, x, y, color):
canvas.create_oval(x - RADIUS, y - RADIUS, x + RADIUS, y + RADIUS,
outline=color, fill=color)
Problem 4 File Processing (25 Points)
You are given a text file containing information about a group of people’s best friends. The file is structured so that each line contains the name of a particular person as well as the name of their best friend. You can assume that people’s names are unique (e.g., anytime a name like “Pat” appears, it is always referring the same person named “Pat”). And to keep things simple, you can also assume that each name is just a single token representing the first name of the person. Also, each person has at most one best friend. A sample data file might look as follows:
data.txt
Bob Alice
Chelsea Bob
Eduardo Don
Alice Chelsea
The file above indicates that Bob’s best friend is Alice, Chelsea’s best friend is Bob, etc. Note that not everyone is required to have a best friend (for example, Eduardo’s best friend is Don, but Don doesn’t have a best friend in the file). And best friends are not necessarily reciprocal (Bob’s best friend is Alice, but Alice’s best friend is not Bob).
You think it would be interesting to determine if there is a “best friend loop” in such data. A “best friend loop” occurs when you start at some person, then find their best friend, then find that person’s best friend, etc. until you get back to the starting person. For example, the data above contains a “best friend loop” since we could start with Bob, then link to Alice (Bob’s best friend), then link to Chelsea (Alice’s best friend), and then link back to Bob (Chelsea’s best friend).
Your job is to write a function contains_loop that is passed the name of a file (string) containing the best friend data and determines if the data contains a “best friend loop”. Your function should return True if the data in the file in contains at least one “best friend loop” and False otherwise (i.e., return False when there are no best friend loops).
Hint: consider reading the file into a dictionary (where the key is a person’s name and the value is the name of that person’s best friend) and use that dictionary to help you determine if a loop exists.
To provide another example, the file noloops.txt below does not contain any “best friend loops”, so your function should return False if the filename "noloops.txt" were passed to it.
noloops.txt
Eric Fran
Fran Helen
Gary Helen
And, it is fine for someone to be their own best friend, which would constitute a “best friend loop”. This is shown in the file loveyourself.txt below (the “best friend loop” is simply starting with Pat and then linking back to Pat). So, your function should return True in this case.
loveyourself.txt
Pat Pat
# Starter code
def contains_loop(filename):
# Solution code
def contains_loop(filename):
# Use a dictionary to keep track of each person's best friend
bf_dict = {}
# Read the file into a dictionary where names are keys, best friends are values
with open(filename, 'r') as file:
for line in file:
line = line.strip()
names = line.split()
bf_dict[names[0]] = names[1]
# For each name in the bf_dict, see if we can find a loop starting at that name
for name in bf_dict.keys():
# Store path from a given person to determine if we loop back into it
path = []
# Loop until we get to a dead-end (or find loop)
while name in bf_dict:
path.append(name) # Add the current name to path of names
name = bf_dict[name] # Look up best friend as the next person in path
# If we reach a name we've seen before in this path, we found a loop
if name in path:
return True
# Will only return false if we've found no loops after trying to
# find one starting from every name in the dictionary.
return False
Problem 5 Using Data Structures (30 Points)
Realizing that the US National Debt is now over $30 trillion, you decide to create the notion of “Big Numbers”, allowing you to represent (and add) arbritrarily large positive integer values. You are going to represent such a large number as a list of digits. For example, the number 16,381,245 could be represented using a list where each entry of the list is a single digit, as follows:
To allow you to more easily add such numbers, it would be useful to store the digits of the “Big Number” backwards, so that the ones digit is always in position 0, the tens digit is always in position 1, the hundreds digit is always in position 2, etc. So, the list representing 16,381,245 would actually look as follows (with indexes shown below the list):
The list should only have as many elements as the number of digits in the number it represents. So, if we had a variable (list) named bignum1 representing the number 9,564 and wanted to add to it another variable (list) named bignum2 representing 867, we should (like you did in first grade) add the ones digits (which are respectively both at index 0), then add the tens digits (at index 1), etc. to get the resulting sum 10,431, shown in the variable result below:
Note that the resulting sum can have more digits than either of the original numbers added together.
Your job is to implement a function named add_bignums that is passed two “Big Numbers” (i.e., lists of digits in backwards order, as discussed above) and returns a new list representing the “Big Number” (i.e. list of digits in backwards order) that represents the sum of the two numbers passed in, using the algorithm described above to add the numbers digit-by-digit, starting at the ones digit). Your function should not modify the two lists that are passed into it.
For example, say your function is called with lists (as defined above) representing the numbers 9,564 and 867 as “Big Numbers”, respectively:
add_bignums([4, 6, 5, 9], [7, 6, 8])
then your function should return the list:
[1, 3, 4, 0, 1]
which would represent the value 10,431 as a “Big Number” (i.e., list of digits in backwards order).
In writing your solution, you should keep in mind that you do not need to write a complete program. All you need is the definition of the function add_bignums that returns the desired result. You may write any additional functions that may help you solve this problem, but you are not required to decompose your solution. Write your solution to this problem on the next page.
# Starter code
def add_bignums(bignum1, bignum2):
#Solution code
def add_bignums(bignum1, bignum2):
"""
Add two "bignumbers" together, and returns a new "bignumber" (list)
representing the sum.
"""
result = []
# Keep track of "carry" when two digits added
carry = 0
# Determine which bignumber has more digits
max_size = max(len(bignum1), len(bignum2))
# Loop through digits/columns of the bignumbers
for i in range(max_size):
# Add digits in current column of bignumbers (including carry)
sum = safe_get_digit(bignum1, i) + safe_get_digit(bignum2, i) + carry
# Determine if there is a carry to the next column
if sum >= 10:
carry = 1
sum = sum - 10
else:
carry = 0
# Add new digit to end of list, since bignum is stored in reverse order
result.append(sum)
# Check for a carry on the last digit/column we added
if carry == 1:
result.append(carry)
return result
# Returns digit at given index in bignum if it exists, returns 0 otherwise
def safe_get_digit(bignum, index):
if index >= len(bignum):
return 0
else:
return bignum[index]
Problem 6 Full Program (30 Points)
Interestingly, people tend to see patterns in data, even when the data may be random. For example, say you are given a file that contains a series of positive integers, one per line. You want to determine when chains appear. A chain is a sequence of numbers that consecutively increase by one. More concretely, say we had the following sequence of 10 numbers:
5, 3, 4, 5, 1, 4, 5, 3, 6
Here, we would have two "chains" in the data (the chains are underlined in the sequence above). To reiterate, a chain is just a sequence of consecutive numbers where each subsequent number is greater than the previous number by one.
We want to write a Python that reads a file of integers (the filename will be specified by the constant FILENAME), containing one integer per line and guaranteed to contain at least one number. The program should print out the length of the longest chain that appears in the file. For clarification, we show three different data files (data1.txt, data2.txt, and data3.txt) below. We highlight the “chains” in each file (with red) to show the reason for the final result in each case. The file will not have this highlighting – it just contains the integers. Your program should just output the length of the longest chain in the file as shown below for each file. If there are no chains found in the data, your program should report "No chains found."
# Starter code
FILENAME = 'datafile.txt'
def main():
if __name__ == '__main__':
main()
# Solution code
FILENAME = 'datafile.txt'
def main():
prior_value = -1 # Initially, have no prior value
max_chain = 0 # Keep track of maximum chain size found
current_chain = 0 # Keep track of size of current chain we are in
with open(FILENAME, 'r') as file:
for line in file:
line = line.strip()
value = int(line)
# Check to see if we continue in a chain
if value == (prior_value + 1):
# If so, increment current chain's length
current_chain += 1
else:
# If not, check to see if the chain we might have been in
# is longer than the maximum chain we found previously
if current_chain > max_chain:
# Maximum chain size is current_chain + 1 since we need to
# account for the very first number in the chain, which was
# not counted in the length of the current chain
max_chain = current_chain + 1
# Note: we are no longer in a chain, so reset current_chain to 0
current_chain = 0
# Value we just read becomes our "prior" value
prior_value = value
# After reading file, need to do final check to see if our current chain was
# longer than maximum (since we might have been in a chain when the file ended)
if current_chain > max_chain:
max_chain = current_chain + 1
# Print out length of longest chain, if we found one
if max_chain > 0:
print("Longest chain: " + str(max_chain))
else:
print("No chains found")
if __name__ == '__main__':
main()
Problem 7 Classes (30 Points)
We want to build a class in Python to handle a box office ticket management system that keeps track of tickets sold for shows at the Bing Concert Hall (referred to as just “Bing” here). For the purposes of this problem, we will assume that Bing has 500 seats that are numbered 1 to 500. Thus, seats are simply designated by integers from 1 to 500. We want to design a class, where we can create an object that allows a user to:
- Determine if there are still tickets available for sale from the box office.
- Get (purchase) the next available ticket from the box office, if there are tickets available.
- Return a previously purchased ticket to the box office (which would make it available for someone else to potentially get/buy in the future).
With this idea in mind, we want to define a class called TicketSystem which has a constructor as well as three methods (“method” is just another name for a function that is in a class), defined as follows:
- has_tickets() – this method returns True if there are tickets still available for purchase, which means that either there are still unsold seats or there are tickets which have been returned and not yet sold again (or both). If no tickets are available, the method returns False .
- next_ticket() – if there are tickets available, this method returns an integer indicating the seat designation of the next available ticket. If no tickets are available, the method returns -1 since there are no valid available seats.
- return_ticket(ticket) – this method is passed a valid (previously purchased) ticket (i.e., integer designating a seat). This ticket is considered returned to the box office and is once again available for sale (i.e., some future call to next_ticket could return this ticket). This method does not need to do error checking on the ticket passed in – you can assume that the ticket will always be a valid number for a seat that was previously sold.
Note that the box office chooses to sell tickets in a particular order, as follows:
- If any tickets for seats have been returned, sell those tickets first in the order in which they were returned, before selling any other available seats.
- If there are no previously sold tickets that have been returned to sell again, then sell seats in order by section number (first) and by seat number (second). So, the first ticket sold would be 1, followed by 2, then 3, etc. Thus, 500 would be the last ticket to be sold (not counting returned tickets). As an example, say we sell tickets 1, 2, 3, and 4. Then, ticket 2 is returned, and then ticket 1 is returned. The next ticket we will sell will be 2, followed by 1. After that (assuming no other ticket has been returned), we would then sell ticket 5 next.
We give you the outline of the class TicketSystem and the methods specified in the class below. Your task is to write the implementation (body) of each of the methods in the class TicketSystem. Write your answer below. Note that you do not have to write a program that creates objects based on your class. We just want you to define the methods in the class.
# Starter Code
# Number of seats available in ticketing system
NUM_SEATS = 500
class TicketSystem:
def __init__(self):
def has_ticket(self):
def next_ticket(self):
def return_ticket(self, ticket):
# Solution Code
# Number of seats available in ticketing system
NUM_SEATS = 500
class TicketSystem:
# Constructor
def __init__(self):
# Keep track of next ticket (seat number)
self.next_seat = 1
# Keep track of returned tickets in a list
self.returned_tickets = []
def has_ticket(self):
# We have tickets to sell if either there are returned tickets
# or we have not yet sold all the seats (tickets)
return self.returned_tickets or self.next_seat <= NUM_SEATS
def next_ticket(self):
# First check for returned tickets to sell
if self.returned_tickets:
# Sell the first returned ticket in the list
return self.returned_tickets.pop(0)
elif self.next_seat <= NUM_SEATS:
# If we still have seats to sell, get the seat number for next ticket
ticket = self.next_seat
# Update the next seat to be sold
self.next_seat += 1
return ticket
else:
# We should only get to this case if there are no returned tickets
# and no seats left to sell, in which case there are no tickets.
return -1
def return_ticket(self, ticket):
# Add the returned ticket to the list of returned tickets
self.returned_tickets.append(ticket)