Quiz 2 Review

August 1st, 2021

Written by Juliette Woodrow, Anna Mistele, John Dalloul, Brahm Capoor, and Nick Parlante

PyCharm Project For One Liners - Capstone CS106A Problems

This is a handout with some practice problems to help you study for the quiz. In addition to these problems, you can do additional problems on the experimental server as well as checkout the grid problem from the section 3 handout as well as all problems in the section 5 handout. We recommend that you try a problem before looking at the solution. Also, try timing yourselves when working through these to simulate the quiz envrionment. If you have any questions, feel free to come to LaIR, office hours, post on Ed, or email Tara.

Grids

Jump Down

For this problem you will implement a new operation that works on one vertical column of squares in the grid. Every square in the grid is either a rock 'r', sand 's', or empty None. The jumpdown(grid, x, n) algorithm works as follows: The parameter x will be an in-bounds x value, indicating the column to work on. The parameter n will be 1 or more, the number of squares down to move each sand.

Look at every "candidate" square in the column, working from the bottom of the column to the top. If the candidate square contains sand, the sand will be moved. Its "destination" square is n squares straight down, (n=1 meaning the square immediately below). If the destination is empty, move the candidate sand there. If the destination is not empty or is out of bounds, then erase the candidate sand from the grid. Obstacles between the candidate sand and its destination do not matter - the sand jumps to its destination.

        
def jumpdown(grid, x, n):
    """
    >>> grid = Grid.build([['s', 's'], ['r', None], [None, 'r']])
    >>> jumpdown(grid, 0, 2)
    [[None, 's'], ['r', None], ['s', 'r']]
    >>> grid = Grid.build([['s', 's'], ['r', None], [None, 'r']])
    >>> jumpdown(grid, 1, 2)
    [['s', None], ['r', None], [None, 'r']]
    >>> grid = Grid.build([['s', None], ['s', None], [None, None]])
    >>> jumpdown(grid, 0, 1)
    [[None, None], ['s', None], ['s', None]]
    """
    pass

Yellowstone

This question is from an old quiz.

There are two functions for this problem, and you can get full credit for each function independent of what you do on the other function. We have a Grid representing Yellowstone park, and every square is either a person 'p', a yelling person 'y', a bear 'b', or empty None.

is_scared(grid, x, y): Given a grid and an in-bounds x,y, return True if there is a person or yelling person at that x,y, and there is a bear to the right of x,y or above x,y. Return False otherwise. (One could check more squares, but we are just checking two.)
run_away(grid): This function implements the idea that when a person is scared of a bear they begin yelling and try to move one square left. Loop over the squares in the grid in the regular top to bottom, left to right order (this loop is provided in the starter code). For each square, if is_scared() is True, (a) set the person stored in the grid to 'y' (i.e. they are yelling). (b) Also, if there is an empty square to their left, then move the person to that square leaving their original square empty. You may call is_scared() even if you did not implement it.

Is Sandy Grid

This question is from an old quiz.

Say we have the grid from the Sand homework, so every square is one of 's', 'r' or None. Write code for an is_sandy(grid, x, y) function as follows: Given a grid and an x,y which is guaranteed to be in-bounds. We'll say that x,y is "sandy" If there is sand either diagonally above-left, or diagonally below-right, or both from that x,y. Return True if the given x,y is sandy, False otherwise.

For example in the grid shown below, the two 'r' squares are the only ones where is_sandy() would return True.

String Parsing

Backward Hashtag

Yesterday, Juliette tried to teach her dad how to use hashtags so that he can sound hip when he texts, tweets, and emails. He wants a program to grab the first hashtag that he uses in a given line of a text, tweet, or email. The catch is that he does not fully understand how to use a hashtag and Juliette doesn't have the heart to correct him. He currently puts a hashtag at the end of a word and only wants them to contain alphabetic characters, numbers, and exclamation points (but no other punctuation). Implement a function, parse_backwards_hashtag(s), which takes in a string and returns Juliette's dad's attempt at a hashtag in that string. If there are no attempts at a hashtag in a given string, return None. A call to parse_backwards_hashtag('Check out how hipIam!!#.') would return 'hipIam#' and parse_backwards_hashtag(Tell the 106A students goodluck!# on their quiz') would return 'goodluck!#'.

