CS 106A June 3rd, 2022
1. Lists (20 Points)
One way to encode a message comprised of a list of words (strings) is to create a new list of strings, where the strings in the new list are a scrambled version of the characters from the original message. If this "scrambling" is done according to a set rule, then the message can be "unscambled" by someone who knows the rule, but appears to just be random characters to people who don't know the rule.
You are to write a function scramble, which is passed a list of strings, and creates such an encoding scheme. Your function should return a new list of strings, where the strings in this new list are created by taking one character from the same position in each of the strings in the original list. To be more precise, the first string in the returned list should be created by taking the first character from each string in the original list in order. The second string in the returned list should be created by taking the second character from each string in the original list in order (skipping any strings that don't have at least two charaters), and so on.
So if your function were passed the following list:
['This', 'is', 'a', 'big', 'test']
it should return the list below:
['Tiabt', 'hsie', 'igs', 'st']
Note that the first string in the returned list ('Tiabt') is generated by taking the first letter in each of the strings in the original list in order (i.e., T from 'This', i from 'is', a from 'a', b from 'big', and t from 'test'). The second string in the returned list ('hsie') is generated by taking the second letter in each of the strings (that have a second letter) in the original list in order (i.e., h from 'This', s from 'is', no character from 'a' because it doesn't have a second character, and e from 'test').
Hint: the number of strings in the returned list is the same as the length of the longest string in the original list passed in.
You can assume that the list passed into your function contains at least one string and that each string in that list contains at least one character. Here are a few more examples of what your function should return for different lists:
scramble(['abc', 'de', 'fghi']) should return: ['adf', 'beg', 'ch', 'i']
scramble(['one']) should return: ['o', 'n', 'e']
scramble(['1', '23', '456', '7890', '!']) should return: ['1247!', '358', '69', '0']
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 scramble 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.
# Starter Code
def scramble(str_list):
# Solution Code
def find_max_length(str_list):
# Returns length of longest string in list.
max_length = 0
for s in str_list:
length = len(s)
if length > max_length:
max_length = length
return max_length
def scramble(str_list):
# Determine maximum length of strings in list
max_length = find_max_length(str_list)
result = []
# Generate scrambled strings
for i in range(max_length):
str_result = ''
for s in str_list:
# Check to see if string s is long enough to have i-th character
if i < len(s):
str_result += s[i]
result.append(str_result)
return result
2. Strings (30 Points)
Having gotten tired of seeing so many hashtags on the internet, you decide to write a function that removes hashtags from a string. A hashtag is defined to be a sequence of characters, such that:
- The [first character]{.underline} in a hashtag is a #. (As a side note, the # character is often called a "hash" symbol, which is where the name hashtag comes from).
- The characters following the # must be alphabetic letters (upper or lower case) or digits. Note that whenever you see a # starting a hashtag you are guaranteed that there will always be [at least one]{.underline} valid letter or digit character following it. So, you will never see two hash symbols in a row, such as ##, since that would not have at least one valid letter or digit after the first # character
- A hashtag ends when it is followed by a character that is [neither a letter nor a digit]{.underline}.
Here are some examples of valid hashtags:
#happy
#FeelingRelieved
#2good
#abc123
Here's an example of four hashtags in one line (note that hashtags are not always separated by spaces):
#Awesome #Love,#Stanford#BeatCal
Your job is to write a function named remove_hashtags that is passed a string representing the original message we want to remove hashtags from, and returns a string which is the original string with all the hashtags (and only the hashtags) removed.
For example, if you call: remove_hashtags('This is great #cs106a') your function should return the string: 'This is great '
Note that there is a final space in the result string since the space before #cs106a in the original string should not be removed since it was not part of a hashtag.
Additional examples of what your method should return are given below:
remove_hashtags('#awesomeness!#happy.#cool') should return: '!.'
remove_hashtags('The #middle is okay') should return: 'The is okay' (Note: there are two spaces between 'The' and 'is' in the returned string above.)
remove_hashtags('More than #1 #hashtag here') should return: 'More than here' (Note: there are three spaces between 'than' and 'here' in the returned string above.)
remove_hashtags('So#many#hashtags#here') should return: 'So'
remove_hashtags('No hashtags') should return: 'No hashtags'
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 remove_hashtags 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.
# Starter Code
def remove_hashtags(message):
# Solution Code
def remove_hashtags(message):
result = ''
in_hashtag = False # Keep track of if we are in a hashtag.
for i in range(len(message)):
ch = message[i]
# Check if we are starting a hashtag
if ch == '#':
in_hashtag = True
# Otherwise, check if we were in a hashtag and it just ended
elif in_hashtag:
if not (ch.isalpha() or ch.isdigit()):
in_hashtag = False
# If we are not in a hashtag, then append the character to the result
if not in_hashtag:
result += ch
return result
3. Using data structures (25 Points)
As we talked about in class, a dictionary can be used to store a phonebook as a set of key/value pairs, where the key is the name of a person and the value is their phone number. For the purpose of this problem, we'll assume that both a person's name and their phone number are kept track of as strings (that way we won't run into any problems with storing dashes in phone numbers). You can assume that all phone numbers in this problem are 7-digit numbers in the standard form XXX-XXXX, so you don't need to do anything special with regard to determining if two numbers are the same.
We would like to write a function shares_phone that determines all the people that share a phone number in your phonebook with at least one other person. The function has the following header, where phonebook is a dictionary as described above:
def shares_phone(phonebook)
Your function should return a list containing the names of all the people who share a phone number with at least one other person in the phone book. If no one in the phone book shares a number with anyone else, you should return an empty list. For example, say you had the following phonebook:
phonebook1 = {
'Jamie Foxx': '725-6847',
'Jessica Alba': '867-5309',
'Harrison Ford': '725-6847',
'Alicia Keyes': '555-1234',
'Tommy Tutone': '867-5309',
'John Elway': '725-6847',
'Ben Stiller': '888-8888'
}
Calling your shares_phone function on phonebook1 above should return the following list:
['Jamie Foxx', 'Jessica Alba', 'Harrison Ford', 'Tommy Tutone', 'John Elway']
As mentioned previously, the list above only contains those people who have the same phone number (value) as at least one other person in the phonebook. For example, 'Jamie Foxx' is in the list because he has the same phone number as 'Harrison Ford' and 'John Elway'. [Each name should only appear once in the list]{.underline}. Note that your list may contain the names in [any]{.underline} order.
As another example, if you had the following phonebook:
phonebook2 = {
'Angela Merkel': '222-2222',
'Kofi Annan': '567-1212'
}
Then calling your shares_phone function on phonebook2 should return the empty list ([]) since no one in phonebook2 shares a phone number.
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 shares_phone 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.
# Starter Code
def shares_phone(phonebook):
# Solution Code
def shares_phone(phonebook):
result = []
# Loop through all the names (keys) in the phonebook
for key1 in phonebook:
# See if there is another person in phonebook with same number (value)
for key2 in phonebook:
# Check for different names with matching numbers
if key1 != key2 and phonebook[key1] == phonebook[key2]:
# Add name to the result list only if not already there
if key1 not in result:
result.append(key1)
return result
4. Nested structures (25 points)
The university registrar's office decides that it is time to rewrite the program for Axess (if only we could be so lucky). They decide to use a dictionary to keep track of the list of course that all students take in a given quarter. In this dictionary, the key is a student's university ID number (which is an integer) and the associated value is a list of strings containing the names of the courses the student is taking this quarter.
The dictionary (name enrollment) below illustrates the courses that five students are taking. For example, we can see that the student with ID number 3637 is taking CS106A, Math41, and Econ1 this quarter.
enrollment = {
3637: ['CS106A', 'Math41', 'Econ1'],
3822: ['SLE91', 'CS106A'],
4107: ['Math41', 'Psych1', 'Stat60', 'English100A'],
5095: ['English100A', 'CS106A', 'Psych1'],
3945: ['Econ1', 'CS106A', 'Math41', 'Psych1']
}
Based on this design, the registrar asks you to write a function named courses_larger_than that returns a list of all the courses that have greater than some number of students in them. The function has the following header:
def courses_larger_than(size, enrollment)
Your function is passed a size threshold (an integer) and a dictionary (of the form described above) of all the student course enrollments. Your function should return a [list of the names]{.underline} of all the courses that have [greater]{.underline} than size number of students in them. For example, if your function was called as follows: courses_larger_than(2, enrollment)
where enrollment is the dictionary defined above, then the function should return the follow list:
['CS106A', 'Math41', 'Psych1']
since those are the only courses that each have [more]{.underline} than 2 students. The names can be in any order in list returned, but [each course should only appear once in the list]{.underline}. Note that your function should [not]{.underline} modify the original dictionary of enrollments passed in.
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 courses_larger_than that returns the desired result. You may write any additional functions that may help you solve this problem. The starter code is provided below.
# Starter Code
def courses_larger_than(size, enrollment):
# Solution Code
def courses_larger_than(size, enrollment):
# Create a dictionary to keep track of how many students are in each course.
# Keys with be course names, values will be the number of students in course.
counts = {}
# Loop through all the students
for key in enrollment:
# Get list of courses that student is enrolled in
courses = enrollment[key]
# For each course the student is enrolled in, increment the count
# of the number of students in that class (or initialize count to 1).
for course in courses:
if course not in counts:
counts[course] = 1
else:
counts[course] += 1
# Create the result list to return
result = []
# Loop through all courses
for key in counts:
# If number of students in course is greater than size,
# add course name to the results list
if counts[key] > size:
result.append(key)
return result
5. Full Program (25 points)
We want to write a program that performs some calculations on a text file. Specifically, the program is given a file that contains a list of integers (one per line), which are separated into groups by either a '+' or '*' operator. An example of such a file (named data.txt) is shown below.
data.txt
10
23
1
+
6
2
*
7
+
14
4
5
+
3
*
2
2
2
*
Your program needs to process this file so that it will compute either the sum or product of each group of numbers separated by an operator, based on what operator comes at the end of the group of numbers. For example, in data.txt above, the first group of numbers includes: 10, 23, and 1. Since there is a '+' operator following this group of numbers, the numbers should all be added to produce the sum 34 (which is then printed to the console). The next group of numbers in the file is: 6 and 2, followed by a '*' operator. The '*' operator indicates that we should compute the product of the numbers in that group (namely, 6 * 2) giving us the value 12. The next group of numbers includes just a single 7 followed by a '+' operator. Here, we take the sum comprised simply of the number 7, which gives us the number 7. Similarly, if we had a single number to take the product of (such as the example of the fifth group of numbers in the data file above, which just contains a single 3 followed by a '*' operator), the result would simply be that number itself (i.e., 3, in this example). So, for the file data.txt above, your program should produce the following output:
34
12
7
23
3
8
You can assume that each line of the data file will contain either a single integer or a '+' or '*'. You can also assume that there will always be at least one integer in each group of numbers (i.e., you'll never have two operators (+' or '*') right after each other in the data file). Finally, you can assume that there will always be an operator after a group of numbers. In writing your program, the following constant is provided for you: DATAFILE = 'data.txt'
The name of the data file your program should process is given by the constant DATAFILE.
# Starter Code
DATAFILE = 'data.txt'
if __name__ == '__main__':
main()
# Solution Code
DATAFILE = 'data.txt'
# Computes and returns the product of all the numbers in num_list
def compute_product(num_list):
product = 1
for value in num_list:
product *= value
return product
def main():
# Keep track of the group of numbers that an operator will be applied to
num_list = []
with open(FILENAME, 'r') as file:
for line in file:
line = line.strip()
if line == '+': # Compute sum
print(sum(num_list))
num_list = [] # Reset list of numbers
elif line == '*': # Compute product
print(compute_product(num_list))
num_list = [] # Reset list of numbers
else:
value = int(line) # Must be integer since it's not operator
num_list.append(value) # Add number to list of numbers
if __name__ == '__main__':
main()
6. Graphics (35 points)
Your job is to write a write a function called draw_shapes that is passed a graphics canvas and the name of a text file containing a list of commands related to drawing rectangles and ovals. Your function should process the file and draw the shapes specified in the file on the graphics canvas. The input text file contains one command per line, where the valid commands in the text file are:
- rectangle width height This command defines a new rectangle shape. The width and height specified in the command line are simply two integers denoting the width and height of the rectangle in pixels, respectively. There are single spaces between rectangle, width, and height in the command text. After a "rectangle" command, all subsequent commands in the file refer to this same rectangle until the next shape command ("rectangle" or "oval") in the file. By default, a rectangle is black in color (and only an outline, not filled).
- oval width height This command defines a new oval shape. The width and height specified in the command line are simply two integers denoting the width and height of the bounding box of the oval in pixels, respectively. There are single spaces between oval, width, and height in the command text. After an "oval" command, all subsequent commands in the file refer to this same oval until the next shape command ("rectangle" or "oval") in the file. By default, an oval is black in color.
- red This command specifies that the shape ("rectangle" or "oval") it refers to (i.e., the most recent shape referred to in the file) should be the color red (and still only an outline, not filled).
- draw x y This command specifies that the shape ("rectangle" or "oval") it refers to should be drawn on the graphics canvas with its upper left-hand corner at the specified (x, y) location. The x and y specified in the command line are simply two integers denoting the x and y location that the shape should be drawn. There are single spaces between draw, x, and y in the command text.
You can assume that each shape defined will be drawn [at most once]{.underline}. In other words, you will not see two draw commands after a single shape command ("rectangle" or "oval"). However, it may be possible that a shape is never drawn if another shape command appears in the file before there is a draw command for the previous shape. [The first line of the file will always be a shape ("rectangle" or "oval") command]{.underline}.
An example of such a file (named shapes.txt) is shown below.
shapes.txt
rectangle 50 25
red
draw 50 50
oval 100 50
draw 100 100
rectangle 40 20
rectangle 80 80
draw 10 100
The first line (rectangle 50 25) defines a new rectangle with width=50 and height=25 pixels. The second line (red) sets the most recently defined shape (the rectangle defined on the first line) to be the color red. The third line (draw 50 50) would cause the rectangle to be displayed in the graphics canvas with its upper left-hand corner at location (50, 50). The fourth line (oval 100 50) defines a new oval shape with width=100 and height=50 pixels. This new shape is what subsequent commands will refer to until yet another shape is defined. The fifth line (draw 100 100) would cause the oval to be drawn at location (100, 100) on the canvas. Line six (rectangle 40 20) would now define a new rectangle shape with width=40 and height=20 pixels. Note that while this new rectangle is defined, it does not have a draw command associated with it (as the next line of the file will define a new rectangle), so the rectangle defined by line six should not be drawn on the graphics canvas. The seventh line (rectangle 80 80) defines a new rectangle shape with width=80 and height=80 pixels. The eighth (and last) line (draw 10 100) would cause the rectangle defined on line seven to be drawn at location (10, 100) on the canvas.
The result of running the program with the shapes.txt file given
here is shown below (with annotations indicating which set of commands
draw which shapes). 
{style="width: 90%"}
As mentioned above, note that the rectangle defined on line 6 of the file is not actually drawn on the graphics canvas.
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_shapes function along with the name of the input file specified in the constant FILENAME. So, you just need to implement the draw_shapes function. Feel free to define any additional functions that you would like to help you solve this problem.
# Starter Code
import tkinter
CANVAS_WIDTH = 500 # Width of drawing canvas in pixels
CANVAS_HEIGHT = 300 # Height of drawing canvas in pixels
FILENAME = 'shapes.txt'
def main():
canvas = make_canvas(CANVAS_WIDTH, CANVAS_HEIGHT) # Assume make_canvas exists
draw_shapes(canvas, FILENAME)
tkinter.mainloop()
# You should implement the draw_shapes function below
def draw_shapes(canvas, filename):
# Solution Code
def draw_shapes(canvas, filename):
# Variables to keep track of information related to shape to draw
shape = '' # We are not actually required to define these variables
width = 0 # here since we know that the first line of the input file
height = 0 # will be a shape command, so these variables would be
color = 'black' # guaranteed to be defined then.
with open(FILENAME, 'r') as file:
for line in file:
line = line.strip()
parts = line.split()
# Check if this is a shape command ('rectangle' or 'oval')
if parts[0] == 'rectangle' or parts[0] == 'oval':
shape = parts[0] # Keep track of shape
width = int(parts[1]) # Keep track of width
height = int(parts[2]) # Keep track of height
color = 'black' # Default color is black
# Check if this is command to set color
elif parts[0] == 'red':
color = 'red' # Update color
# Otherwise, we must have a 'draw' command
else:
x = int(parts[1]) # Get x coordinate from command
y = int(parts[2]) # Get y coordinate from command
# Draw the appropriate type of shape
if shape == 'rectangle':
canvas.create_rectangle(x, y, x + width, y + height, outline=color)
else: # If it's not a rectangle, it must be an oval
canvas.create_oval(x, y, x + width, y + height, outline=color)
7. Classes (20 points)
We want to build a [class]{.underline} in Python to keep track of the money dispensed from an Automated Teller Machine (ATM) at a bank. For the purposes of this problem, we will assume that the ATM has access to two denominations of bills: $10 bills and $1 bills. And you can assume the ATM will never run out of any type of bill that it dispenses.
In the ATM, we want to allow a user to withdraw money (in positive integer dollar amounts) and the ATM will determine how many of each bill type to give to the user. The ATM tries to satisfy the amount of the withdrawal by giving as many $10 bills as possible, and then gives $1 bills until it has provided the requested amount. For example, if a user wants to withdraw $24, the ATM should give the user two $10 bills and four $1 bills. For accounting purposes, the ATM should keep track of the total number of $10 bills and $1 bills it has dispensed over time.
With this idea in mind, we want to define a class called ATM which has a constructor as well as two methods ("method" is just another name for a function that is in a class), defined as follows:
- dispense_cash(amount) – this is the method called when a user withdraws money from the ATM. You can assume the amount passed in is always a [positive integer]{.underline} value. The method should [return a list]{.underline} with two elements denoting, in order, the number of $10 bills and $1 bills that are dispensed to the user. For example if this method was called with amount = 24, it should return the list [2, 4] to indicate two $10 bills and four $1 bills.
- total_bills_dispensed() – this method should [return a list]{.underline} with two elements denoting, in order, the total number of $10 bills and $1 bills that have been dispensed by the ATM at the time the method is called.
To show an example of the behvaior of your ATM class, we show a main() function below that would create an ATM object (named atm) and then print the results of various calls to methods of that object.
from atm import ATM
def main():
atm = ATM()
print('Total cash dispensed:', atm.total_bills_dispensed())
print('Dispense cash $24 returned:', atm.dispense_cash(24))
print('Total cash dispensed:', atm.total_bills_dispensed())
print('Dispense cash $80 returned:', atm.dispense_cash(80))
print('Total cash dispensed:', atm.total_bills_dispensed())
print('Dispense cash $3 returned:', atm.dispense_cash(3))
print('Total cash dispensed:', atm.total_bills_dispensed())
Output of the program:
Total cash dispensed: [0, 0]
Dispense cash $24 returned: [2, 4]
Total cash dispensed: [2, 4]
Dispense cash $80 returned: [8, 0]
Total cash dispensed: [10, 4]
Dispense cash $3 returned: [0, 3]
Total cash dispensed: [10, 7]
We give you the outline of the class ATM and the methods specified in the class on the right. Your task is to write the implementation (body) of each of the methods in the class ATM. 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
class ATM:
def __init__(self):
def dispense_cash(self, amount):
def total_bills_dispensed(self):
# Solution Code
class ATM:
# Constructor
def __init__(self):
# Keep track of number of each bill dispensed
self.tens = 0
self.ones = 0
# Return a list with two elements denoting, in order, the number of
# $10 bills and $1 bills that are dispensed to the user.
def dispense_cash(self, amount):
# Determine how many ten dollar bills to dispense
num_tens = amount // 10
# Update total number of ten dollar bills dispensed
self.tens += num_tens
# The remaining amount (after dividing by 10) must be dispensed
# as one dollar bills
num_ones = amount % 10
# Update total number of one dollar bills dispensed
self.ones += num_ones
# Returns list of each denomination dispensed
return [num_tens, num_ones]
def total_bills_dispensed(self):
# Return total number of each denomination of bill dispensed
return [self.tens, self.ones]