#!/usr/bin/env python
# coding: utf-8

# # Week 2 Day 9 Thursday Main Exercises - **More Recursion!**
# 

# ## Question 1
# **Fibonacci numbers** have many applications in nature and math. Here are the first 10 Fibonacci numbers:
# 
# ```
# fib(0) == 0
# fib(1) == 1
# fib(2) == 1
# fib(3) == 2
# fib(4) == 3
# fib(5) == 5
# fib(6) == 8
# fib(7) == 13
# fib(8) == 21
# fib(9) == 34
# ...
# ```
# 
# Can you see a pattern? Using math, we can define the $n^{th}$ Fibonacci  number, $F(n)$, using a recurrence:
# 
# $F(0) = 0$
# 
# $F(1) = 1$
# 
# and for $n \ge 2$:
# 
# $F(n) = F(n - 1) + F(n - 2)$
# 
# **Task:** Write code to find the $n^{th}$ Fibonacci number.

# In[ ]:


def fib(n):
    # YOUR ANSWER HERE
    pass

# When you finish, these should all print True
print(fib(0) == 0)
print(fib(1) == 1)
print(fib(2) == 1)
print(fib(3) == 2)
print(fib(6) == 8)
print(fib(9) == 34)
print(fib(20) == 6765)


# ## Question 2
# Consider a recursive function called `tribonacci(n)`:
# * It takes a positive integer n
# * It returns the nth number in the tribonacci series.
# 
# **Tribonacci numbers** are like the Fibonacci numbers, but instead of starting with two predetermined terms, the sequence starts with three predetermined terms and each term afterwards is the sum of the preceding three terms. That is,
# 
# $\text{Tribonacci}(n) = \text{Tribonacci}(n-1) + \text{Tribonacci}(n-2) + \text{Tribonacci}(n-3)$
# 
# with $\text{Tribonacci}(0) = \text{Tribonacci}(1) = 0$ and $\text{Tribonacci}(2) = 1$
# 
# The first few tribonacci numbers are:
# 
# ```
# tribonacci(0) == 0
# tribonacci(1) == 0
# tribonacci(2) == 1
# tribonacci(3) == 1
# tribonacci(4) == 2
# tribonacci(5) == 4
# tribonacci(6) == 7
# tribonacci(7) == 13
# tribonacci(9) == 44
# tribonacci(11) == 149
# ```
# 
# Implement `tribonacci(num)`.
# 
# Hint: The base case includes 0, 1 and 2.

# In[ ]:


def tribonacci(n):
    # your code here
    pass

# after you finish, these all should print true
print('Test passed:', tribonacci(0) == 0)
print('Test passed:', tribonacci(1) == 0)
print('Test passed:', tribonacci(4) == 2)
print('Test passed:', tribonacci(5) == 4)
print('Test passed:', tribonacci(11) == 149)


# ## Question 3

# The [Catalan numbers](https://en.wikipedia.org/wiki/Catalan_number) count (among many other things) the number of parentheses expressions using `n` correctly matched pairs of parentheses. (You will see these expressions in `9a_supp`.)
# 
# For example:
# - $C_1 = 1$: `()`
# - $C_2 = 2$: `(())       ()()`
# - $C_3 = 5$: `((()))     (()())     (())()     ()(())     ()()() `
# 
# They are defined recursively as follows:
# 
# $$C_0 = 1$$
# 
# $$C_{n+1} = \sum_{i=0}^n C_iC_{n-i}$$
# 
# **Write a function** that computes $C_n$ given an input value `n`. **Use recursion!**

# In[ ]:


def catalan(n):
    # your code here
    pass

# after you finish, these all should print true
print('Test passed:', catalan(0) == 1)
print('Test passed:', catalan(1) == 1)
print('Test passed:', catalan(2) == 2)
print('Test passed:', catalan(3) == 5)
print('Test passed:', catalan(5) == 42)
print('Test passed:', catalan(7) == 429)


# ## Question 4
# 
# **Task:** Write the function `print_list(lst)` that prints out all the words in a nested list.
# 
# For example, if we have
# ```
# lst = [["hello"], "darkness", ["my", "old", ["friend"]]]
# ```
# it should give
# ```
# hello
# darkness
# my
# old
# friend
# ```
# 
# Hint: In your function, use a `for` loop to go through the list. Then:
#     
# - If the current element `x` is a list (`type(x) == list`), call your function `print_list` recursively with `x` as the argument. 
# - Otherwise, print `x` (This is the base case)
# 

# In[ ]:


def print_list(lst):
    # your code here
    pass 


# Test your code here
print_list([["hello"], "darkness", ["my", "old", ["friend"]]])


# ## Question 5
# Consider a recursive function called `nestedListSum(nestedList)`:
# * It takes a nested list `nestedList`, which can contain either integers or nested lists.
# * It returns the sum of all the integers in the nested list.
# 
# For example:
# 
# ```
# nestedListSum([1, 2, 3, [4, 5]]) == 15
# nestedListSum([[1, 2], [3, [4, 5]]]) == 15
# nestedListSum([1, [2, [3, [4, [5]]]]]) == 15
# ```
# 
# Implement `nestedListSum(nestedList)`.
# 
# Hint: Use the same `type` check as in the previous question.

# In[ ]:


