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


def sq_dists(X: np.ndarray, C: np.ndarray) -> np.ndarray:
    """(n, d) and (k, d) -> (n, k) squared Euclidean distances."""
    d2 = (X * X).sum(1)[:, None] + (C * C).sum(1)[None, :] - 2.0 * X @ C.T
    return np.maximum(d2, 0.0)               # clip tiny negatives from round-off


def kmeans_pp_init(X: np.ndarray, k: int, rng: np.random.Generator) -> np.ndarray:
    n = X.shape[0]
    centers = [X[rng.integers(n)]]
    d2 = sq_dists(X, centers[0][None, :])[:, 0]
    for _ in range(1, k):
        total = d2.sum()
        if total == 0:                       # all points sit on centers already
            idx = rng.integers(n)
        else:
            idx = rng.choice(n, p=d2 / total)  # pick far points more often
        centers.append(X[idx])
        d2 = np.minimum(d2, sq_dists(X, X[idx][None, :])[:, 0])
    return np.array(centers)


def kmeans(X: np.ndarray, k: int, max_iter: int = 300, tol: float = 1e-6,
           seed: int = 0) -> tuple[np.ndarray, np.ndarray, float]:
    """Lloyd's algorithm. Returns (centers (k, d), labels (n,), inertia)."""
    rng = np.random.default_rng(seed)
    C = kmeans_pp_init(X, k, rng)
    for _ in range(max_iter):
        D = sq_dists(X, C)                   # (n, k)
        labels = D.argmin(1)
        new_C = np.empty_like(C)
        for j in range(k):
            members = X[labels == j]
            if len(members) == 0:
                # Empty cluster: move it to the point worst served right now.
                far = D[np.arange(len(X)), labels].argmax()
                new_C[j] = X[far]
                labels[far] = j
                D[far, :] = 0.0              # so a second empty cluster picks another point
            else:
                new_C[j] = members.mean(0)
        shift = np.sqrt(((new_C - C) ** 2).sum(1)).max()
        C = new_C
        if shift < tol:
            break
    D = sq_dists(X, C)
    labels = D.argmin(1)
    inertia = float(D[np.arange(len(X)), labels].sum())
    return C, labels, inertia


if __name__ == "__main__":
    rng = np.random.default_rng(2)
    true = np.array([[0, 0], [5, 5], [0, 5]], dtype=float)
    X = np.vstack([c + 0.3 * rng.normal(size=(100, 2)) for c in true])
    C, labels, inertia = kmeans(X, 3)
    # Each true center should have a found center within 0.15.
    assert np.sqrt(sq_dists(true, C)).min(1).max() < 0.15
    assert np.bincount(labels).tolist() == [100, 100, 100]
    # Duplicate points force an empty cluster. It must still return k centers.
    C2, l2, _ = kmeans(np.array([[0.0, 0.0]] * 5 + [[1.0, 1.0]]), 3)
    assert C2.shape == (3, 2) and np.isfinite(C2).all()
    print("ok inertia", round(inertia, 2))
