Assign points to the nearest centroid

The assignment step of k-means: every point joins the cluster of its nearest centroid.

What to build

A program that assigns points on a line to their nearest centroid and counts each cluster's size.

Requirements

  • Clusters are numbered from 1 in the order the centroids are given; a tie goes to the lower number.
  • Print the cluster number of each point on one line, separated by spaces.
  • Then print sizes followed by the number of points in each cluster.

Input

Line 1: the centroids. Line 2: the points.

Output

Two lines.

Constraints

1 to 20 centroids; 1 to 1000 points.

Example

Input:

2 10
1 3 9 12 6

Output:

1 1 2 2 1
sizes 3 2

Why it works

Each point goes where its distance, and so its contribution to the inertia, is smallest, which is exactly what the assignment step needs.

Examples

Example 1 · Input
2 10
1 3 9 12 6
Expected output
1 1 2 2 1
sizes 3 2
Example 2 · Input
0
5 -5
Expected output
1 1
sizes 2

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

For each point, find the centroid with the smallest absolute difference.

Hint 2

On a tie, keep the centroid listed first.

Solution

Show one correct solution (try it yourself first)
centroids = list(map(float, input().split()))
points = list(map(float, input().split()))
labels = [min(range(len(centroids)), key=lambda k: (abs(p - centroids[k]), k)) + 1 for p in points]
print(*labels)
print("sizes", *[labels.count(k + 1) for k in range(len(centroids))])

Lesson: Clustering with k-means →