# Lab 5: Midterm Review

*Due by 11:59pm on Wednesday, July 13.*

## Starter Files

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

# Midsemester Survey

Please fill out the course-wide midsemester survey by Wednesday, 7/13 @ 11:59pm PT. This survey is designed to help us make short term adjustments to the course so that it works better for you. We appreciate your feedback. We may not be able to make every change that you request, but we will read all the feedback and consider it.

# Required Questions

Let's say we'd like to model a bank account that can handle interactions
such as depositing funds or gaining interest on current funds.
In the following questions, we will be building off of the `Account`

class.
Here's our current definition of the class:

```
class Account:
"""An account has a balance and a holder.
>>> a = Account('John')
>>> a.deposit(10)
10
>>> a.balance
10
>>> a.interest
0.02
>>> a.time_to_retire(10.25) # 10 -> 10.2 -> 10.404
2
>>> a.balance # balance should not change
10
>>> a.time_to_retire(11) # 10 -> 10.2 -> ... -> 11.040808032
5
>>> a.time_to_retire(100)
117
"""
max_withdrawal = 10
interest = 0.02
def __init__(self, account_holder):
self.balance = 0
self.holder = account_holder
def deposit(self, amount):
self.balance = self.balance + amount
return self.balance
def withdraw(self, amount):
if amount > self.balance:
return "Insufficient funds"
if amount > self.max_withdrawal:
return "Can't withdraw that amount"
self.balance = self.balance - amount
return self.balance
```

### Q1: Retirement

Add a `time_to_retire`

method to the `Account`

class.
This method takes in an `amount`

and returns how many years the holder would
need to wait in order for the current `balance`

to grow to at least `amount`

,
assuming that the bank adds `balance`

times the `interest`

rate to the total
balance at the end of every year.

```
def time_to_retire(self, amount):
"""Return the number of years until balance would grow to amount."""
assert self.balance > 0 and amount > 0 and self.interest > 0
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q Account`

### Q2: FreeChecking

Implement the `FreeChecking`

class, which is like the `Account`

class from
lecture except that it charges a withdraw fee after 2 withdrawals.
If a withdrawal is unsuccessful, it still counts towards the number of free
withdrawals remaining, but no fee for the withdrawal will be charged.

Hint: Don't forget that`FreeChecking`

inherits from`Account`

! Check the Inheritance section in Topics for a refresher.

```
class FreeChecking(Account):
"""A bank account that charges for withdrawals, but the first two are free!
>>> ch = FreeChecking('Jack')
>>> ch.balance = 20
>>> ch.withdraw(100) # First one's free
'Insufficient funds'
>>> ch.withdraw(3) # And the second
17
>>> ch.balance
17
>>> ch.withdraw(3) # Ok, two free withdrawals is enough
13
>>> ch.withdraw(3)
9
>>> ch2 = FreeChecking('John')
>>> ch2.balance = 10
>>> ch2.withdraw(3) # No fee
7
>>> ch.withdraw(3) # ch still charges a fee
5
>>> ch.withdraw(5) # Not enough to cover fee + withdraw
'Insufficient funds'
"""
withdraw_fee = 1
free_withdrawals = 2
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q FreeChecking`

## Submit

Make sure to submit this assignment by running:

`python3 ok --submit`

# Suggested Questions

## Control

### Q3: Ordered Digits

Implement the function `ordered_digits`

, which takes as input a
positive integer and returns `True`

if its digits, read left to right,
are in non-decreasing order, and `False`

otherwise. For example, the
digits of 5, 11, 127, 1357 are ordered, but not those of 21 or 1375.

Note:You can solve this with either iteration or recursion. We recommend trying both for practice purposes but you will credit for either one.

```
def ordered_digits(x):
"""Return True if the (base 10) digits of X>0 are in non-decreasing
order, and False otherwise.
>>> ordered_digits(5)
True
>>> ordered_digits(11)
True
>>> ordered_digits(127)
True
>>> ordered_digits(1357)
True
>>> ordered_digits(21)
False
>>> result = ordered_digits(1375) # Return, don't print
>>> result
False
"""
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q ordered_digits`

### Q4: K Runner

An *increasing run* of an integer is a sequence of consecutive digits in
which each digit is larger than the last. For example, the number 123444345
has four increasing runs: 1234, 4, 4 and 345. Each run can be indexed
**from the end** of the number, starting with index 0. In the example, the
0th run is 345, the first run is 4, the second run is 4 and the third run is
1234.

Implement `get_k_run_starter`

, which takes in integers `n`

and `k`

and returns
the 0th digit of the `k`

th increasing run within `n`

. The 0th digit is the
leftmost number in the run. You may assume that there are at least `k+1`

increasing runs in `n`

.

```
def get_k_run_starter(n, k):
"""Returns the 0th digit of the kth increasing run within n.
>>> get_k_run_starter(123444345, 0) # example from description
3
>>> get_k_run_starter(123444345, 1)
4
>>> get_k_run_starter(123444345, 2)
4
>>> get_k_run_starter(123444345, 3)
1
>>> get_k_run_starter(123412341234, 1)
1
>>> get_k_run_starter(1234234534564567, 0)
4
>>> get_k_run_starter(1234234534564567, 1)
3
>>> get_k_run_starter(1234234534564567, 2)
2
"""
i = 0
final = None
while ____________________________:
while ____________________________:
____________________________
final = ____________________________
i = ____________________________
n = ____________________________
return final
```

Use Ok to test your code:

`python3 ok -q get_k_run_starter`

## Higher Order Functions

These are some utility function definitions you may see being used as part of the doctests for the following problems.

```
from operator import add, mul
square = lambda x: x * x
identity = lambda x: x
triple = lambda x: 3 * x
increment = lambda x: x + 1
```

