## Starter Files

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

This lab assignment is OPTIONAL. This means it does not count toward your final grade, and completing it will NOT earn you any extra credit. It is intended to help with studying for the final exam. Note that the topics listed in this lab are NOT comprehensive of the scope of the final.

You do not have to submit to Gradescope, although there is an assignment with the autograder if you want to check your work.

Solutions are available here.

## Control

### Question 1: Second Max

Write a function that finds the second highest number in a list of positive integers. You can assume that the list always has at least two integers.

``````def second_max(lst):
"""
Return the second highest number in a list of positive integers.

>>> second_max([3, 2, 1, 0])
2
>>> second_max([2, 3, 3, 4, 5, 6, 7, 2, 3])
6
>>> second_max([1, 5, 5, 5, 1])
5
>>> second_max([5, 6, 6, 7, 1])
6
>>> second_max([5, 6, 7, 7, 1])
7
"""

highest = 0
second_highest = 0
for num in lst:
if num >= highest:
second_highest = highest
highest = num
elif num < highest and num > second_highest:
second_highest = num
return second_highest``````

Use OK to test your code:

``python3 ok -q second_max``

## Higher Order Functions

### Question 2: Count van Count

Consider the following implementations of `count_factors` and `count_primes`:

``````def count_factors(n):
"""Return the number of positive factors that n has."""
i, count = 1, 0
while i <= n:
if n % i == 0:
count += 1
i += 1
return count

def count_primes(n):
"""Return the number of prime numbers up to and including n."""
i, count = 1, 0
while i <= n:
if is_prime(i):
count += 1
i += 1
return count

def is_prime(n):
return count_factors(n) == 2 # only factors are 1 and n``````

The implementations look quite similar! Generalize this logic by writing a function `count_cond`, which takes in a two-argument predicate function ```mystery_function(n, i)```. `count_cond` returns a count of all the numbers from 1 to `n` that satisfy `mystery_function`.

Note: A predicate function is a function that returns a boolean (`True` or `False`).

``````def count_cond(mystery_function, n):
"""
>>> def divisible(n, i):
...     return n % i == 0
>>> count_cond(divisible, 2) # 1, 2
2
>>> count_cond(divisible, 4) # 1, 2, 4
3
>>> count_cond(divisible, 12) # 1, 2, 3, 4, 6, 12
6

>>> def is_prime(n, i):
...     return count_cond(divisible, i) == 2
>>> count_cond(is_prime, 2) # 2
1
>>> count_cond(is_prime, 3) # 2, 3
2
>>> count_cond(is_prime, 4) # 2, 3
2
>>> count_cond(is_prime, 5) # 2, 3, 5
3
>>> count_cond(is_prime, 20) # 2, 3, 5, 7, 11, 13, 17, 19
8
"""

i, count = 1, 0
while i <= n:
if mystery_function(n, i):
count += 1
i += 1
return count``````

Use OK to test your code:

``python3 ok -q count_cond``

## Lists and Dictionaries

### Question 3: Deep-Len

A list that contains one or more lists as elements is called a deep list. For example, `[1, [2, 3], 4]` is a deep list.

Write a function `deep_len` that takes a list and returns its deep length. See the doctests for the function's behavior.

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 deep_len(lst):
"""Returns the deep length of the list.

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

Use OK to test your code:

``python3 ok -q deep_len``

### Question 4: Counter

Implement the function `counter` which takes in a string of words `message`, and returns a dictionary where each key is a word in the message, and each value is the number of times that word is present in the original string.

``````def counter(message):
""" Returns a dictionary of each word in message mapped
to the number of times it appears in the input string.

>>> x = counter('to be or not to be')
>>> x['to']
2
>>> x['be']
2
>>> x['not']
1
>>> y = counter('run forrest run')
>>> y['run']
2
>>> y['forrest']
1
"""
word_list = message.split()

result_dict = {}
for word in word_list:
if word in result_dict:
result_dict[word] += 1
else:
result_dict[word] = 1
return result_dict``````

Use OK to test your code:

``python3 ok -q counter``

## Recursion

### Question 5: Knapsack

You're are a thief, and your job is to pick among `n` items that are of different weights and values. You have a knapsack that supports `c` pounds, and you want to pick some subset of the items so that you maximize the value you've stolen.

Define `knapsack`, which takes a list `weights`, list `values` and a capacity `c`, and returns that max value. You may assume that item 0 weighs `weights[0]` pounds, and is worth `values[0]`; item 1 weighs `weights[1]` pounds, and is worth `values[1]`; etc.

``````def knapsack(weights, values, c):
"""
>>> w = [2, 6, 3, 3]
>>> v = [1, 5, 3, 3]
>>> knapsack(w, v, 6)
6
"""
if weights == []:
return 0
else:
first_weight, rest_weights = weights[0], weights[1:]
first_value, rest_values = values[0], values[1:]
with_first = first_value + knapsack(rest_weights, rest_values, c - first_weight)
without_first = knapsack(rest_weights, rest_values, c)
if first_weight <= c:
return max(with_first, without_first)
return without_first``````

Use OK to test your code:

``python3 ok -q knapsack``

### Question 6: repeated, repeated

In Homework 2 you encountered the `repeated` function, which takes arguments `f` and `n` and returns a function equivalent to the nth repeated application of `f`. This time, we want to write `repeated` recursively. You'll want to use `compose1`, given below for your convenience:

``````def compose1(f, g):
""""Return a function h, such that h(x) = f(g(x))."""
def h(x):
return f(g(x))
return h``````
``````def repeated(f, n):
"""
>>> f = lambda x: x + 1
>>> g = repeated(f, 1)
>>> g(5)
6
>>> h = repeated(f, 3)
>>> h(5)
8
>>> f2 = lambda x: x * 2
>>> g2 = repeated(f2, 3)
>>> g2(3)
24
"""
if n == 0:
return lambda x: x # Identity
return compose1(f, repeated(f, n - 1))``````

