Solution Files

You can find the solutions in hw03.py.

Vitamins

Vitamin questions must be completed alone.

Question 1: Extending Rationals

Starting with the rational ADT from lecture, implement the two additional functions div_rat(x,y), which divides rational number x by y, and lt_rat(x, y), which returns True iff rational number x is less than rational y.

Use OK to test your code:

python3 ok -q div_rat
python3 ok -q lt_rat

Question 2: Has Seven

Write a function has_seven that takes a positive integer n and returns whether n contains the digit 7. Do not use any assignment statements - use recursion instead:

def has_seven(k):
    """Returns True if at least one of the digits of k is a 7, False otherwise.

    >>> has_seven(3)
    False
    >>> has_seven(7)
    True
    >>> has_seven(2734)
    True
    >>> has_seven(2634)
    False
    >>> has_seven(734)
    True
    >>> has_seven(7777)
    True
    """
if k % 10 == 7: return True elif k < 10: return False else: return has_seven(k // 10)

Use OK to test your code:

python3 ok -q has_seven

Required questions

You may choose to work with a partner on homework questions, but you must submit your own solution. That is, try to share ideas rather than code.

Recursion

Question 3: Ping pong

The ping-pong sequence counts up starting from 1 and is always either counting up or counting down. At element k, the direction switches if k is a multiple of 7 or contains the digit 7. The first 30 elements of the ping-pong sequence are listed below, with direction swaps marked using brackets at the 7th, 14th, 17th, 21st, 27th, and 28th elements:

1 2 3 4 5 6 [7] 6 5 4 3 2 1 [0] 1 2 [3] 2 1 0 [-1] 0 1 2 3 4 [5] [4] 5 6

Implement a function pingpong that returns the nth element of the ping-pong sequence. Do not use any assignment statements; however, you may use def statements.

Hint: If you're stuck, try implementing pingpong first using assignment and a while statement. Any name that changes value will become an argument to a function in the recursive definition.

def pingpong(n):
    """Return the nth element of the ping-pong sequence.

    >>> pingpong(7)
    7
    >>> pingpong(8)
    6
    >>> pingpong(15)
    1
    >>> pingpong(21)
    -1
    >>> pingpong(22)
    0
    >>> pingpong(30)
    6
    >>> pingpong(68)
    2
    >>> pingpong(69)
    1
    >>> pingpong(70)
    0
    >>> pingpong(71)
    1
    >>> pingpong(72)
    0
    >>> pingpong(100)
    2
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'pingpong', ['Assign', 'AugAssign'])
    True
    """
def pingpong_next(k, p, up): if k == n: return p if up: return pingpong_switch(k+1, p+1, up) else: return pingpong_switch(k+1, p-1, up) def pingpong_switch(k, p, up): if k % 7 == 0 or has_seven(k): return pingpong_next(k, p, not up) else: return pingpong_next(k, p, up) return pingpong_next(1, 1, True) # Alternate solution def pingpong2(n): if n <= 7: return n return direction(n) + pingpong(n-1) def direction(n): if n < 7: return 1 if (n-1) % 7 == 0 or has_seven(n-1): return -1 * direction(n-1) return direction(n-1)

You may use the function has_seven, which returns True if a number k contains the digit 7 at least once.

Use OK to test your code:

python3 ok -q pingpong

Linked Lists

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.

Question 4: Change

Write a function that takes in a linked list, lst, and two elements, s and t. The function returns a copy of lst but with all instances of s replaced with t.

def change(lst, s, t):
    """Returns a link matching lst but with all instances of s (if any)
    replaced by t.

    >>> lst = link(1, link(2, link(3)))
    >>> new = change(lst, 3, 1)
    >>> print_link(new)
    1 2 1
    >>> newer = change(new, 1, 2)
    >>> print_link(newer)
    2 2 2
    >>> newest = change(newer, 5, 1)
    >>> print_link(newest)
    2 2 2
    """
if lst == empty: return lst if first(lst) == s: return link(t, change(rest(lst), s, t)) return link(first(lst), change(rest(lst), s, t))

Use OK to test your code:

python3 ok -q change

Question 5: Insert-at-end

Write a function that returns a new linked list that is the same as lst with elem added at the end.

def insert_at_end(lst, elem):
    """Return a linked list that is the same as lst with elem added
    at the end.

    >>> lst1 = insert_at_end(empty, 1)
    >>> print_link(lst1)
    1
    >>> lst2 = insert_at_end(lst1, 2)
    >>> print_link(lst2)
    1 2
    >>> lst3 = insert_at_end(lst2, 3)
    >>> print_link(lst3)
    1 2 3
    """
if lst == empty: return link(elem, empty) else: return link(first(lst), insert_at_end(rest(lst), elem))

Use OK to test your code:

python3 ok -q insert_at_end

Question 6: Deep Linked List Length

A linked list that contains as elements one or more linked lists (each of which is also possibly deep) is called a deep linked list. For this problem, assume that each list item (i.e., value returned by first) is either an integer or a linked list. Write a function deep_len that takes in such a (possibly deep) linked list and returns the deep length of that linked list, which is the total number of integers contained in the deep list. To test if a value v is an integer, you can use type(v) is int.

def deep_len(lnk):
    """ Returns the deep length of a possibly deep linked list of integers.
    >>> deep_len(link(1, link(2, link(3, empty))))
    3
    >>> deep_len(link(link(1, link(2, empty)), link(3, link(4, empty))))
    4
    >>> deep_len(link(link(link(1, link(2, empty)), \
            link(3, empty)), link(link(4, empty), link(5, empty))))
    5
    """
if isempty(lnk): return 0 elif type(first(lnk)) is int: return 1 + deep_len(rest(lnk)) else: return deep_len(first(lnk)) + deep_len(rest(lnk))

Use OK to test your code:

python3 ok -q deep_len

Python Sequences

Question 7: Flatten

Write a function flatten that takes a (possibly deep) list and "flattens" it. For example:

>>> lst = [1, [[2], 3], 4, [5, 6]]
>>> flatten(lst)
[1, 2, 3, 4, 5, 6]

Hint: you can check if something is a list by using the built-in type function. For example,

>>> type(3) == list
False
>>> type([1, 2, 3]) == list
True
def flatten(lst):
    """Returns a flattened version of lst.

    >>> flatten([1, 2, 3])     # normal list
    [1, 2, 3]
    >>> x = [1, [2, 3], 4]      # deep list
    >>> flatten(x)
    [1, 2, 3, 4]
    >>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
    >>> flatten(x)
    [1, 1, 1, 1, 1, 1]
    """
if not lst: return [] elif type(lst[0]) == list: return flatten(lst[0]) + flatten(lst[1:]) else: return [lst[0]] + flatten(lst[1:])

Use OK to test your code:

python3 ok -q flatten

Question 8: Riffle Shuffle

The familiar riffle shuffle of a deck of cards (or in our case, of a sequence of things) results in a new configuration of cards in which the original top card is followed by the original middle card, then by the original second card, then the card after the middle, and so forth. Assuming the deck (sequence) contains an even number of cards, write a list comprehension that produces the shuffled sequence.

Hint: To write this as a single comprehension, you may find the expression k%2, which evaluates to 0 on even numbers and 1 on odd numbers, to be useful.

def riffle(deck):
    """Produces a single, perfect riffle shuffle of DECK, consisting of
    DECK[0], DECK[M], DECK[1], DECK[M+1], ... where M is position of the
    second half of the deck.  Assume that len(DECK) is even.
    >>> riffle([3, 4, 5, 6])
    [3, 5, 4, 6]
    >>> riffle(range(20))
    [0, 10, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 17, 8, 18, 9, 19]
    """
return [ deck[(i % 2) * len(deck)//2 + i // 2] for i in range(len(deck)) ]

Use OK to test your code:

python3 ok -q riffle

Trees

Question 9: Build ones

Define the function build_binary_ones, which takes in a height, h, as an argument and returns a new tree whose labels are all 1, with two branches at each inner (non-leaf) node, and whose height is h (a tree of height 0 has a single node with label 1.)

Then, write a function build_ones, which takes in a height as before but now a branching factor as well. We want to be able to generalize from just two branches per node to a specified number of branches per node.

You will find the tree abstraction you should use included in the .py file.

def build_binary_ones(h):
    """
    >>> print_tree(build_binary_ones(1))
    1
      1
      1
    >>> print_tree(build_binary_ones(2))
    1
      1
        1
        1
      1
        1
        1
    """
if h == 0: return tree(1) return tree(1, [build_binary_ones(h - 1), build_binary_ones(h - 1)])
def build_ones(h, branching_factor=2): """ >>> print_tree(build_ones(2)) 1 1 1 1 1 1 1 >>> print_tree(build_ones(3, 1)) 1 1 1 1 """
if h == 0: return tree(1) return tree(1, [build_ones(h - 1, branching_factor) for _ in range(branching_factor)])

There are even more ways to generalize this operation! We can determine which number is used to build the tree, e.g. 0. We can also provide a list of branching factors instead of using just one. The list goes on...

Use OK to test your code:

python3 ok -q build_binary_ones
python3 ok -q build_ones