### Q5: Make Repeater

Implement the function `make_repeater`

so that `make_repeater(func, n)(x)`

returns `func(func(...func(x)...))`

, where `func`

is applied `n`

times. That
is, `make_repeater(func, n)`

returns another function that can then be applied
to another argument. For example, `make_repeater(square, 3)(42)`

evaluates to
`square(square(square(42)))`

.

```
def make_repeater(func, n):
"""Return the function that computes the nth application of func.
>>> add_three = make_repeater(increment, 3)
>>> add_three(5)
8
>>> make_repeater(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
243
>>> make_repeater(square, 2)(5) # square(square(5))
625
>>> make_repeater(square, 4)(5) # square(square(square(square(5))))
152587890625
>>> make_repeater(square, 0)(5) # Yes, it makes sense to apply the function zero times!
5
"""
"*** YOUR CODE HERE ***"
def composer(func1, func2):
"""Return a function f, such that f(x) = func1(func2(x))."""
def f(x):
return func1(func2(x))
return f
```

Use Ok to test your code:

`python3 ok -q make_repeater`

### Q6: Apply Twice

Using `make_repeater`

define a function `apply_twice`

that takes a function of
one argument as an argument and returns a function that applies the
original function twice. For example, if `inc`

is a function that
returns `1`

more than its argument, then `double(inc)`

should be a
function that returns two more:

```
def apply_twice(func):
""" Return a function that applies func twice.
func -- a function that takes one argument
>>> apply_twice(square)(2)
16
"""
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q apply_twice`

## Environment Diagrams

### Q7: Doge

Draw the environment diagram for the following code.

```
wow = 6
def much(wow):
if much == wow:
such = lambda wow: 5
def wow():
return such
return wow
such = lambda wow: 4
return wow()
wow = much(much(much))(wow)
```

You can check out what happens when you run the code block using Python Tutor. Please ignore the “ambiguous parent frame” message on step 18. The parent is in fact f1.

### Q8: Environment Diagrams - Challenge

These questions were originally developed by Albert Wu and are included here for extra practice. We recommend checking your work in PythonTutor after filling in the diagrams for the code below.

#### Challenge 1

Draw the environment diagram that results from executing the code below.

Guiding Notes: Pay special attention to the names of the frames!

Multiple assignments in a single line: We will first evaluate the expressions on the right of the assignment, and then assign those values to the expressions on the left of the assignment. For example, if we had

`x, y = a, b`

, the process of evaluating this would be to first evaluate`a`

and`b`

, and then assign the value of`a`

to`x`

, and the value of`b`

to`y`

.

```
def funny(joke):
hoax = joke + 1
return funny(hoax)
def sad(joke):
hoax = joke - 1
return hoax + hoax
funny, sad = sad, funny
result = funny(sad(1))
```

#### Challenge 2

Draw the environment diagram that results from executing the code below.

```
def double(x):
return double(x + x)
first = double
def double(y):
return y + y
result = first(10)
```

## Recursion

### Q9: Add Characters

Given two words, `w1`

and `w2`

, we say `w1`

is a subsequence of `w2`

if all the letters in `w1`

appear in `w2`

in the same order (but
not necessarily all together). That is, you can add letters to any position in
`w1`

to get `w2`

.
For example, "sing" is a substring of "ab**s**orb**ing**" and "cat" is a substring of
"**c**ontr**a**s**t**".

Implement `add_chars`

, which takes in `w1`

and `w2`

, where `w1`

is a substring of `w2`

. This means that `w1`

is shorter than `w2`

. It should
return a string containing the characters you need to add to `w1`

to get `w2`

. **Your solution
must use recursion**.

In the example above, you need to add the characters "aborb" to "sing" to get "absorbing", and you need to add "ontrs" to "cat" to get "contrast".

The letters in the string you return should be in the order you have to add them from left to right.
If there are multiple characters in the `w2`

that could correspond to characters in `w1`

, use the
leftmost one. For example, `add_words("coy", "cacophony")`

should return "acphon", not "caphon"
because the first "c" in "coy" corresponds to the first "c" in "**c**ac**o**phon**y**".

```
def add_chars(w1, w2):
"""
Return a string containing the characters you need to add to w1 to get w2.
You may assume that w1 is a subsequence of w2.
>>> add_chars("owl", "howl")
'h'
>>> add_chars("want", "wanton")
'on'
>>> add_chars("rat", "radiate")
'diae'
>>> add_chars("a", "prepare")
'prepre'
>>> add_chars("resin", "recursion")
'curo'
>>> add_chars("fin", "effusion")
'efuso'
>>> add_chars("coy", "cacophony")
'acphon'
>>> from construct_check import check
>>> # ban iteration and sets
>>> check(LAB_SOURCE_FILE, 'add_chars',
... ['For', 'While', 'Set', 'SetComp']) # Must use recursion
True
"""
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q add_chars`

## Dictionaries

### Q10: Replace All

Given a dictionary `d`

, replace all occurrences of `x`

as a value (not a key)
with `y`

.

Hint: You can iterate through the keys of a dictionary using a`for`

statement:`>>> for k in {1: 2, 3: 4, 5: 6}: ... print(k) 1 3 5`

```
def replace_all(d, x, y):
"""Replace all occurrences of x as a value (not a key) in d with y.
>>> d = {3: '3', 'foo': 2, 'bar': 3, 'garply': 3, 'xyzzy': 99}
>>> replace_all(d, 3, 'poof')
>>> d == {3: '3', 'foo': 2, 'bar': 'poof', 'garply': 'poof', 'xyzzy': 99}
True
"""
"*** YOUR CODE HERE ***"
```

Use Ok to test your code:

`python3 ok -q replace_all`