def nestedListSum(nestedList):
    # your code here
    pass


# after you finish, these all should print true
print('Test passed:', nestedListSum([]) == 0)
print('Test passed:', nestedListSum([1, 2, 3, [4, 5]]) == 15)
print('Test passed:', nestedListSum([[1, 2], [3, [4, 5]]]) == 15)
print('Test passed:', nestedListSum([1, [2, [3, [4, [5]]]]]) == 15)


# ## Question 6

# In this exercise, we want to use recursion to create a flood-fill function for images. Our flood-fill function is supposed to fill a **connected region of black pixels** with a different color.
# 
# For example, if we do flood-fill with red color on the center of this image:
# 
# ![](floodfill-example-base.png)
# 
# the region containing the center pixel becomes red:
# 
# ![](floodfill-example-filled.png)
# 
# We first start with a function generating black-white noise images that we can use to test our function on later. Run the code below.

# In[ ]:


from simpleimage import SimpleImage
import random

def get_random_image(size, threshold):
    image = SimpleImage.blank(size, size)
    for y in range(size):
        for x in range(size):
            if random.random() > threshold:
                image.set_rgb(x, y, 0, 0, 0)
    return image

image = get_random_image(50, 0.7)
image.show(resize_width=200)


# **Exercise:** Now fill in the `floodfill(img, x, y, r, g, b)` function below. Its parameters are:
# - an image `img` to do the flood-fill on
# - a starting position `x` and `y`
# - the `r`, `g` and `b` components of the color to fill in.
# 
# Whenever we find a black pixel, we fill it with the new color and then do the same flood-fill procedure for the neighbors of our pixel, to expand the region we are filling in.
# 
# Hint: Proceed as follows:
# - Check if $(x, y)$ is within the boundary of the image, and if the pixel at $(x, y)$ is black. If yes:
#   - change the color of the pixel at $(x, y)$ using `img.set_rgb`
#   - recursively call `floodfill` for the pixels at $(x-1, y)$, $(x+1, y)$, $(x, y-1)$ and $(x, y+1)$.

# In[ ]:


def floodfill(img, x, y, r, g, b):
    # Your code here!
      
# This code tests your function on a 15x15 random image
image = get_random_image(15, 0.45)
image.set_rgb(7, 7, 0, 0, 0)  # Make sure the center pixel is black
image.show(resize_width=200)  # Show image before flood-fill
floodfill(image, 7, 7, 255, 0, 0)  # Do flood-fill at the center.
image.show(resize_width=200)  # Show image after flood-fill


# # Question 7
# 
# Write a function, `robotGrid(m, n)` that calculates the **number of unique paths** a robot placed at the top-left corner of a `m x n` grid can take to reach the bottom-right corner. The robot can only move **either down or right** at any point in time.
# 
# For example:
# 
# ```
# robotGrid(0, 0) == 1 
# # Explanation: There is only one way to reach the bottom-right corner of a 0 x 0 grid.
# 
# robotGrid(1, 1) == 2
# # Explanation: There are two ways to reach the bottom-right corner of a 1 x 1 grid. 
# #             1. Right -> Down
# #             2. Down -> Right
# 
# robotGrid(2, 2) == 6
# # Explanation: There are six ways to reach the bottom-right corner of a 2 x 2 grid.
# #             1. Right -> Right -> Down -> Down
# #             2. Right -> Down -> Right -> Down
# #             3. Right -> Down -> Down -> Right
# #             4. Down -> Right -> Right -> Down
# #             5. Down -> Right -> Down -> Right
# #             6. Down -> Down -> Right -> Right
# ```
# 
# ![](robotgrid.png)
# 
# Implement `robotGrid(m, n)` recursively.
# 
# Hint: If we know the number of unique paths to the point $(m-1, n)$ and $(m, n-1)$, how can this help us compute the number of unique paths to $(m, n)$?

# In[ ]:


def robotGrid(m, n):
    # your code here
    pass


# after you finish, these all should print true
print('Test passed:', robotGrid(0, 0) == 1)
print('Test passed:', robotGrid(1, 1) == 2)
print('Test passed:', robotGrid(1, 2) == 3)
print('Test passed:', robotGrid(2, 2) == 6)
print('Test passed:', robotGrid(3, 2) == 10)


# # Question 8
# 
# Write a Python program to calculate the harmonic sum of `n`.
# 
# Note: The harmonic sum is the sum of reciprocals of the positive integers.
# 
# Examples:
# ```
# harmonic_sum(1) == 1
# harmonic_sum(2) == (1 + 1/2)
# harmonic_sum(3) == (1 + 1/2 + 1/3)
# harmonic_sum(4) == (1 + 1/2 + 1/3 + 1/4)
# ```
# 
# Implement `harmonic_sum(n)`.

# In[ ]:


def harmonic_sum(n):
  # Your code here
  pass


# test your code here
print('Test passed:', harmonic_sum(7) == 1 + 1 / 2 + 1 / 3 + 1 / 4 + 1 / 5 + 1 / 6 + 1 / 7)
print('Test passed:', harmonic_sum(4) == 1 + 1 / 2 + 1 / 3 + 1 / 4)
print('Test passed:', harmonic_sum(5) == 1 + 1 / 2 + 1 / 3 + 1 / 4 + 1 / 5)