# Lab 5 Solutions

## Review

### Question 1: WWPD: Higher Order Functions

Use Ok to test your knowledge with the following "What Would Python Display?" questions:

`python3 ok -q hof -u`

For all WWPD questions, type

`Function`

if you believe the answer is`<function...>`

,`Error`

if it errors, and`Nothing`

if nothing is displayed.

```
>>> def even(f):
... def odd(x):
... if x < 0:
... return f(-x)
... return f(x)
... return odd
>>> steven = lambda x: x
>>> stewart = even(steven)
>>> stewart
______<function ...>
>>> stewart(61)
______61
>>> stewart(-4)
______4
```

```
>>> def cake():
... print('beets')
... def pie():
... print('sweets')
... return 'cake'
... return pie
>>> chocolate = cake()
______beets
>>> chocolate
______Function
>>> chocolate()
______sweets
'cake'
>>> more_chocolate, more_cake = chocolate(), cake
______sweets
>>> more_chocolate
______'cake'
>>> def snake(x, y):
... if cake == more_cake:
... return lambda: x + y
... else:
... return x + y
>>> snake(10, 20)
______Function
>>> snake(10, 20)()
______30
>>> cake = 'cake'
>>> snake(10, 20)
______30
```

### Question 2: GCD

The greatest common divisor of two positive integers `a`

and `b`

is the
largest integer which evenly divides both numbers (with no remainder).
Euclid, a Greek mathematician in 300 B.C., realized that the greatest
common divisor of `a`

and `b`

is one of the following:

- the smaller value if it evenly divides the larger value (base case), OR
- the greatest common divisor of the smaller value and the remainder of the larger value divided by the smaller value (recursive call)

In other words, if `a`

is greater than `b`

and `a`

is not divisible by
`b`

, then

`gcd(a, b) == gcd(b, a % b)`

Write the `gcd`

function recursively using Euclid's algorithm.

`gcd(20, 30) == gcd(20, 30 % 20) == gcd(20, 10) == 10`

```
def gcd(a, b):
"""Returns the greatest common divisor of a and b.
Should be implemented using recursion.
>>> gcd(34, 19)
1
>>> gcd(39, 91)
13
>>> gcd(20, 30)
10
>>> gcd(40, 40)
40
"""
"*** YOUR CODE HERE ***"
a, b = max(a, b), min(a, b)
if a % b == 0:
return b
else:
return gcd(b, a % b)
```

Use OK to test your code:

`python3 ok -q gcd`

This is an example of the elegance that recursive solutions permit. Here for comparison is an iterative solution.

```
# Iterative solution, if you're curious
def gcd_iter(a, b):
"""Returns the greatest common divisor of a and b, using iteration.
>>> gcd_iter(34, 19)
1
>>> gcd_iter(39, 91)
13
>>> gcd_iter(20, 30)
10
>>> gcd_iter(40, 40)
40
"""
while a % b != 0:
a, b = b, a % b
return b
```

### Question 3: 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.

*Hint:* You can use `//`

and `%`

to separate a positive integer into
its one's digit and the rest of its digits.

```
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
>>> cases = [(1, True), (9, True), (10, False), (11, True), (32, False),
... (23, True), (99, True), (111, True), (122, True), (223, True),
... (232, False), (999, True),
... (13334566666889, True), (987654321, False)]
>>> [ordered_digits(s) == t for s, t in cases].count(False)
0
"""
"*** YOUR CODE HERE ***"
last = x % 10
val = x // 10
while x > 0 and last >= x % 10:
last = x % 10
x = x // 10
return x == 0
```

We split off each digit in turn from the right, comparing it to the previous digit we split off, which was the one immediately to its right. We stop when we run out of digits or we find an out-of-order digit.

Use OK to test your code:

`python3 ok -q ordered_digits`

### Question 4: A Bad List Flattener

There is something wrong with the following code! Figure out what is wrong with it, and then fix it to pass the doc string.

Hint, your fix should be very minor! Do not rewrite the whole program.

