"""The clustering error of the days of one year at Krems an der Donau:
the average loss of a clustering, under three choices of the loss.

Purpose
-------
Numerical companion to the glossary entry 'clusteringerror'.  The 366
days of 2024 at Krems are data points with the feature vector (morning
minimum temperature, maximum daytime temperature).  A hard clustering
represents each cluster by a centroid and assigns a day to the nearest
centroid; its clustering error is the average, over the days, of a loss
that measures how far a day is from the centroid it is assigned to.

The demo checks the entry's claims: the clustering error is the average
of a per-data-point loss, so it is a training error; Lloyd's algorithm
never increases it and stops at a fixed point where every centroid is
the mean of its days; replacing the squared Euclidean distance by the
Euclidean distance or by the Manhattan distance changes the centroid
update (geometric median, coordinate-wise median) but not the
assignment step; adding a centroid never increases the clustering
error, so it falls with the number of clusters and reaches zero when
every day is its own cluster, which is why it cannot choose the number
of clusters.

Deterministic: Lloyd's algorithm starts from k-means++ seeds drawn with
a fixed seed and from the previous solution warm-started with one more
centroid.  Self-contained: numpy + matplotlib only; the GeoSphere
download falls back to the committed CSV.

Blocks
------
[B-data]      Download the daily minimum and maximum temperature of 2024
              at Krems (GeoSphere station 3805) or read the committed
              copy; 366 days, no missing value.
[B-loss]      The clustering error for k = 2 centroids equals the
              average of the per-day loss, the squared Euclidean
              distance to the nearest centroid.
[B-lloyd]     Lloyd's algorithm with k = 2: the clustering error never
              increases, the assignments stop changing, and at the
              fixed point each centroid is the mean of its days; the two
              clusters are the cold and the warm days.
[B-norms]     The same two clusters under the Euclidean distance
              (centroid = geometric median, Weiszfeld's iteration) and
              under the Manhattan distance (centroid = coordinate-wise
              median): the assignment rule is unchanged, the centroids
              and the error values are not.
[B-k]         Clustering error for k = 1, ..., 8 under the squared
              Euclidean loss: non-increasing in k (a warm start with one
              more centroid cannot be worse), and zero at k = 366.
[B-plot]      Every 18th day for the figure (21 of 366 days) with
              its cluster for k = 2, the two centroids, and the error
              curve.

Outputs
-------
clusteringerror_weather.csv     : date, tmin, tmax (committed copy).
clusteringerror_points_plot.csv : the 21 drawn days with their cluster.
clusteringerror_centroids.csv   : the two centroids under each loss.
clusteringerror_curve.csv       : k, clustering error, k = 1, ..., 8.
clusteringerror.png             : matplotlib preview (checking only).
"""

# /// script
# requires-python = ">=3.10"
# dependencies = ["matplotlib==3.10.7", "numpy==2.3.4"]
# ///

import json
import urllib.request
from pathlib import Path

import numpy as np
import matplotlib

matplotlib.use("Agg")
import matplotlib.pyplot as plt

OUT_DIR = Path(__file__).parent

report = []


def check(name, ok):
    report.append((name, bool(ok)))
    print(f"  [{'ok' if ok else 'FAIL'}] {name}")


# ---- [B-data] daily minimum and maximum temperature at Krems, 2024
print("[B-data] daily minimum and maximum temperature at Krems, 2024")
URL = ("https://dataset.api.hub.geosphere.at/v1/station/historical/"
       "klima-v2-1d?parameters=tlmin,tlmax&station_ids=3805"
       "&start=2024-01-01&end=2024-12-31")
CSV = OUT_DIR / "clusteringerror_weather.csv"
try:
    with urllib.request.urlopen(URL, timeout=120) as resp:
        payload = json.load(resp)
    params = payload["features"][0]["properties"]["parameters"]
    records = [(stamp[:10], lo, hi)
               for stamp, lo, hi in zip(payload["timestamps"],
                                        params["tlmin"]["data"],
                                        params["tlmax"]["data"])]
    with open(CSV, "w") as fh:
        fh.write("date,tmin,tmax\n")
        for day, lo, hi in records:
            fh.write(f"{day},{lo},{hi}\n")
    print(f"    downloaded {len(records)} days")
