"""
p57 — Coin Change (LeetCode 322, MEDIUM).

dp[a] = 1 + min(dp[a - c] for c in coins if c <= a), with dp[0] = 0.
Return dp[amount] or -1.
"""
from __future__ import annotations
import random
from collections import deque
from typing import List


def coin_change_dp(coins: List[int], amount: int) -> int:
    INF = amount + 1   # sentinel; any real answer <= amount when coin 1 exists
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] <= amount else -1


def coin_change_bfs(coins: List[int], amount: int) -> int:
    if amount == 0:
        return 0
    visited = {0}
    q = deque([(0, 0)])
    while q:
        a, steps = q.popleft()
        for c in coins:
            nxt = a + c
            if nxt == amount:
                return steps + 1
            if nxt < amount and nxt not in visited:
                visited.add(nxt)
                q.append((nxt, steps + 1))
    return -1


def coin_change_brute(coins: List[int], amount: int) -> int:
    # Exponential. Stress only with small amount.
    if amount < 0:
        return -1
    if amount == 0:
        return 0
    best = -1
    for c in coins:
        sub = coin_change_brute(coins, amount - c)
        if sub != -1:
            cand = sub + 1
            if best == -1 or cand < best:
                best = cand
    return best


def edge_cases() -> None:
    assert coin_change_dp([1, 2, 5], 11) == 3
    assert coin_change_dp([2], 3) == -1
    assert coin_change_dp([1], 0) == 0
    assert coin_change_dp([1], 1) == 1
    assert coin_change_dp([1], 2) == 2
    # Greedy-trap
    assert coin_change_dp([1, 3, 4], 6) == 2
    assert coin_change_bfs([1, 3, 4], 6) == 2
    # Impossible with large coin only
    assert coin_change_dp([5, 10], 3) == -1
    # amount=0
    assert coin_change_bfs([1, 2, 5], 0) == 0
    print("edge_cases: PASS")


def stress_test() -> None:
    rng = random.Random(42)
    for trial in range(200):
        k = rng.randint(1, 4)
        coins = sorted({rng.randint(1, 7) for _ in range(k)})
        amount = rng.randint(0, 12)
        a = coin_change_dp(coins, amount)
        b = coin_change_bfs(coins, amount)
        c = coin_change_brute(coins, amount)
        assert a == b == c, f"trial {trial}: coins={coins} amount={amount} dp={a} bfs={b} brute={c}"
    print("stress_test: 200 trials — dp, bfs, brute agree.")


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")