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


def pairwise_sq_dists(A: np.ndarray, B: np.ndarray) -> np.ndarray:
    """||a - b||^2 = ||a||^2 + ||b||^2 - 2 a.b for all pairs. (m, d), (n, d) -> (m, n)."""
    a2 = np.einsum("ij,ij->i", A, A)[:, None]   # (m, 1)
    b2 = np.einsum("ij,ij->i", B, B)[None, :]   # (1, n)
    return np.maximum(a2 + b2 - 2.0 * A @ B.T, 0.0)


def knn_predict(X_train: np.ndarray, y_train: np.ndarray, X_test: np.ndarray,
                k: int = 5) -> np.ndarray:
    """Classify each test row by majority vote of its k nearest train rows.

    Ties in the vote go to the class with the smallest total distance.
    y_train holds integer labels 0..C-1.
    """
    D = pairwise_sq_dists(X_test, X_train)                  # (m, n)
    k = min(k, X_train.shape[0])
    idx = np.argpartition(D, k - 1, axis=1)[:, :k]          # k nearest, unordered
    nd = np.sqrt(np.take_along_axis(D, idx, axis=1))        # (m, k) distances
    nl = y_train[idx]                                       # (m, k) labels
    n_classes = int(y_train.max()) + 1
    onehot = np.eye(n_classes)[nl]                          # (m, k, C)
    votes = onehot.sum(1)                                   # (m, C)
    dist_sum = (onehot * nd[:, :, None]).sum(1)             # (m, C)
    # Rank by votes first, then by smaller distance. Scale keeps votes dominant.
    score = votes - dist_sum / (dist_sum.max() + 1.0) / (k + 1)
    score[votes == 0] = -np.inf
    return score.argmax(1)


if __name__ == "__main__":
    A = np.array([[0.0, 0.0], [1.0, 0.0]])
    B = np.array([[0.0, 1.0], [3.0, 4.0], [1.0, 0.0]])
    brute = ((A[:, None, :] - B[None, :, :]) ** 2).sum(-1)
    assert np.allclose(pairwise_sq_dists(A, B), brute)
    Xtr = np.array([[0.0], [1.0], [10.0], [11.0]])
    ytr = np.array([0, 0, 1, 1])
    assert knn_predict(Xtr, ytr, np.array([[0.4], [10.6]]), k=3).tolist() == [0, 1]
    # Tie: k=2, one vote each. Class 1 point is closer, so class 1 wins.
    assert knn_predict(np.array([[0.0], [3.0]]), np.array([1, 0]), np.array([[1.0]]), k=2).tolist() == [1]
    print("ok")
