Stanford, Fall 2022-23
# 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()
startswith() endswith()
find() upper() lower() split() strip()
[replace()] [join()]
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
lines = f.readlines() # read as list of strings
Lambda:
lambda n: 2 * n
SimpleImage:
# read filename
image = SimpleImage(filename)
# create blank image
image = SimpleImage.blank(width, height)
# foreach loop
for pixel in image:
# range/y/x loop
for y in range(image.height):
for x in range(image.width):
pixel = image.get_pixel(x, y)
pixel = image.get_pixel(x, y) # access pixel by x,y
pixel has .x .y .red .green .blue
pix = image.get_pix(x, y) # pix (r, g, b) tuple form
image.set_pix(x, y, pix)
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)
# TK versions
canvas.create_line(x1, y1, x2, y2)
canvas.create_text(x, y, text='str')
Grid 2D:
grid = Grid.build([['row', '0'], ['row', '1']])
grid.in_bounds(x, y) - True if in bounds
grid.width, grid.height - properties
grid.get(x, y) - returns contents at that x,y, or None if empty
grid.set(x, y, value) - sets new value into grid at x,y
Each of the following Python expressions evaluates to something without error. Write the resulting Python value on each line marked "result".
>>> 23 // 5
result:
>>> 10 - 2 * 3 + 1
result:
>>> s = 'Goblin'
>>> s[1:3]
result:
>>> d = {'cat': 10, 'dog': 499, 'bat': 13}
>>> sorted(d.keys())
result:
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 + 1.
>>> nums = [2, 7, 20, 9]
# yields: [3, 8, 21, 10]
# b. Given a list of strings, compute a list
# where each new string is a lowercase version
# of the original followed by an uppercase version
# within brackets '[' .. ']'
>>> strs = ['is', 'Mystery', 'How']
# yields: ['is[IS]', 'mystery[MYSTERY]', 'how[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', 8, 8)]
# yields: [('Palo Alto', 6, 9), ('Vale', 8, 8), ('Merced', 1, 5)]
Find the first '[[' and the first ']]' after it in s. If both are present, return the chars between the two, and None otherwise. Use s.find().
'xx[[abc]]xx' -> 'abc' 'xxx[[123]] [[]]' -> '123' 'xx]] [[ok]]' -> 'ok' 'xx]] [[nope' -> None 'xx]] [[nope]' -> None 'abc' -> None
def double_bracket(s):
pass
Given a string s. Compute and return a new string. (1) For every alphabetic char in s, the new string should have a '@'. (2) For every dash char '-' in s the new string should also have a dash char. All other chars in s should be omitted from the result.
'^^ab-cd^^' -> '@@-@@' 'x$$ab-cd**x--*' -> '@@@-@@@--'
def alpha_at(s):
pass
not-doing-2023
We'll say a "phrase" begins with an alphabetic char and is made of a mixture of alphabetic chars and space chars (space char is ' '). Find and return the first phrase in s, or None if there is not one. Use 2 non-nested while loops.
'^^ this is it^^' -> 'this is it' '**woot** toot' -> 'woot' '$$$' -> None '$x y z$a' -> 'x y z'
def find_phrase(s):
pass
Suppose you are working on simulation using a grid. Every square is either a bear 'b', coffee 'c', donut 'd'or empty None. For an x, y, the Sudden Donut move has two conditions:
1. The square at (x, y) must contain a bear
2. The square 1 down and 2 to the right of the bear must contain coffee
We'll call the square above the coffee the "destination". If both conditions are met, set the destination to contain donut regardless of what it contained before, and return True. Otherwise leave the grid unchanged and return False. Write code for the Sudden Donut function, taking in a grid and an in-bounds x, y.
def sudden_donut(grid, x, y):
pass
Most of the code for this provided, with just a couple key lines left for you to complete. Given an input image. Create an output image which is twice as wide. We will write every other column of pixels in the output image, leaving the other half the columns blank. The column of pixels at x = 0 in the input go to x = 0 in the output. The pixels at x = 1 in the input go to x = 2 in the output, and so on, leaving x = 1, 3, 5 .. blank in the output. In addition, the pixels are vertically flipped to be upside down in the output.
x = 0 in input -> x = 0 in output x = 1 in input -> x = 2 in output x = 2 in input -> x = 4 in output ... (x = 1 3 5 ... left blank in output)
def columns(filename):
image = SimpleImage(filename)
#### a. Create "out" image (Your one-line here)
# Write each input x, y pixel to output
for y in range(image.height):
for x in range(image.width):
pixel = image.get_pixel(x, y)
#### b. Set "pixel_out" (Your one-line here)
pixel_out.red = pixel.red
pixel_out.green = pixel.green
pixel_out.blue = pixel.blue
Given a canvas and its width and height. Given parameters x, y, pct.
The x, y identify a pixel in the bottom half of the canvas.
The pct parameter is an int in the range 0..100 inclusive.
Draw a line on the canvas starting at x, y, and extending vertically towards the top of the canvas. When pct is 0, the line should begin and end on x, y. When pct is 100, the line should start at x,y, and extend vertically up, ending at the topmost row of pixels. For values between 0 and 100 .. the line should extend proportionately. Use floating point math. Your code may or may not need to use the given width or height. Reminder: Use canvas.draw_line(x1, y1, x2, y2) to draw each line.
def draw_pct(canvas, width, height x, y, pct):
pass
For simplicity, assume there are no uppercase chars in the input string for this problem. We have an "alphas" list, listing the lowercase alphabetic chars in some order. We also have an "indexes" dict, which has a key for every alphas index number 0..len-1. For each index number key, the value is another index number. Here is what the data structures look like, here just using the chars 'a, b, c, d':
alphas = ['c', 'a', 'b', 'd']
0 1 2 3
indexes = {
0: 2,
1: 3,
2: 0,
3: 1
}
Given alphas, indexes, and a string s, compute the encrypted form of s as follows: For each char in s, if the char does not appear in alphas, then its encrypted form is the char itself. Otherwise, find the index of the char in the alphas list, calling this "index1". Look up index1 in the dict - it is guaranteed to be in there. Call the corresponding value in the dict "index2". The encrypted form of the original char is the char at index2 in the alphas list.
Examples with above alphas/indexes: encode 'a': 'a' -> 1 -> 3 -> 'd' encode 'b': 'b' -> 2 -> 0 -> 'c' encode '$': '$' -> '$'
Write the code to build and return the encrypted form of s with the above algorithm:
def dict_crypt(alphas, indexes, s):
pass
Suppose we have a "states" dict where the keys are state codes like 'ca'. The value for each state is a nested dict where the key is an int zipcode, and its value is the vote count for that zipcode, like this:
states = {
'ca': {94301: 3456, 94303: 255, ... },
'tx': {77494: 400, 75034: 9863, ... },
...
}
We'll say a location is a state-zipcode string, like this: 'ca-94303'. The "locs" is a list of location strings:
locs = ['ca-94303', 'tx-77494', ...]
Write a find_votes() function that takes in the states dict and the locs list, and looks up the vote count for each location 'ca-94303'. Return a list containing one tuple of the form ('ca-94303', 255) for each location, giving the vote count for that location. So the result list looks like
[('ca-94303', 255), ('tx-77494', 400), ...]
If the data for a location is not present in the states dict, then do not include a tuple for that location in the result. The tuples may be in any order in the result list. Syntax reminder: to create a variable "t" holding a tuple length-2 holding 'a' and 123, the syntax is: t = ('a', 123)
def find_votes(states, locs):
pass
This problem has two parts, and you can get full credit for each part independent of the other part. Somehow you end up running a social network populated with influencers. You need to keep track of how many times each influencer posts a url. You have a text file recording influencer posts. (1) The first element on each line is the url-start, e.g. http://foo.com/. (2) The rest of the line is made of sally^news.html pairs — made of an influencer id (sally), an up-hat (^), and a url-end (news.html). Here is an example line from the file:
http://foo.com/,sally^news.html,bobby^hot/meh.php
The url-end inside each pair needs the url-start added to make the full url: 'http://foo.com/' + 'news.html' -> 'http://foo.com/news.html'
Part-a. Write code to read in all the lines, building and returning a "posts" dict with a key for each influencer. The value for each influencer should be a nested count dict, with a key for each full url that influencer posted, and its value is a count of how many times the influencer posted that url. The basic file-reading code is provided as a starting point. The resulting dict looks like:
posts = {
'sally': {'http://foo.com/news.html': 4,
'http://z.org/hot.php': 1023, ... },
'xi': {'http://stanford.edu/hi.html': 3,
'https://ny.org/xi/king.php': 6, ...},
...
def read_posts(filename):
posts = {}
with open(filename) as f:
for line in f:
line = line.strip()
Part-b. Write a print_posts() function that takes in the "posts" dict produced by Part-a, and prints out all the influencer ids in sorted order, one per line. For each influencer, print out all their urls in sorted order, each indented by one space and followed by its count, like this:
aardvarkman http://foo.com/a.html 4 http://zebra.org/bleh/truth.php 1 ... ... zoltar http://ant.com/bleh.html 1 http://bear.org/b.html 5 ...
def print_posts(posts):
pass
#### 1 Warmup
23 // 5
result: 4
10 - 2 * 3 + 1
result: 5
result: 'ob'
result: ['bat', 'cat', 'dog']
#### 2 1-Liners
[n + 1 for n in nums]
[s.lower() + '[' + s.upper() + ']' for s in strs]
sorted(cities, key=lambda city: city[2], reverse=True)
#### 3 String-1
def double_bracket(s):
left = s.find('[[')
if left == -1:
return None
right = s.find(']]', left + 2) # + 2 not mandatory
if right == -1:
return None
return s[left + 2:right]
#### 4 String-2
def alpha_at(s):
result = ''
for ch in s:
if ch.isalpha():
result += '@'
if ch == '-': # could have else, not required
result += '-'
# otherwise don't add to result
return result
#### 5 String-3
def find_phrase(s):
start = 0
while start < len(s) and not s[start].isalpha():
start += 1
if start == len(s): # not found
return None
end = start + 1 # + 1 not mandatory
while end < len(s) and (s[end].isalpha() or s[end] == ' '):
# s[end].isspace() ok alternate
end += 1
return s[start:end] # no +- !
#### 6. Grid Donut
def sudden_donut(grid, x, y):
if grid.get(x, y) != 'b':
return False
if grid.in_bounds(x + 2, y + 1) and grid.get(x + 2, y + 1) == 'c':
grid.set(x + 2, y, 'd') # not y + 1, will be in-bounds
return True
return False
#### 7. Image
# a. - twice as wide
out = SimpleImage.blank(image.width * 2, image.height)
# b. - a very dense line
pixel_out = out.get_pixel(x * 2, out.height - y - 1)
#### 8. Draw
def draw_pct(canvas, width, height x, y, pct):
# strategy: (fraction) * max
y_add = (pct / 100) * y
canvas.draw_line(x, y, x, y - y_add)
#### 9. Dict-Crypt
def dict_crypt(alphas, indexes, s):
result = ''
for ch in s:
if ch in alphas:
idx1 = alphas.index(ch)
idx2 = indexes[idx1]
result += alphas[idx2]
else:
result += ch
return result
#### 10. Dict-Vote
def find_votes(states, locs):
result = []
for loc in locs:
state = loc[:2]
zip = int(loc[3:]) # int() here is minor
if state in states:
zips = states[state] # var points to nested dict
if zip in zips:
count = zips[zip]
pair = (loc, count)
result.append(pair)
# we solve with multiple lines, but can pack into one:
# result.append((loc, zips[zip]))
return result
#### 11. Capstone
# Loop over lines, use split() to get parts of each line
def read_posts(filename):
posts = {}
with open(filename) as f:
for line in f:
line = line.strip()
pass
parts = line.split(',')
url_start = parts[0]
for s in parts[1:]: # slice to omit first
pair = s.split('^') # id^urlend
id = pair[0] # influencer id
url = url_start + pair[1] # form whole url
# have id/url .. load up dict
if id not in posts:
posts[id] = {}
urls = posts[id] # var points to nested dict
# standard dict-count per url
if url not in urls:
urls[url] = 0
urls[url] += 1
return posts
def print_posts(posts):
for id in sorted(posts.keys()):
print(id)
urls = posts[id]
for url in sorted(urls.keys()):
print(' ' + url, urls[url]) # ok if use + instead of ,