'''
Recursion - Fibonacci Sequence

'''
import functools
import math
from numpy import matrix


def fibonacci_oneliner(n):
    '''
    Generate Fibonacci Sequence from F_0 to F_n

    returns list[F_0, F_1, ..., F_n]
    Adapted from Mayer2020 using one python line of code.
    '''
    fibs = functools.reduce(lambda x, _: x + [x[-2] + x[-1]],
                            [0] * (n - 1), [0, 1])
    return fibs


@functools.lru_cache(None)  # Comment this line to have a non-memoized version
def fibonacci_recursive(n):
    '''Recursive F_n
    '''
    if n < 0:
        raise ValueError('n must be non negative integer.')
    elif n > 1:
        return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
    else:
        return n


# Static constants for Binet's and rounding implementations
__denom = 5 ** 0.5
__golden = (1 + __denom) / 2  # Golden Ratio
__psi = (1 - __denom) / 2


def fibonacci_binet(n):
    r'''
    Closed-form expression: Binet's Formula
    F_n = \frac{}{\sqrt{5}}

    Golden ratio $\phi = \frac{1 + \sqrt{5}}{2}$
    \phi^2 = \phi + 1
    \psi = (1 - \sqrt{5}) / 2
    \psi^2 =  \psi + 1

    Rounding errors above 71 (i.e. n < 72)
    '''
    if n < 0:
        raise ValueError('n must be non negative integer.')
    elif n > 71:
        raise ValueError('This function has rounding errors above n=71.')
    else:
        return int((__golden ** n - __psi ** n) / __denom)


def fibonacci_rounding(n):
    """
    Fast Fibonacci using rounding

    It is limited to n < 71"""
    if n < 0:
        raise ValueError('Fibs for negative values are not defined.')
    elif n > 70:
        raise ValueError('This function has rounding errors above n=70.')
    return round(math.pow(__golden, n) / __denom)


def fibonacci_matrix(n):
    '''
    Fibonacci number F_n using matrix powers

    From bebidek2018 <https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it>
    '''
    return (matrix('0 1; 1 1', dtype='object') ** n).item(1)


class Solution:
    def fib(self, N: int) -> int:
        if N <= 1:
            return N
        F = [0] * (N + 1)
        F[1] = 1
        for n in range(2, N + 1):
            F[n] = F[n-1] + F[n-2]
        return F[N]

    def fib2(self, N: int) -> int:
        if N <= 1:
            return N
        F = [0, 1, 1]
        for n in range(3, N + 1):
            F[0], F[1], F[2] = F[1], F[2], F[-1] + F[-2]
        return F[-1]


if __name__ == '__main__':
    n = 45  # n > 1 # 70 is the limit for fast_fib
    fibs = fibonacci_oneliner(n)

    # Some known values to verify
    if n >= 70:
        assert fibs[70] == 190392490709135
        assert fibs[71] == 308061521170129

    # lr = lb = []
    if n < 72:
        lb = ([fibonacci_binet(ni) for ni in range(n + 1)])
        print(f'lb\n{lb}')
        assert fibs == lb
    if n < 71:
        lf = ([fibonacci_rounding(ni) for ni in range(n + 1)])
        print(lf)
        assert fibs == lf, "Disc"

    if n < 5000:
        lr = ([fibonacci_recursive(ni) for ni in range(n + 1)])
        assert fibs == lr
        # print(f'lr\n{lr}')
    lm = [fibonacci_matrix(ni) for ni in range(n + 1)]
    assert lm == fibs

    # From Wolfram|Alpha: Fibo[100] = 354224848179261915075
    fibo100 = 354224848179261915075
    print(f'{fibo100=}')
    assert fibonacci_recursive(100) == fibo100
