# Lab 14: Final Review

## Starter Files

Download lab14.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

## Linked Lists

### Question 1: Remove All

Implement a function `remove_all`

that takes a `Link`

, and a `value`

,
and remove any list node containing that value. You can assume the
list already has at least one node containing `value`

and the first element is
never removed. Notice that you are not returning anything, so you should mutate the list.

```
def remove_all(link , value):
"""Remove all the nodes containing value. Assume there exists some
nodes to be removed and the first element is never removed.
>>> l1 = Link(0, Link(2, Link(2, Link(3, Link(1, Link(2, Link(3)))))))
>>> print_link(l1)
<0 2 2 3 1 2 3>
>>> remove_all(l1, 2)
>>> print_link(l1)
<0 3 1 3>
>>> remove_all(l1, 3)
>>> print_link(l1)
<0 1>
"""
"*** YOUR CODE HERE ***"
if link is Link.empty or link.rest is Link.empty:
return
if link.rest.first == value:
link.rest = link.rest.rest
remove_all(link, value)
else:
remove_all(link.rest, value)
# alternate solution
if link is not Link.empty and link.rest is not Link.empty:
remove_all(link.rest, value)
if link.rest.first == value:
link.rest = link.rest.rest
```

Use OK to test your code:

`python3 ok -q remove_all`

## Trees

### Question 2: Reverse Other

Write a function `reverse_other`

that mutates the tree such that *every other*
(odd_indexed) level of the tree's entries are all reversed. For example
`Tree(1,[Tree(2), Tree(3)])`

becomes `Tree(1,[Tree(3), Tree(2)])`

```
def reverse_other(t):
"""Reverse the entries of every other level of the tree using mutation.
>>> t = Tree(1, [Tree(2), Tree(3), Tree(4)])
>>> reverse_other(t)
>>> t
Tree(1, [Tree(4), Tree(3), Tree(2)])
>>> t = Tree(1, [Tree(2, [Tree(5, [Tree(7), Tree(8)]), Tree(6)]), Tree(3)])
>>> reverse_other(t)
>>> t
Tree(1, [Tree(3, [Tree(5, [Tree(8), Tree(7)]), Tree(6)]), Tree(2)])
"""
"*** YOUR CODE HERE ***"
def reverse_helper(t, need_reverse):
if t.is_leaf():
return
new_labs = [child.root for child in t.branches][::-1]
for i in range(len(t.branches)):
child = t.branches[i]
reverse_helper(child, not need_reverse)
if need_reverse:
child.root = new_labs[i]
reverse_helper(t, True)
```

Use OK to test your code:

`python3 ok -q reverse_other`

## Object-Oriented Programming

### Question 3: Mint

Complete the `Mint`

and `Coin`

classes so that the coins created by a mint have
the correct year and worth.

- Each
`Mint`

instance has a`year`

stamp. The`update`

method sets the`year`

stamp to the`current_year`

class attribute of the`Mint`

class. - The
`create`

method takes a subclass of`Coin`

and returns an instance of that class stamped with the`mint`

's year (which may be different from`Mint.current_year`

if it has not been updated.) - A
`Coin`

's`worth`

method returns the`cents`

value of the coin plus one extra cent for each year of age beyond 50. A coin's age can be determined by subtracting the coin's year from the`current_year`

class attribute of the`Mint`

class.