except OSError as err:
    print(f"    download failed ({err}); reading the committed CSV")
    rows = CSV.read_text().strip().splitlines()[1:]
    records = [(d, float(a), float(b))
               for d, a, b in (r.split(",") for r in rows)]

check("[B-data] 366 days for 2024", len(records) == 366)
check("[B-data] no day is missing a temperature",
      all(lo is not None and hi is not None for _, lo, hi in records))
X = np.array([[lo, hi] for _, lo, hi in records], dtype=float)
m = len(X)


# ---- the three losses and their centroid updates
def sq_euclid(x, w):
    return np.sum((x - w) ** 2, axis=-1)


def euclid(x, w):
    return np.sqrt(np.sum((x - w) ** 2, axis=-1))


def manhattan(x, w):
    return np.sum(np.abs(x - w), axis=-1)


def geometric_median(pts, iters=200):
    """Weiszfeld's fixed-point iteration for the geometric median."""
    w = pts.mean(axis=0)
    for _ in range(iters):
        d = np.sqrt(np.sum((pts - w) ** 2, axis=1))
        if np.any(d < 1e-12):
            return pts[np.argmin(d)]
        wts = 1.0 / d
        w = (wts[:, None] * pts).sum(axis=0) / wts.sum()
    return w


LOSSES = {
    "squared Euclidean": (sq_euclid, lambda pts: pts.mean(axis=0)),
    "Euclidean": (euclid, geometric_median),
    "Manhattan": (manhattan, lambda pts: np.median(pts, axis=0)),
}


def assign(X, W, dist):
    """Index of the nearest centroid for every data point."""
    return np.argmin(np.stack([dist(X, w) for w in W], axis=1), axis=1)


def clustering_error(X, W, dist):
    """Average loss: the loss of a data point is its distance to the
    nearest centroid."""
    return float(np.mean(np.min(np.stack([dist(X, w) for w in W], axis=1),
                                axis=1)))


def lloyd(X, W0, dist, update, max_iter=500):
    """Lloyd's algorithm from the centroids W0; returns the centroids,
    the assignments, and the clustering error after every iteration."""
    W = np.array(W0, dtype=float)
    errors = [clustering_error(X, W, dist)]
    c = assign(X, W, dist)
    for _ in range(max_iter):
        W_new = np.array([update(X[c == j]) if np.any(c == j) else W[j]
                          for j in range(len(W))])
        c_new = assign(X, W_new, dist)
        W = W_new
        errors.append(clustering_error(X, W, dist))
        if np.array_equal(c_new, c):
            c = c_new
            break
        c = c_new
    return W, c, errors


def kmeanspp_seeds(X, k, rng):
    W = [X[rng.integers(m)]]
    for _ in range(1, k):
        d2 = np.min(np.stack([sq_euclid(X, w) for w in W], axis=1), axis=1)
        W.append(X[rng.choice(m, p=d2 / d2.sum())])
    return np.array(W)


def best_clustering(X, k, dist, update, rng, warm=None, restarts=20):
    """Smallest clustering error over k-means++ restarts and, if given,
    a warm start (the previous centroids plus one more)."""
    best = None
    starts = [kmeanspp_seeds(X, k, rng) for _ in range(restarts)]
    if warm is not None:
        starts.append(warm)
    for W0 in starts:
        W, c, errs = lloyd(X, W0, dist, update)
        if best is None or errs[-1] < best[2][-1]:
            best = (W, c, errs)
    return best


# ---- [B-loss] the clustering error is an average loss
print("[B-loss] the clustering error of two centroids is an average loss")
rng = np.random.default_rng(2024)
W_two, c_two, errs_two = best_clustering(X, 2, sq_euclid,
                                         LOSSES["squared Euclidean"][1], rng)
per_day = np.array([sq_euclid(x, W_two[c]) for x, c in zip(X, c_two)])
err_two = clustering_error(X, W_two, sq_euclid)
check(f"[B-loss] average of the per-day losses {per_day.mean():.2f} equals "
      f"the clustering error {err_two:.2f}",
      abs(per_day.mean() - err_two) < 1e-9)
