Fall 2024-25, 90 minutes, 150 points
# CS106A Exam Reference Reminder # [square brackets] denote functions listed here that have been # mentioned but we have not used significantly. # Exam questions do not require such functions. General functions: len() int() str() float() range() list() abs() min() max() sum() sorted(lst, key=lambda, reverse=True) String functions: isalpha() isdigit() isupper() islower() find() upper() lower() split() strip() [replace()] [join()] startswith() endswith() List functions: append() index() map() [extend() pop()] Dict functions: keys() values() items() File functions with open(filename) as f: # with form for line in f: # loop over lines s = f.read() # read as one big string Lambda: lambda n: 2 * n Canvas/TK Draw # (The problem statement will mention any graphic functions # you need, so this list is just a reference.) canvas.draw_line(x1, y1, x2, y2) # x,y is upper left, optional color='red' parameter # float values are truncated to int automatically canvas.draw_rect(x, y, width, height) canvas.fill_rect(x, y, width, height) canvas.draw_oval(x, y, width, height) canvas.fill_oval(x, y, width, height) SimpleImage: # read filename image = SimpleImage(filename) # create blank image image = SimpleImage.blank(width, height) pixel = image.get_pixel(x, y) # access pixel by x,y pixel has .x .y .red .green .blue
Each of the following Python expressions evaluates to a value without error. Write the resulting Python value in each box.
>>> 57 % 5
>>> 16 // 5
>>> s = 'Python' >>> s[3:] + s[:2]
>>> d = {'zebra': 3, 'ark': 4, 'bee': 2}
>>> sorted(d.keys())
One-Liners For each part, write a 1-line expression to compute the indicated value with: map() or sorted() or min() or max() or a comprehension. You do not need to call list() for these.
# a. Given a list of int values, compute a list where # each value is multiplied * 2 >>> nums = [2, -7, 20, 9] # yields: [4, -14, 40, 18]
# b. Given a list of strings, compute a list # where each new string is a lowercase version # of the original with an exclamation mark ! added >>> strs = ['IS', 'Mystery', 'How'] # yields: ['is!', 'mystery!', 'how!']
# c. Given a list of (x, y, z) tuples of numbers. # write a sorted/lambda expression to order the tuples # in decreasing order by z >>> tuples = [(1, 2, 3), (3, 1, 5), (2, 2, 2)] # yields: [(3, 1, 5), (1, 2, 3), (2, 2, 2)]
Given an image filename and ints a, and b, which are 1 or more. Produce a new out image with three features: (1) a blank vertical stripe a pixels wide running down the left side of the output image. (2) immediately to the right of the vertical stripe and at the bottom of the output, a vertically flipped copy of the original image. (3) a blank rectangle b pixels high, just above the flipped image.
a. At the #### marker below, write one line of code to create the out image.
Reminder: SimpleImage.blank(width, height)
b. Almost all of the code to write the flipped image is provided — looping over the original image, writing the colors at each "pixel" to "pixel_out". Write the one line of code which sets the "pixel_out" variable used by the later lines in this loop. The blank areas are just blank, not requiring any pixel-setting code.
def do_image(filename, a, b):
image = SimpleImage(filename)
#### a. Create "out" image
# Write flipped image to out
for y in range(image.height):
for x in range(image.width):
pixel = image.get_pixel(x, y)
#### b. Set "pixel_out"
pixel_out.red = pixel.red
pixel_out.green = pixel.green
pixel_out.blue = pixel.blue
a. Given a string s, return a string made of the chars in s which are not digits and not the char 'e' (upper or lower case).
'123abee$EEAB' -> 'ab$AB'
def naughty(s):
b. Use s.find() to find the first '@' in s. Consider the index that is 2 greater than the index of the '@'. If the char at that index is alphabetic, return the uppercase form of that char. Otherwise return the '@' itself. If there is no '@', return the empty string.
'xx@$ab' -> 'A' 'xx@$$b' -> '@' 'xx@a' -> '@' 'xx' -> ''
def atupper(s):
a. Given a string s. If the first char of the string is a digit, then for this problem, it is safe to assume that the whole string is made of digits. Return the string form of the number in the original string multiplied by 2. So for example the string input '16' returns the string '32'. If the first char is not a digit, then return the original string unchanged.
'16' -> '32' '231' -> '462' 'xyz' -> 'xyz' '' -> ''
def doubles(s):
b. Use s.find() to find the first '***' in s, and the first non-overlapping '**' after it. If the '***' and '**' are not present, return the string unchanged. If the stars are present, return a form of the original s, with the substring between the stars passed through the doubles(s) function from part (a). Assume the doubles(s) function works correctly. So for example, 'xx***12**xx' returns 'xx***24**xx'. In effect, if there is a number between the stars, it will be doubled. Input assumption: for the string s, it is guaranteed that the chars between the stars will either all be digits, or none will be digits. This simplifies detecting and handling the number between the stars.
'xx***12**xx' -> 'xx***24**xx' '**x***6349**' -> '**x***12698**' 'cat***bird**dog' -> 'cat***bird**dog' 'xyz***' -> 'xyz***' 'xyz' -> 'xyz'
def stars(s):
We'll say a "phrase" in the string is a sequence of alphabetic chars and dashes '-'. Return the substring made by the first 'OMG' in s, including any "phrase" chars that immediately follow it. So for example 'woot OMG-this-rocks! yo' returns 'OMG-this-rocks'. Use s.find() to find the 'OMG' and a while loop to figure the extent of the phrase chars. If there is no 'OMG', return the empty string.
'woot OMG-this-rocks! yo' -> 'OMG-this-rocks' 'OMGxx--' -> 'OMGxx--' 'nope' -> ''
def omg_phrase(s):
For this problem, you will work out the coordinates to draw 1 line.
The canvas contains two rectangles. The first rectangle is at the upper left of the canvas, with width w1, and height h1. The second rectangle is immediately below and to the right of the first, with width w2, and height h2. We have a number num which is in the range 0..357. We want to draw a vertical line at the right edge of the the second rectangle, starting at the upper right of the rectangle, with its length extending proportionate to num. When num is 357, the line should reach all the way to bottom right pixel. When num is 0, the line starts and ends at the upper right pixel of the second rectangle.
For your expressions below, use w1, h1, w2, h2, num in your code as needed.
The start point of the line is fixed at the upper right pixel of the second rectangle. The end point of the line extends down vertically, depending on num, which is in the range 0..357.
a. What is the Python expression for the x value of the start point:
b. What is the Python expression for the y value of the start point:
c. The line extends down to its end point. What is the python expression for the y value of its end point?
This problem is essentially the standard dict-count algorithm. Given a string s, construct and return a counts dict of the alphabetic chars in s, ignoring the non-alphabetic chars. The counts dict should have a key for each alphabetic char in s, and its value is the count of the times that char appears in s.
'AaaB@AA3' -> {'A': 3, 'a': 2, 'B': 1}
def count_alpha(s):
We have a bunch of cats living together, and their data is stored in a nested dict structure like this:
cats = {
'abe': {'id': 2354, 'pal': 'monica'},
'sarah': {'id': 45, 'pal': 'monica'},
'monica': {'id': 33, 'pal': 'abe'},
'mike': {'id': 123, 'pal': 'phil'}
}
Each cat has a name, like 'abe', which is the key for that cat's dict. Each cat dict always has 'id' and 'pal' keys in it. The 'pal' value is the name of that cat's best friend (e.g. The pal of 'abe' is 'monica'). Sometimes the pal names a cat which is not in the data (e.g 'phil' on the last line above is not in the dict).
We'll say a cat is "paired" as follows: suppose there is a cat Alice, and that cat's pal is Bob. Now look at Bob - if Bob's pal is Alice, then we'll say Alice is "paired". By this definition, 'abe' above is paired, but 'sarah' is not.
Write code for a function paired(cats), which takes in the whole cats dict, and returns a list of the names of the "paired" cats. For the example above, the list would be: ['abe', 'monica']
def paired(cats):
Suppose you are running a new social network based on people sharing photos of their cats. There are so many cat enthusiasts, this will somehow make money. Each time a user shares a photo, they pick a hashtag like '#cute' and the system knows the state their are in like 'ca' or 'tx'. We want to build a dictionary with a key for every hashtag seen. The value for each tag is a nested dictionary counting the number of photos for that hashtag, organized by state. For example, with the data show below, the number of photos with the tag '#cute' from 'ca' is 12:
tags = {
'#cute': {'ca': 12, 'tx': 7, 'tn': 146},
'#meow': {'tx': 4, 'ca': 3, 'fl': 1},
...}
a. Write code for an add_tag(tags, tag, state) function which takes in an existing tags dict, and a tag/state pair of strings, and adds that data to the tags dict, which is returned. Note that the tags dict may be empty to start. So for example, calling with the above tags add_tag(tags, '#cute', 'tx') would increase the 'tx' count from 7 to 8.
def add_tag(tags, tag, state):
b. Write code for a state_sum(tags, state) function. Given the tags dict and a state like 'tx', return the total number of photos for that state, across all the hashtags, returning 0 if here are no photos for that state.
def state_sum(tags, state):
Suppose we are running some sort of massive live audio chat with a few speakers, represented by the dictionary below. There is a 'speakers' key, and its value is a nested dict of the speakers. Each speaker has a name in the system, e.g. 'catso', which is the key to their data in the speakers dict. The dict for each speaker always contains the keys 'sites' and 'likes'. The 'sites' value is a list of the sites that speaker has mentioned, and 'likes' is an int count of the likes they have gotten.
chat = {
'key': '56af-baff-23',
'speakers': {
'catso': {'sites': ['bleh.com', 'pets.com'], 'likes': 34},
'miguelx': {'sites': ['spork.org', 'bleh.com'], 'likes': 112},
'stig': {'sites': ['moof.org'], 'likes': 5}
}
}
a. Write code for a function has_site(chat, name, site), which takes the chat dict, and a name like 'catso' and a site like 'bleh.com', and returns True if that name is in the data and has mentioned that site, or False otherwise.
# chat = { .. the data above ..}
has_site(chat, 'catso', 'pets.com') -> True
has_site(chat, 'catso', 'chase.com') -> False
has_site(chat, 'dogso', 'pets.com') -> False
def has_site(chat, name, site):
b. Write code for an add_pity(chat, limit, pity_site) function which is given the chat dict, an int limit like 10, and a pity_site like 'pity.com'. The function adds the pity_site to the sites list of all the speakers where their likes number is below the given limit. For example, with the chat dict shown above and limit=10 and pity_site='pity.com', the code would change the sites list of 'stig' to: ['moof.org', 'pity.com']. The other speakers would not be changed. (You may omit the final return chat line.)
def add_pity(chat, limit, pity_site):
You are processing data files from a tweeting platform. Each line in the file looks like this, with a series of "groups" separated by commas.
helen@12@foo.com,sarah@3@bar.com,miguel@7@foo.com
There are 1 or more groups on each line. Each group has 3 parts separated by at signs '@', like 'helen@12@foo.com'. The first word is the user ('helen'), the second is the number ('12'), and the last word is the host ('foo.com'). The words themselves do not contain commas or at signs. We want to build a "hosts" dict with a key for each host seen. The value for each host is a nested dict of all the users who appear with that host. The value for each user is the sum of all the numbers for that user and host. the users and hosts can appear repeatedly and in any combination in the file.
hosts = {
'foo.com': {'sarah': 42, 'miguel': 24, 'aparna': 55},
'bar.com': {'john': 5, 'sarah': 22},
...
}
Part-a. Write code to read in all the lines from the given filename, building and returning the "hosts" dict. The basic file-reading code is provided.
def read_hosts(filename):
hosts = {}
with open(filename) as f:
for line in f:
line = line.strip()
# Reminder of hosts structure
hosts = {
'foo.com': {'sarah': 42, 'miguel': 24, 'aparna': 55},
'bar.com': {'john': 5, 'sarah': 22},
...
}
Part-b. Write a print_hosts() function that takes in the "hosts" dict produced by Part-a, and prints out all the hosts in sorted order, one per line. For each host, print out all its users in sorted order, each indented by one space and followed by its sum like this:
aardvark.com abe 7 basil 28 .. zephyr 22 ... zoo.com aparna 57 ... zadie 3
def print_hosts(hosts):
#### 1. Short Answer
>>> 57 % 5
2
>>> 16 // 5
3
>>> s = 'Python'
>>> s[3:] + s[:2]
'honPy'
>>> d = {'zebra': 3, 'ark': 4, 'bee': 2}
>>> sorted(d.keys())
['ark', 'bee', 'zebra']
# a. Given a list of int values, compute a list where
# each value is multiplied * 2
>>> nums = [2, -7, 20, 9]
# yields: [4, -14, 40, 18]
[n * 2 for n in nums]
# -or-
map(lambda n: n * 2, nums)
>>> strs = ['IS', 'Mystery', 'How']
# yields: ['is!', 'mystery!', 'how!']\
[s.lower() + '!' for s in strs]
>>> tuples = [(1, 2, 3), (3, 1, 5), (2, 2, 2)]
# yields: [(3, 1, 5), (1, 2, 3), (2, 2, 2)]
sorted(tuples, key=lambda tup: tup[2], reverse=True)
#### 2. Image
out = SimpleImage.blank(image.width + a, image.height + b)
pixel_out = out.get_pixel(x + a, image.height + b - 1 - y)
# or out.height - 1 - y
#### 3. String-1
def naughty(s):
result = ''
for ch in s:
if not ch.isdigit() and ch.lower() != 'e':
result += ch
return result
def atupper(s):
at = s.find('@')
if at == -1:
return ''
if at + 2 < len(s):
ch = s[at + 2]
if ch.isalpha():
return ch.upper()
return '@'
#### 4. String-2
def doubles(s):
# Pick-off cases where it's not a number
if s == '':
return s
if not s[0].isdigit():
return s
n = int(s) # str -> int
n = n * 2 # do the math
return str(n) # int -> str
# Or could use format string f'{n * 2}'
def stars(s):
a = s.find('***')
b = s.find('**', a + 3) # +3 to skip first stars
if a == -1 or b == - 1:
return s
# Chars between stars
mid = s[a + 3:b]
# Put it all together
return s[:a + 3] + doubles(mid) + s[b:]
#### 5. String-3
def omg_phrase(s):
omg = s.find('OMG')
if omg == -1:
return ''
# Advance end over phrase chars
end = omg + 3
while end < len(s) and (s[end].isalpha() or s[end] == '-'):
end += 1
return s[omg:end]
#### 6. Draw
a. w1 + w2 - 1
b. h1
c. h1 + (num / 357) * (h2 - 1)
#### 7. Dict-1
def count_alpha(s):
# The standard count code, with the addition
# of only counting alphabetic chars
counts = {}
for ch in s:
if ch.isalpha():
if ch not in counts:
counts[ch] = 0
counts[ch] += 1
return counts
#### 8. Dict-2 Paired
def paired(cats):
# Maybe a little trickier than it looks.
# Multiple names and multiple dicts -
# Try to use distinct var names and a drawing to
# keep the parts straight.
result = []
# Loop over cat names, check each
for name in cats.keys():
inner = cats[name] # Var points to inner
pal_name = inner['pal']
if pal_name in cats:
# Get pal dict, does it point back to name?
pal_inner = cats[pal_name]
if pal_inner['pal'] == name:
result.append(name)
return result
#### 9. Dict-3 For The Meows
def add_tag(tags, tag, state):
if tag not in tags:
tags[tag] = {}
states = tags[tag] # Var points to inner
# Now it's just regular count algo
if state not in states:
states[state] = 0
states[state] += 1
return tags
def state_sum(tags, state):
total = 0
# Loop over all the tags, for each, lookup the state
for tag in tags.keys():
states = tags[tag] # Var points to inner
if state in states:
total += states[state]
return total
#### 10 Dict-4
def has_site(chat, name, site):
names = chat['speakers']
if name in names:
user = names[name]
if site in user['sites']:
return True
return False
def add_pity(chat, limit, pity_site):
names = chat['speakers']
for name in names.keys():
user = names[name]
if user['likes'] < limit:
user['sites'].append(pity_site)
return chat
#### 11 Capstone - Hosts
def read_hosts(filename):
hosts = {} # typo: had "tags" on exam
with open(filename) as f:
for line in f:
line = line.strip()
groups = line.split(',')
for group in groups:
# group e.g. helen@12@foo.com
# Get data out of the group into named vars.
# Var names help the following step a little.
parts = group.split('@')
user = parts[0]
n = int(parts[1])
host = parts[2]
if host not in hosts:
hosts[host] = {}
users = hosts[host] # Var points to inner
if user not in users:
users[user] = 0
users[user] += n
return hosts
def print_hosts(hosts):
for host in sorted(hosts.keys()):
print(host)
users = hosts[host]
for user in sorted(users.keys()):
print(' ' + user, users[user])