Due at 11:59:59 pm on 2/16/2020 .

## Instructions

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

Submission: When you are done, submit with `python3 ok --submit`. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on okpy.org. See this article for more instructions on okpy and submitting assignments.

Readings: This homework relies on following references:

## Questions

### Question 1: Falling Factorial

Let's write a function `falling`, which is a "falling" factorial that takes two arguments, `n` and `k`, and returns the product of `k` consecutive numbers, starting from `n` and working downwards.

If `k` is larger than n, only multiply up to n consecutive numbers!

``````def falling(n, k):
"""Compute the falling factorial of n to depth k.

>>> falling(6, 3)  # 6 * 5 * 4
120
>>> falling(4, 3)  # 4 * 3 * 2
24
>>> falling(4, 1)  # 4
4
>>> falling(4, 0)
1
"""

Use OK to test your code:

``python3 ok -q falling``

### Question 2: Hailstone

Complete this question using iteration!

Douglas Hofstadter's Pulitzer-prize-winning book, Gödel, Escher, Bach, poses the following mathematical puzzle:

1. Pick a positive integer `n` as the start.
2. If `n` is even, divide it by 2.
3. If `n` is odd, multiply it by 3 and add 1.
4. Continue this process until `n` is 1.

The sequence of values of `n` is often called a Hailstone sequence, because hailstones also travel up and down in the atmosphere before falling to earth. Write a function that takes a single argument with formal parameter name `n`, prints out the hailstone sequence starting at `n`, and returns the number of steps in the sequence:

``````def hailstone(n):
"""Print the hailstone sequence starting at n and return its
length.

>>> a = hailstone(10)
10
5
16
8
4
2
1
>>> a
7
"""

Hailstone sequences can get quite long! Try 27. What's the longest you can find?

Use OK to test your code:

``python3 ok -q hailstone``

### Question 3: Classify the elements

Complete the function `odd_even` that classifies an number as either `'odd'` or `'even'` and the function `classify` that takes in a list and applies `odd_even` to all elements in the list.

``````def odd_even(x):
"""Classify a number as odd or even.

>>> odd_even(4)
'even'
>>> odd_even(3)
'odd'
"""

def classify(s):
"""
Classify all the elements of a sequence as odd or even
>>> classify([0, 1, 2, 4])
['even', 'odd', 'even', 'even']
"""

Use OK to test your code:

``python3 ok -q odd_even``

Use OK to test your code:

``python3 ok -q classify``

### Question 4: Deep List

Implement the function `deep_list`, which takes in a list, and returns a new list which contains only elements of the original list that are also lists. Use a list comprehension.

``````def deep_list(seq):
"""Returns a new list containing elements of the original list that are lists.

>>> seq = [49, 8, 2, 1, 102]
>>> deep_list(seq)
[]
>>> seq = [[500], [30, 25, 24], 8, [0]]
>>> deep_list(seq)
[[500], [30, 25, 24], [0]]
>>> seq = ["hello", [12, [25], 24], 8, [0]]
>>> deep_list(seq)
[[12, [25], 24], [0]]
"""
``````

Use OK to test your code:

``python3 ok -q deep_list``

### Question 5: arange

Implement the function `arange`, which behaves just like np.arange(start, end, step) from Data 8. You only need to support positive values for step.

``````def arange(start, end, step=1):
"""
arange behaves just like np.arange(start, end, step).
You only need to support positive values for step.

>>> arange(1, 3)
[1, 2]
>>> arange(0, 25, 2)
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24]
>>> arange(999, 1231, 34)
[999, 1033, 1067, 1101, 1135, 1169, 1203]

"""
``````

Use OK to test your code:

``python3 ok -q arange``

### Question 6: 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 ```condition(n, i)```. `count_cond` returns a count of all the numbers from 1 to `n` that satisfy `condition`.

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

``````def count_cond(condition, 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
"""
``````

Use OK to test your code:

``python3 ok -q count_cond``

### Question 7: Match and Apply

Sometimes when we are given a dataset, we need to alter it for specific values. For example, say we have a table with one column being people's names and the other being the price they have to pay.

We can use a list of pairs for this:

`[["Jessica", 5], ["Andrew", 9], ["Alex", 2], ["Amir", 11], ["John", 3], ["Lyric", 2]]`

The first value in each pair is the name, the second is the price.

Now, let's say we want to give a discount to specific people. We have a discount function that we want to apply to the person's price. Now, we need a function that will only apply the discount function to specific people.

Implement `match_and_apply(pairs, function)`:

• `pairs` is a list of pairs.
• `function` is some function

`match_and_apply` returns a function such that when the function is given an input that matches the first of a pair, returns the result of applying `function` to the second value in the pair.

``````def match_and_apply(pairs, function):
"""
>>> pairs = [[1, 2], [3, 4], [5, 6], [7, 8], [9, 0]]
>>> def square(num):
...     return num**2
>>> func = match_and_apply(pairs, square)
>>> result = func(3)
>>> result
16
>>> result = func(1)
>>> result
4
>>> result = func(7)
>>> result
64
>>> result = func(15)
>>> print(result)
None

"""
``python3 ok -q match_and_apply``