Stanford, Winter 2021-22. Solutions code at the end.
# 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() 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".
>>> 20 - 5 + 2
result:
>>> 57 // 10
result:
>>> s = 'Spring'
>>> s[2:]
result:
>>> d = {'c': 4, 'a': 5, 'd': 13, 'b': 2}
>>> 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 multiplied by 10.
>>> nums = [2, 7, 20]
# yields: [20, 70, 200]
# b. Given a list of non-empty strings, compute a list
# where for each string, take the lowercase form of its
# first char and add a '#' at its start
>>> strs = ['is', 'Mystery', 'How']
# yields: ['#i', '#m', '#h']
# c. 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 stars
>>> movies = [('movie1', 110, 4), ('Titanic', 194, 5), ('movie2', 105, 3)]
# yields: [('Titanic', 194, 5), ('movie1', 110, 4), ('movie2', 105, 3)]
Given a string s, return a string made of all the alphabetic chars of s followed by all the non-alphabetic chars of s. Solve with one or two loops.
'a12bc$' -> 'abc12$' '123123A' -> 'A123123' '$$x$' -> 'x$$$'
def alpha_first(s):
pass
What is better than a hashtag? Two hashtags like '##yay.'
Find the first double-hash in a string and return the tag following the double-hash. The end of the tag will be be marked by a period '.' or by the end of the string. The tag may contain any type of char. If there is no double-hash, return None. Examples:
'xx ##spring. xx' -> 'spring' 'xx ##summer' -> 'summer' 'x#. ##l@@k!.' -> 'l@@k!' 'xx ##.' -> '' 'xx #nope. xx' -> None 'abc' -> None
def double_hash(s):
pass
We'll say a "word" is 1 or more alphabetic or dash chars '-', but always ends with an alphabetic char like 'donut-day-now'. Given a non-empty string s, first find the last char in the last word in s using a while loop working backwards from the end of the string. For example, for string 'xx abc-def**', loop to find the 'f'.
Then use a second while loop to find the beginning of the last word and ultimately return the whole word. If there is no word in s, return None. Examples:
'xx abc-def**' -> 'abc-def' 'owl apple-pie$$!' -> 'apple-pie' 'mouse abc-xyz-def^.^' -> 'abc-xyz-def' 'x.abc$' -> 'abc' '$$$' -> None '$x$' -> 'x'
def last_word(s):
pass
Suppose you are working on a video game using a grid, and each square in the grid is either a squirrel 's', a bear 'b', honey 'h', or empty None. The "power" move is one where there's a bear and a squirrel, and the squirrel is next to honey in a particular direction. For the power move in that case, the bear and the squirrel switch places.
a. Write code for the attempt_power() function that works as follows: Given the guaranteed in-bounds (x1, y1) and (x2, y2), check these conditions:
1. (x1, y1) contains a squirrel
2. (x2, y2) contains a bear
3. The square diagonally above and to the right of the squirrel contains honey
If the three conditions above are met, perform the power move: put a bear in the squirrel square, and a squirrel in the bear square (so in effect, they exchange places, and the bear is next to honey). Return the changed grid. In all other cases, return the grid unchanged. Essentially, the function does the move if possible, and otherwise does nothing.
b. (Assume the code for part (a) works correctly. You can get full credit for this part, regardless of your code for part (a)). The power_points() function takes in a list of tuple len-2, each tuple representing the (x, y) of potential squirrel square in the grid.
points = [(1, 3), (2, 4), .. # potential squirrel at (x=1, y=3), (x=2, y=4) ..
For each (x, y) in the list, attempt the power move with the potential squirrel at that (x, y) and the bear in the square immediately below. The (x, y) in the list and the squares immediately below them are guaranteed to be in-bounds, but everything else needs to be checked.
def attempt_power(grid, x1, y1, x2, y2):
pass
def power_points(grid, points):
pass
Given a canvas, the canvas width and height, and a temps list of temperature values. Each temperature value is in the range 0..212 inclusive. For each temp value, draw a 1-pixel horizontal line starting at the rightmost column of pixels and extending towards the left side of the canvas, its length proportionate to the temperature. For a temp of 212, the line should end on the leftmost column of pixels. For a temp of 0, the line should begin and end on the rightmost column of pixels. Draw the first temperature at y = 0, the next at y = 1, and so on.
Reminder: Use canvas.draw_line(x1, y1, x2, y2) to draw each line.
def draw_temps(canvas, width, height, temps):
pass
Suppose we have a "dates" list of 'yyyy-mm-dd' date strings corresponding to earthquake events, like this:
['2022-03-14', '2020-03-01', '2021-12-31', '2022-02-01']
We want to count how many events there are for each month, ignoring the year and day. Write code to build and return a counts dict with an int key for each month, e.g. 12 is December, and its value is the number of events for that month. For the above list, the counts dict would be:
{
3: 2,
12: 1,
2: 1
}
def month_count(dates):
pass
Suppose we have a dict with int keys and string values, like this:
{
100: 'radish',
200: 'apple',
101: 'radish',
202: 'pear',
201: 'donut',
102: 'radish',
203: 'pear',
103: 'grape',
205: 'pear'
}
We'll say a key/value pair is "special" when a key and that key + 1 have the same value. In the example above, key 100 is special because it and the key 101 have the value, 'radish'. The key 101 is also special, sharing the same value with 102. Finally, the key 202 is special with the same value as 203.
Given an input dict structured like the example above, compute and return a list of all the special key values in increasing order. For the example above, the result would be [100, 101, 202]
def the_special(d):
pass
Suppose you create a joke crypto currency called "foolz", but then it accidentally becomes super popular and now you have all this data to organize. Typical.
You have a text file representing foolz transactions. The text data looks like this with words separated by commas:
t26691,w45307,w87755 t77340,w23001,w45307,w55820 ...
The first word on each line is a foolz transaction id, followed by one or more wallet ids involved in that transaction (treating each id as a string). Any of these ids may occur again on later lines.
In the foolz_errand() function, read in all the lines to build a dict using wallet ids as the keys. The basic file-reading code is provided as a starting point. For each wallet id, build a list of all the transaction ids that appeared on a line with that wallet id. Do not include duplicates in the list of transaction ids. The resulting dict looks like this:
{
'w45309': ['t26691', 't77340', ...],
'w87755': ['t99800;, 't26691', ...],
...
}
Once all the data is read in, print out all the wallet ids in sorted order, one per line. For each wallet id, print out all its transaction ids in sorted order, one per line, indented by one space, like this:
w45309 t26691 t30001 t34500 ... w45406 t10045 t11920 ..
def foolz_errand(filename):
wallets = {}
with open(filename) as f:
for line in f:
line = line.strip() # remove \n
pass
## 2. Warmup
>>> 20 - 5 + 2
result: 17
>>> 57 // 10
result: 5
>>> s = 'Spring'
>>> s[2:]
result: 'ring'
>>> d = {'c': 4, 'a': 5, 'd': 13, 'b': 2}
>>> sorted(d.keys())
result: ['a', 'b', 'c', 'd']
## 3. One-Liners
map(lambda x: x * 10, nums)
[val * 10 for val in nums]
map(lambda s: '#' + s[0].lower(), strs)
['#' + s[0].lower() for s in strs]
sorted(movies, lambda movie: movie[2], reverse=True)
## 4. String-1
def alpha_first(s):
alpha = ''
non_alpha = ''
for ch in s:
if ch.isalpha():
alpha += ch
else:
non_alpha += ch
return alpha + non_alpha
# -instead of "else" could use "if not ch.isalpha()"
# -could have one result, loop1 adds alpha, then loop2
# adds non-alpha
## 5. String-2
def double_hash(s):
hash = s.find('##')
if hash == -1:
return None
dot = s.find('.', hash + 2) # + 2 optional
if dot != -1:
return s[hash + 2:dot]
# no dot, so use end of string
return s[hash + 2:]
## 6. String-3
def last_word(s):
# Move end to last alpha
end = len(s) - 1
while end >= 0 and not s[end].isalpha():
end -= 1
if end < 0:
return None
# Move start over alpha-dash - parens vs. and/or
start = end - 1
while start >= 0 and (s[start].isalpha() or s[start] == '-'):
start -= 1
return s[start + 1:end + 1]
## 7. Grid
def attempt_power(grid, x1, y1, x2, y2):
# make sure there is a squirrel and a bear
if grid.get(x1, y1) != 's' or grid.get(x2, y2) != 'b':
return grid
# check to make sure the square above-right of squirrel is honey
if not grid.in_bounds(x1 + 1, y1 - 1) or grid.get(x1 + 1, y1 - 1) != 'h':
return grid
# do the swap
grid.set(x1, y1, 'b')
grid.set(x2, y2, 's')
return grid
def power_points(grid, points):
for pt in points:
attempt_power(grid, pt[0], pt[1], pt[0], pt[1] + 1)
## 8. Draw
def draw_temps(canvas, width, height, temps):
for i in range(len(temps)):
temp = temps[i] # 0..212
y = i
# extend how far in x direction?
extend = (temp / 212) * (width - 1)
canvas.draw_line(width - 1, y, width - 1 - extent, y)
## 9. Dict-1
def month_count(dates):
counts = {}
for date in dates:
# Could use .find() to locate dashes
# but in fact they are at 4 and 7
mo_str = date[5:7]
mo = int(mo_str)
# Then its straight dict-count algo
if mo not in counts:
counts [mo] = 0
counts[mo] += 1
return count
## 10. Dict-2
def the_special(d):
result = []
for k in d.keys():
k2 = k + 1 # "next" key number
if k2 in d: # in there with same value?
if d[k] == d[k2]:
result.append(k)
return sorted(result)
## 11. Capstone Foolz Errand
def foolz_errand(filename):
wallets = {}
with open(filename) as f:
for line in f:
line = line.strip()
parts = line.split(',')
tid = parts[0]
for wid in parts[1:]
if wid not in wallets:
wallets[wid] = []
tids = wallets[wid]
if tid not in tids:
tids.append(tid)
# printing code
for wid in sorted(wallets.keys()):
print(wid)
tids = wallets[wid]
for tid in sorted(tids):
print(' ' + tid)