Due by 11:59pm on Tuesday, 2/14

## Instructions

Submission: When you are done, submit with `python3 ok --submit`. 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 okpy.org. 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:

## 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
"""
``````

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
"""
``````

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``

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.

>>> new = change(lst, 3, 1)
1 2 1
>>> newer = change(new, 1, 2)
2 2 2
2 2 2
"""
``````

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)
1
>>> lst2 = insert_at_end(lst1, 2)
1 2
>>> lst3 = insert_at_end(lst2, 3)
1 2 3
"""
``````

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.
3
4
5
"""
``````

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]
"""
``````

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 _______
``````

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
"""

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
"""
``````python3 ok -q build_binary_ones