```
def bad_list_flattener(lst1, lst2):
"""
Flattens both lst1 and lst2, and returns the
concatenation of the two flattened lists. Flattening
a list means to collapse the list into one
dimension (like np.flatten).
>>> girls = [['Rachel', 'Green'], ['Phoebe', 'Buffay']]
>>> boys = [['Ross', 'Geller'], ['Chandler', 'Bing']]
>>> bad_list_flattener(girls, boys)
['Rachel', 'Green', 'Phoebe', 'Buffay', 'Ross', 'Geller', 'Chandler', 'Bing']
>>> cats = [['Persian'], ['British', 'Shorthair']]
>>> dogs = [['Golden', 'Retriever']]
>>> bad_list_flattener(dogs, cats)
['Golden', 'Retriever', 'Persian', 'British', 'Shorthair']
"""
newlist1 = []
newlist2 = []
for inner_lst in lst1:
for item in inner_lst:
newlist1 += item
for inner_lst in lst2:
for item in inner_lst:
newlist2 += item
return newlist1 + newlist2
```

```
def bad_list_flattener(lst1, lst2):
"""
Flattens both lst1 and lst2, and returns the
concatenation of the two flattened lists. Flattening
a list means to collapse the list into one
dimension (like np.flatten).
>>> girls = [['Rachel', 'Green'], ['Phoebe', 'Buffay']]
>>> boys = [['Ross', 'Geller'], ['Chandler', 'Bing']]
>>> bad_list_flattener(girls, boys)
['Rachel', 'Green', 'Phoebe', 'Buffay', 'Ross', 'Geller', 'Chandler', 'Bing']
>>> cats = [['Persian'], ['British', 'Shorthair']]
>>> dogs = [['Golden', 'Retriever']]
>>> bad_list_flattener(dogs, cats)
['Golden', 'Retriever', 'Persian', 'British', 'Shorthair']
"""
newlist1 = []
newlist2 = []
for inner_lst in lst1:
for item in inner_lst:
newlist1 += item
for inner_lst in lst2:
for item in inner_lst:
newlist2 += item
return newlist1 + newlist2
```

Use OK to test your code:

`python3 ok -q bad_list_flattener`

Please note that the question below, flatten, uses tree recursion, which is a topic that will not be tested on the midterm but is in scope for the final.

### Question 5: Flatten

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

. For
example:

```
>>> isinstance([1,2,3],list)
True
>>> isinstance(3,list)
False
```

or using the builtin function `type`

.

```
>>> 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]
"""
"*** YOUR CODE HERE ***"
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`

## Submit

Make sure to submit this assignment by running:

`python3 ok --submit`

## Extra Credit Practice Open in a new window

These questions are new this semester. They're a mix of Parsons Problems, Code Tracing questions, and Code Writing questions.

Confused about how to use the tool? Check out https://codestyle.herokuapp.com/cs88-lab01 for some problems designed to demonstrate how to solve these types of problems.

These cover some similar material to lab, so can be helpful to further review or try to learn the material. Unlike lab and homework, after you've worked for long enough and tested your code enough times on any of these questions, you'll have the option to view an instructor solution. You'll unlock each question one at a time, either by correctly answering the previous question or by viewing an instructor solution.

**Starting from lab 2 onward, each set of questions are worth half (0.5) a point per lab, for a total opportunity of 4-5 points throughout the semester.**

Use OK to test your code:

`python3 ok -q extra_credit`

## Past Midterms

For your reference, here is a table of past midterms to study with!

Name | Blank Exam | Solutions | Professor(s) | Walkthrough Video | Notes |
---|---|---|---|---|---|

Spring 2016 Practice | Link | Link | David Culler | ||

Spring 2016 | Link | Link | David Culler | Link | |

Spring 2016 Retake | Link | Link | David Culler | Link | Please see correction below for Q4. |

Spring 2018 | Link | Link | Gerald Friedland | Link | |

Fall 2018 | Link | Link | David Culler | Link | |

Spring 2019 | Link | Link | Gerald Friedland | Link | |

Fall 2019 | Link | Link | Michael Ball | Link | The correct calls to alt_fib(6) is 25 not 26. |

Fall 2019 CSM Mock Midterm | Link | Link | N/A |