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


def fit_linear_gd(X: np.ndarray, y: np.ndarray, lr: float = 0.1,
                  epochs: int = 1000, tol: float = 1e-8) -> tuple[np.ndarray, float]:
    """Fit y ~ X @ w + b by batch gradient descent on mean squared error.

    X: (n, d) features. y: (n,) targets. Returns (w of shape (d,), b).
    """
    n, d = X.shape
    w = np.zeros(d)
    b = 0.0
    prev_loss = np.inf
    for _ in range(epochs):
        err = X @ w + b - y                  # (n,) residuals
        loss = (err @ err) / (2 * n)         # half MSE, so gradients are clean
        grad_w = X.T @ err / n               # (d,)
        grad_b = err.mean()
        w -= lr * grad_w
        b -= lr * grad_b
        if abs(prev_loss - loss) < tol:      # stop when loss stops moving
            break
        prev_loss = loss
    return w, b


def fit_linear_closed(X: np.ndarray, y: np.ndarray, l2: float = 0.0) -> tuple[np.ndarray, float]:
    """Normal equations with an intercept column. Uses solve, never inv."""
    n, d = X.shape
    Xb = np.hstack([X, np.ones((n, 1))])     # (n, d+1)
    reg = l2 * np.eye(d + 1)
    reg[-1, -1] = 0.0                        # do not shrink the intercept
    theta = np.linalg.solve(Xb.T @ Xb + reg, Xb.T @ y)
    return theta[:-1], float(theta[-1])


if __name__ == "__main__":
    rng = np.random.default_rng(0)
    X = rng.normal(size=(500, 3))
    y = X @ np.array([2.0, -1.0, 0.5]) + 3.0 + 0.01 * rng.normal(size=500)
    mu, sd = X.mean(0), X.std(0)             # scale features before GD
    w, b = fit_linear_gd((X - mu) / sd, y)
    w_raw, b_raw = w / sd, b - (mu / sd) @ w  # map back to raw units
    w2, b2 = fit_linear_closed(X, y)
    assert np.allclose(w_raw, w2, atol=1e-3) and abs(b_raw - b2) < 1e-3
    print("ok", np.round(w2, 3), round(b2, 3))
