Stanford, Fall 2021-22
# 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() sorted(lst, key=lambda, reverse=True)
String functions:
isalpha() isdigit() isspace() isupper() islower()
startswith() endswith()
find() upper() lower() split() strip()
replace() [join()] [format()] [splitlines()]
List functions:
append() extend() pop() index() map()
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, fill='red')
canvas.create_text(x, y, text='str', fill='red', anchor=tkinter.SW)
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".
>>> 10 + 3 * 4 result: >>> 64 // 10 result: >>> 64 % 10 result: >>> s = 'Corona' >>> s[:3] result: >>> s[3:] 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 minus 5.
>>> nums = [10, 7, 20]
# yields: [5, 2, 15]
# b. Given a list of strings, compute a list where
# each string is converted to uppercase and a '!'
# is added at its end.
>>> strs = ['is', 'Mystery', 'How']
# yields: ['IS!', 'MYSTERY!', 'HOW!']
# c. Given a list of 2-digit strings, compute a list
# of the int values of their first digits.
>>> strs = ['12', '98', '61', '42']
# yields: [1, 9, 6, 4]
# d. Given a list of tuples about movies: (movie, minutes, stars)
# movie=string title, minutes=int minutes running time,
# and stars = 1..5 stars rating, e.g. ('Titanic', 194, 5)
# write a sorted/lambda expression to order the movies
# in decreasing order by minutes
>>> movies = [('movie1', 100, 5), ('Titanic', 194, 5), ('movie2', 120, 4)]
# yields: [('Titanic', 194, 5), ('movie2', 120, 4), ('movie1', 100, 5)]
Given a string s, return a version of s without any digit or '$' chars.
'$abc123' -> 'abc' '$x$x99' -> 'xx' '9a^$$bc12#' -> 'a^bc#'
def without_dig(s):
pass
Given a string s, find the first and second instances of substring '@@@' in s, and return the 1 or more chars between them. If there are not 2 '@@@' or there are no chars between them, return None
'xx@@@dog@@@yy' -> 'dog' 'xx@@@dogy' -> None 'xxx@@@A@@@yyy' -> 'A' 'xxx@@@@@@yyy' -> None 'xxx' -> None
def ats(s):
pass
Given a string s, find the first 'host:' in s followed by a substring made of zero or more alphabetic or period '.' chars. Return the alpha/. substring after the 'host:' or None if there is no 'host:'
'xx host:foo.com yy' -> 'foo.com' 'abc host:www.bleh.edu' -> 'www.bleh.edu' 'host:ABC9' -> 'ABC' 'host:##' -> '' 'xyz' -> None
def host(s):
pass
(Note: this is similar to one of our practice problems, but with some differences.)
Given a string s, write a while loop to find
the first alphabetic char in s.
Write a second while loop to find the last digit char
in s. If both of these chars exist and the digit char
is after the alpha char, consider the substring
starting at the alpha char and continuing through and including the digit char.
Return a string made of just the alphabetic and digit chars of that substring.
Otherwise, if there is not a first alpha followed by a last digit char, return None.
'^^99abc$$123xx' -> 'abc123' '1.a.x.9.9.z' -> 'ax99' 'ax99' -> 'ax99' '99ax' -> None 'abc' -> None '123' -> None
def alpha_dig(s):
pass
Given an image filename and ints a and b which are 1 or more. Create a new out image with empty columns a pixels wide on both sides and a pure black horizontal stripe b pixels high across the top of the out image. Place a vertically flipped copy of the original image below the black stripe and between the two a columns. The starter code includes an a-b-c outline and some code you can use, but any solution which gets the right output is fine.
def black_top(filename, a, b):
image = SimpleImage(filename)
# a. Create out image
out = SimpleImage.blank( ??????? )
# b. Create stripe
pass
# your code here
# c. Loop over original image, write flipped copy
for y in range(image.height):
for x in range(image.width):
pass
# your code here
return out
Suppose you are working on a video game using a grid, each square in the grid is either sparkle 's', a bear 'b', or empty None.
A sparkle-combine event at x,y in this game happens when (1) the x,y square is empty, (2) there is sparkle in the square diagonally up-right from x,y, (3) there is also sparkle in the square diagonally down-left from x,y. When all three of those preconditions are met, the sparkle-combine changes the two sparkle squares to be empty, and sets x,y to be sparkle.
Write code for a sparkle_combine(grid, x, y) function which, given a grid and in-bounds x,y, and detects if the preconditions for sparkle-combine are met, and if so performs the sparkle-combine on the grid and returns True. Otherwise leave the grid unchanged and return False.
def sparkle_combine(grid, x, y):
pass
Reminder: the canvas draw_line function:
canvas.draw_line(x1, y1, x2, y2) - draws a line from x1,y1 to x2,y2
As on the Quilt homework, this function takes in the (left, top, width, height) of a figure positioned on the canvas, plus two int parameters, and draws lines within that figure.
The provided code draws a blue rectangle at the outer edge of the figure.
Given ints a and n which are 2 or more. Do not draw any lines in a stripe a pixels tall at the top of the figure. Draw a series of n horizontal lines across the figure. The topmost line just below the a stripe, and the bottommost line at the bottom edge of the figure, and with the other lines distributed evenly in between.
def draw(canvas, left, top, width, height, a, n):
canvas.draw_rect(left, top, width, height, color='lightblue')
pass
San Francisco is more associated with fog than with sunshine. Suppose we have a sf dict of data where each key is a year-month-day date string like '2021-12-6', and its value is the fahrenheit high temperature reading for that day in San Francisco. The data is a little spotty - some dates are in the dict and some are not. The dict looks like this:
{'2021-12-6': 68, '2021-12-3': 65, '2021-11-29': 64, '2021-11-30': 68}
a. Suppose we want to know how often each temperature occurs in the data. Write code in the temp_counts(sf) function to compute a counts dict, where each key is an int temperature value from the data, and its value is a count of how many times that temperature appears.
For example, with the 4 values above, the counts dict would be
{68: 2, 65: 1, 64: 1}
b. Suppose we have an sf dict with the San Francisco data, and also a pa dict with the same sort of data for Palo Alto. Write code for the sf_hot(sf, pa) function that, given the two dicts, computes a new dict with a key for each date such that both dicts have that date and that date was hotter in San Francisco than in Palo Alto. In the result dict, the value for each hotter day should be the sf temperature. For example, here is the sf_hot() output for two input dicts:
# e.g. with sf=
{'2021-12-6': 68, '2021-12-3': 65, '2021-11-29': 64, '2021-11-30': 68}
# and pa=
{'2021-12-6': 99, '2021-12-3': 99, '2021-11-29': 61, '2021-1-1': 65}
# sf_hot =
{'2021-11-29': 64}
# a.
def temp_counts(sf):
pass
# b.
def sf_hot(sf, pa):
pass
The code for this problem will take in a char ch and return its encrypted form. As a simplification, all alphabetic chars in this problem will be lowercase.
a. The encrypted form of digit chars will be defined by a list length 10 of the chars '0' .. '9' in some order.
['8', '3', '4', .. '5']
The input char '0' should be encrypted with the char at index 0 in the list (e.g. '8' in the list above), the char '1' encrypted with the char at index 1, and so on.
b. We'll say that a "crypt" dict has a lowercase char like 'a' for each key, and its value like 'z' is the encrypted form of that char.
Given an int n which is 1 or more, a "super" dict has keys for the int values 0, 1, 2 .. n-1. For each key, the value is a nested crypt dict. The super-crypt also contains a 'digits' key, and its value is a list of the 10 digit chars in some order.
# super dict with n=3
{
0: {'a': 'z', 'x': 'y'},
1: {'o': 'm', 'i': 'c'},
2: {'d': 'e', 'l': 't'},
'digits': ['8', '3', '4', .. '5'] # 10 digit chars
}
To encrypt a char, if the char is a digit, return its digit encrypted form. Otherwise check if the char is in the crypt for key 0, and if it is return the value from that crypt. Otherwise try the crypt for key 1, and so on until there is a match. If there is no match, return the char unchanged.
# Examples of encrypting a ch # with above super dict '0' -> '8' # it's a digit '1' -> '3' 'a' -> 'z' # found in crypt 0 'i' -> 'c' # found in crypt 1 'd' -> 'e' # found in crypt 2 '$' -> '$' # not found
def super_crypt(super, n, ch):
pass
Suppose we have an input file, and each line is divided into left and right parts, separated by one '@', like this:
1:14:1@oh,no 0:16@no,is,empty 10:20:6:6@is,mystery,how
There will be exactly one '@' per line. The left part is made of 2 or more int values separated by colons. The right part is made of 2 or more non-empty, alphabetic words separated by commas.
For each line, consider the sum of the ints of the left part - for example the first two lines above have sum 16, and the third line has sum 42. Build a "sums" dict where each sum of a line is a key, and its value is a list of all the words that appear on a line with that sum. Do not include duplicate words in the list. For example, here is the sums dict for the above lines:
{
16: ['oh', 'no', 'is', 'empty'],
42: ['is', 'mystery', 'how']
}
After the dict is built, print out its contents. Print the sums in increasing order, one per line. For each sum, print its words, one per line, with a space added to the left of each word to indent it (the words for each key can be in any order), like this:
16 oh no is empty 42 is mystery how
def sum_key(filename):
with open(filename) as f:
for line in f:
line = line.strip() # remove \n
pass
## 2 Warmups
>>> 10 + 3 * 4
result: 22
>>> 64 // 10
result: 6
>>> 64 % 10
result: 4
>>> s = 'Corona'
>>> s[:3]
result: 'Cor'
>>> s[3:]
result: 'ona'
## 3 One-liners
a. [n - 5 for n in nums]
or map(lambda n: n - 5, nums)
b. [s.upper() + '!' for s in strs]
c. [int(s[0]) for s in strs]
d. sorted(movies, key=lambda tup: tup[1], reverse=True)
## 4
def without_dig(s):
result = ''
for ch in s:
if not ch.isdigit() and ch != '$':
result += ch
return result
## 5
def ats(s):
first = s.find('@@@')
if first == -1:
return None
second = s.find('@@@', first + 3)
if second == -1:
return None
inner = s[first + 3:second]
if inner == '': # of if first + 3 == second:
return None
return inner
## 6
def host(s):
start = s.find('host:')
if start == -1:
return None
begin = start + 5
end = begin
while end < len(s) and (s[end].isalpha() or s[end] == '.'):
end += 1
return s[begin:end]
## 7
def alphadig(s):
start = 0
while start < len(s) and not s[start].isalpha():
start += 1
end = len(s) - 1
while end >= 0 and not s[end].isdigit():
end -= 1
if end < start:
return None
# pull out substring
sub = s[start:end + 1]
result = ''
for ch in sub:
if ch.isdigit() or ch.isalpha():
result += ch
return result
## 8 Image
def black_top(filename, a, b):
image = SimpleImage(filename)
# a. Create out image
out = SimpleImage.blank(image.width + 2 * a, image.height + b)
# b. Create stripe
for y in range(b):
for x in range(out.width):
out_pix = out.get_pixel(x, y)
out_pix.red = 0
out_pix.green = 0
out_pix.blue = 0
# c. Loop over original image, write flipped copy
for y in range(image.height):
for x in range(image.width):
pix = image.get_pixel(x, y)
out_pix = out.get_pixel(x + a, out.height - 1 - y)
out_pix.red = pix.red
out_pix.green = pix.green
out_pix.blue = pix.blue
return out
## 9 Grid
def sparkle_combine(grid, x, y):
# could use "or" for all these cases, but here
# just using a series of ifs
if grid.get(x, y) != None:
return False
if not grid.in_bounds(x + 1, y - 1): # up-right
return False
if not grid.in_bounds(x - 1, y + 1): # down-left
return False
if grid.get(x + 1, y - 1) == 's' and grid.get(x - 1, y + 1) == 's':
grid.set(x + 1, y - 1, None)
grid.set(x - 1, y + 1, None)
grid.set(x, y, 's')
return True
return False
## 10 Draw
def draw(canvas, left, top, width, height, a, n):
canvas.draw_rect(left, top, width, height, color='lightblue')
for i in range(n):
y_add = (i / (n - 1)) * (height - a - 1)
canvas.draw_line(left, top + a + y_add, left + width - 1, top + a + y_add)
## 11 - temp_counts - a few solution patterns:
# temp_counts sol 1
def temp_counts(sf):
counts = {}
for key, val in sf.items():
if val not in counts:
counts[val] = 0
counts[val] += 1
return counts
# temp_counts sol 2
def temp_counts(sf):
counts = {}
for key in sf.keys():
val = sf[key]
if val not in counts:
counts[val] = 0
counts[val] += 1
return counts
# temp_counts sol 3
def temp_counts(sf):
counts = {}
for key in sf.keys():
val = sf[key]
if val not in counts:
counts[val] = 1
else:
counts[val] += 1
return counts
# sf_hot solution
# joke solution: just return {}
# since SF is never hotter than PA
def sf_hot(sf, pa):
result = {}
for day in sf.keys():
temp = sf[day]
if day in pa and temp > pa[day]:
result[day] = temp
return result
## 12
def super_crypt(super, n, ch):
if ch.isdigit():
idx = int(ch) # key!
digits = super['digits']
return digits[idx]
for i in range(n):
crypt = super[i]
if ch in crypt:
return crypt[ch]
return ch
## 13
def sum_key(filename):
with open(filename) as f:
sums = {}
for line in f:
line = line.strip() # trim \n
at = line.find('@')
left = line[:at]
lefts = left.split(':')
right = line[at + 1:]
rights = right.split(',')
# figure the sum
sum = 0
for s in lefts:
sum += int(s)
# dict-logic
if sum not in sums:
sums[sum] = []
# Put all the words in there
words = sums[sum]
for word in rights:
if word not in words:
words.append(word)
for num in sorted(sums.keys()):
print(num)
words = sums[num]
for word in words:
print(' ' + word)