"""
p05 — Climbing Stairs
=====================
LeetCode 70 · Easy · Topics: Math, DP, Memoization
"""

import random
import sys
from functools import lru_cache


# ----------------------------------------------------------------------
# 1. BRUTE FORCE — plain recursion. O(2^N). Oracle for small N only.
# ----------------------------------------------------------------------
def climb_brute(n: int) -> int:
    if n <= 2:
        return n
    return climb_brute(n - 1) + climb_brute(n - 2)


# ----------------------------------------------------------------------
# 2. TOP-DOWN MEMOIZATION — O(N) time, O(N) space (call stack + cache).
# ----------------------------------------------------------------------
def climb_memo(n: int) -> int:
    @lru_cache(maxsize=None)
    def f(k: int) -> int:
        if k <= 2:
            return k
        return f(k - 1) + f(k - 2)
    return f(n)


# ----------------------------------------------------------------------
# 3. OPTIMAL — iterative two-scalar DP. O(N) time, O(1) space.
# ----------------------------------------------------------------------
def climb(n: int) -> int:
    # DP RECIPE applied:
    #   State:      f(k) = number of distinct ways to reach step k
    #   Recurrence: f(k) = f(k-1) + f(k-2)  (last move was 1 or 2)
    #   Base:       f(1) = 1, f(2) = 2
    #   Order:      bottom-up, k = 3..n
    #   Compression: only last 2 values needed → 2 scalars, O(1) space.
    if n <= 2:
        return n
    prev2, prev1 = 1, 2  # f(1), f(2)
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1


# ----------------------------------------------------------------------
# 4. STRESS TEST
# ----------------------------------------------------------------------
def stress_test(iterations: int = 200) -> None:
    rng = random.Random(42)
    # Cap n at 25 so the brute recursion stays cheap as the oracle.
    for _ in range(iterations):
        n = rng.randint(1, 25)
        a = climb_brute(n)
        b = climb(n)
        c = climb_memo(n)
        assert a == b == c, f"disagree at n={n}: brute={a}, opt={b}, memo={c}"
    print(f"stress_test PASSED — {iterations} iterations (3 algorithms agree)")


# ----------------------------------------------------------------------
# 5. EDGE CASES
# ----------------------------------------------------------------------
def edge_cases() -> None:
    cases = [
        (1, 1, "n=1 base case"),
        (2, 2, "n=2 base case"),
        (3, 3, "n=3 first recurrence application"),
        (4, 5, "n=4 Fibonacci pattern emerges"),
        (5, 8, "n=5"),
        (45, 1_836_311_903, "max LC constraint — confirms no overflow in Python"),
    ]
    for n, expected, label in cases:
        actual = climb(n)
        status = "PASS" if actual == expected else "FAIL"
        print(f"  [{status}] {label}: n={n} → {actual} (expected {expected})")


if __name__ == "__main__":
    # Raise the recursion limit only as a safety net for climb_memo on n=25.
    sys.setrecursionlimit(10_000)
    print("=== Edge cases ===")
    edge_cases()
    print("\n=== Stress test ===")
    stress_test()