Due at 11:59pm on 02/20/2017.

Starter Files

Download lab04.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.


By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded.

  • To receive credit for this lab, you must complete Questions 1-6 in lab04.py and submit through OK.
  • Questions 7-10 are extra practice on trees. It can be found in the lab04_extra.py file. It is recommended that you complete this problem on your own time.

Lists warm-up!

Question 1: List Indexing

In each of following, what does the list indexing look like to get the number 7? Ex. x = [7], answer would be x[0]. You can use the interpreter or Python tutor to experiment with your answers.

Use OK to test your knowledge with the following "List Indexing" questions:

python3 ok -q indexing -u
>>> x = [1, 3, [5, 7], 9]
>>> x = [[7]]
>>> x = [1, [2, [3, [4, [5, [6, [7]]]]]]]

Answer the following to solidify your understanding of list indexing.

>>> lst = [3, 2, 7, [84, 83, 82]]
>>> lst[4]
>>> lst = [3, 2, 7, [84, 83, 82]] # Write the code that indexes into lst to output the 82
>>> lst[3][0]

Question 2: If This Not That

Define if_this_not_that, which takes a list of integers i_list, and an integer this, and for each element in i_list if the element is larger than this then print the element, otherwise print that.

def if_this_not_that(i_list, this):
    """Define a function which takes a list of integers `i_list` and an integer
    `this`. For each element in `i_list`, print the element if it is larger
    than `this`; otherwise, print the word "that".

    >>> original_list = [1, 2, 3, 4, 5]
    >>> if_this_not_that(original_list, 3)
"*** YOUR CODE HERE ***"
for elem in i_list: if elem <= this: print("that") else: print(elem) # List comprehension version def if_this_not_that(i_list, this): [print(i) if i > this else print('that') for i in i_list]

Use OK to test your code:

python3 ok -q if_this_not_that

List Comprehension

List comprehensions are a compact and powerful way of creating new lists out of sequences. Let's work with them directly:

>>> [i**2 for i in [1, 2, 3, 4] if i%2 == 0]
[4, 16]

is equivalent to

>>> lst = []
>>> for i in [1, 2, 3, 4]:
...     if i % 2 == 0:
...         lst += [i**2]
>>> lst
[4, 16]

The general syntax for a list comprehension is

[<expression> for <element> in <sequence> if <conditional>]

The syntax is designed to read like English: "Compute the expression for each element in the sequence if the conditional is true."

Note: The if clause in a list comprehension is optional.

Question 3: WWPD: Lists?

What would Python display? Try to figure it out before you type it into the interpreter!

Use OK to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q lists -u
>>> [x*x for x in range(5)]
[0, 1, 4, 9, 16]
>>> [n for n in range(10) if n % 2 == 0]
[0, 2, 4, 6, 8]
>>> ones = [1 for i in ["hi", "bye", "you"]] >>> ones + [str(i) for i in [6, 3, 8, 4]]
[1, 1, 1, '6', '3', '8', '4']
>>> [i+5 for i in [n for n in range(1,4)]]
[6, 7, 8]
>>> [i**2 for i in range(10) if i < 3]
[0, 1, 4]
>>> lst = ['hi' for i in [1, 2, 3]] >>> print(lst)
['hi', 'hi', 'hi']
>>> lst + [i for i in ['1', '2', '3']]
['hi', 'hi', 'hi', '1', '2', '3']

Question 4: Coordinates

Implement a function coords that takes a function fn, a sequence seq, and a lower and upper bound on the output of the function. coords then returns a list of coordinate pairs (lists) such that:

  • Each (x, y) pair is represented as [x, fn(x)]
  • The x-coordinates are elements in the sequence
  • The result contains only pairs whose y-coordinate is within the upper and lower bounds (inclusive)

See the doctest for examples.

Note: your answer can only be one line long. You should make use of list comprehensions!

def coords(fn, seq, lower, upper):
    >>> seq = [-4, -2, 0, 1, 3]
    >>> fn = lambda x: x**2
    >>> coords(fn, seq, 1, 9)
    [[-2, 4], [1, 1], [3, 9]]
"*** YOUR CODE HERE ***" return ______
return [[x, fn(x)] for x in seq if lower <= fn(x) <= upper]

Use OK to test your code:

python3 ok -q coords

Linked Lists (same as rlists)

These problems use a slight variation of the rlist abstraction used in lecture for linked lists. Specifically, they use the function link in place of make_rlist, and the variable empty in place of empty_rlist.

Python has many built-in types of sequences: lists, ranges, and strings, to name a few. In this lab, we instead construct our own type of sequence called a linked list. A linked list is a simple type of sequence that is comprised of multiple links that are connected.

Linked List

Each link is a pair where the first element is an item in the linked list, and the second element is another link.

  • Constructors:

    • link(first, rest): Construct a linked list with first element and the next link rest.
    • empty: The empty linked list.
  • Selectors

    • first(s): Returns the first element in the given linked list s.
    • rest(s): Returns the rest of the linked list s.
  • Other

    • is_link(s): Returns True if s is a linked list.
    • print_link(s): Prints out the linked list s.

We can construct the Linked list shown above by using the constructors. The first element of this Linked list is 12 while the rest is another Linked list that contains 99 and 37:

>>> x = link(12, link(99, link(37)))
>>> first(x)
>>> first(rest(x))
>>> first(rest(rest(x)))

Note: Notice that we can just use link(37) instead link(37, empty). This is because the second argument of the link constructor has a default argument of empty.

Question 5: Link to List

Write a function link_to_list that takes a linked list and converts it to a Python list.

Hint: To check if a linked list is empty, you can use lst == empty. Also, you can combine two Python lists using +.

def link_to_list(linked_lst):
    """Return a list that contains the values inside of linked_lst

    >>> link_to_list(empty)
    >>> lst1 = link(1, link(2, link(3, empty)))
    >>> link_to_list(lst1)
    [1, 2, 3]
