Solution Files

You can find the solutions in hw04.py.

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
    """
    return abs(street(a)-street(b)) + abs(avenue(a)-avenue(b))

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: sum(first[:m]) == sum(second[:n])
    while m <= len(first) and n <= len(second) and not equal_prefix():
        if sum(first[:m]) < sum(second[:n]):
            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]
    """
    for e in lst[:]:
        if not condition(e):
            lst.remove(e)

# Alternate solution
def filter2(condition, lst):
    elems_to_remove = [e for e in lst if not condition(e)]
    for e in elems_to_remove:
        lst.remove(e)

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.