



"""simple docstring"""


import warnings

import numpy as np
import pandas as pd
from matplotlib import pyplot as plt
from sklearn.metrics import pairwise_distances

warnings.filterwarnings("""ignore""")

snake_case_         = """K-MEANS-CLUST/ """

def 				_lowerCAmelCase   (     lowercase_	,			lowercase_	,			lowercase_=None		):
						if seed is not None:  # useful for obtaining consistent results
												np.random.seed(lowercase_		)
						UpperCAmelCase    =				data.shape[0]  # number of data points

						# Pick K indices from range [0, N).
						UpperCAmelCase    =				np.random.randint(0	,			lowercase_	,			lowercase_		)

						# Keep centroids as dense format, as many entries will be nonzero due to averaging.
						# As long as at least one document in a cluster contains a word,
						# it will carry a nonzero weight in the TF-IDF vector of the centroid.
						UpperCAmelCase    =				data[rand_indices, :]

						return centroids

def 				_lowerCAmelCase   (     lowercase_	,			lowercase_		):
						return pairwise_distances(lowercase_	,			lowercase_	,			metric='euclidean'		)

def 				_lowerCAmelCase   (     lowercase_	,			lowercase_		):
						# Compute distances between each data point and the set of centroids:
						# Fill in the blank (RHS only)
						UpperCAmelCase    =				centroid_pairwise_dist(lowercase_	,			lowercase_		)

						# Compute cluster assignments for each data point:
						# Fill in the blank (RHS only)
						UpperCAmelCase    =				np.argmin(lowercase_	,			axis=1		)

						return cluster_assignment

def 				_lowerCAmelCase   (     lowercase_	,			lowercase_	,			lowercase_		):
						UpperCAmelCase    =				[]
						for i in range(lowercase_		):
												# Select all data points that belong to cluster i. Fill in the blank (RHS only)
												UpperCAmelCase    =				data[cluster_assignment == i]
												# Compute the mean of the data points. Fill in the blank (RHS only)
												UpperCAmelCase    =				member_data_points.mean(axis=0		)
												new_centroids.append(lowercase_		)
						UpperCAmelCase    =				np.array(lowercase_		)

						return new_centroids

def 				_lowerCAmelCase   (     lowercase_	,			lowercase_	,			lowercase_	,			lowercase_		):
						UpperCAmelCase    =				0.0
						for i in range(lowercase_		):
												# Select all data points that belong to cluster i. Fill in the blank (RHS only)
												UpperCAmelCase    =				data[cluster_assignment == i, :]

												if member_data_points.shape[0] > 0:  # check if i-th cluster is non-empty
																		# Compute distances from centroid to data points (RHS only)
																		UpperCAmelCase    =				pairwise_distances(
																		    lowercase_	,			[centroids[i]]	,			metric='euclidean'		)
																		UpperCAmelCase    =				distances**2
																		heterogeneity += np.sum(lowercase_		)

						return heterogeneity

def 				_lowerCAmelCase   (     lowercase_	,			lowercase_		):
						plt.figure(figsize=(7, 4)		)
						plt.plot(lowercase_	,			linewidth=4		)
						plt.xlabel('# Iterations'		)
						plt.ylabel('Heterogeneity'		)
						plt.title(F"""Heterogeneity of clustering over time, K={k:d}"""		)
						plt.rcParams.update({'font.size': 16}		)
						plt.show()

def 				_lowerCAmelCase   (     lowercase_	,			lowercase_	,			lowercase_	,			lowercase_=500	,			lowercase_=None	,			lowercase_=False		):
						UpperCAmelCase    =				initial_centroids[:]
						UpperCAmelCase    =				None

						for itr in range(lowercase_		):
												if verbose:
																		print(lowercase_	,			end=''		)

												# 1. Make cluster assignments using nearest centroids
												UpperCAmelCase    =				assign_clusters(lowercase_	,			lowercase_		)

												# 2. Compute a new centroid for each of the k clusters, averaging all data
												#    points assigned to that cluster.
												UpperCAmelCase    =				revise_centroids(lowercase_	,			lowercase_	,			lowercase_		)

												# Check for convergence: if none of the assignments changed, stop
												if (
												    prev_cluster_assignment is not None
												    and (prev_cluster_assignment == cluster_assignment).all()
												):
																		break

												# Print number of new assignments
												if prev_cluster_assignment is not None:
																		UpperCAmelCase    =				np.sum(prev_cluster_assignment != cluster_assignment		)
																		if verbose:
																								print(
																								    F"""    {num_changed:5d} elements changed their cluster assignment."""		)

        # Record heterogeneity convergence metric
												if record_heterogeneity is not None:
																		# YOUR CODE HERE
																		UpperCAmelCase    =				compute_heterogeneity(lowercase_	,			lowercase_	,			lowercase_	,			lowercase_		)
																		record_heterogeneity.append(lowercase_		)

												UpperCAmelCase    =				cluster_assignment[:]

						return centroids, cluster_assignment


# Mock test below
if False:  # change to true to run this test case.
				from sklearn import datasets as ds

				snake_case_         = ds.load_iris()
				snake_case_         = 3
				snake_case_         = []
				snake_case_         = get_initial_centroids(dataset["""data"""], k, seed=0)
				snake_case_  ,     snake_case_         = kmeans(
				    dataset["""data"""],
				    k,
				    initial_centroids,
				    maxiter=400,
				    record_heterogeneity=heterogeneity,
				    verbose=True,
				)
				plot_heterogeneity(heterogeneity, k)

