Stanford, Spring 2018-19
The median score on this exam was 90%.
# CS106AP Exam Reference Reminder
General functions:
len() int() str() range() list()
sorted() # key= and reverse= optional params
min() max() # key= optional param
String functions:
isalpha() isdigit() isspace() isalnum() find()
startswith() endswith()
isupper() islower() upper() lower()
replace() split() join() format() splitlines()
List functions:
append() extend() pop() map()
Dict functions:
keys() values() items()
File functions
with open(filename, 'r') as f:
for line in f: # loop over lines
s = f.read() # read as one big string
lines = f.readlines() # read as list of strings
Lambda syntax:
lambda n: 2 * n
SimpleImage:
image = SimpleImage(filename)
image = SimpleImage.blank(width, height)
image has .width and .height int properties
for pixel in image: # loop pixel over whole image
pixel = image.get_pixel(x, y) # access pixel by x,y
pixel has .x .y .red .green .blue
# "pix" functions
pix = image.get_pix(x, y) # pix (r, g, b) tuple form
image.set_pix(x, y, pix)
# loop over all pixel x,y
for y in range(image.height):
for x in range(image.width):
pixel = image.get_pixel(x, y)
Each of the following Python expressions evaluates to something without error. Write the resulting Python value on each line marked "result". You may need to scroll down to see all of the parts. The lsat question is a function-trace, write the 3 numbers printed.
>>> 1 + 2 + 3 * 2
result:
>>> 9 // 2
result:
>>> 9 / 2
result:
>>> 1 + 1 + 1.0 + 1
result:
>>> s = 'Python'
>>> s[:2]
result:
>>> s[2:]
result:
>>> x = [3, 1, 4]
>>> y = [1, 5]
>>> x.append(y)
result, x is:
>>> # list(range(xxx)) places the numbers in a list
>>> list(range(90, 100, 2))
result:
>>> d = {'a': 8, 'z': 1, 'd': 5}
>>> sorted(d.items())
result:
>>> points = [(2, 3), (3, 4), (1, 2)]
>>> min(points, key=lambda point: point[1])
result:
## Function trace
def dog(x, y):
y = 0
return x + y
def caller():
x = 10
y = 20
z = dog(y, x)
print(x, y, z)
# What 3 numbers are printed
result:
# end of question
dedigit(s):
Given a string s, return a version
of the string omitting contiguous digits
at its start, so '123abc6'
returns 'abc6'. If there are no digits
at the start of the string, return it unchanged.
def dedigit(s):
"""
>>> dedigit('123abc6')
'abc6'
>>> dedigit('abc')
'abc'
>>> dedigit('123')
''
>>> dedigit('')
''
"""
# your code
An IP address like '171.64.64.11' identifies a computer on the internet. For this problem we'll define the IP address syntax with a lot more slack: a substring starting with a digit followed by any combination of digits and dots, so '1.2' and '123' and '1..' all qualify. Implement the following function:
parse_ips(s): Given string s, parse out and return all the IP address substrings as defined above and return them in a list.
'1.2 x 3..4x7' → ['1.2', '3..4', '7'] '123 .7.x' → ['123', '7.']
def parse_ips(s):
# your code
Given an image, create an out image 3 times as wide as the original. Copy the original image, upside down, to the rightmost 1/3 of the out image. Leave the left 2/3 of the out image blank. The starter code includes some common elements filled in, with some details for you to add. You may use either image.get_pixel() (used on HW2 Bluescreen) or image.get_pix() (used on HW7 Ghost).
SimpleImage functions:
image = SimpleImage(filename)
image = SimpleImage.blank(width, height)
image has .width and .height int properties
for pixel in image: # loop pixel over whole image
pixel = image.get_pixel(x, y) # access pixel by x,y
pixel has .x .y .red .green .blue
# "pix" functions
pix = image.get_pix(x, y) # pix (r, g, b) tuple form
image.set_pix(x, y, pix)
# loop over all pixel x,y
for y in range(image.height):
for x in range(image.width):
pixel = image.get_pixel(x, y)
def third_up(filename):
image = SimpleImage(filename)
out = SimpleImage.blank( ) # fill in the parameters here
## Standard y/x loop over image
for y in range(image.height):
for x in range(image.width):
## your code
We'll say an email addr string looks like this 'alice@foo.com', with the following structure: there is exactly one '@', separating a user substring ('alice'), and host ('foo.com'). For this problem, assume that all email addrs are correctly formatted in this way.
Given a list of email addr strings, e.g. ['alice@foo.com', 'bob@bar.org', ...] , compute a "hosts" dict with a key for every host string that occurs within the addresses. The value for each host key is a list of all the user strings for that host. For example, the following hosts dict has a key 'foo.com' with 3 user strings:
{
...
'foo.com': ['bob', 'alice', 'sal'],
...
}
The user strings in the nested list may be in any order, but should not include duplicates, e.g. if the addr 'alice@foo.com' is seen twice, 'alice' should be in the list only once.
def parse_hosts(addrs):
"""
Given list of email addrs
['alice@foo.com', 'bob@bar.org', ...]
compute and return a hosts dict.
"""
# your code
For this problem, suppose you are building a new messaging service where every user has an address like '@bob'. You have a log file of lines like this..
@bob,@alice,@mo @mo,@pierre ...
Each line represents one sent message in the system. The first address on a line is the sender, followed by 1 or more destination (dest) addresses for that message. The dest addresses will not include duplicates. Users can send many messages over time with various sets of 1 or more dests. For this problem, you will process a file of log lines to analyze the flow of messages.
We'll say a "sends" dict has a key for every sender address that has sent a message. The value for each sender is a nested dict which counts how many messages have been sent from that sender to each dest. So for example, the sends dict below shows that '@bob' sent 3 messages including '@alice' as a recipient and 1 message including '@mo'.
{
...
'@bob': {'@alice': 3, '@mo': 1},
...
}
parse_sends(filename): given a filename of a log file, read through all the log lines to build and return a sends dict.
def parse_sends(filename):
# your code
This problem uses the "sends" dict format from the previous problem, but the code here is independent, and you can work on it without solving the previous problem.
As a reminder, here is the previous example sends dict, showing that '@bob' sent 3 messages including '@alice' as a recipient and 1 including '@mo'.
{
...
'@bob': {'@alice': 3, '@mo': 1},
...
}
commons(sends, srca, srcb):
Given a sends dict, and srca and srcb are sender
addrs which have sent messages.
Compute and return a "commons" list of the dest
addresses that each have received messages from
both srca and srcb.
The addrs in the commons list may be in any order,
but should not include duplicates, i.e. no address
should be in the list twice.
Several approaches are possible
and we are not grading on efficiency here,
so any approach that computes the list correctly is fine.
So for example with sends
{
...
'@bob': {'@a': 2, '@b': 1, '@x': 12},
'@mo': {'@b': 6, '@x': 1, '@y': 1}
...
}
Calling the function with srca '@bob' and srcb '@mo', the commons list is ['@b', '@x'].
def commons(sends, srca, srcb):
# your code
Given a canvas of the given int width and height, and a list of int values, each in the range 1..100 inclusive. For this problem, there's an imaginary vertical line running down the center of the canvas at x=width/2 (the width is guaranteed to be an even number).
For each value in the list, draw a horizontal line that starts on the center line and extends to the right towards the edge, its length proportionate to the value. When the value is 100, the line should end on the column of rightmost pixels of the canvas. Draw the first line at y=0, the next at y=1, and so on. The height of the canvas will be sufficient for all the lines to fit.
TK create_line reminder, draw a black 1-pixel-wide line:
canvas.create_line(x1, y1, x2, y2)
def draw_lines(canvas, width, height, values):
# your code
For each of parts a, b, and c, write a comprehension expression or a sorted/lambda expression to compute the output described. Each part gives an example input and result to help define the needed computation.
# a. Given list of non-empty strs, write a comprehension to form # a list of the strings in upper case. >>> strs = ['Rhyme', 'Donut', '3xx', 'Orange'] # yields ['RHYME', 'DONUT', '3XX', 'ORANGE'] # your comprehension: # b. Given list of non-empty strs, write a comprehension to form # a list of the strings unchanged, but only including the strings # where the first char is alphabetic. >>> strs = ['Rhyme', 'Donut', '314', 'Orange', 'a42'] # yields ['Rhyme', 'Donut', 'Orange', 'a42'] # your comprehension: # c. Given list of (x, y) points, write a sorted/lambda # expression to order these points in increasing order # by the sum of the x+y of each point. >>> points = [(10, 0), (1, 3), (3, 2), (5, 4)] # yields [(1, 3), (3, 2), (5, 4), (10, 0)] # your sorted:
### 2. Warmups
>>> 1 + 2 + 3 * 2
result: 9
>>> 9 // 2
result: 4
>>> 9 / 2
result: 4.5
>>> 1 + 1 + 1.0 + 1
result: 4.0
>>> s = 'Python'
>>> s[:2]
result: 'Py' or Py
>>> s[2:]
result: 'thon'
>>> x = [3, 1, 4]
>>> y = [1, 5]
>>> x.append(y)
result, x is: [3, 1, 4, [1, 5]]
>>> # list(range(xxx)) places the numbers in a list
>>> list(range(90, 100, 2))
result: [90, 92, 94, 96, 98]
>>> d = {'a': 8, 'z': 1, 'd': 5}
>>> sorted(d.items())
result:[('a', 8), ('d', 5), ('z', 1)]
>>> points = [(2, 3), (3, 4), (1, 2)]
>>> min(points, key=lambda point: point[1])
result: (1, 2)
## Function trace
def dog(x, y):
y = 0
return x + y
def caller():
x = 10
y = 20
z = dog(y, x)
print(x, y, z)
# What 3 numbers are printed
result: 10 20 10
## 3.
def dedigit(s):
# scan forward for a non-digit (could use while)
for i in range(len(s)):
if not s[i].isdigit():
return s[i:]
# it was all digits .. end up here
return ''
## 4.
def parse_ips(s):
"""
>>> parse_ips('xx1.2xx11.22..xx4')
['1.2', '11.22..', '4']
>>> parse_ips('1..x.33')
['1..', '33']
"""
start = 0
result = []
while True:
# find the start
while start < len(s) and not s[start].isdigit():
start += 1
if start >= len(s):
break
# find the end
end = start + 1
while end < len(s) and (s[end].isdigit() or s[end] == '.'):
end += 1
result.append(s[start:end])
start = end + 1 # ok without + 1
return result
## 5.
def third_up(filename):
image = SimpleImage(filename)
out = SimpleImage.blank(image.width * 3, image.height)
## Standard y/x loop over image
for y in range(image.height):
for x in range(image.width):
out_left = 2 * image.width / 3 # int math fine here
out_x = out_left + x
out_y = image.height - 1 - y
pixel = image.get_pixel(x, y)
out_pixel = out.get_pixel(out_x, out_y)
out_pixel.red = pixel.red
out_pixel.green = pixel.green
out_pixel.blue = pixel.blue
## 6
def parse_hosts(addrs):
"""
>>> parse_hosts(['a@x', 'b@x', 'a@x'])
{'x': ['a', 'b']}
>>> parse_hosts(['a@x', 'b@x', 'a@y'])
{'x': ['a', 'b'], 'y': ['a']}
>>> parse_hosts(['a@x', 'bob@x', 'c@z'])
{'x': ['a', 'bob'], 'z': ['c']}
"""
hosts = {}
for addr in addrs:
at = addr.find('@')
user = addr[:at]
host = addr[at + 1:]
if host not in hosts:
hosts[host] = []
users = hosts[host] # style: decomp by var
if user not in users: # no duplicates
users.append(user)
return hosts
## 7
def parse_sends(filename):
with open(filename, 'r') as f:
sends = {}
for line in f:
line = line.strip() # \n handling, not marking off for this
parts = line.split(',')
src = parts[0]
if src not in sends:
sends[src] = {}
nested = sends[src] # decomp by var
for dst in parts[1:]:
if dst not in nested:
nested[dst] = 0
nested[dst] += 1
return sends
## 8
def commons(sends, srca, srcb):
countsa = sends[srca] # Given that srca/b are in sends
countsb = sends[srcb] # so don't need "in" check first.
result = []
for dest in countsa.keys():
# is it in b too? "in" handy here
if dest in countsb:
result.append(dest)
return dest
## 9
def draw_lines(canvas, width, height, values):
mid_x = width / 2 # int math would be fine too
for i in range(len(values)):
val = values[i]
y = i
x_len = (val/100) * (width/2)
canvas.create_line(mid_x, y, mid_x + x_len, y)
## 10
>>> strs = ['Rhyme', 'Donut', '3xx', 'Orange']
# yields ['RHYME', 'DONUT', '3XX', 'ORANGE']
[s.upper() for s in strs]
# b. Given list of non-empty strs, write a comprehension to form
# a list of the strings unchanged, but only including the strings
# where the first char is alphabetic.
>>> strs = ['Rhyme', 'Donut', '314', 'Orange', 'a42']
# yields ['Rhyme', 'Donut', 'Orange', 'a42']
[s for s in strs if s[0].isalpha()]
# can refer to s[0] safely because given that strings are non-empty
# c. Given list of (x, y) points, write a sorted/lambda
# expression to order these points in increasing order
# by the sum of the x+y of each point.
>>> points = [(10, 0), (1, 3), (3, 2), (5, 4)]
# yields [(1, 3), (3, 2), (5, 4), (10, 0)]
sorted(points, key=lambda pt: pt[0] + pt[1])