This week in section, we are going to focus on lists of lists and strings, which will be good practice for the midterm and Assignment 3. There are more problems on this handout than we expect you to cover in section, so you're encouraged to use this handout for exam review.
Here's the Section 3 starter code. You'll unzip/extract this file and open it in PyCharm just like you do with your assignment starter code. We've included some Doctests for you to test your code with, but you should also add some of your own.
Bubble Up
Recall our introduction to grids and 2-D lists the end of Fridays's lecture. Today, you’ll work with a grid where each square is either a bubble ('b'), rock ('r'), or empty (None).
can_bubble_up(grid, x, y)
Implement a function can_bubble_up(grid, x, y) that takes in a grid of any size and with any values inside of it, and integers x, y representing coordinates. x, y is guaranteed to be in bounds of grid.
You must check if the location x, y in grid can be "bubbled up" to the square directly above it. A grid location can be bubbled up if:
- The square at that location is a bubble (
'b'), and - the location directly above it is in bounds and empty.
Here is some nice art to help you visualize the problem.
As a first step to the problem, walk through each cell of the grid and write down by hand (not using code) if it can be bubbled and why. This should help you determine the cases you will need to check in the code. Once you have completed this step, you can move on to coding the solution.
Implement the function can_bubble_up(grid, x, y) so that it correctly returns True or False depending on which grid and coordinates are passed in.
Analyzing Doctests
Now that we've written some code, let's see if it works as expected. We can use Doctests to test our functions, and in this section we'll use them to confirm that when can_bubble_up(grid, x, y) is given specific inputs, it returns the expected output. As shown below, the syntax is three greater-than signs followed by a space and then the name of the function and the specific parameters you want to test. On the next line, you put the output you expect.
To run a Doctest in PyCharm, right‑click on the greater‑than signs and hit Run 'Doctest name_of_function'.
Here is an example of what Doctests for can_bubble_up(grid, x, y) might look like:
def can_bubble_up(grid, x, y):
"""
Implement this function as described in the handout.
>>> grid = [[None, 'r', 'b'], ['b', 'b', 'b']] # creates a grid identical to the one above
>>> can_bubble_up(grid, 0, 1) # tests can_bubble_up for this grid at location (0, 1)
True # states expected return value
>>> can_bubble_up(grid, 0, 0)
False
>>> can_bubble_up(grid, 2, 1)
False
"""
Which square in the diagram above is each Doctest referring to? Why will can_bubble_up(grid, x, y) return True or False in each case?
row_has_bubble_up(grid, y)
Now implement a function row_has_bubble_up(grid, y), which takes in a grid and an integer y identifying a row in the grid. This function should return True if at least one square in row y can be bubbled up and False otherwise. Hint: use the nice function you wrote in part 1 as a helper.
Writing Doctests
Now, it's your turn to write a Doctest for your function row_has_bubble_up(grid, y). Write one Doctest for the example grid.
Here's another copy of the grid so you don't have to scroll up 🙂
def can_bubble_up(grid, x, y):
"""
Implement this function as described in the handout.
>>> grid = [[None, 'r', 'b'], ['b', 'b', 'b']]
>>> can_bubble_up(grid, 0, 1)
True
>>> can_bubble_up(grid, 0, 0)
False
>>> can_bubble_up(grid, 2, 1)
False
"""
# check if the square is a bubble
if grid[y][x] != 'b':
return False
# check if the square above is in bounds
if y - 1 < 0:
return False
# check if the square above is empty
if grid[y - 1][x] is not None:
return False
return True
def row_has_bubble_up(grid, y):
"""
Implement this function as described in the handout. Add your own Doctests.
>>> grid = [[None, 'r', 'b'], ['b', 'b', 'b']]
Your Doctests here
"""
for x in range(len(grid[0])):
if can_bubble_up(grid, x, y):
return True
return False
Enumerate
Write a function enumerate(lst) that takes in a list lst and returns a list
of lists where each nested list contains the index of an element in the original list and the element itself.
These lists should appear in increasing order of indices. Here are some sample calls of enumerate and
what should be returned:
>>> enumerate(['cs106a', 'is', 'super', 'fun'])
[[0, 'cs106a'], [1, 'is'], [2, 'super'], [3, 'fun']]
>>> enumerate(['hello'])
[[0, 'hello']]
>>> enumerate([])
[]
def enumerate(lst):
enum_lsts = []
for i in range(len(lst)):
val = lst[i]
enum_lsts.append([i, val])
return enum_lsts
Double Char
Write a function double_char(s) that takes in a string s and returns a
string where all the characters in s have been doubled. Here's a few sample calls
of double_char:
>>> double_char('Hello')
'HHeelllloo'
>>> double_char('cs106a')
'ccss110066aa'
def double_char(s):
result = ''
for ch in s:
result = result + ch + ch
return result
Catty
Implement the function catty(s) that takes in a string s and returns a new
string made of the chars from s that are 'c' 'a' or 't' (not case sensitive).
>>> catty('xCtxxxTacx')
'CtTac'
def catty(s):
result = ''
for i in range(len(s)):
# Decomp var: save lower form in var
low = s[i].lower()
if low == 'c' or low == 'a' or low == 't':
result += s[i] # Use original, not low
return result
Find Differences
Implement the function find_diffs(str1, str2) that takes in two equal length strings as parameters
and returns the number of indices where the two strings have different characters.
>>> find_diffs("ATGCC", "ATTCA")
2
>>> find_diffs("ABC", "DEF")
3
>>> find_diffs("CAT", "CAT")
0
def find_diffs(str1, str2):
count = 0
for i in range(len(str1)):
ch1 = str1[i]
ch2 = str2[i]
if ch1 != ch2:
count += 1
return count