"*** YOUR CODE HERE ***"
if linked_lst == empty: return [] else: return [first(linked_lst)] + link_to_list(rest(linked_lst)) # Iterative version def link_to_list_iterative(linked_lst): """ >>> link_to_list_iterative(empty) [] >>> lst1 = link(1, link(2, link(3, empty))) >>> link_to_list_iterative(lst1) [1, 2, 3] """ new_lst = [] while linked_lst != empty: new_lst += [first(linked_lst)] linked_lst = rest(linked_lst) return new_lst

Use OK to test your code:

python3 ok -q link_to_list

Question 6: Interleave

Write interleave(s0, s1), which takes two linked lists and produces a new linked list with elements of s0 and s1 interleaved. In other words, the resulting list should have the first element of the s0, the first element of s1, the second element of s0, the second element of s1, and so on.

If the two lists are not the same length, then the leftover elements of the longer list should still appear at the end.

def interleave(s0, s1):
    """Interleave linked lists s0 and s1 to produce a new linked

    >>> evens = link(2, link(4, link(6, link(8, empty))))
    >>> odds = link(1, link(3, empty))
    >>> print_link(interleave(odds, evens))
    1 2 3 4 6 8
    >>> print_link(interleave(evens, odds))
    2 1 4 3 6 8
    >>> print_link(interleave(odds, odds))
    1 1 3 3
"*** YOUR CODE HERE ***"
# Recursive version if s0 == empty: return s1 elif s1 == empty: return s0 return link(first(s0), link(first(s1), interleave(rest(s0), rest(s1)))) # Iterative version def interleave(s0, s1): interleaved = empty while s0 != empty and s1 != empty: interleaved = link(first(s1), link(first(s0), interleaved)) s0, s1 = rest(s0), rest(s1) remaining = s1 if s0 == empty else s0 while remaining != empty: interleaved = link(first(remaining), interleaved) remaining = rest(remaining) return reverse_iterative(interleaved) def reverse_iterative(s): rev_list = empty while s != empty: rev_list = link(first(s), rev_list) s = rest(s) return rev_list

Use OK to test your code:

python3 ok -q interleave

Extra Tree Questions

A tree is a data structure that represents a hierarchy of information. A file system is a good example of a tree structure. For example, within your cs61a folder, you have folders separating your projects, lab assignments, and homework. The next level is folders that separate different assignments, hw01, lab01, hog, etc., and inside those are the files themselves, including the starter files and ok. Below is an incomplete diagram of what your cs61a directory might look like.

cs61a tree

As you can see, unlike trees in nature, the tree abstract data type is drawn with the root at the top and the leaves at the bottom.

Our tree abstract data type consists of a root label and a list of its branches. To create a tree and access its label and branches, use the following constructor and selectors:

  • Constructor

    • tree(label, branches=[]): creates a tree object with the given label value at its root and list of branches.
  • Selectors

    • label(tree): returns the value in the root of tree.
    • branches(tree): returns the list of branches of the given tree.
  • Convenience function

    • is_leaf(tree): returns True if tree's list of branches is empty, and False otherwise.

For example, the tree generated by

t = tree(1,

would look like this:

 / | \
2  3  6
  / \  \
 4   5  7

To extract the number 3 from this tree, which is the label of the root of its second branch, we would do this:


Question 7: Create pyTunes

All pyTunes accounts come with the free songs below. Define the function make_pytunes, which takes in username and creates this tree:

pytunes tree

The doctest below shows the print_tree representation of a default pyTunes tree.

def make_pytunes(username):
    """Return a pyTunes tree as shown in the diagram with USERNAME as the value
    of the root.

    >>> pytunes = make_pytunes('i_love_music')
    >>> print_tree(pytunes)
        justin bieber
            what do you mean?
        2015 pop mashup