```
class Mint:
"""A mint creates coins by stamping on years.
The update method sets the mint's stamp to Mint.current_year.
>>> mint = Mint()
>>> mint.year
2017
>>> dime = mint.create(Dime)
>>> dime.year
2017
>>> Mint.current_year = 2100 # Time passes
>>> nickel = mint.create(Nickel)
>>> nickel.year # The mint has not updated its stamp yet
2017
>>> nickel.worth() # 5 cents + (85 - 50 years)
38
>>> mint.update() # The mint's year is updated to 2100
>>> Mint.current_year = 2175 # More time passes
>>> mint.create(Dime).worth() # 10 cents + (75 - 50 years)
35
>>> Mint().create(Dime).worth() # A new mint has the current year
10
>>> dime.worth() # 10 cents + (160 - 50 years)
118
>>> Dime.cents = 20 # Upgrade all dimes!
>>> dime.worth() # 20 cents + (160 - 50 years)
128
>>> m = Mint()
>>> n = m.create(Nickel)
>>> n.worth()
5
>>> n.year = 2017
>>> n.worth()
113
"""
current_year = 2017
def __init__(self):
self.update()
def create(self, kind):
"*** YOUR CODE HERE ***"
return kind(self.year)
def update(self):
"*** YOUR CODE HERE ***"
self.year = Mint.current_year
class Coin:
def __init__(self, year):
self.year = year
def worth(self):
"*** YOUR CODE HERE ***"
return self.cents + max(0, Mint.current_year - self.year - 50)
class Nickel(Coin):
cents = 5
class Dime(Coin):
cents = 10
```

Use OK to test your code:

`python3 ok -q Mint`

## Scheme

Scheme questions are to be done in `lab14.scm`

.

### Question 4: Accumulate

Fill in the definition for the procedure `accumulate`

, which combines the first
`n`

natural numbers according to the following parameters:

`combiner`

: a function of two arguments`start`

: a number with which to start combining`n`

: the number of natural numbers to combine`term`

: a function of one argument that computes the*n*th term of a sequence

For example, we can find the product of all the numbers from 1 to 5 by using the multiplication operator as the `combiner`

, and starting our product at 1:

```
scm> (define (identity x) x)
scm> (accumulate * 1 5 identity) ; 1 * 1 * 2 * 3 * 4 * 5
120
```

We can also find the sum of the squares of the same numbers by using the addition operator as the `combiner`

and `square`

as the `term`

:

```
scm> (define (square x) (* x x))
scm> (accumulate + 0 5 square) ; 0 + 1^2 + 2^2 + 3^2 + 4^2 + 5^2
55
```

```
(define (accumulate combiner start n term)
(if (= n 0)
start
'YOUR-CODE-HERE
(combiner (accumulate combiner
start
(- n 1)
term)
(term n)) )
)
;;; Tests
(define (identity x) x)
(accumulate * 1 5 identity)
; expect 120
(define (square x) (* x x))
(accumulate + 0 5 square)
; expect 55
```

Use OK to test your code:

`python3 ok -q accumulate`

### Question 5: How Many Dots?

Implement `how-many-dots`

, which takes in a nested scheme list `s`

and returns
the number of dots that appear when it is displayed by the interpreter (not
counting decimal points). You may assume that `s`

is a nested list that
contains only numbers.

*Hints*: A dot appears when the second element of a pair is not a well formed
list. The procedures `pair?`

, `null?`

, and `number?`

test whether a value is a pair, `nil`

, or a number, respectively.

```
(define (how-many-dots s)
'YOUR-CODE-HERE
(if (not (pair? s))
0
(+ (if (and (not (pair? (cdr s)))
(not (null? (cdr s))))
1
0)
(how-many-dots (car s))
(how-many-dots (cdr s)))))
;;; Tests
(how-many-dots '(1 2 3))
; expect 0
(how-many-dots '(1 2 . 3))
; expect 1
(how-many-dots '((1 . 2) 3 . 4))
; expect 2
(how-many-dots '((((((1 . 2) . 3) . 4) . 5) . 6) . 7))
; expect 6
(how-many-dots '(1 . (2 . (3 . (4 . (5 . (6 . (7))))))))
; expect 0
```

Use OK to test your code:

`python3 ok -q how-many-dots`

### Question 6: Swap

Write a tail-recursive function `swap`

, which takes in a Scheme list `s`

and returns a new Scheme list where every two elements in `s`

are swapped.

