Stanford, Winter 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 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) # 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".
>>> 20 - (1 + 2 * 3) + 1
result:
>>> 57 % 5
result:
>>> s = 'Python'
>>> s[1:4]
result:
>>> d = {'tx': 146, 'ca': 2, 'ar': 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 * 10
>>> nums = [2, 7, 20, 9]
# yields: [20, 70, 200, 90]
# b. Given a list of strings, compute a list
# where each new string is an uppercase version
# of the original with parenthesis around 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 fanciness
>>> cities = [('Merced', 1, 5), ('Palo Alto', 6, 9), ('Vale', 9, 8)]
# yields: [('Vale', 9, 8), ('Palo Alto', 6, 9), ('Merced', 1, 5)]
Given a string s, find the first and second '#' in s. If both are present, return the chars before the first followed by the chars after the second, so 'ab#xyz#cd' returns 'abcd'. Return None if there are not at least two '#'. Use str.find().
'ab#xyz#cd' -> 'abcd' '1#aaaa#zzz' -> '1zzz' '1##z' -> '1z' '1#z' -> None
def outside(s):
Given a string s. Compute and return a new string. For every alphabetic char in s, the new string should have the uppercase version of that char. For all other chars (i.e. not alphabetic) the new string should have a '@' char.
'aBc-1z$' -> 'ABC@@Z@' 'XyZ..' -> 'XYZ@@' '^^^' -> '@@@'
def alpha_up(s):
pass
Our new social network called "Digital" gives each user an id that begins with '@@' followed by a series zero or more digits and dashes, e.g. '@@12-00--912-'. Given a string s, return the first Digital id in s, not including the '@@' from the start of the result. Or if there is no Digital id return None. Use str.find() and a while loop.
'woot @@912--4-5xx' -> '912--4-5' '@@1' -> '1' 'hi@@-4-hi@@7' -> '-4-'
def digital_id(s):
pass
Suppose we are working on a new grid based game called Squirrel Fun. Every square is either acorn 'a', squirrel 's', or empty None. The levicorn() function attempts to do the levicorn move, taking in a grid, an in-bounds x, y, and an int n.
def levicorn(grid, x, y, n):
The levicorn() move has two conditions:
1. The square at (x, y) must contain a squirrel
2. The square 1 to the left and n squares down from the squirrel must contain an acorn. The parameter n will be 1 or more.
If both conditions are met, the function should move the acorn up, one square higher in the grid and return True. If there is an acorn in the correct square, it is guaranteed that the square above the acorn will be in-bounds and empty, so the code does not need to check that. If the conditions are not met, the function should leave the grid unchanged and return False. Here is an example, calling the function at (1, 0) with n = 2:
def levicorn(grid, x, y, n):
This problem is an application of the standard dict-count algorithm. Given a words list of word strings, construct and return a counts dict with a key for each word in the list, and its value is the number of times that word appears in the list. Store and count the lowercase version of each word.
words = ['Tea', 'time', 'tea', 'COFFEE'] ->
{'tea': 2, 'time': 1, 'coffee': 1}
def word_count(words):
We want to analyze people's favorite food, paying attention to which state each person lives in. We'll say a foods dict looks like this:
foods = {
'apple': {'ca': 123, 'nj': 14, 'tx': 214, 'wi': 99},
'peach': {'tx': 35, 'ga': 592},
}
The key of the foods dict is one food, e.g. 'apple'. Its value is a nested dict, which counts how many people in each state liked that food. For example, in the above example, 123 people in 'ca' liked 'apple'.
a. Write code for the add_food(foods, food, state) function that takes in a foods dict, a food e.g. 'apple', and a state e.g. 'ca', and adds that data to the foods dict. Each call to the add_food() function corresponds to one more person liking that food for that state. Return the foods dict in all cases.
def add_food(foods, food, state):
b. Write 2 Doctests for add_food(). For credit on the second Doctest, there must be an if-statement in your add_food() that gets a different True/False compared to the first Doctest. In other words, the Doctests should be different enough to prompt the code to take different actions. Simplifying suggestion: note that the empty dict { } is a valid foods dict.
>>> # Doctest syntax reminder:
>>> double_char('Hello')
'HHeelllloo'
c. Write a function food_states(foods, food), which takes the foods dict and a food. It constructs and returns a list of all the states where 100 or more people like that food. Return the empty list if the food is not in the data. For example with this foods data:
foods = {
'apple': {'ca': 123, 'tx': 14, 'nj': 214, 'wi': 99},
'banana': {'fl': 500, 'mi': 4},
...
}
Calling the function for the food 'apple' returns the list ['ca', 'nj']. The states may be in any order in the returned list.
def food_states(foods, food):
We have a nums dict where each key is an int, and its value is a list of ints, like this:
nums = {
23: [14, 52, 19, 22],
52: [1, 113, 113, 113],
113: [16],
22: [16]
}
In the above example, the key 23 has the nested list [14, 52, 19, 22]
We'll say a number in such a nested list is magic if it also appears as a key in the outer nums dict.
Write code for a count_magic(nums, key) function that takes in the nums dict and a "key" int. Return the count of the magic numbers in the list for that key. Return -1 if the key is not in the dict. For example the magic count for key = 23 is 2, since 52 and 22 are magic.
# Example magic counts with above dict: key = 23 -> 2 key = 52 -> 3 key = 22 -> 0 key = 99 -> -1
def count_magic(nums, key):
Given a canvas, its width and height, and a vals list of numbers, with each number in the range 0 .. 100 inclusive. Write code to go through all the numbers in the vals list. Draw a horizontal line at y=0 for the first value, y=1 for the next value, and so on. The horizontal line should start at the leftmost pixel, extending towards the right side proportionate to the value, ending on the rightmost pixel of the canvas when the value is 100. Assume the canvas is tall enough to hold all the lines.
def draw_vals(canvas, width, height, vals):
You have a data file of lines. Each line is divided into "parts" by commas, and each part is in one of two patterns explained below.
dog@noun,eat@verb,verb-pray-love fluffy@adjective,noun-apple,dog@noun
1. The "at-pattern" looks like 'dog@noun' - first there is a word, e.g. 'dog', then an at-sign '@', then a category, e.g. 'noun'. The at-pattern text will always contains one at-sign and no dashes.
2. The "dash-pattern" looks like 'verb-eat-pray-love' - here the category is first, e.g. 'verb', followed by one or more words, all separated by dashes '-' . The dash-pattern text will always contain one or more dashes and no at-signs. The dash pattern will only appear in the data after a category has been established, so processing a dash-pattern, you can assume the category exists in the dict.
Part-a. Write code to read in all the lines from the given filename, building and returning a "cats" dict (short for "categories") with a key for each category word. The value for each category should be a nested list of all the words with that category in the file. A word may appear in a list multiple times. For example, here is the cats dict built from the above two lines:
cats = {
'noun': ['dog', 'apple', 'dog'],
'verb': ['eat', 'pray', 'love'],
'adjective': ['fluffy']
}
def read_cats(filename):
cats = {}
with open(filename) as f:
for line in f:
line = line.strip()
Part-b. Write a print_cats() function that takes in the "cats" dict produced by Part-a, and prints out all the categories in sorted order, one per line. For each category, print out all its words, including duplicates, in sorted order, each indented by one space like this:
noun apple apple cat dog ... zebra ... verb argue bore ... vow
def print_cats(cats):
#### 1. Short Answer
14
2
'yth'
['ar', 'ca', 'tx']
#### 2. 1-Liners
[n * 10 for n in nums]
['(' + s.upper() + ')' for s in strs]
sorted(cities, key=lambda city: city[1], reverse=True)
#### 3 String-1
def outside(s):
a = s.find('#')
b = s.find('#', a + 1) # + 1 is needed
if a == -1 or b == -1: # just b is sufficient
return None
return s[:a] + s[b + 1:]
#### 4 String-2
def alpha_up(s):
result = ''
for ch in s: # for/i/range ok too
if ch.isalpha():
result += ch.upper()
else:
result += '@'
return result # Could .upper() here instead
#### 5 String-3
def digital_id(s):
at = s.find('@@')
if at == -1:
return None
# Advance end past digits/dash
end = at + 2
while end < len(s) and (s[end].isdigit() or s[end] == '-'):
end += 1
return s[at + 2:end]
#### 6 Grid
# Here nested if-tests for the success condition
def levicorn(grid, x, y):
if grid.get(x, y) == 's':
if grid.in_bounds(x - 1, y + n) and grid.get(x - 1, y + n) == 'a':
grid.set(x - 1, y + n, None)
grid.set(x - 1, y + n - 1, 'a')
return True
return False
# Here return False early if first condition fails
def levicorn(grid, x, y):
if grid.get(x, y) != 's':
return False
if grid.in_bounds(x - 1, y + n) and grid.get(x - 1, y + n) == 'a':
grid.set(x - 1, y + n, None)
grid.set(x - 1, y + n - 1, 'a')
return True
return False
#### 7 Word Count
def word_count(words):
counts = {}
for word in words:
low = word.lower()
if low not in counts:
counts[low] = 0
counts[low] += 1
return counts
#### 8 Foods
# foods is a dict
# food and state are strings
def add_food(foods, food, state):
# There is no loop here
if food not in foods:
foods[food] = {}
counts = foods[food] # var points to nested
if state not in counts:
counts[state] = 0
counts[state] += 1
return foods
# Foods Doctests
# foods parameter must be given some value e.g. {}
>>> add_food({}, 'apple', 'ca')
{'apple': {'ca': 1}}
>>>
>>> add_food({'apple': {'ca': 1}}, 'apple', 'tx')
{'apple': {'ca': 1, 'tx': 1}}
# ^ difference: does not create nested dict
# any difference between the tests is sufficient
def food_states(foods, food):
result = []
# No loop here, use key with in/[]
if food in foods:
counts = foods[food] # var points to nested
for state in counts.keys():
if counts[state] >= 100:
result.append(state)
return result
#### 9 Magic
def count_magic(nums, key):
# Do not need to loop on nums, just in/[]
if key not in nums:
return -1
# Go through list and count
count = 0
lst = nums[key]
for n in lst:
if n in nums:
count += 1
return count
#### 10 Draw
def draw_vals(canvas, width, height, vals):
for i in range(len(vals)):
y = i
val = vals[i]
# add = fraction * max
x_add = (val / 100) * (width - 1)
canvas.draw_line(0, y, x_add, y)
#### 11 Capstone Cats
def read_cats(filename):
cats = {}
with open(filename) as f:
for line in f:
line = line.strip()
parts = line.split(',')
# Go through parts, check type of each one
for part in parts:
if '@' in part:
# Could slice manually, here using split
lst = part.split('@')
word = lst[0]
cat = lst[1]
if cat not in cats:
cats[cat] = []
words = cats[cat]
words.append(word)
if '-' in part: # Could use else here
lst = part.split('-')
cat = lst[0]
# Problem statement says
# we can assume words list exists
words = cats[cat]
# Append all the words, skipping 0
for word in lst[1:]:
words.append(word)
return cats
def print_cats(cats):
for cat in sorted(cats.keys()):
print(cat)
words = cats[cat]
for word in sorted(words):
print(' ' + word)