"*** YOUR CODE HERE ***"
return tree(username, [tree('pop', [tree('justin bieber', [tree('single', [tree('what do you mean?')])]), tree('2015 pop mashup')]), tree('trance', [tree('darude', [tree('sandstorm')])])])

Use OK to test your code:

python3 ok -q make_pytunes

Question 8: Number of Songs

A pyPod can only hold a certain number of songs, and you need to find out whether or not all the songs in your pyTunes account will fit. Define the function num_songs, which takes in a pyTunes tree t and returns the number of songs in t. Recall that there are no empty directories in pyTunes, so all leaves in t are songs.

Hint: You can use is_leaf to check whether a given tree is a leaf.

>>> no_branches = tree(1)
>>> is_leaf(no_branches)
>>> is_leaf(tree(5, [tree(3), tree(4)]))
def num_songs(t):
    """Return the number of songs in the pyTunes tree, t.

    >>> pytunes = make_pytunes('i_love_music')
    >>> num_songs(pytunes)
"*** YOUR CODE HERE ***"
if is_leaf(t): return 1 return sum([num_songs(b) for b in branches(t)]) # Alternate solution def num_songs(t): if is_leaf(t): return 1 leaves = 0 for b in branches(t): leaves += num_songs(b) return leaves

Use OK to test your code:

python3 ok -q num_songs

Question 9: Add Song

Of course, you should be able to add music to your pyTunes. Write add_song to add song to the given category. You should not be able to add a song under a song or to a category that doesn't exist. See the doctests for examples.

def add_song(t, song, category):
    """Returns a new tree with SONG added to CATEGORY. Assume the CATEGORY
    already exists.

    >>> indie_tunes = tree('indie_tunes',
    ...                  [tree('indie',
    ...                    [tree('vance joy',
    ...                       [tree('riptide')])])])
    >>> new_indie = add_song(indie_tunes, 'georgia', 'vance joy')
    >>> print_tree(new_indie)
        vance joy

"*** YOUR CODE HERE ***"
if label(t) == category: return tree(label(t), branches(t) + [tree(song)]) kept_branches = [] for b in branches(t): kept_branches += [add_song(b, song, category)] return tree(label(t), kept_branches) # Alternative Solution def add_song(t, song, category): if label(t) == category: return tree(label(t), branches(t) + [tree(song)]) all_branches = [add_song(b, song, category) for b in branches(t)] return tree(label(t), all_branches)

Use OK to test your code:

python3 ok -q add_song

Question 10: Delete

You also want to be able to delete a song or category from your pyTunes. Define the function delete, which takes in a pyTunes tree t and returns a new tree that is the same as t except with target deleted. If target is a genre, artist, or album, delete everything inside of it. It should not be possible to delete the entire account or root of the tree. Deleting all the songs within a category should not remove that category.

def delete(t, target):
    """Returns the tree that results from deleting TARGET from t. If TARGET is
    a category, delete everything inside of it.

    >>> my_account = tree('kpop_king',
    ...                    [tree('korean',
    ...                          [tree('gangnam style'),
    ...                           tree('wedding dress')]),
    ...                     tree('pop',
    ...                           [tree('t-swift',
    ...                                [tree('blank space')]),
    ...                            tree('uptown funk'),
    ...                            tree('see you again')])])
    >>> new = delete(my_account, 'pop')
    >>> print_tree(new)
        gangnam style
        wedding dress
"*** YOUR CODE HERE ***"
kept_branches = [] for b in branches(t): if label(b) != target: kept_branches += [delete(b, target)] return tree(label(t), kept_branches) # Alternate solution def delete(t, target): kept_branches = [delete(b, target) for b in branches(t) if label(b) != target] return tree(label(t), kept_branches)

Use OK to test your code:

python3 ok -q delete