<jupyter_start><jupyter_text>The Fibonacci Sequence **Reference Note:** This reference notebook includes 3 reference implementations: one checking for a hash map implementation, one checking for a dynamic programming implementation, and one checking that a student is _not_ using the naive recursive implementation.<jupyter_code>import pybryt
import pybryt.complexities as cplx

map_annots = []
dyn_annots = []<jupyter_output><empty_output><jupyter_text>Hash Map Implementation<jupyter_code>fibs = {}

def fibonacci(n, track=True):
    """
    Return the n^th number in the Fibonacci sequence, n >= 0.

    Uses the hash map implementation of the Fibonacci sequence algorithm.
    
    Parameters
    ----------
    n     : int
        the index of the desired Fibonacci number
    track : bool
        whether to add a value annotation to the reference implementation

    Returns
    -------
    integer
        the n^th Fibonacci number
    """
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n in fibs:
        return fibs[n]
    f = fibonacci(n-1) + fibonacci(n-2)
    fibs[n] = f
    if track:
        map_annots.append(pybryt.Value(fibs, success_message="Found hash map implementation", name="hash_map"))
    return f
for n in range(10):
    print(fibonacci(n), end=" ")
%%time
checker = pybryt.TimeComplexityChecker("fib_runtime")
for n in range(30):
    with checker(n):
        fibonacci(n, track=False)
checker.determine_complexity()
map_annots.append(pybryt.TimeComplexity(cplx.linear, name="fib_runtime", success_message="Runs in linear time", failure_message="ERROR: Does not run in linear time"))<jupyter_output><empty_output><jupyter_text>Dynamic Programming Implementation<jupyter_code>import numpy as np

def fibonacci(n, track=True):
    """
    Return the n^th number in the Fibonacci sequence, n >= 0.

    Uses the dynamic programming implementation of the Fibonacci sequence algorithm.
    
    Parameters
    ----------
    n : integer
        the index of the desired Fibonacci number
    track : bool
        whether to add a value annotation to the reference implementation

    Returns
    -------
    integer
        the n^th Fibonacci number
    """
    fibs = np.zeros(n + 1, dtype=int)
    if n > 0:
        fibs[1] = 1
    for i in range(2, n + 1):
        fibs[i] = fibs[i-1] + fibs[i-2]
    if track:
        dyn_annots.append(pybryt.Value(fibs, success_message="Found dynamic programming implementation", name="dyn_array"))
    return fibs[n]
for n in range(10):
    print(fibonacci(n), end=" ")
%%time
checker = pybryt.TimeComplexityChecker("fib_runtime")
for n in range(30):
    with checker(n):
        fibonacci(n, track=False)
checker.determine_complexity()
dyn_annots.append(pybryt.TimeComplexity(cplx.linear, name="fib_runtime", success_message="Runs in linear time", failure_message="ERROR: Does not run in linear time"))
len(dyn_annots)<jupyter_output><empty_output><jupyter_text>Reference Creation<jupyter_code>not_recursive = map_annots[-2] | dyn_annots[-2] # found indicators of one of the algorithms
not_recursive.failure_message = "Did not find indicators of hash map or dynamic programming implementations. Make sure you're not using the naive algorithm!"
map_ref = pybryt.ReferenceImplementation("fibonacci_map", map_annots)
dyn_ref = pybryt.ReferenceImplementation("fibonacci_dyn", dyn_annots)
no_recurse_ref = pybryt.ReferenceImplementation("fibonacci_no_recurse", [not_recursive])<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10063073394495413, 'fraction_numerical': 0.007740825688073395, 'mean_word_length': 3.8593314763231197, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 20, 'https://': 0, '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': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '69186', 'license': 'MIT', 'n_tokens_mistral': 1146, 'n_tokens_neox': 1088, 'n_words': 317, 'path': 'demo/fibonacci/fibonacci.ipynb', 'repo_name': 'ranigb/pybryt', 'size': '3488'}