Homework 2
Due at 11:59:59 pm on 9/18/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:

• Section 1.5
• Section 1.6
• Section 2.3

To submit: run ok with the --submit option:

python3 ok --submit

Questions

Question 1: Fibonacci

The Fibonacci sequence is a famous sequence in mathematics. The first element in the sequence is 0 and the second element is 1. The nth element is defined as F_n = F_n-1 + F_n-2.

Implement the fib function, which takes an integer n and returns the nth Fibonacci number. Use a while loop in your solution.

def fib(n):
    """Returns the nth Fibonacci number.

    >>> fib(0)
    0
    >>> fib(1)
    1
    >>> fib(2)
    1
    >>> fib(3)
    2
    >>> fib(4)
    3
    >>> fib(5)
    5
    >>> fib(6)
    8
    >>> fib(100)
    354224848179261915075
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q fib

Question 2: Right Triangle

Write a function that takes in 3 sides a, b, and c and checks to see if they can be possible lenths of the sides of a right triangle. Recall Pythagorean's Theorem:

x^2 + y^2 = z^2 # where z is the hypotenuse

Hint: Find the smallest and largest side first

def right_triangle(a, b, c):
    """Determine whether a, b, and c can be sides of a right triangle
    >>> right_triangle(1, 1, 1)
    False
    >>> right_triangle(5, 3, 4)
    True
    >>> right_triangle(8, 10, 6)
    True
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q right_triangle

Question 3: Disneyland Discounts

Disneyland is having a special where they give discounts for grandparents accompanying their grandchildren. Help Disneyland figure out when the discount should be given. Define a function gets_discount that takes two numbers as input (representing the two ages) and returns True if one of them is a senior citizen (age 65 or above) and the other is a child (age 12 or below). You should not use if in your solution.

def gets_discount(x, y):
    """ Returns True if this is a combination of a senior citizen
    and a child, False otherwise.

    >>> gets_discount(65, 12)
    True
    >>> gets_discount(9, 70)
    True
    >>> gets_discount(40, 45)
    False
    >>> gets_discount(40, 75)
    False
    >>> gets_discount(65, 13)
    False
    >>> gets_discount(7, 9)
    False
    >>> gets_discount(73, 77)
    False
    >>> gets_discount(70, 31)
    False
    >>> gets_discount(10, 25)
    False
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q gets_discount

Question 4: Mul_by_num

Using higher order functions, complete the mul_by_num function. This function should take an argument and return a one argument function that multiplies any value passed to it by the original number.

def mul_by_num(factor):
    """
    Returns a function that takes one argument and returns num
    times that argument.
    >>> x = mul_by_num(5)
    >>> y = mul_by_num(2)
    >>> x(3)
    15
    >>> y(-4)
    -8
    """
    "*** YOUR CODE HERE ***"
    

Use OK to test your code:

python3 ok -q mul_by_num

Question 5: 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 condition.

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

Use OK to test your code:

python3 ok -q count_cond