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

# # Week 4 Day 16, Core: Memoization

# In[ ]:


def check_test(actual, expected):
    if expected != actual:
        print(f"Function should return the value {expected}, it is returning the value {actual}")
    else:
        print(f"Congratulations, the test case passed!")


# ## 0. Climbing Stairs

# You are climbing a staircase. It takes `n` steps to reach the top. Each time you can either climb `1` or `2` steps. In how many distinct ways can you climb to the top?

# ### 0.1

# Write a recursive function `climbing_stairs(n)` that takes an integer `n` and returns the number of distinct ways  you can climb to the top.
# 
# <details>
#     <summary><b>Give me a Hint (click)</b></summary>
#     If you know in how many ways you can climb <tt>n-2</tt> steps, and in how many ways you can climb <tt>n-1</tt> steps, how does that help you in computing in how many ways you can climb <tt>n</tt> steps?
# </details>

# In[ ]:


def climbing_stairs(n):
    # Your code here
    pass


# In[ ]:


# Test your code
print(climbing_stairs(10))  # This should give 89
print(climbing_stairs(35))  # This should give 14930352


# You might notice that the computation of `climbing_stairs(35)` takes a few seconds.

# ### 0.2 
# Add `print("Calculating value for " + str(n))` at the beginning of your function (make it the first line), run it, and run the cell below :

# In[ ]:


climbing_stairs(10)


# How many times does it print `3` ?

# Answer here:

# What did you learn from the number?

# Answer here: 

# ## Check your answer here

# In[ ]:


def check_test(actual, expected):
    if expected != actual:
        print(f"Function should return the value {expected}, it is returning the value {actual}")
    else:
        print(f"Congratulations, the test case passed!")
        
check_test(climbing_stairs(2), 2)
check_test(climbing_stairs(5), 8)
check_test(climbing_stairs(6), 13)


# ## 1. Climbing Stairs - Memoized

# We are going to store things we have computed before in a list `mem` such that <br/><br/>
# $$
# mem[i] = \begin{cases}-1 \text{ if we haven't computed } climbing\_stairs_i \text{ before }\\
#       climbing\_stairs_i \text{ if we have already computed it}
#     \end{cases}
# $$
# 
# ### 1.1
# Write a function `create_memory(n)` that takes an integer `n` and returns a list L of length `n` that contains the integer `-1` repeated `n` times.
# 
# 

# In[ ]:


def create_memory(n):
    # Your code here


# 
# ### 1.2
# Write a function `check(i, mem)` that takes an index `i` and a list `mem` and returns `True` if `mem[i]` is not equal to `-1`:

# In[ ]:


def check(i, mem):
    # Your code here


# ### 1.3
# Write a function `add(mem, i, value)` that takes a list `mem`, an index `i` and an integer `value` and that stores the integer `value` in the list `mem` at index `i` :

# In[ ]:


def add(mem, i, value):
    # Your code here


# ### 1.4
# Write a recursive function `memo_climbing_stairs(n, mem)` that takes an integer `n` and a list `mem`.<br/><br/>
# Here is how it should work : 
# <ul>
#     <li> If <code>mem[n]</code> is <i>not</i> equal to <code>-1</code>, it should return <code>mem[n]</code></li>
#     <li> If <code>mem[n]</code> is equal to <code>-1</code>, it should compute the value recursively and store it in <code>mem[n]</code> before returning it.</li>
# </ul>

# In[ ]:


def memo_climbing_stairs(n, mem):
    # Your code here


# ### 1.5
# Write a function `climbing_stairs(n)` that takes an integer `n`. It should use `create_memory(n)` and `memo_climbing_stairs(n, mem)`.<br><br>*Hint: Remember that we are storing values from 0 to n*

# In[ ]:


def climbing_stairs(n):
    # Your code here

# Check your answer here
check_test(climbing_stairs(2), 2)
check_test(climbing_stairs(5), 8)
check_test(climbing_stairs(6), 13)
check_test(climbing_stairs(35), 14930352)


# Do you notice any difference in how long it takes to compute `climbing_stairs(35)`?