Find Alpha Piece

Implement a function, find_alpha_piece(s), which takes in a string s representing a string that has a code somewhere in it and returns the alphabetic piece of that code. If there is no code, return None. A code starts with some number (at least one) of alphabetic characters, followed by some number (at least one) of digits, and always ends in a hashtag. Some example codes would be: 'CS106#', 'aaB112#', 'xxxWxx0000#'. A call to find_alpha_piece('The code for your quiz is: CS106#') would return 'CS', a call to find_alpha_piece('aaB112# is the code to type in to prove you are not a robot') would return 'aaB', and a call to find_alpha_piece('Your 2 factor verification code is xxxWxx0000#. Please type it in in the next 5 seconds.') would return 'xxxWxx'. Strategy: rather than using two while loops from left to right, you will have to use two while loops that search from right to left starting at the character right before the hashtag.

Liked Chars

This question is from an old quiz.

Implement a function that is given a "liked" list of chars, with each char in lowercase form, e.g. ['a', 'b', 'c']. A liked word is a sequence of 1 or more liked chars. The chars making up the liked word may be in upper or lowercase form, e.g. 'cAB'. Your function should parse out and return the first liked word that is length 2 or more in the given string s. So for example if liked is ['a', 'b', 'c'], the string 'xxabad..A..BB' returns 'aba'. The starter code includes the first few lines of our standard parsing while-True loop.

liked = ['a', 'b', 'c']

'xxabad..A..BB' -> 'aba'
'^^AB.BBD.CD.' -> 'AB'

Experimental Server

Checkout the parse1 section on the experimental server for more string parsing practice. Juliette used at_words as an example in lecture, so feel free to rewatch Lecture 13 or check out the slides if you want to re-walk through these types of problems. Also, the Section 5 Handout has some string parsing problems that will help you study.

Strings and Lists

Swap Words for 'x'

A popular gaming site has decided to censor chat messages so that users cannot share personal information about themselves. They have created a tool that identifies personal information in each message and creates a censor pattern for each message, where a space represents a character that may be left alone and an "x" represents a character that should be censored in the final message with an "x". Now, they need a coder to create a function that takes a chat message and its corresponding censor pattern and outputs a safe message that has been censored to remove personal information.

Please design censor_chat(message, pattern) to read through the message string and replace characters with an "x" if the pattern string contains an "x" at the character's index. You can assume message and pattern will be the same length. For example, running the below program would print "My name is xxxxx, and I live in xxxxxxxxxxx!"

          
def main():
  msg = "My name is Karel, and I live in Wilbur Hall!"
  ptn = "           xxxxx                xxxxxxxxxxx "
  print(censor(msg, ptn))

Double Encrypt

This question is from an old quiz.

his problem is similar to the Crypto homework with the simplification that the encryption is done entirely with lowercase chars. This "double" encryption uses two source lists, src1 and src2, and two slug lists, slug1 and slug2. All the lists contain chars and are the same length. Implement a function, encrypt_double(src1, slug1, src2, slug2, char), with the following algorithm: use the lowercase version of the input char, which may be uppercase. If the char is in src1, return the char at the corresponding index in slug1. If the char is in src2, return the char at the corresponding "reverse index" in slug2, e.g. like this for lists length 4:

index     reverse index
0         3
1         2
2         1
3         0

If the char is not in src1 or src2, return the char unchanged. No char appears in both src1 and src2.

Double Encrypt Example (len 4)
src1  = ['a', 'b', 'c', 'd']
slug1 = ['s', 't', 'u', 'v']
src2  = ['e', 'f', 'g', 'h']
slug2 = ['w', 'x', 'y', 'z']
encrypt 'A' -> 's'
encrypt 'e' -> 'z'
encrypt 'f' -> 'y'
encrypt '$' -> '$'

More Crypto

This question is from an old quiz.

This problem is somewhat similar to the Crypto homework. This encryption will not make any adjustments for upper vs lower case.

Given source and slug lists of chars which are the same length. Compute and return the encrypted form of a char as follows: if the char appears in the source list, return the char at the next index in the slug list. So if the char is at index 2, its encrypted form is at index 3 in the slug list. Except, if the char is at the last source index, then its encrypted form is first char in the slug list. If the char does not appear in the source list, then return it unchanged.

      
Say we have these len-4 source and slug lists
source = ['a', 'b', 'c', 'd']
slug   = ['w', 'x', 'y', 'z']

encryption:
'a' -> 'x'
'c' -> 'z'
'd' -> 'w'

Drawing

Fancy Lines with Margin

In this problem, impelement a function, draw(canvas, left, top, width, height, n), which takes in a left, top, width, height and number of lines n. The function should leave a 10-pixel high margin across the top and bottom of the figure without any drawing. Given int n which is 2 or more, draw n lines, as follows: The first line should begin at the left edge, 10 pixels from the top, and extend to the right edge, 10 pixels from the bottom. The last line should start at the left edge, 10 pixels from the bottom, and extend to the right edge 10 pixels from the top, with the other lines distributed proportionately.

Here is a picture showing the drawing for n=4 lines. The 4 lines to draw are shown as heavy black lines, with the outer edge of the figure and the margin areas outlined in gray.

Diagonal Lines

In this problem, impelement a function, draw(canvas, left, top, width, height, n), which takes in a left, top, width, height and number of lines n. Given int n which is 2 or more, draw n lines, each starting on the left edge and ending at the lower right corner of the figure. The first line should start at the upper left corner, the last line should start at the lower left corner, with the other lines distributed evenly.

Here is a picture showing the figure boundaries in gray with n=4 lines

More Lines

This question is from an old quiz.

As on the Quilt homework, the function takes in the (left, top, width, height) of a figure positioned on the canvas, and draw lines within that figure.

Draw a blue rectangle at the outer edge of the figure (this code is included).

Given int n which is 2 or more. Draw a series of lines distributed across the top edge of the figure, all terminating at the lower-right corner. The first line should start at the upper left corner, the last line should start at the upper right corner, with the other lines distributed evenly in between.

Draw Grid

Working with data structures like Grids can get a little tricky when you can't visualize what you're working with! Let's code the visualize_grid(grid) function, that takes a Grid as input and draws the grid to the canvas. Each box in the grid should have height and width CELL_SIZE. We also want to print the contents of each grid cell as a string on the canvas! You can assume that the grid's contents are all strings.

Below is an example call to visualize_grid(grid) on a grid with 4 rows and 3 columns.

          
            grid = Grid.build([['1', '2', '3'], ['4', '5', '6'], ['7', '8', '9'], ['10', '11', '12']])
visualize_grid(grid)

One Liners

Given list of non-empty strs, write a map/lambda to form a list of the strings in upper case.

            
>>> strs = ['Rhyme', 'Donut', '3xx', 'Orange']
# yields ['RHYME', 'DONUT', '3XX', 'ORANGE']

Given list of (x, y) points, write a sorted/lambda expression to order these points in decreasing order by the sum of the x+y of each point.

            
>>> points = [(10, 0), (1, 3), (3, 2), (5, 4)]
# yields [(10, 0), (5, 4), (3, 2), (1, 3)]

Checkout the lambda and sort sections on the experimental server for more practice with this.

One lines from Quiz #3 Winter Quarter. You do not need to write a def for these questions. 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 numbers.
# Call map() to produce a result where each
# number is multiplied by -1. (or equivalently write a comprehension)
>>> nums = [3, 0, -2, 5]
# yields [-3, 0, 2, -5]
# your expression:

pass



# b. Given a list of (x, y) "point" tuples where x and y are int values.
# Call map() to produce a result where each (x, y) is replaced
# by the sum of x and y. (or equivalently write a comprehension)
>>> points = [(1, 2), (4, 4), (1, 3)]
# yields [3, 8, 4]
# your expression:

pass




# c. Given a list of (city-name, zip-code, current-temperature) tuples, like this
>>> cities = [('modesto', 95351, 92), ('palo alto', 94301, 80), ...]
# Call sorted() to produce a list of these tuples sorted in decreasing
# order by temperature.
# your expression:

