How Many Depots?

More depots always bring the customers closer, so the within-cluster sum of squares alone cannot say how many depots to build. The company looks for the point where one more depot stops helping much.

Write choose_k(points, k_max, restarts, threshold) that returns a tuple (wcss, k):

• For every k from 1 to min(k_max, len(points)), run kmeans(points, k, seed) for the seeds 0, 1, …, restarts - 1 and keep the smallest sum of squares. wcss is the list of these values, for k = 1, 2, ….
• k is the smallest number of clusters for which going to k + 1 lowers the sum of squares by less than the fraction threshold of its value, that is (W_k - W_(k+1)) / W_k < threshold, where W_k is the value for k clusters. If W_k = 0, that k is chosen. If no k qualifies, the largest k tried is chosen.

The setup provides kmeans(points, k, seed, max_rounds=100), the k-means of the previous problem, which returns (centres, assign, wcss, rounds); make_blobs(seed) (30 points around three centres) and customer_map(n, groups, seed) (n customers around groups towns).

Examples

Input:  points = make_blobs(1), k_max = 6, restarts = 10, threshold = 0.3
Output: ([416.6173333333333, 180.2265, 42.233999999999995, 34.959, 28.74333333333333, 21.181249999999995], 3)
Explanation: going from 3 to 4 clusters lowers the sum by only (42.23 - 34.96) / 42.23 = 17%.

Input:  points = [[0], [10]], k_max = 5, restarts = 3, threshold = 0.5
Output: ([50.0, 0.0], 2)
Explanation: only 2 clusters can be tried; 1 → 2 lowers the sum by 100%, so no k qualifies.

Constraints

• 1 <= len(points) <= 300, 1 <= k_max <= 8, 1 <= restarts <= 10, 0 < threshold < 1
• floats are compared with a tolerance of 1e-6

Goals

• Protect k-means against bad starts by keeping the best of several seeded runs
• Tabulate the within-cluster sum of squares against the number of clusters
• Choose k by a stated elbow rule, since the sum of squares always falls as k grows