def 				_lowerCAmelCase   (     lowercase_	,			lowercase_	,			lowercase_=None		):
						# Fill missing values with given rules
						if fill_missing_report:
												UpperCAmelCase    =				df.fillna(value=lowercase_		)
						UpperCAmelCase    =				1
						UpperCAmelCase    =				df.select_dtypes(np.number		).columns
						UpperCAmelCase    =				(
						    df.groupby(['Cluster']		)[  # construct report dataframe
						        numeric_cols
						    ]  # group by cluster number
						    .agg(
						        [
						            ('sum', np.sum),
						            ('mean_with_zeros', lambda lowercase_		: np.mean(np.nan_to_num(lowercase_		)		)),
						            ('mean_without_zeros', lambda lowercase_		: x.replace(0	,			np.NaN		).mean()),
						            (
						                'mean_25-75',
						                lambda lowercase_		: np.mean(
						                    np.nan_to_num(
						                        sorted(lowercase_		)[
						                            round(len(lowercase_		) * 25 / 100		) : round(len(lowercase_		) * 75 / 100		)
						                        ]		)		),
						            ),
						            ('mean_with_na', np.mean),
						            ('min', lambda lowercase_		: x.min()),
						            ('5%', lambda lowercase_		: x.quantile(0.0_5		)),
						            ('25%', lambda lowercase_		: x.quantile(0.2_5		)),
						            ('50%', lambda lowercase_		: x.quantile(0.5_0		)),
						            ('75%', lambda lowercase_		: x.quantile(0.7_5		)),
						            ('95%', lambda lowercase_		: x.quantile(0.9_5		)),
						            ('max', lambda lowercase_		: x.max()),
						            ('count', lambda lowercase_		: x.count()),
						            ('stdev', lambda lowercase_		: x.std()),
						            ('mode', lambda lowercase_		: x.mode()[0]),
						            ('median', lambda lowercase_		: x.median()),
						            ('# > 0', lambda lowercase_		: (x > 0).sum()),
						        ]		)
						    .T.reset_index()
						    .rename(index=lowercase_	,			columns={'level_0': 'Features', 'level_1': 'Type'}		)
						)  # rename columns
						# calculate the size of cluster(count of clientID's)
						UpperCAmelCase    =				report[
						    (report['Features'] == 'dummy') & (report['Type'] == 'count')
						].copy()  # avoid SettingWithCopyWarning
						UpperCAmelCase    =				(
						    'ClusterSize'  # rename created cluster df to match report column names
						)
						UpperCAmelCase    =				'# of Customers'
						UpperCAmelCase    =				pd.DataFrame(
						    clustersize.iloc[:, 2:].values
						    / clustersize.iloc[:, 2:].values.sum()		)
						UpperCAmelCase    =				'% of Customers'  # rename created cluster df to match report column names
						UpperCAmelCase    =				'ClusterProportion'
						UpperCAmelCase    =				clusterproportion.columns.tolist()
						UpperCAmelCase    =				cols[-2:] + cols[:-2]
						UpperCAmelCase    =				clusterproportion[cols]  # rearrange columns to match report
						UpperCAmelCase    =				report.columns
						UpperCAmelCase    =				pd.DataFrame(
						    abs(
						        report[report['Type'] == 'count'].iloc[:, 2:].values
						        - clustersize.iloc[:, 2:].values		)		)  # generating df with count of nan values
						UpperCAmelCase    =				0
						UpperCAmelCase    =				'# of nan'
						UpperCAmelCase    =				report[
						    report['Type'] == 'count'
						].Features.tolist()  # filling values in order to match report
						UpperCAmelCase    =				a.columns.tolist()
						UpperCAmelCase    =				cols[-2:] + cols[:-2]
						UpperCAmelCase    =				a[cols]  # rearrange columns to match report
						UpperCAmelCase    =				report.columns  # rename columns to match report
						UpperCAmelCase    =				report.drop(
						    report[report.Type == 'count'].index		)  # drop count values except cluster size
						UpperCAmelCase    =				pd.concat(
						    [report, a, clustersize, clusterproportion]	,			axis=0		)  # concat report with clustert size and nan values
						UpperCAmelCase    =				report['Features'].isin(lowercase_		)
						UpperCAmelCase    =				report.columns.tolist()
						UpperCAmelCase    =				cols[0:2] + cols[-1:] + cols[2:-1]
						UpperCAmelCase    =				report[cols]
						UpperCAmelCase    =				{
						    'ClusterSize': 9,
						    'ClusterProportion': 8,
						    'mean_with_zeros': 7,
						    'mean_with_na': 6,
						    'max': 5,
						    '50%': 4,
						    'min': 3,
						    '25%': 2,
						    '75%': 1,
						    '# of nan': 0,
						    '# > 0': -1,
						    'sum_with_na': -2,
						}
						UpperCAmelCase    =				(
						    report.assign(
						        Sortera=lambda lowercase_		: x.Type.map(lowercase_		)	,			Sortera=lambda lowercase_		: list(reversed(range(len(lowercase_		)		)		)		)	,			)
						    .sort_values(['Sorter1', 'Mark', 'Sorter2']	,			ascending=lowercase_		)
						    .drop(['Sorter1', 'Sorter2']	,			axis=1		)
						)
						UpperCAmelCase    =				''
						UpperCAmelCase    =				report.reset_index()
						UpperCAmelCase    =				report.drop(columns=['index']		)
						return report


if __name__ == "__main__":
				import doctest

				doctest.testmod()










"""simple docstring"""


from collections import Counter

def 				_lowerCAmelCase   (     lowercase_		):
						return sum(socks_by_color // 2 for socks_by_color in Counter(lowercase_		).values()		)


if __name__ == "__main__":
				import doctest

				doctest.testmod()

				snake_case_         = [int(x) for x in input("""Enter socks by color :""").rstrip().split()]
				print(f'''sock_merchant({colors}) = {sock_merchant(colors)}''')





