#!/usr/bin/env python3
"""
LeetCode No.70: Climbing Stairs
Distinct ways to climb a n step staircase where
each time you can either climb 1 or 2 steps.

Args:
    n: number of steps of staircase

Returns:
    Distinct ways to climb a n step staircase

Raises:
    AssertionError: n not positive integer
"""


def climb_stairs(n: int) -> int:
    """
    Original cached solution.
    >>> climb_stairs(3)
    3
    >>> climb_stairs(1)
    1
    >>> climb_stairs(-7)  # doctest: +ELLIPSIS
    Traceback (most recent call last):
        ...
    AssertionError: n needs to be positive integer, your input -7
    """
    assert (
        isinstance(n, int) and n > 0
    ), f"n needs to be positive integer, your input {n}"
    if n == 1:
        return 1
    dp = [0] * (n + 1)
    dp[0], dp[1] = (1, 1)
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]


def climb_stairs_constant_memory(n: int) -> int:
    """
    Forget old results when they're obsolete.
    >>> climb_stairs(3)
    3
    >>> climb_stairs(1)
    1
    >>> climb_stairs(-7)  # doctest: +ELLIPSIS
    Traceback (most recent call last):
        ...
    AssertionError: n needs to be positive integer, your input -7
    """
    assert (
        isinstance(n, int) and n > 0
    ), f"n needs to be positive integer, your input {n}"
    if n == 1:
        return 1
    previous, current = 1, 1
    for _ in range(n - 1):
        current, previous = current + previous, current
    return current


def benchmark2(verbose: bool) -> None:
    from timeit import timeit

    original = timeit(f"z.climb_stairs({n})", setup="import __main__ as z")
    constant_memory = timeit(f"z.climb_stairs_constant_memory({n})", setup="import __main__ as z")

    assert constant_memory <= original

    if verbose:
        print(f"> timeit(climb_stairs({n})) = {original} seconds")
        print(f"> timeit(climb_stairs_constant_memory({n})) = {constant_memory} seconds")


def benchmark(verbose: bool) -> None:
    from timeit import timeit

    print(f"{'input':^16} | {'original':^16} | {'new':^16} | {'ratio':^16}")
    for n in range(2, 51, 3):
        original_time = timeit(f"z.climb_stairs({n})", setup="import __main__ as z")
        constant_memory = timeit(f"z.climb_stairs_constant_memory({n})", setup="import __main__ as z")

        print(f"{n:>16} | {original_time:>16.4} | {constant_memory:>16.4} | {constant_memory / original_time:>16.4}")
        assert constant_memory <= original_time


def verify_equivalence() -> None:
    from hypothesis import given
    from hypothesis.strategies import integers

    @given(integers(min_value=1, max_value=500))
    def test_equivalence(n: int) -> None:
        assert climb_stairs(n) == climb_stairs_constant_memory(n)

    test_equivalence()


def _test(verbose: bool) -> None:
    import doctest

    doctest.testmod()
    verify_equivalence()
    benchmark(verbose)


if __name__ == "__main__":
    import argparse
    parser = argparse.ArgumentParser()
    parser.add_argument("-v", "--verbose", help="Add prints", action="store_true", default=False)
    args = parser.parse_args()
    _test(args.verbose)