# **your answer here**

# ## 2. Fibonnacci Sequence
# 
# The fibonnacci sequence is defined as below :
# 
# $$
# \Large
# f_n = \begin{cases}n \text{ if }  \leq 1\\
#     f_{n-1} + f_{n-2} \text{ if } n > 1
#     \end{cases}
# $$
# 
# For example, the first eight Fibonnacci numbers are:
# 
# 0,1,1,2,3,5,8,13 . . .
# 
# ### 2.1
# 
# Write a recursive function `fib(n)` that takes an integer `n` and returns $f_n$.

# In[ ]:


def fib(n):
    # Your code here


# ### 2.2
# 
# Write a memoized version of the above function.
# 
# <details>
#     <summary><b>Give me a Hint (click)</b></summary>
# This should work the same way as 2.4.
# </details>

# In[ ]:


def memo_fib(n, mem):
    # Your code here


# ### 2.3
# 
# Write a function `fib(n)` that takes an integer `n`. It should use `create_memory(n)` and `memo_fib(n, mem)`.<br><br>*Hint: Remember that we are storing fibs from 0 to n*

# In[ ]:


def fib(n):
    # Your code here


# ## Check your answer here

# In[ ]:


check_test(fib(7), 13)
check_test(fib(0), 0)
check_test(fib(1), 1)


# ## Q:
# Do you think `fibonnacci sequence` and `climbing stairs` are related? If so, how?

# YOUR ANSWER GOES HERE

# ## 3. Making Basketball Teams
# 
# You have `n` classmates. You want to create a team of `k` players. How many different teams can you create ?
# 
# You may have seen in math class that the number we are looking for is :
# $$
# \Large
# \binom{n}{k}
# $$
# 
# To choose your team, you can either pick the tallest classmate and then pick the remaining `k-1` players, or you can decide to leave out your tallest classmate and pick a team among `n-1` classmates. 
# 
# This yields the recursive formula :
# $$
# \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}
# $$
# 
# 
# ### 3.1
# Write a recursive function `binom(n, k)` that takes two integers `n` and `k` and returns $\binom{n}{k}$ :
# 
# *Hint : Think of your base case carefully. What is $\binom{n}{0}$ ? What is $\binom{0}{k}$ if $k \neq 0$ ?*
# 

# In[ ]:





# ### 3.2
# We're going to create a list of lists called `mem` such that : <br/><br/>
# $$
# mem[i][j] =
# \begin{cases}
# -1 \text{  if }\binom{i}{j} \text{ has not been computed before}\\
# \binom{i}{j} \text{ if it has}
# \end{cases}
# $$
# 
# Write a function `create_memory(r, c)` that takes two integers `r` and `c` and returns a list of lists with `r` rows and `c` colums where **all entries are -1**.
# 
# <details>
#     <summary><b>Give me a Hint (click)</b></summary>
# Make sure the rows are referencing different lists!
#     
# For example, the code below **does NOT work**:
# ```python
# lst = [ [-1] * 4 ] * 3
# ```
# 
# If you now modify an entry, for example `list[0][0] = 5`, the whole first column will change to 5, because all rows point to the same list. If you have internet, you can use `pythontutor.com` to visualize this!
#     
# Instead, use a list comprehension or for loop to create the rows.
# </details>

# In[ ]:


def create_memory(r, c):
    # Your code here

# Check your answer here
matrix = create_memory(3, 2)
check_test(matrix, [[-1, -1], [-1, -1], [-1, -1]])
matrix[0][0] = 5  # Make sure only one entry changes
check_test(matrix, [[5, -1], [-1, -1], [-1, -1]])


# ### 3.3
# Write a function `memo_binom(n, k, mem)` that takes two integers `n`, `k` and a list of lists `mem` and that returns $\binom{n}{k}$.
# 
# As before, this function should **check** in `mem` if $\binom{n}{k}$ has been computed before, and if not, compute it recursively and add the answer to `mem`.

# In[ ]:





# ### 3.4
# Write a function `binom(n, k)` that returns $\binom{n}{k}$. It should use `create_memory(r, c)` and `memo_binom(n, k, mem)`.

