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

# # Week 4 Day 1, Core: Memoization
# 
# ## Creators: 
# Charis Pipis, Monica Song, Yosef Worku
# ## Reviewers: 
# Abraham Negash, Andrew Zuckerman
# 

# ## 1. 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 . . .
# 
# ### 1.1 
# Write a recursive function `fib(n)` that takes an integer `n` and returns $f_n$.

# In[ ]:


def fib(n):
    pass


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

# In[ ]:


fib(7)


# How many times does it calculate fib of `1` ?

# In[ ]:


# 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(fib(7), 13)
check_test(fib(0), 0)
check_test(fib(1), 1)


# ## 2. Fibonacci Sequence - 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 fib(i) before }\\
#       f_i \text{ if we have already computed it}
#     \end{cases}
# $$
# 
# ### 2.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):
    pass


# 
# ### 2.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):
    pass


# ### 2.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):
    pass


# ### 2.4
# Write a recursive function `memo_fib(n, mem)` that takes an integer `n` and a list `mem` and returns $f_n$. <br/>
# Here is how it should work : <br/>
# <ul>
#     <li> If `mem[n]` is **not** equal to `-1`, it should return `mem[n]`</li>
#     <li> If `mem[n]` is equal to `-1`, it should compute $f_n$ recursively and store it in `mem[n]` before returning it.</li>
# </ul>

# In[ ]:


def memo_fib(n, mem): 
    pass


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

# In[ ]:


def fib(n):
    pass


# ## Check your answer here

# In[ ]:


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