```
(define (swap s)
'YOUR-CODE-HERE
(define (helper sofar rest)
(cond ((null? rest) sofar)
((null? (cdr rest)) (append sofar (list (car rest))))
(else (helper (append sofar (list (car (cdr rest)) (car rest)))
(cdr (cdr rest))))))
(helper () s))
;;; Tests
(swap (list 1 2 3 4))
; expect (2 1 4 3)
(swap (list 1 2 3 4 5))
; expect (2 1 4 3 5)
```

Use OK to test your code:

`python3 ok -q swap`

## Interpreters

### Question 7: Eval/Apply

This question is from the final review.With your Project 4 implementation, how many total calls to `scheme_eval`

and `scheme_apply`

would be made when evaluating the following two
expressions? Assume that you are not using the tail call optimized
`scheme_eval_optimized`

function.

```
(define (square x) (* x x))
(+ (square 3) (- 3 2))
```

`14 eval calls, 4 apply calls`

## Iterators and Generators

### Question 8: Str

Write an iterator that takes a string as input and outputs the letters in order when iterated over.

```
class Str:
def __init__(self, str):
self.str = str
def __iter__(self):
return iter(self.str)
```

That works (why?), but just kidding.

```
class Str:
"""
>>> s = Str("hello")
>>> for char in s:
... print(char)
...
h
e
l
l
o
>>> for char in s: # a standard iterator does not restart
... print(char)
"""
"*** YOUR CODE HERE ***"
def __init__(self, str):
self.str = str
self.i = -1
def __iter__(self):
return self
def __next__(self):
self.i += 1
if self.i >= len(self.str):
raise StopIteration
return self.str[self.i]
```

Use OK to test your code:

`python3 ok -q Str`

### Question 9: List-Dictionary Iterator

Create an `ListDictIter`

iterator class that is initialized with a list and dictionary. Calling next on an instance of the class will return `x`

. `x`

is the dictionary value of the next item of the list, or, if the item is not a key in the dictionary, `x`

is just the item.

Hint: you can use the get method of a dictionary to specify a default value if a key is not in the dictionary, e.g. `dct.get("dog", "cat")`

will return either the value that "dog" is a key for in dct, or "cat" if "dog" is not a key.

```
class ListDictIter:
""" Returns an iterator that yields either the corresponding
dictionary value of the next element in the list or the element
itself if it is not a key in the dictionary.
>>> sounds = {'cat': 'meow', 'cow': 'moo','ghost': 'boo'}
>>> things = ['cat', 'moo', 'ghost', 'pikachu']
>>> x = ListDictIter(things, sounds)
>>> list(x)
['meow', 'moo', 'boo', 'pikachu']
>>> y = ListDictIter(things, sounds)
>>> next(y)
'meow'
>>> next(y)
'moo'
"""
def __init__(self, lst, dct):
"*** YOUR CODE HERE ***"
self.lst = lst
self.dct = dct
self.index = 0
def __iter__(self):
return self
def __next__(self):
"*** YOUR CODE HERE ***"
if self.index >= len(self.lst):
raise StopIteration
else:
m = self.index
self.index += 1
return self.dct.get(self.lst[m], self.lst[m])
```

Use OK to test your code:

`python3 ok -q ListDictIter`

### Question 10: Pairs (generator)

Write a generator function `pairs`

that takes a list and yields all the
possible pairs of elements from that list.

```
def pairs(lst):
"""
>>> type(pairs([3, 4, 5]))
<class 'generator'>
>>> for x, y in pairs([3, 4, 5]):
... print(x, y)
...
3 3
3 4
3 5
4 3
4 4
4 5
5 3
5 4
5 5
"""
"*** YOUR CODE HERE ***"
for i in lst:
for j in lst:
yield i, j
```

Use OK to test your code:

`python3 ok -q pairs`

### Question 11: Pairs (iterator)

Now write an iterator that does the same thing. You are only allowed to use a linear amount of space - so computing a list of all of the possible pairs is not a valid answer. Notice how much harder it is - this is why generators are useful.