check("[B-loss] the per-day loss is the squared distance to the NEAREST "
      "centroid", np.all(per_day <= sq_euclid(X, W_two[1 - c_two]) + 1e-12))

# ---- [B-lloyd] Lloyd's algorithm for k = 2 from a crude start
print("[B-lloyd] Lloyd's algorithm with k = 2")
order = np.argsort(X[:, 0])
W0 = np.array([X[order[: m // 2]].mean(axis=0), X[order[m // 2:]].mean(axis=0)])
W_l, c_l, errs_l = lloyd(X, W0, sq_euclid, LOSSES["squared Euclidean"][1])
check(f"[B-lloyd] the clustering error never increases over "
      f"{len(errs_l) - 1} iterations ({errs_l[0]:.2f} -> {errs_l[-1]:.2f})",
      all(b <= a + 1e-9 for a, b in zip(errs_l, errs_l[1:])))
check("[B-lloyd] at the fixed point each centroid is the mean of its days",
      all(np.allclose(W_l[j], X[c_l == j].mean(axis=0)) for j in range(2)))
check("[B-lloyd] the fixed point is the best of the k-means++ restarts",
      abs(errs_l[-1] - err_two) < 1e-6)
cold, warm = sorted(range(2), key=lambda j: W_two[j, 1])
n_cold, n_warm = int(np.sum(c_two == cold)), int(np.sum(c_two == warm))
check(f"[B-lloyd] cold days: centroid ({W_two[cold, 0]:.1f}, "
      f"{W_two[cold, 1]:.1f}) with {n_cold} days; warm days: centroid "
      f"({W_two[warm, 0]:.1f}, {W_two[warm, 1]:.1f}) with {n_warm} days",
      W_two[cold, 1] < 12 < W_two[warm, 1] and n_cold + n_warm == m)
months = np.array([int(d[5:7]) for d, _, _ in records])
check("[B-lloyd] every July and August day is a warm day, every January "
      "and February day a cold day",
      np.all(c_two[np.isin(months, [7, 8])] == warm)
      and np.all(c_two[np.isin(months, [1, 2])] == cold))

# ---- [B-norms] the same clustering task under the other two losses
print("[B-norms] k = 2 under the Euclidean and the Manhattan distance")
results = {"squared Euclidean": (W_two, c_two, err_two)}
for name in ("Euclidean", "Manhattan"):
    dist, update = LOSSES[name]
    rng = np.random.default_rng(2024)
    W, c, errs = best_clustering(X, 2, dist, update, rng, warm=W_two)
    results[name] = (W, c, errs[-1])
    kind = ("geometric median" if name == "Euclidean"
            else "coordinate-wise median")
    check(f"[B-norms] {name}: at the fixed point each centroid is the "
          f"{kind} of its days",
          all(np.allclose(W[j], update(X[c == j]), atol=1e-3)
              for j in range(2)))
    agree = np.mean(c == c_two) if np.mean(c == c_two) > 0.5 \
        else np.mean(c != c_two)
    check(f"[B-norms] {name}: clustering error {errs[-1]:.2f}, centroids "
          f"({W[0, 0]:.1f}, {W[0, 1]:.1f}) and ({W[1, 0]:.1f}, "
          f"{W[1, 1]:.1f}); {100 * agree:.1f}% of the days keep their "
          f"cluster", agree > 0.9)
W_e = results["Euclidean"][0]
check("[B-norms] the assignment rule is the same: nearest centroid under "
      "the Euclidean distance and under its square agree for every day",
      np.array_equal(assign(X, W_e, euclid), assign(X, W_e, sq_euclid)))
check("[B-norms] the Euclidean error is below the square root of the "
      "squared Euclidean error (Jensen)",
      results["Euclidean"][2] < np.sqrt(err_two))

# ---- [B-k] clustering error against the number of clusters
print("[B-k] clustering error for k = 1, ..., 8 (squared Euclidean)")
curve = {}
prev = None
for k in range(1, 9):
    rng = np.random.default_rng(100 + k)
    warm_start = None
    if prev is not None:
        W_prev, c_prev, _ = prev
        far = np.argmax(np.min(np.stack([sq_euclid(X, w) for w in W_prev],
                                        axis=1), axis=1))
        warm_start = np.vstack([W_prev, X[far]])
    prev = best_clustering(X, k, sq_euclid, LOSSES["squared Euclidean"][1],
                           rng, warm=warm_start)
    curve[k] = prev[2][-1]
check("[B-k] " + ", ".join(f"k={k}: {curve[k]:.2f}" for k in curve),
      all(curve[k + 1] <= curve[k] + 1e-9 for k in range(1, 8)))
check(f"[B-k] k = 1: the clustering error {curve[1]:.2f} is the total "
      f"variance of the two features",
      abs(curve[1] - np.sum(X.var(axis=0))) < 1e-9)
check(f"[B-k] k = 2 halves it and more ({curve[2]:.2f}); the fall from "
      f"k = 2 to 8 ({curve[2] - curve[8]:.2f}) is smaller than the fall "
      f"from k = 1 to 2 ({curve[1] - curve[2]:.2f})",
      curve[2] < curve[1] / 2 and curve[2] - curve[8] < curve[1] - curve[2])
check("[B-k] k = 366, every day its own centroid: clustering error 0",
      clustering_error(X, X.copy(), sq_euclid) == 0.0)

# ---- [B-plot] CSVs and preview
print("[B-plot] thinned scatter, centroids, error curve")
idx = np.arange(0, m, 18)
with open(OUT_DIR / "clusteringerror_points_plot.csv", "w") as fh:
    fh.write("tmin,tmax,cluster,ctmin,ctmax\n")
    for i in idx:
        j = c_two[i]
        fh.write(f"{X[i, 0]:.1f},{X[i, 1]:.1f},{int(j == warm)},"
                 f"{W_two[j, 0]:.4f},{W_two[j, 1]:.4f}\n")
check(f"[B-plot] every 18th day: {len(idx)} of the {m} days are drawn",
      len(idx) == 21)
with open(OUT_DIR / "clusteringerror_centroids.csv", "w") as fh:
    fh.write("lossid,loss,cluster,tmin,tmax,error\n")
    for lid, (name, (W, c, e)) in enumerate(results.items()):
        cold_j = int(np.argmin(W[:, 1]))
        for j in (cold_j, 1 - cold_j):
            fh.write(f"{lid},{name},{int(j != cold_j)},{W[j, 0]:.4f},"
                     f"{W[j, 1]:.4f},{e:.4f}\n")
with open(OUT_DIR / "clusteringerror_curve.csv", "w") as fh:
    fh.write("k,error\n")
    for k, e in curve.items():
        fh.write(f"{k},{e:.4f}\n")

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9.4, 3.9))
for j, mk, lab in ((cold, "o", "cold days"), (warm, "s", "warm days")):
    sel = idx[c_two[idx] == j]
    ax1.scatter(X[sel, 0], X[sel, 1], marker=mk, facecolors="none",
                edgecolors="black", s=28, label=f"{lab} (every 18th day)")
    for i in sel:
        ax1.plot([X[i, 0], W_two[j, 0]], [X[i, 1], W_two[j, 1]],
                 color="0.6", lw=0.6, ls="--")
ax1.scatter(W_two[:, 0], W_two[:, 1], marker="x", color="black", s=60,
            label="centroids (k = 2)")
ax1.set_xlabel("morning minimum temperature (°C)")
ax1.set_ylabel("maximum daytime temperature (°C)")
ax1.set_title("loss of a day: squared length of its dashed line")
ax1.legend(frameon=False, fontsize=8)
ks = sorted(curve)
ax2.plot(ks, [curve[k] for k in ks], "ko-")
ax2.set_xlabel("number of clusters k")
ax2.set_ylabel("clustering error (squared Euclidean)")
ax2.set_title("the clustering error only falls with k")
fig.tight_layout()
fig.savefig(OUT_DIR / "clusteringerror.png", dpi=110)

n_ok = sum(ok for _, ok in report)
print(f"\n{n_ok}/{len(report)} checks pass")
if n_ok != len(report):
    raise SystemExit(1)
