Due by 11:59pm on Friday, July 14

Instructions

Download hw03.zip. Inside the archive, you will find a file called hw03.py, along with a copy of the ok autograder.

Submission: When you are done, submit the assignment by uploading all code files you've edited to Gradescope. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on Gradescope. See Lab 0 for more instructions on submitting assignments.

Using Ok: If you have any questions about using Ok, please refer to this guide.

Readings: You might find the following references useful:

• Section 2.2
• Section 2.3
• Section 2.4

Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. There is a homework recovery policy as stated in the syllabus. This homework is out of 2 points.

Required Questions

Mutability

Q1: Filter

Write a function filter that takes in a list lst and predicate function pred and mutates lst so that it only contains elements satisfying pred.

Hint: Avoid mutating the list as you are iterating through it as this may cause issues with iterating through all the elements.

def filter(pred, lst):
    """Filters lst with pred using mutation.
    >>> original_list = [5, -1, 2, 0]
    >>> filter(lambda x: x % 2 == 0, original_list)
    >>> original_list
    [2, 0]
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q filter
Copy
✂️

Q2: Deep Map

Write the function deep_map_mut that takes a Python list and mutates all of the elements (including elements of sublists) to be the result of calling the function given, func, on each element. Note that the function does not return the mutated list!

Hint: type(a) == list will return True if a is a list.

def deep_map_mut(func, lst):
    """Deeply maps a function over a Python list, replacing each item
    in the original list object.

    Does NOT create new lists by either using literal notation
    ([1, 2, 3]), +, or slicing.

    Does NOT return the mutated list object.

    >>> l = [1, 2, [3, [4], 5], 6]
    >>> deep_map_mut(lambda x: x * x, l)
    >>> l
    [1, 4, [9, [16], 25], 36]
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q deep_map_mut
Copy
✂️

Trees

Q3: Has Path

Write a function has_path that takes in a tree t and a string word. It returns True if there is a path that starts from the root where the entries along the path spell out the word, and False otherwise. (This data structure is called a trie, and it has a lot of cool applications, such as autocomplete). You may assume that every node's label is exactly one character.

def has_path(t, word):
    """Return whether there is a path in a tree where the entries along the path
    spell out a particular word.

    >>> greetings = tree('h', [tree('i'),
    ...                        tree('e', [tree('l', [tree('l', [tree('o')])]),
    ...                                   tree('y')])])
    >>> print_tree(greetings)
    h
      i
      e
        l
          l
            o
        y
    >>> has_path(greetings, 'h')
    True
    >>> has_path(greetings, 'i')
    False
    >>> has_path(greetings, 'hi')
    True
    >>> has_path(greetings, 'hello')
    True
    >>> has_path(greetings, 'hey')
    True
    >>> has_path(greetings, 'bye')
    False
    >>> has_path(greetings, 'hint')
    False
    """
    assert len(word) > 0, 'no path for empty word.'
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q has_path
Copy
✂️

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit

Make sure to submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. For a refresher on how to do this, refer to Lab 00.

Optional Questions

Arms-length recursion

Tip: Adding extra code in a recursive function to handle examples that are already handled by existing base cases and recursive calls is redundant, adds complexity, and makes code harder to follow. One common example called arms-length recursion occurs when a base case is checked before a recursive call even though it would have been checked after the recursive call. Try to avoid this! For example, the lines marked # CAN BE REMOVED can (and should) be removed without changing the behavior of this function.

def min_depth(t):
    """Return the number of steps in the shortest path to a leaf in tree t."""
    if is_leaf(t):
        return 0
    for b in branches(t):  # CAN BE REMOVED
        if is_leaf(b):     # CAN BE REMOVED
            return 1       # CAN BE REMOVED
    return 1 + min([min_depth(b) for b in branches(t)])

Mobiles

Acknowledgements This mobile example is based on a classic problem from MIT Structure and Interpretation of Computer Programs, Section 2.2.2.

We are making a planetarium mobile. A mobile is a type of hanging sculpture. A binary mobile consists of two arms. Each arm is a rod of a certain length, from which hangs either a planet or another mobile. For example, the below diagram shows the left and right arms of Mobile A, and what hangs at the ends of each of those arms.

We will represent a binary mobile using the data abstractions below.

• A mobile must have both a left arm and a right arm.
• An arm has a positive length and must have something hanging at the end, either a mobile or planet.
• A planet has a positive mass, and nothing hanging from it.

Below are the implementations of the various data abstractions used in mobiles. The mobile and arm data abstractions have been completed for you.

Implementation of the Mobile Data Abstraction (for your reference, no need to do anything here):

def mobile(left, right):
    """Construct a mobile from a left arm and a right arm."""
    assert is_arm(left), "left must be a arm"
    assert is_arm(right), "right must be a arm"
    return ['mobile', left, right]

def is_mobile(m):
    """Return whether m is a mobile."""
    return type(m) == list and len(m) == 3 and m[0] == 'mobile'

def left(m):
    """Select the left arm of a mobile."""
    assert is_mobile(m), "must call left on a mobile"
    return m[1]

def right(m):
    """Select the right arm of a mobile."""
    assert is_mobile(m), "must call right on a mobile"
    return m[2]

def arm(length, mobile_or_planet):
    """Construct a arm: a length of rod with a mobile or planet at the end."""
    assert is_mobile(mobile_or_planet) or is_planet(mobile_or_planet)
    return ['arm', length, mobile_or_planet]

def is_arm(s):
    """Return whether s is a arm."""
    return type(s) == list and len(s) == 3 and s[0] == 'arm'

def length(s):
    """Select the length of a arm."""
    assert is_arm(s), "must call length on a arm"
    return s[1]

def end(s):
    """Select the mobile or planet hanging at the end of a arm."""
    assert is_arm(s), "must call end on a arm"
    return s[2]

Q4: Weights

Implement the planet data abstraction by completing the planet constructor and the mass selector so that a planet is represented using a two-element list where the first element is the string 'planet' and the second element is its mass.

def planet(mass):
    """Construct a planet of some mass."""
    assert mass > 0
    "*** YOUR CODE HERE ***"

def mass(w):
    """Select the mass of a planet."""
    assert is_planet(w), 'must call mass on a planet'
    "*** YOUR CODE HERE ***"

def is_planet(w):
    """Whether w is a planet."""
    return type(w) == list and len(w) == 2 and w[0] == 'planet'

The total_weight function demonstrates the use of the mobile, arm, and planet abstractions. You do NOT need to implement anything here. You may use the total_weight function in questions 3 and 4.

def examples():
    t = mobile(arm(1, planet(2)),
               arm(2, planet(1)))
    u = mobile(arm(5, planet(1)),
               arm(1, mobile(arm(2, planet(3)),
                             arm(3, planet(2)))))
    v = mobile(arm(4, t), arm(2, u))
    return t, u, v

def total_weight(m):
    """Return the total weight of m, a planet or mobile.

    >>> t, u, v = examples()
    >>> total_weight(t)
    3
    >>> total_weight(u)
    6
    >>> total_weight(v)
    9
    """
    if is_planet(m):
        return mass(m)
    else:
        assert is_mobile(m), "must get total weight of a mobile or a planet"
        return total_weight(end(left(m))) + total_weight(end(right(m)))

Run the ok tests for total_weight to make sure that your planet and mass functions are implemented correctly.

Use Ok to test your code:

python3 ok -q total_weight
Copy
✂️

Q5: Balanced

Implement the balanced function, which returns whether m is a balanced mobile. A mobile is balanced if both of the following conditions are met:

1. The torque applied by its left arm is equal to the torque applied by its right arm. The torque of the left arm is the length of the left rod multiplied by the total weight hanging from that rod. Likewise for the right. For example, if the left arm has a length of 5, and there is a mobile hanging at the end of the left arm of total weight 10, the torque on the left side of our mobile is 50.
2. Each of the mobiles hanging at the end of its arms is itself balanced.

Planets themselves are balanced, as there is nothing hanging off of them.

Reminder: You may use the total_weight function defined for you in Question 2 (as well as any of the other functions defined in Question 2).

def balanced(m):
    """Return whether m is balanced.

    >>> t, u, v = examples()
    >>> balanced(t)
    True
    >>> balanced(v)
    True
    >>> w = mobile(arm(3, t), arm(2, u))
    >>> balanced(w)
    False
    >>> balanced(mobile(arm(1, v), arm(1, w)))
    False
    >>> balanced(mobile(arm(1, w), arm(1, v)))
    False
    >>> from construct_check import check
    >>> # checking for abstraction barrier violations by banning indexing
    >>> check(HW_SOURCE_FILE, 'balanced', ['Index'])
    True
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q balanced
Copy
✂️

Q6: Totals

Implement totals_tree, which takes in a mobile or planet and returns a tree whose root label is the total weight of the input. For a planet, totals_tree should return a leaf. For a mobile, totals_tree should return a tree whose label is that mobile's total weight, and whose branches are totals_trees for the ends of its arms. As a reminder, the description of the tree data abstraction can be found here.

def totals_tree(m):
    """Return a tree representing the mobile with its total weight at the root.

    >>> t, u, v = examples()
    >>> print_tree(totals_tree(t))
    3
      2
      1
    >>> print_tree(totals_tree(u))
    6
      1
      5
        3
        2
    >>> print_tree(totals_tree(v))
    9
      3
        2
        1
      6
        1
        5
          3
          2
    >>> from construct_check import check
    >>> # checking for abstraction barrier violations by banning indexing
    >>> check(HW_SOURCE_FILE, 'totals_tree', ['Index'])
    True
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q totals_tree
Copy
✂️

Exam Practice

Homework assignments will also contain prior exam-level questions for you to take a look at. These questions have no submission component; feel free to attempt them if you'd like a challenge!

1. Summer 2021 MT Q4: Maximum Exponen-tree-ation
2. Summer 2019 MT Q8: Leaf It To Me
3. Summer 2017 MT Q9: Temmie Flakes