# In[ ]:





# ## 4. Moving in a grid
# 
# 
# We want to find the number of paths that go from `A` to `Z` in the grid below :
# 
# <center>
#     <img src = "gridpaths.png" width = "500px">
# </center>
# 
# Two examples paths are drawn below in red: 
# 
# <table>
#     <tr>
#         <td><img src = "onepath.png" width = "300px"> </td>
#         <td><img src = "path2.png" width = "300px"> </td>
# </table>
# 
# We number the points in the grid like so :
# 
# 
#  <img src = "numbered.png" width = "300px"> 
# 
# Let $T(a,b)$ denote the number of ways of getting from (0,0) to (a, b). For example $T(0,1) = 1$ and $T(1,1) = 3$
# 
# ##### Recursive formula :
# 
# If you know $T(a-1, b)$, $T(a, b-1)$ and $T(a-1, b-1)$, how can you find $T(a,b)$ ? 
# 

# **Your answer here**

# 
# ### 4.1
# Write a recursive function `T(a,b)` that takes two integers `a` and `b` and returns the number of ways of getting from (0,0) to (a,b):
# 
# 
# <details>
#     <summary><b>Give me a Hint (click)</b></summary>
# For the base case, how many different paths are there from $(0, 0)$ to $(a, 0)$? How many different paths are there from $(0, 0)$ to $(0, b)$?
# </details>

# In[ ]:





# ### 4.2
# How many ways are there of getting from `A` to `Z` ?
# <br/>
# 
# 

# In[ ]:


# Answer here



# ### 4.3
# Following the previous exercise's procedure, write a function `memo_T(a,b)` that takes integers `a` and `b` and returns $T(a,b)$: 

# In[ ]:





# ### 4.4 
# Write a function `T(a, b)` that takes two integers `a` and `b` and returns the number of ways of getting from (0,0) to (a,b). It should use `memo_T(a, b)` :

# In[ ]:





# ## 5. Min Number of Ways to Make Change
# 
# Suppose you live in a country whose coin denominations are in the list ```L```. For example, in Ethiopia we would have ```L = [1,5,10,50,100,200]```, but other countries have different coin systems. Implement a function ```makeChange(n, L)``` which returns the minimum number of coins needed to make change for ```n``` cents using the coins in ```L```. 
# 
# *For example*, ```makeChange(14, [1,5,10,50,100,200])``` should return ```5```, since you can make change for ```14``` cents by giving one ```10``` cent piece and four ```1``` cent pieces, for a total of ```5``` coins (you could also give two ```5``` cent pieces and four ```1``` cent pieces, or ```14``` ```1``` cent pieces, but those options would each require more coins). If it is impossible to make change for ```n``` cents using ```L```, you should return ```-1```. For example, ```makeChange(3, [2, 5])``` should return ```-1``` since there is no way to make change for ```3``` cents using ```2``` cent and ```5``` cent pieces.
# 
# ### 5.1 
# First implement a function ```makeChange``` that takes as input an integer $n$ and a list $L$ (with coin values sorted in increasing order) and returns the minimum number of ways to make change using plain recursion.

# In[ ]:


def make_change(n, L):
    # Your code here
    pass


check_test(make_change(14, [1,5,10,25,50,100]), 5)
check_test(make_change(12,[1,4,6,8,10,12]), 1)
check_test(make_change(11,[4,6,8]), -1)


# ### 5.2
# Implement a faster version or your solution using memoization in `makeChange_memo(n, L)`.

# In[ ]:


def make_change_memo(n, L):
    # Your code here
    pass

check_test(make_change_memo(14, [1,5,10,25,50,100]), 5)
check_test(make_change_memo(50,[1,4,6,8,10,12]), 5)
check_test(make_change_memo(11,[4,6,8]), -1)


# ### 5.3 (Challenge)
# 
# Can you modify your code so that it returns the list of coins that sum up to the amount you want (or `None` if no solution exists)?
# 
# Hint: In your memoization table, store lists of coins rather than the amount of coins.

# In[ ]: