Quiz 2 Review

May 2nd, 2021

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



Solutions


PyCharm Project

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 2 handout as well as all problems in the section 4 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 Juliette.

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.

  1. 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.)
  2. 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. Nick 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 4 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)


© Stanford 2020 | CS106A has been developed over decades by many talented teachers. Website designed by Chris Piech.