k-Means, and the Cluster That Loses All Its Points

Every from-scratch k-means implementation works on the textbook example and breaks on real data the first time a cluster loses every point it had. The mean of zero points is nan, and from that iteration on, everything downstream is nan too.

Write kmeans(X, k, seed, max_iters=100) implementing Lloyd's algorithm:

1. Initialise k centroids by drawing k distinct rows of X without replacement, using np.random.default_rng(seed).
2. Assign each point to its nearest centroid by Euclidean distance.
3. Update each centroid to the mean of the points assigned to it.
4. Stop when an assignment step produces the same labels as the previous one, or after max_iters iterations.

If an update step leaves a cluster with zero points assigned, its centroid does not become nan. Reassign it to the point in X currently farthest from its own assigned centroid — the single point contributing the most to the total squared distance — breaking ties by the smallest index. Give that reassigned centroid the point that was picked for it, so the next assignment step is not immediately contradicted.

Return (labels, centroids): labels an (n,) int array with values in [0, k), centroids a (k, d) float array.