Use OK to test your code:

``python3 ok -q repeated``

## OOP and Inheritance

### Question 7: 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.) Hint: Check out the `create_animal` method in this demo.
• 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
2020
>>> dime = mint.create(Dime)
>>> dime.year
2020
>>> Mint.current_year = 2100  # Time passes
>>> nickel = mint.create(Nickel)
>>> nickel.year     # The mint has not updated its stamp yet
2020
>>> nickel.worth()  # 5 cents + (80 - 50 years)
35
>>> 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 + (155 - 50 years). 155 is because this dime instance has year 2020
115
>>> Dime.cents = 20  # Upgrade all dimes!
>>> dime.worth()     # 20 cents + (155 - 50 years)
125
>>> m = Mint()
>>> n = m.create(Nickel)
>>> n.worth()
5
>>> n.year = 2015
>>> n.worth() # 5 cents + (160 - 50 years). 160 is from 2175 - 2015
115
"""
current_year = 2020

def __init__(self):
self.update()

def create(self, coin):
return coin(self.year)
def update(self):
self.year = Mint.current_year
class Coin:
cents = 0 # Default value of 0. This value will be overridden in subclasses.

def __init__(self, year):
self.year = year

def worth(self):
"The worth is a coin's face value + 1 cent for each year over age 50."
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``

### Question 8: Insert

Implement a function `insert` that takes a `Link`, a `value`, and an `index`, and inserts the `value` into the `Link` at the given `index`. You can assume the linked list already has at least one element. Do not return anything — `insert` should mutate the linked list.

Note: If the index is out of bounds, you can raise an `IndexError` with:

``raise IndexError``
``````def insert(link, value, index):
"""Insert a value into a Link at the given index.

<1 2 3>
<9001 1 2 3>
<9001 1 100 2 3>
IndexError
"""
if index == 0:
raise IndexError
else:

# iterative solution
index -= 1
if index == 0:
else:
raise IndexError``````

Use OK to test your code:

``python3 ok -q insert``

## Trees

### Question 9: Path

Write a function `path` that returns the path from the root of the tree to the given value `target` as a list if it exists and `[]` if it does not. You can assume all values are unique.

``````def path(t, target):
"""
>>> t = Tree(9, [Tree(7, [Tree(3), Tree(2)]), Tree(5)])
>>> path(t, 2)
[9, 7, 2]
>>> path(t, 5)
[9, 5]
>>> path(t, 8)
[]
"""
if t.value == target:
return [target]
elif t.is_leaf():
return []
else:
for b in t.branches:
rest = path(b, target)
if rest:
return [t.value] + rest
return []``````

Use OK to test your code:

``python3 ok -q path``

## Iterators and Generators

### Question 10: 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:
"""
>>> hey_iter = Str('hey')
>>> for char in hey_iter:
...     print(char)
h
e
y
>>> list(hey_iter)
[]
"""
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 11: Generate permutations

Given a list of unique elements, a permutation of the list is a reordering of the elements. For example, `[2, 1, 3]`, `[1, 3, 2]`, and `[3, 2, 1]` are all permutations of the list `[1, 2, 3]`.

Implement `generate_perms`, a generator function which takes in a `lst` and yields all the unique permutations of `lst` one at a time (see doctest for examples).

``````def generate_perms(lst):
"""
Generates the permutations of lst one by one.
>>> perms = generate_perms([1, 2, 3])
>>> hasattr(perms, '__next__')
True
>>> p = list(perms)
>>> p.sort()
>>> p
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
"""
if lst == []:
yield []    else:
for perm in generate_perms(lst[1:]):
for i in range(len(lst)):
yield perm[:i] + [lst[0]] + perm[i:]``````

Use OK to test your code:

``python3 ok -q generate_perms``

Feel free to replace the `for` loops with list comprehensions if you would rather use that.

## Efficiency

There is no code to submit for this part.

### Question 12

What is the asymptotic run time of the baz function?
``````def baz(n):
i = 1
sum = 0
while i <= n:
sum += bam(i)
i += 1
return sum

def bam(n):
i = 1
sum = 0
while i <= n:
sum += i
i += 1
return sum``````

Highlight the text on the line below this line to see the solution:

### Question 13

What is the asymptotic run time of the bonk function?

``````def bonk(n):
sum = 0
while n >= 2:
sum += n
n = n / 2
return sum``````

Highlight the text on the line below this line to see the solution:

## Submission

When you are done, submit your file to Gradescope. You only need to upload the following files:

• `lab12.py`