#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
Created on Sat Dec 3 18:16:57 2016
@author: taylor@mst.edu
"""

from functools import lru_cache
from typing import Dict, Optional


# %% Recall, fib is slow with recursion
# memoization specific to the problem is a fix
def fib_memo(n: int, memo: Dict[int, int]) -> int:
    """
    Computes the first n fib numbers.
    """
    if n not in memo:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]


memo: Dict[int, int] = {0: 0, 1: 1}
print(fib_memo(35, memo))


# %% memoizatino v2 (general)
def fib_memo_gen(n: int, fib_cache: Optional[Dict[int, int]] = None) -> int:
    """
    Return Fibonacci of x, where x is a non-negative int
    Hides the memoiziation from the user!
    """
    if fib_cache is None:
        fib_cache = {}
    if n in fib_cache:
        return fib_cache[n]
    if n < 2:
        return n  # or 1
    else:
        value = fib_memo_gen(n - 1, fib_cache) + fib_memo_gen(n - 2, fib_cache)
        fib_cache[n] = value
    return value


print(fib_memo_gen(35))


# %% memoization v3 (Python general)
@lru_cache(maxsize=1000)
def fib_memo_lru(n: int) -> int:
    """
    Return Fibonacci of x, where x is a non-negative int
    Uses a decorator memoization method
    """
    if n < 2:
        return n  # or 1
    else:
        return fib_memo_lru(n - 1) + fib_memo_lru(n - 2)


print(fib_memo_lru(35))