#!/usr/bin/env python3
# Source: q4-ml-coding.html
import numpy as np


def init_params(d_in: int, d_hidden: int, d_out: int, seed: int = 0) -> dict[str, np.ndarray]:
    rng = np.random.default_rng(seed)
    return {
        "W1": rng.normal(size=(d_in, d_hidden)) * np.sqrt(2.0 / d_in),  # He init for ReLU
        "b1": np.zeros(d_hidden),
        "W2": rng.normal(size=(d_hidden, d_out)) * np.sqrt(1.0 / d_hidden),
        "b2": np.zeros(d_out),
    }


def forward_backward(p: dict[str, np.ndarray], X: np.ndarray,
                     y: np.ndarray) -> tuple[float, dict[str, np.ndarray]]:
    """X: (n, d_in). y: (n,) class ids. Returns (mean CE loss, grads)."""
    n = X.shape[0]
    # Forward
    h_pre = X @ p["W1"] + p["b1"]                 # (n, H)
    h = np.maximum(h_pre, 0.0)                    # ReLU
    logits = h @ p["W2"] + p["b2"]                # (n, C)
    z = logits - logits.max(1, keepdims=True)
    logp = z - np.log(np.exp(z).sum(1, keepdims=True))
    loss = -logp[np.arange(n), y].mean()
    # Backward
    dlogits = np.exp(logp)
    dlogits[np.arange(n), y] -= 1.0
    dlogits /= n                                  # (n, C)
    grads = {"W2": h.T @ dlogits, "b2": dlogits.sum(0)}
    dh = dlogits @ p["W2"].T                      # (n, H)
    dh_pre = dh * (h_pre > 0)                     # ReLU passes grad only where active
    grads["W1"] = X.T @ dh_pre
    grads["b1"] = dh_pre.sum(0)
    return float(loss), grads


def grad_check(p: dict[str, np.ndarray], X: np.ndarray, y: np.ndarray,
               eps: float = 1e-5) -> float:
    """Max relative error between analytic and centered-difference grads."""
    _, g = forward_backward(p, X, y)
    worst = 0.0
    for name, W in p.items():
        it = np.nditer(W, flags=["multi_index"])
        for _ in it:
            i = it.multi_index
            old = W[i]
            W[i] = old + eps
            lp, _ = forward_backward(p, X, y)
            W[i] = old - eps
            lm, _ = forward_backward(p, X, y)
            W[i] = old                            # always restore
            num = (lp - lm) / (2 * eps)
            rel = abs(num - g[name][i]) / max(1e-8, abs(num) + abs(g[name][i]))
            worst = max(worst, rel)
    return worst


def train(X: np.ndarray, y: np.ndarray, hidden: int = 32, lr: float = 0.5,
          epochs: int = 500) -> dict[str, np.ndarray]:
    p = init_params(X.shape[1], hidden, int(y.max()) + 1)
    for _ in range(epochs):
        _, g = forward_backward(p, X, y)
        for k in p:
            p[k] -= lr * g[k]
    return p


if __name__ == "__main__":
    rng = np.random.default_rng(6)
    X = rng.normal(size=(6, 3))
    y = np.array([0, 1, 2, 1, 0, 2])
    assert grad_check(init_params(3, 5, 3, seed=1), X, y) < 1e-6
    # XOR is not linearly separable. The MLP should solve it.
    Xx = np.array([[0, 0], [0, 1], [1, 0], [1, 1]], dtype=float)
    yx = np.array([0, 1, 1, 0])
    p = train(Xx, yx, hidden=16, lr=0.5, epochs=2000)
    pred = (np.maximum(Xx @ p["W1"] + p["b1"], 0) @ p["W2"] + p["b2"]).argmax(1)
    assert pred.tolist() == yx.tolist(), pred
    print("ok")
