90 minutes, 160 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 on each line marked "result".
>>> 10 - 2 * 4 + 1
result:
>>> 23 % 5
result:
>>> s = 'Python'
>>> s[2:5]
result:
>>> d = {'xyz': 3, 'abc': 2, 'def': 1}
>>> sorted(d.keys())
result:
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 of
# each value multiplied by -1
>>> nums = [2, -7, 20, 9]
# yields: [-2, 7, -20, -9]
# b. Given a list of strings, compute a list
# where each new string is a lowercase version
# of the original with an exclamation mark after it
>>> strs = ['IS', 'Mystery', 'How']
# yields: ['is!', 'mystery!', 'how!']
# c. Given a list of tuples about cities: (name, fanciness, smugness)
# fanciness and smugness are ratings 1..10
# write a sorted/lambda expression to order the cities
# in decreasing order by smugness
>>> cities = [('Merced', 1, 5), ('Palo Alto', 6, 9), ('Vale', 9, 8)]
# yields: [('Palo Alto', 6, 9), ('Vale', 9, 8), ('Merced', 1, 5)]
Given an image filename and ints a, b, and c which are 1 or more. Produce a new out image with four features: (1) a blank vertical stripe a pixels wide running down the left side of the output image. (2) a blank horizontal stripe b pixels high running across the top of the output image. (3) below the horizontal stripe and to the right of the vertical stripe, a vertically flipped copy of the original image. (4) a second blank horizontal stripe c pixels high below the flipped image. Add your code in the 2 indicated places to complete the function.
1. Write one line of code to create the out image.
Reminder: SimpleImage.blank(width, height)
2. 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, c):
image = SimpleImage(filename)
#### 1. 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)
#### 2. Set "pixel_out"
pixel_out.red = pixel.red
pixel_out.green = pixel.green
pixel_out.blue = pixel.blue
a. Given a string s, create and return a new string based on the lowercase chars in s. For every lowercase char in s, the new string should have that lowercase char followed by the uppercase version of that char.
'12aBc$d' -> 'aAcCdD' 'AbC' -> 'bB' 'AAA' -> ''
def lowup(s):
b. Given a string s, return the numeric sum of the individual digit chars in s. So for example '12abc3' returns 6. Return 0 if there are no digits in s.
'12abc3' -> 6 '3001' -> 4 '' -> 0
def sums(s):
Given a string s, find the first and second '@@@' in s. If both are present, consider (1) the substring before the first '@@@', and (2) the substring between but not including the two '@@@'. Return whichever of these two substrings is longer, or if they are the same length, return the first. If there are not two '@@@' return None. Use s.find() and slices.
'hello@@@hi@@@yy' -> 'hello' 'hi@@@hello@@@yy' -> 'hello' 'hi@@@bye' -> None
def between(s):
We discover a software robot communicating to its owners using "hi-code" strings embedded in text messages. Each hi-code string begins with four plus chars '++++' followed by a series of zero or more 'h' and 'i' chars. Given a string s, return the first hi-code string in s, or the empty string '' if there is none. Use str.find() and a while loop. So for example, 'hi++++ihhihibye' returns 'ihhihi'.
'hi++++ihhihibye' -> 'ihhihi' 'woot++++hhhhHIhi' -> 'hhhh' '++++i' -> 'i' '+++hi' -> ''
def hi_str(s):
For this problem, you will draw a single line in the function draw_one(). The parameters are
canvas - the canvas to draw on
width, height - the width and height of the canvas
margin_top, margin_bot - height of blank vertical areas at the top and bottom of the canvas. Do not draw in these areas. The rectangle of canvas not including the margins is the drawable area.
x_pct - an int in the range 0..100 inclusive. Compute the line endpoint x from this, with x_pct=0 placing the endpoint x at the leftmost column of the drawable area, and x_pct=100 the rightmost
y_pct - an int in the range 0..100 inclusive. Compute the line endpoint y from this, with y_pct=0 placing the endpoint y at the topmost row of the drawable area, and y_pct=100 the bottommost
Write code to draw 1 line, with one endpoint at the lower-right corner of the drawable area, and the other endpoint given proportionately by x_pct, y_pct. Reminder: Use canvas.draw_line(x1, y1, x2, y2) to draw the line.
def draw(canvas, width, height, margin_top, margin_bot,
x_pct, y_pct):
We have two lists of ints a and b. Compute and return a new list containing all the elements in a which are also in b. It's fine if the solution is not the fastest, so long as it gets the right result. The result list may be in any order.
combine([3, 1, 2, 4, 5], [6, 4, 2]) -> [2, 4]
def combine(a, b):
This problem is essentially the standard dict-count algorithm. Given a nums list of int numbers, construct and return a counts dict with a key for each number in the list, and its value is the count of times that number appears in the list. Convert any negative numbers to their absolute value before counting. Reminder: The Python absolute-value function for a number n is abs(n)
nums = [7, 11, -7, -10, 7] ->
{7: 3, 11: 1, 10: 1}
def count_nums(nums):
We are running an experiment about how many people are in different parts of the city each day. We have a "peaks" dict with cities as keys. Each city has cell phone hotspots with names like 'a23'. We want to keep track of the peak (max) number of phones seen by each spot during the day.
We get reports in real time like city='palo alto', spot='a23', and count=17 — meaning there are 17 phones at that spot right now. We want to maintain a "peaks" dict, as show below, that keeps track of the peak (max) number of phones seen by each spot.
peaks = {
'palo alto': {'a23': 9, 'hf7': 14, 'q': 214},
'san diego': {'p2': 22, 'v7': 1},
...
}
Write code for an add_peak() function which takes in a peaks dict (possibly empty), a spot name, and the current number of phones at that spot, and adds that data to the peaks data if needed. In all cases, return the peaks dict. Only add the count for a spot if that count is larger than the existing count for that spot.
>>> add_peak({'palo alto': {'a23': 4}}, 'palo alto', 'z15', 9)
{'palo alto': {'a23': 4, 'z15': 9}}
>>> add_peak(peaks, {'palo alto': {'a23': 4, 'z15': 9}},
'palo alto', 'z15', 12)
{'palo alto': {'a23': 4, 'z15': 12}}
def add_peak(peaks, city, spot, count):
We are running an online game that hosts events where players work together on teams. We have a "teams" dict where the key is a team name, and its value is a list of (user, score) tuples listing their score for the event, like this:
teams = {
'team23': [('arun', 23), ('maya', 6), ('smith', 10), ('billy', 3)],
...
}
Some of the players may have a bonus number, stored in a separate "bonuses" dict like this:
bonuses = {
'arun': 3,
'jennifer': 2,
'maya': 10,
'billy': 2
}
We'll say the total-score for a player is their score from the teams dict, plus their bonus number if they have a bonus. Write the code for a top_scores() function that takes the "teams" and "bonuses" dicts and a team-name and returns a list of (name, total-score) tuples for the players on that team, but only the players with a total-score of 10 or more.
With the dicts shown above, the result for 'team23' is shown below. The bonus is added to make each total-score, and only players with total-score of 10 or more are included in the list. The list may be in any order.
# Example call with dicts as shown above
top_scores(teams, 'team23', bonuses) ->
[('arun', 26), ('maya', 16), ('smith', 10)]
def top_scores(teams, team, bonuses):
You are running a new social network, and you have a text file that records posts to the network. Each line in the file looks like:
icecream-6378-juanita-26,cats-352-anna,meh-612-gordo-2
Each line is made of a series of 1 or more posts separated by commas. Each post is divided into parts by dashes, like: icecream-6378-juanita-26 - the first part is the tag, e.g. 'icecream', the second part is a number not used in this problem, the third part is the poster 'juanita', and the fourth part, if present, is a count number, e.g. '26'. The tags, poster, and number strings themselves will not contain commas or dashes.
Write a function to read through all the lines, and build and return a "posters" dict with a key for each poster seen. The value for each key should be a nested dict of all the tags that appear with that poster. The value for each tag should be the sum of the counts seen with that tag and poster. If a particular post does not include a count number, e.g. the 'anna' example post above, treat the count for that post as 1.
posters = {
'juanita': {'cats': 345,
'iceream': 162},
'anna': {'meh': 19254,
...
}
Part-a. Write code to read in all the lines from the given filename, building and returning the "posters" dict. The basic file-reading code is provided.
def read_posters(filename):
posters = {}
with open(filename) as f:
for line in f:
line = line.strip()
Part-b. (As usual, credit for this part does not depend on your code for the previous part.) Write a print_posters() function that takes in the "posters" dict produced by Part-a, and prints out all the posters in sorted order, one per line. For each poster, print out all its tags in sorted order, each indented by one space and followed by its count like this:
anna icecream 45 meh 2532 zebras 1 ... zoe animals 22 boring 91 meh 2 zebras 2
def print_posters(posters):
#### 1. Short Answer
>>> 10 - 2 * 4 + 1
result: 3
>>> 23 % 5
result: 3
>>> s = 'Python'
>>> s[2:5]
result: 'tho'
>>> d = {'xyz': 3, 'abc': 2, 'def': 1}
>>> sorted(d.keys())
result: ['abc', 'def', 'xyz']
# a. mult by -1
[n * -1 for n in nums]
map(nums, lambda n: n * -1)
# b. strings
[s.lower() + '!' for s in strs]
# c. tuples
sorted(cities, key=lambda city: city[2], reverse=True)
#### 2. Image
out = SimpleImage.blank(image.width + a, image.height + b + c)
pixel_out = out.get_pixel(a + x, b + image.height - 1 - y)
# or out.height - c - 1 - y
#### 3. String-1
# a.
def lowup(s):
result = ''
for ch in s: # for/i/range ok too
if ch.islower():
result += ch + ch.upper()
return result
# b.
def sums(s):
sum = 0
for ch in s: # for/i/range ok too
if ch.isdigit():
sum += int(ch) # '6' -> 6
return sum
#### 4. string-2 Between
def between(s):
a = s.find('@@@')
b = s.find('@@@', a + 3) # +1 is sufficient
if a == -1 or b == -1:
return None
# Could compute lengths with arithmetic,
# but len(substr) is handy alternative
before = s[:a] # Add var strategy
between = s[a + 3:b]
if len(before) >= len(between):
return before
return between
#### 5 string-3 while
def hi_str(s):
start = s.find('++++')
if start == -1:
return ''
# Advance end past 'h' 'i'
end = start + 4
while end < len(s) and (s[end] == 'h' or s[end] == 'i'):
end += 1
return s[start + 4:end]
#### 6. Draw
def draw(canvas, width, height, margin_top, margin_bot,
x_pct, y_pct):
canvas.draw_line(width - 1, height - margin_bot - 1, # lower right
(x_pct / 100) * (width - 1),
(y_pct / 100) * (height - margin_top - margin_bot - 1) + margin_top)
#### 7. List Combine
def combine(a, b):
# Simplest approach: loop over a,
# check each element to see if it's in b.
result = []
for n in a:
if n in b:
result.append(n)
return result
# Aside: an advanced approach (which we are
# not doing here) would build a dict
# of the b elements, so the "check if in b"
# step is fast. That would run much faster
# if the lists were very long - a CS106B strategy.
#### 8. Dict-Count
def count_nums(nums):
counts = {}
for n in nums:
n = abs(n) # Could have if n < 0 logic
if n not in counts:
counts[n] = 0
counts[n] += 1
return counts
#### 9. Dict-2 Peak
add_peak(peaks, city, spot, count):
if city not in peaks
peaks[city] = {}
# Var pointing to nested
spots = peaks[city]
if spot not in spots: # Not in there
spots[spot] = count
elif spots[spot] < count: # Current val too small
spots[spot] = count
# Here using elif, but regular if is ok too
# or could do it with "or" of 2 tests
#### 10. Dict-3 Teams
def topscores(teams, team, bonuses) {
result = []
pairs = teams[team]
for pair in pairs:
user = pair[0] # Helpful to store in named var
score = pair[1]
if user in bonuses:
score += bonuses[user]
# Here if-bonus logic modifies score var
# Could put if-bonus logic later
if score >= 10:
tuple = (user, score)
result.append(tuple)
return result
# The problem statement was not strict about the need
# to check "team in teams", so we did not require it.
#### 11. Capstone
def read_posters(filename):
posters = {}
with open(filename) as f:
for line in f:
line = line.strip()
posts = line.split(',')
for post in posts:
parts = post.split('-')
tag = parts[0] # Add var strategy
poster = parts[2]
count = 1
# If-logic - count is present?
if len(parts) == 4:
count = int(parts[3])
if poster not in posters:
posters[poster] = {}
tags = posters[poster] # Var points to nested
if tag not in tags:
tags[tag] = 0
# Could have if-logic about count down here
tags[tag] += count
return posters
def print_posters(cats):
for poster in sorted(posters.keys()):
print(poster)
tags = posters[poster]
for tag in sorted(tags.keys()):
print(' ' + tag, tags[tag])