pass



# d. Given a non-empty list of (flower-name, scent-score, color-score) tuples
# like the following, scores are in the range 1 .. 10
>>> flowers = [('rose', 4, 8), ('orchid', 7, 2), ... ]
# Call max() or min() to return the flower tuple with the highest scent score.
# your expression:

pass

Dictionaries

Checkout the dict4 section on the experimental server for more practice with this. These ones are challenging.

Dict Problem from Winter Quarter Quiz #3

We have a social network, and every user is identified by an id string like '@sal'. We have a "recent" dict which tracks which users across the whole system have sent a message recently. For each user who has sent a message within the last hour, there will be an entry in the recent dict with that user as the key and their most recent recipient as the value. For example with the following dict, we see that '@sal' sent a message to '@alice'.

recent = {
  '@sal': '@alice',
  '@miguel': '@sophie',
  ...
}

Write code for the send_score() function below - given two users, a and b, and the recent dict, return a "sending" score as follows: if a sent a message to b, the score is 5. If a sent a message to some user, "x", and x sent a message to b, the score is 1. Otherwise the score is 0.

  def send_score(recent, a, b):
    # your code here
    pass

Emails

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.

Implement a function, parse_hosts(addrs, which 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.

Sent Messages

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' as a recipient.

          
{
...
'@bob': {'@alice': 3, '@mo': 1},
...
}

Implement a function, parse_sends(filename), which given a filename of a log file, read through all the log lines to build and return a sends dict.

Common Senders

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.

Implement a function, commons(sends, src_a, src_b), which given a sends dict, and src_a and src_b which are sender addrs which have sent messages, computes and returns a "commons" list of the dest addresses that each have received messages from both src_a and src_b. 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 src_a: '@bob' and src_b: '@mo', the commons list is ['@b', '@x'].

Make County

Implement a function, make_county(words) which given a list of non-empty words, produces a 'county' dict where each first-char-of-word seen is a key, and its value is a count dict of words starting with that char. For example, make_county(['aaa', 'abb', 'aaa']) would return {'a': {'aaa':2, 'abb':1}}.

Recipes

You are putting together an app that helps people find recipes they can make with the ingredients that they already have on hand. Implement the following function, find_recipes(curr_ingredients, recipe_book), which takes as parameters curr_ingredients, a list of ingredients that the user already has on hand and recipe_book, a dictionary representing a recipe book in which the keys are recipe names and values are the list of ingredients required to make that recipe. The function should return a list of recipe names that the user can make.

Building a Glossary

Implement the following function: make_glossary(filename) that takes as a parameter a string filename and constructs a glossary of the file. A glossary is defined as a dictionary from words to lists of tuples whose first elements are line numbers and second elements are the lines themselves. For example, calling the function on this file:

1st line 
2nd line

would return this dictionary: {"1st": [(0, "1st line")], "line": [(0, "1st line"), (1, "2nd line")], "2nd": [(1, "2nd line")]} Be sure to remove newline characters from the line. You may assume that each word appears at most once per line of the file.

Finding Grandparents

This problem is slightly harder than what we would put on the quiz. Implement a function find_grandchildren, which given a dictionary parents whose keys are strings representing parent names and whose values are lists of those parent's children's names, produces and return s a dictionary mapping from people's names to those lists of those people's grandchildren's names.

For example, given this dictionary:

            
parents_to_children = {
  'Khaled': ['Chibundu', 'Jesmyn'],
  'Daniel': ['Khaled', 'Eve'],
  'Jesmyn': ['Frank'],
  'Eve': ['Grace']
}

Daniel's grandchildren are Chibundu, Jesmyn and Grace, since those are the children of his children. Additionally, Khaled is Frank's grandparent, since Frank's parent is Khaled's child. Therefore, calling find_grandchildren (parents_to_children) returns this dictionary:

            
{
  'Khaled': ['Frank'],
  'Daniel': ['Chibundu', 'Jesmyn', 'Grace']
}

Note that the people who aren't grandparents don't show up as keys in the new dictionary

Capstone CS106A Problems

Dict File Problem from Winter Quarter Quiz #3

Suppose it is the year 2040, and the most important thing in the world is celebrities, each identified by a handle like '@alice'. Celebrities post on the hot new social network PipPop. Each PipPop channel has a name like '#watsup' or '#meh'.

Given a text file with the following format: each line in the file represents one post by a celebrity to 1 or more channels. The first word on the line is a celebrity name like '@alice', followed by 1 or more PipPop channel names, like this:

@alice^#meh^#wut

The line is divided into parts by '^'. The celebrity and channel names may contain punctuation, but will not contain '^'.

We'll say a "posts" dict has a key for each channel, and its value is a nested list of the celebrities that posted to that channel. The list of celebrities should not have duplicates in it; a celebrity should be in the list at most once.

{
 ...
 '#meh': ['@juliette', '@arun', '@nick'],
 '#texas': ['@miguel', '@rose'],
 ...
}

Write code to read through the file described above, building and returning the posts dict. The boilerplate code to read the files lines is provided, and you can change that code if you wish.

  def read_posts(filename):
    # your code here
    pass

Prime File

The given file contains text data on each line as follows. Each line is made of a mixture of non-empty alphabetic words and non-negative ints, all separated by colons. The numbers can be distinguished since their first char is a digit. Lines like this: aaa:123:420:xyz:xxx:44:zz:a The first element is the "prime" for that line, and is always alphabetic. Implement a function, prime_file(filename) which reads through all the lines and builds a dictwith a key for each prime, and its value is a list of all the int number values from all the lines with that prime. Add every number to the list, even if it is a duplicate. When all the data is loaded, print the primes in alphabetical order 1 per line, each followed by its sorted list of numbers, like this aaa [44, 123, 123, 125, 420, 693] bbb [16, 23, 101, 101]

Dict File

Suppose you are part of a team handling a sudden surge of package deliveries. You have a data file for each day that looks like this:

ca,94301-0001,94025-1122,94301-9999,...
wa,98001-0000,98001-4322,...
...

The parts of each line are separated by commas. The first word is a 2-char state code. After the state are 1 or more zip+4 codes, like '94301-0001', each representing one delivery. The format of the zip+4 is: 5 digit zipcode, dash, 4 digits. We will treat the zipcode as a string.

Write code to build a "states" dict with a key for every state, The value for each state key is a nested dict which counts the number of times each zipcode string has a delivery, considering only the zipcode '94301' part of the zip+4 '94301-0001'.

        
{
 'ca': {'94301': 2, '94025': 1, ...}
 'wa': {'98001': 5, '98002': 1, ...}
}

Once the states dict is built, write code to print each state code on a line by itself, in increasing alphabetic order. Each state should be followed by its zip/count data, with the zipcodes in increasing order, so the overall print output looks like this:

This function does not return anything - it prints its output. The standard code to open a file and loop over its lines is provided.

Lightning

There are many lightning strikes each day across the united states. Each lightning strike is represented by a number 1..100. Suppose you have a data file where each line represents one or more lightning events. Each line is made of one or more lightning strike ints followed by the state name, separated by commas like this:

26,1,ca
99,100,100,tx
12,50,ca
44,28,tx

Write a function to read the lines of this file and build a "states" dict with a key for each state, e.g. 'ca', and its value is a list of all that states's int strike numbers. So for example, the 4 lines of text above make this states dict:

  

{ 'ca': [26, 1, 12, 50],
  'tx': [99, 100, 100, 44, 28],
}

When all the data is loaded, print the states in alphabetical order, 1 per line, each followed by its list of numbers, followed by the sum of the numbers, like this:

ak [100, 12] 112
ca [26, 1, 12, 50] 89
tx [99, 100, 100, 44, 28] 371
...

This function does not return anything - it prints its output. The standard code to open a file and loop over its lines is provided.

  
>>> # Reminder of how to print a list of ints:
>>> nums = [1, 2, 3]
>>> print(nums)
[1, 2, 3]

  
def parse_lightning(filename):
    states = {}
    with open(filename, 'r') as f:
        for line in f:
            pass