<jupyter_start><jupyter_text>What is Caching? Caching can be defined as the process of storing data into a temporary data storage to avoid recomputation or to avoid reading the data from a relatively slower part of memory again and again. Thus cachig serves as a fast "look-up" storage allowing programs to execute faster.  *Let's use caching to chalk out an efficient solution for **a problem from the Recursion lesson**.*  Problem Statement - (Recursion) - Repeat Exercise A child is running up a staircase and can hop either 1 step, 2 steps or 3 steps at a time. Given that the staircase has a total `n` steps, write a function to count the number of possible ways in which child can run up the stairs. For e.g. * `n == 1` then `answer = 1`* `n == 3` then `answer = 4`   The output is `4` because there are four ways we can climb the staircase:    - 1 step +  1 step + 1 step    - 1 step + 2 steps     - 2 steps + 1 step    - 3 steps * `n == 5` then `answer = 13`**Hint**You would need to make use of the [Inductive Hypothesis](https://en.wikipedia.org/wiki/Mathematical_inductionDescription), which comprises of the following two steps:1. **The Inductive Hypothesis**: Calculate/assume the results for base case. In our problem scenario, the base cases would be when n = 1, 2, and 3. 2. **The Inductive Step**: Prove that for every $n >= 3$, if the results are true for $n$ , then it holds for $(n+1)$ as well. In other words, assume that the statement holds for some arbitrary natural number $n$ , and prove that the statement holds for $(n+1)$.<jupyter_code>def staircase(n):
    # Base Case - What holds true for minimum steps possible i.e., n == 1? Return the number of ways the child can climb one step.
    if n == 1:
        return 1
    # Inductive Hypothesis - What holds true for n == 2 or n == 3? Return the number of ways to climb them.
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    # Inductive Step (n > 3) - use Inductive Hypothesis to formulate a solutio
    return staircase(n-1)+staircase(n-2)+staircase(n-3)


def test_function(test_case):
    answer = staircase(test_case[0])
    if answer == test_case[1]:
        print("Pass")
    else:
        print("Fail")
            
test_case = [4, 7]
test_function(test_case)
test_case = [5, 13]
test_function(test_case)
test_case = [3, 4]
test_function(test_case)
test_case = [20, 121415]
test_function(test_case)<jupyter_output>Pass<jupyter_text>Show Solution  Problem Statement - (Caching)While using recursion for the above problem, you might have noticed a small problem with efficiency.Let's take a look at an example.* Say the total number of steps are `5`. This means that we will have to call at `(n=4), (n=3), and (n=2)`* To calculate the answer for `n=4`, we would have to call `(n=3), (n=2) and (n=1)`You can notice that even for a small number of staircases (here 5), we are calling `n=3` and `n=2` multiple times. Each time we call a method, additional time is required to calculate the solution. In contrast, instead of calling on a particular value of `n` again and again, we can **calculate it once and store the result** to speed up our program.>Which data structure are you thinking to store the results?Your job is to use any data-structure that you have used until now to write a faster implementation of the function you wrote earlier while using recursion.<jupyter_code>def staircase1(n):
    stair = dict()
    return climb_stair(n,stair)

def climb_stair(n,stair):

    if n == 1:
        method = 1
    elif n == 2:
        method = 2
    elif n == 3:
        method = 4
    elif n in stair:
        method = stair[n]
    else:
        if n-1 in stair:
            first = stair[n-1]
        else:
            first = climb_stair(n-1,stair)
        if n-2 in stair:
            second = stair[n-2]
        else:
            second = climb_stair(n-2,stair)
        if n-3 in stair:
            third = stair[n-3]
        else:
            third = climb_stair(n-3,stair)
        method = first+second+third
        stair[n] = method
    return method

staircase1(20)
test_case = [4, 7]
test_function(test_case)
test_case = [5, 13]
test_function(test_case)
test_case = [3, 4]
test_function(test_case)
test_case = [20, 121415]
test_function(test_case)
staircase1(6)<jupyter_output><empty_output><jupyter_text>Hide Solution<jupyter_code>def staircase2(n):
    
    # start with a blank dictionary. It will populate in the recursive call
    num_dict = dict({})           
    return staircase_faster(n, num_dict)


'''Recursice function'''
def staircase_faster(n, num_dict):
    ''' 
    Here `n` is a key and `output` would be the corresponding value 
    to be inserted into the dictionary as a pair
    '''
    
    # Base cases
    if n == 1:
        output = 1
    elif n == 2:
        output = 2
    elif n == 3:
        output = 4
    else:
        
        # Simply check if the "value" corresponding to "(n-1)" key is already available in the dictionary
        if (n - 1) in num_dict:
            first_output = num_dict[n - 1]

        # Otherwise, calculate and insert the new key-value pair into the dictioanry
        else:
            first_output =  staircase_faster(n - 1, num_dict)
        
        if (n - 2) in num_dict:
            second_output = num_dict[n - 2]
        else:
            second_output = staircase_faster(n - 2, num_dict)
            
        if (n - 3) in num_dict:
            third_output = num_dict[n - 3]
        else:
            third_output = staircase_faster(n - 3, num_dict)
        
        output = first_output + second_output + third_output
    
    num_dict[n] = output;   # insert a key-value pair in the ORIGINAL dictionary 
    return output

staircase2(20)

import time

start_time = time.time()
staircase2(20)
print("--- %s seconds ---" % (time.time() - start_time))
start_time = time.time()
staircase1(20)
print("--- %s seconds ---" % (time.time() - start_time))
start_time = time.time()
staircase(20)
print("--- %s seconds ---" % (time.time() - start_time))
import timeit
#original method
print(timeit.timeit('''def staircase1(n):
    stair = dict()
    return climb_stair(n,stair)

def climb_stair(n,stair):

    if n == 1:
        method = 1
    elif n == 2:
        method = 2
    elif n == 3:
        method = 4
    elif n in stair:
        method = stair[n]
    else:
        if n-1 in stair:
            method = stair[n-1]+stair[n-2]+stair[n-3]
        elif n-2 in stair:
            method = climb_stair(n-1,stair)+stair[n-2]+stair[n-3]
        elif n-3 in stair:
            method = climb_stair(n-1,stair)+climb_stair(n-2,stair)+stair[n-3]
        else:
            method = climb_stair(n-1,stair)+climb_stair(n-2,stair)+climb_stair(n-3,stair)
        stair[n] = method
    return method

staircase1(20)''',number = 100000))
print(timeit.timeit('''def staircase1(n):
    stair = dict()
    return climb_stair(n,stair)

def climb_stair(n,stair):

    if n == 1:
        method = 1
    elif n == 2:
        method = 2
    elif n == 3:
        method = 4
    elif n in stair:
        method = stair[n]
    else:
        if n-1 in stair:
            first = stair[n-1]
        else:
            first = climb_stair(n-1,stair)
        if n-2 in stair:
            second = stair[n-2]
        else:
            second = climb_stair(n-2,stair)
        if n-3 in stair:
            third = stair[n-3]
        else:
            third = climb_stair(n-3,stair)
        method = first+second+third
        stair[n] = method
    return method

staircase1(20)
''',number = 100000))<jupyter_output>1.0587403920000042
{'fraction_non_alphanumeric': 0.10297995780590717, 'fraction_numerical': 0.027030590717299578, 'mean_word_length': 2.574458058435438, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 14, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '487882', 'license': 'MIT', 'n_tokens_mistral': 2573, 'n_tokens_neox': 2413, 'n_words': 885, 'path': 'data_structure/Caching.ipynb', 'repo_name': 'chensuhui03/udacity_python_practice', 'size': '7584'}