Due by 11:59pm on Wednesday, October 1

Instructions

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

Submission: When you are done, submit the assignment 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.4

Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. This homework is out of 6 points.

Required Questions

Q1: Taxicab Distance

An intersection in midtown Manhattan can be identified by an avenue and a street, which are both identified by positive integers.

• Streets in Manhattan run East–West (horizontally).
• Avenues in Manhattan run North–South (vertically).

The Manhattan distance or taxicab distance between two intersections is the number of blocks that must be traversed to reach one from the other, ignoring one-way street restrictions and construction. For example, Times Square is on 46th Street and 7th Avenue. Ess-a-Bagel is on 51st Street and 3rd Avenue. The taxicab distance between them is 9 blocks (5 blocks from 46th to 51st street and 4 blocks from 7th avenue to 3rd avenue). Taxicabs cannot cut diagonally through buildings to reach their destination!

In the intersection ADT, we have the following functions: intersection which creates a new intersection at the given street and avenue; street which returns the street number of a given intersection; and avenue which returns the avenue number of a given intersection.

Important: Do not modify the ADT.

Implement taxicab, which computes the taxicab distance between two intersections using the following data abstraction. Hint: You don't need to know what a Cantor pairing function is; just use the abstraction.

def intersection(st, ave):
    """Represent an intersection using the Cantor pairing function."""
    return (st+ave)*(st+ave+1)//2 + ave

def street(inter):
    return w(inter) - avenue(inter)

def avenue(inter):
    return inter - (w(inter) ** 2 + w(inter)) // 2

w = lambda z: int(((8*z+1)**0.5-1)/2)

def taxicab(a, b):
    """Return the taxicab distance between two intersections.

    >>> times_square = intersection(46, 7)
    >>> ess_a_bagel = intersection(51, 3)
    >>> taxicab(times_square, ess_a_bagel)
    9
    >>> taxicab(ess_a_bagel, times_square)
    9
    >>> home = intersection(10, 10)
    >>> work = intersection(14, 13)
    >>> taxicab(home, work)
    7
    >>> taxicab(work, home)
    7
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q taxicab
Copy
✂️

Q2: Trade

In the integer market, each participant has a list of positive integers to trade. When two participants meet, they trade the smallest non-empty prefix of their list of integers. A prefix is a slice that starts at index 0.

Write a function trade that exchanges the first m elements of list first with the first n elements of list second, such that the sums of those elements are equal, and the sum is as small as possible. If no such prefix exists, return the string 'No deal!' and do not change either list. Otherwise change both lists and return 'Deal!'. A partial implementation is provided.

Note: You can mutate a slice of a list using slice assignment. To do so, specify a slice of the list [i:j] on the left-hand side of an assignment statement and another list on the right-hand side of the assignment statement. The operation will replace the entire given slice of the list from i inclusive to j exclusive with the elements from the given list. The slice and the given list need not be the same length.

>>> a = [1, 2, 3, 4, 5, 6]
>>> b = a
>>> a[2:5] = [10, 11, 12, 13]
>>> a
[1, 2, 10, 11, 12, 13, 6]
>>> b
[1, 2, 10, 11, 12, 13, 6]

Additionally, recall that the starting and ending indices for a slice can be left out and Python will use a default value. lst[i:] is the same as lst[i:len(lst)], and lst[:j] is the same as lst[0:j].

Important: The starter code has already implemented the part of the function that performs the swap using slice assignment. Your task is only to figure out the correct prefix lengths to swap.

def trade(first, second):
    """Exchange the smallest prefixes of first and second that have equal sum.

    >>> a = [1, 1, 3, 2, 1, 1, 4]
    >>> b = [4, 3, 2, 7]
    >>> trade(a, b)  # Trades 1+1+3+2=7 for 4+3=7
    'Deal!'
    >>> a  # a's prefix [1,1,3,2] is replaced with b's prefix [4,3]
    [4, 3, 1, 1, 4]
    >>> b  # b's prefix [4,3] is replaced with a's prefix [1,1,3,2]
    [1, 1, 3, 2, 2, 7]
    >>> c = [3, 3, 2, 4, 1]
    >>> trade(b, c)  # No prefixes with equal sum
    'No deal!'
    >>> b  # b remains unchanged
    [1, 1, 3, 2, 2, 7]
    >>> c  # c remains unchanged
    [3, 3, 2, 4, 1]
    >>> trade(a, c)  # Trades 4+3+1=8 for 3+3+2=8
    'Deal!'
    >>> a
    [3, 3, 2, 1, 4]
    >>> b
    [1, 1, 3, 2, 2, 7]
    >>> c
    [4, 3, 1, 4, 1]
    >>> d = [1, 1]
    >>> e = [2]
    >>> trade(d, e)  # Trades 1+1=2 for 2=2
    'Deal!'
    >>> d
    [2]
    >>> e
    [1, 1]
    """
    m, n = 1, 1

    equal_prefix = lambda: ______________________
    while _______________________________:
        if __________________:
            m += 1
        else:
            n += 1

    if equal_prefix():
        first[:m], second[:n] = second[:n], first[:m]
        return 'Deal!'
    else:
        return 'No deal!'

Use Ok to test your code:

python3 ok -q trade
Copy
✂️

Q3: Filter

Write a function filter that takes in a list lst and condition, a one-argument function that returns either True or False, and mutates lst so that it only contains elements satisfying condition.

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

def filter(condition, lst):
    """Filters lst with condition 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
✂️

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 Assignment

Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.