```
class PairsIterator:
"""
>>> for x, y in PairsIterator([3, 4, 5]):
... print(x, y)
...
3 3
3 4
3 5
4 3
4 4
4 5
5 3
5 4
5 5
"""
def __init__(self, lst):
"*** YOUR CODE HERE ***"
self.lst = lst
self.i = 0
self.j = 0
def __next__(self):
"*** YOUR CODE HERE ***"
if self.i == len(self.lst):
raise StopIteration
result = (self.lst[self.i], self.lst[self.j])
if self.j == len(self.lst) - 1:
self.i += 1
self.j = 0
else:
self.j += 1
return result
def __iter__(self):
"*** YOUR CODE HERE ***"
return self
```

Use OK to test your code:

`python3 ok -q PairsIterator`

## Streams

### Question 12: Cycle

Define a function `cycle`

which takes in as input an ordinary Python
list and returns a stream which just repeats that list over and over
For example, `cycle(['a', 'b', 'c'])`

is the stream containing elements
`['a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', ...]`

. If the input list
is empty, output the empty stream; otherwise, the output stream should
be infinite.

```
def cycle(list):
"""
Returns a Stream that cycles through each entry of the list.
>>> s = cycle(['a', 'b', 'c'])
>>> s.first
'a'
>>> s.rest.first
'b'
>>> s.rest.rest.rest.rest.first
'b'
>>> t = cycle([])
>>> t is Stream.empty
True
>>> isinstance(s, Stream)
True
>>> isinstance(s.rest.rest, Stream)
True
"""
"*** YOUR CODE HERE ***"
if list == []:
return Stream.empty
return Stream(list[0], lambda: cycle(list[1:] + list[:1]))
```

Use OK to test your code:

`python3 ok -q cycle`

### Question 13: Run-Length Encoding

Run-length encoding is a very simple data compression technique,
whereby runs of data are compressed and stored as a single value. A
*run* is defined to be a contiguous sequence of the same number. For
example, in the (finite) sequence

`1, 1, 1, 1, 1, 6, 6, 6, 6, 2, 5, 5, 5`

there are four runs: one each of 1, 6, 2, and 5. We can represent the same sequence as a sequence of tuples:

`(5, 1), (4, 6), (1, 2), (3, 5)`

Notice that the first element of each tuple is the number of times a particular number appears in a run, and the second element is the number in the run.

We will extend this idea to (possibly infinite) streams. Write a
function called `rle`

that takes in a stream of data, and returns a
corresponding stream of tuples, which represents the run-length encoded
version of the stream. It will also take in the maximum size of any
given run (default 10) to prevent having to compress infinite runs.

```
def rle(s, max_run_length=10):
"""
>>> example_stream = lst_to_stream([1, 1, 1, 2, 3, 3])
>>> encoded_example = rle(example_stream)
>>> stream_to_list(encoded_example, 3)
[(3, 1), (1, 2), (2, 3)]
>>> shorter_encoded_example = rle(example_stream, 2)
>>> stream_to_list(shorter_encoded_example, 4)
[(2, 1), (1, 1), (1, 2), (2, 3)]
>>> ints = Stream(1, lambda: increment_stream(ints))
>>> encoded_naturals = rle(ints)
>>> stream_to_list(encoded_naturals, 3)
[(1, 1), (1, 2), (1, 3)]
>>> ones = Stream(1, lambda: ones)
>>> encoded_ones = rle(ones, max_run_length=3)
>>> stream_to_list(encoded_ones, 3)
[(3, 1), (3, 1), (3, 1)]
"""
"*** YOUR CODE HERE ***"
if s == Stream.empty:
return s
first, s, count = s.first, s.rest, 1
while s != Stream.empty and s.first == first and count < max_run_length:
s, count = s.rest, count+1
return Stream((count, first), lambda: rle(s, max_run_length))
```

Use OK to test your code:

`python3 ok -q rle`