# Homework 3 Solutions

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