






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')

A										=      'K-MEANS-CLUST/ '



def        _lowerCamelCase(      lowerCAmelCase__					:		Union[str, Any]     ,     lowerCAmelCase__					:		str     ,     lowerCAmelCase__					:		int=None   ):





				'''simple docstring'''







				if seed is not None:  # useful for obtaining consistent results
								np.random.seed(lowerCAmelCase__   )
				SCREAMING_SNAKE_CASE_ :						Optional[int]    				= data.shape[0]  # number of data points

				# Pick K indices from range [0, N).
				SCREAMING_SNAKE_CASE_ :						Union[str, Any]    				= np.random.randint(0     ,     lowerCAmelCase__     ,     lowerCAmelCase__   )

				# 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.
				SCREAMING_SNAKE_CASE_ :						Tuple    				= data[rand_indices, :]

				return centroids



def        _lowerCamelCase(      lowerCAmelCase__					:		Tuple     ,     lowerCAmelCase__					:		str   ):





				'''simple docstring'''







				return pairwise_distances(lowerCAmelCase__     ,     lowerCAmelCase__     ,     metric='euclidean'   )



def        _lowerCamelCase(      lowerCAmelCase__					:		List[Any]     ,     lowerCAmelCase__					:		Dict   ):





				'''simple docstring'''







				SCREAMING_SNAKE_CASE_ :						str    				= centroid_pairwise_dist(lowerCAmelCase__     ,     lowerCAmelCase__   )

				# Compute cluster assignments for each data point:
				# Fill in the blank (RHS only)
				SCREAMING_SNAKE_CASE_ :						Optional[int]    				= np.argmin(lowerCAmelCase__     ,     axis=1   )

				return cluster_assignment



def        _lowerCamelCase(      lowerCAmelCase__					:		List[str]     ,     lowerCAmelCase__					:		Any     ,     lowerCAmelCase__					:		Dict   ):





				'''simple docstring'''







				SCREAMING_SNAKE_CASE_ :						str    				= []
				for i in range(lowerCAmelCase__   ):
								# Select all data points that belong to cluster i. Fill in the blank (RHS only)
								SCREAMING_SNAKE_CASE_ :						int    				= data[cluster_assignment == i]
								# Compute the mean of the data points. Fill in the blank (RHS only)
								SCREAMING_SNAKE_CASE_ :						Tuple    				= member_data_points.mean(axis=0   )
								new_centroids.append(lowerCAmelCase__   )
				SCREAMING_SNAKE_CASE_ :						Any    				= np.array(lowerCAmelCase__   )

				return new_centroids



def        _lowerCamelCase(      lowerCAmelCase__					:		Optional[Any]     ,     lowerCAmelCase__					:		Optional[int]     ,     lowerCAmelCase__					:		Tuple     ,     lowerCAmelCase__					:		Dict   ):





				'''simple docstring'''







				SCREAMING_SNAKE_CASE_ :						Union[str, Any]    				= 0.0
				for i in range(lowerCAmelCase__   ):
								# Select all data points that belong to cluster i. Fill in the blank (RHS only)
								SCREAMING_SNAKE_CASE_ :						Optional[int]    				= 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)
												SCREAMING_SNAKE_CASE_ :						Optional[Any]    				= pairwise_distances(
												    lowerCAmelCase__     ,     [centroids[i]]     ,     metric='euclidean'   )
												SCREAMING_SNAKE_CASE_ :						int    				= distances**2
												heterogeneity += np.sum(lowerCAmelCase__   )

				return heterogeneity



def        _lowerCamelCase(      lowerCAmelCase__					:		List[Any]     ,     lowerCAmelCase__					:		Dict   ):





				'''simple docstring'''







				plt.figure(figsize=(7, 4)   )
				plt.plot(lowerCAmelCase__     ,     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(      lowerCAmelCase__					:		Optional[Any]     ,     lowerCAmelCase__					:		List[Any]     ,     lowerCAmelCase__					:		int     ,     lowerCAmelCase__					:		List[Any]=500     ,     lowerCAmelCase__					:		Optional[Any]=None     ,     lowerCAmelCase__					:		Any=False   ):





				'''simple docstring'''







				SCREAMING_SNAKE_CASE_ :						Optional[int]    				= initial_centroids[:]
				SCREAMING_SNAKE_CASE_ :						Any    				= None

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

								# 1. Make cluster assignments using nearest centroids
								SCREAMING_SNAKE_CASE_ :						Tuple    				= assign_clusters(lowerCAmelCase__     ,     lowerCAmelCase__   )

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

								# 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:
												SCREAMING_SNAKE_CASE_ :						Union[str, Any]    				= 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
												SCREAMING_SNAKE_CASE_ :						Tuple    				= compute_heterogeneity(lowerCAmelCase__     ,     lowerCAmelCase__     ,     lowerCAmelCase__     ,     lowerCAmelCase__   )
												record_heterogeneity.append(lowerCAmelCase__   )

								SCREAMING_SNAKE_CASE_ :						int    				= 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

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



def        _lowerCamelCase(      lowerCAmelCase__					:		pd.DataFrame     ,     lowerCAmelCase__					:		np.ndarray     ,     lowerCAmelCase__					:		str=None   ):





				'''simple docstring'''







				if fill_missing_report:
								SCREAMING_SNAKE_CASE_ :						str    				= df.fillna(value=lowerCAmelCase__   )
				SCREAMING_SNAKE_CASE_ :						Tuple    				= 1
				SCREAMING_SNAKE_CASE_ :						Optional[Any]    				= df.select_dtypes(np.number   ).columns
				SCREAMING_SNAKE_CASE_ :						List[Any]    				= (
				    df.groupby(['Cluster']   )[  # construct report dataframe
				        numeric_cols
				    ]  # group by cluster number
				    .agg(
				        [
				            ('sum', np.sum),
				            ('mean_with_zeros', lambda lowerCAmelCase__   : np.mean(np.nan_to_num(lowerCAmelCase__   )   )),
				            ('mean_without_zeros', lambda lowerCAmelCase__   : x.replace(0     ,     np.NaN   ).mean()),
				            (
				                'mean_25-75',
				                lambda lowerCAmelCase__   : np.mean(
				                    np.nan_to_num(
				                        sorted(lowerCAmelCase__   )[
				                            round(len(lowerCAmelCase__   ) * 25 / 100   ) : round(len(lowerCAmelCase__   ) * 75 / 100   )
				                        ]   )   ),
				            ),
				            ('mean_with_na', np.mean),
				            ('min', lambda lowerCAmelCase__   : x.min()),
				            ('5%', lambda lowerCAmelCase__   : x.quantile(0.05   )),
				            ('25%', lambda lowerCAmelCase__   : x.quantile(0.25   )),
				            ('50%', lambda lowerCAmelCase__   : x.quantile(0.50   )),
				            ('75%', lambda lowerCAmelCase__   : x.quantile(0.75   )),
				            ('95%', lambda lowerCAmelCase__   : x.quantile(0.95   )),
				            ('max', lambda lowerCAmelCase__   : x.max()),
				            ('count', lambda lowerCAmelCase__   : x.count()),
				            ('stdev', lambda lowerCAmelCase__   : x.std()),
				            ('mode', lambda lowerCAmelCase__   : x.mode()[0]),
				            ('median', lambda lowerCAmelCase__   : x.median()),
				            ('# > 0', lambda lowerCAmelCase__   : (x > 0).sum()),
				        ]   )
				    .T.reset_index()
				    .rename(index=lowerCAmelCase__     ,     columns={'level_0': 'Features', 'level_1': 'Type'}   )
				)  # rename columns
				# calculate the size of cluster(count of clientID's)
				SCREAMING_SNAKE_CASE_ :						Union[str, Any]    				= report[
				    (report['Features'] == 'dummy') & (report['Type'] == 'count')
				].copy()  # avoid SettingWithCopyWarning
				SCREAMING_SNAKE_CASE_ :						Optional[Any]    				= (
				    'ClusterSize'  # rename created cluster df to match report column names
				)
				SCREAMING_SNAKE_CASE_ :						List[str]    				= '# of Customers'
				SCREAMING_SNAKE_CASE_ :						Tuple    				= pd.DataFrame(
				    clustersize.iloc[:, 2:].values
				    / clustersize.iloc[:, 2:].values.sum()   )
				SCREAMING_SNAKE_CASE_ :						Optional[int]    				= '% of Customers'  # rename created cluster df to match report column names
				SCREAMING_SNAKE_CASE_ :						Any    				= 'ClusterProportion'
				SCREAMING_SNAKE_CASE_ :						int    				= clusterproportion.columns.tolist()
				SCREAMING_SNAKE_CASE_ :						int    				= cols[-2:] + cols[:-2]
				SCREAMING_SNAKE_CASE_ :						Union[str, Any]    				= clusterproportion[cols]  # rearrange columns to match report
				SCREAMING_SNAKE_CASE_ :						int    				= report.columns
				SCREAMING_SNAKE_CASE_ :						List[str]    				= pd.DataFrame(
				    abs(
				        report[report['Type'] == 'count'].iloc[:, 2:].values
				        - clustersize.iloc[:, 2:].values   )   )  # generating df with count of nan values
				SCREAMING_SNAKE_CASE_ :						Dict    				= 0
				SCREAMING_SNAKE_CASE_ :						Any    				= '# of nan'
				SCREAMING_SNAKE_CASE_ :						List[Any]    				= report[
				    report['Type'] == 'count'
				].Features.tolist()  # filling values in order to match report
				SCREAMING_SNAKE_CASE_ :						Optional[Any]    				= a.columns.tolist()
				SCREAMING_SNAKE_CASE_ :						Any    				= cols[-2:] + cols[:-2]
				SCREAMING_SNAKE_CASE_ :						Optional[Any]    				= a[cols]  # rearrange columns to match report
				SCREAMING_SNAKE_CASE_ :						Optional[Any]    				= report.columns  # rename columns to match report
				SCREAMING_SNAKE_CASE_ :						List[Any]    				= report.drop(
				    report[report.Type == 'count'].index   )  # drop count values except cluster size
				SCREAMING_SNAKE_CASE_ :						str    				= pd.concat(
				    [report, a, clustersize, clusterproportion]     ,     axis=0   )  # concat report with clustert size and nan values
				SCREAMING_SNAKE_CASE_ :						str    				= report['Features'].isin(lowerCAmelCase__   )
				SCREAMING_SNAKE_CASE_ :						Any    				= report.columns.tolist()
				SCREAMING_SNAKE_CASE_ :						Union[str, Any]    				= cols[0:2] + cols[-1:] + cols[2:-1]
				SCREAMING_SNAKE_CASE_ :						str    				= report[cols]
				SCREAMING_SNAKE_CASE_ :						int    				= {
				    '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,
				}
				SCREAMING_SNAKE_CASE_ :						Optional[Any]    				= (
				    report.assign(
				        Sortera=lambda lowerCAmelCase__   : x.Type.map(lowerCAmelCase__   )     ,     Sortera=lambda lowerCAmelCase__   : list(reversed(range(len(lowerCAmelCase__   )   )   )   )     ,     )
				    .sort_values(['Sorter1', 'Mark', 'Sorter2']     ,     ascending=lowerCAmelCase__   )
				    .drop(['Sorter1', 'Sorter2']     ,     axis=1   )
				)
				SCREAMING_SNAKE_CASE_ :						List[str]    				= ''
				SCREAMING_SNAKE_CASE_ :						str    				= report.reset_index()
				SCREAMING_SNAKE_CASE_ :						Dict    				= report.drop(columns=['index']   )
				return report


if __name__ == "__main__":
				import doctest

				doctest.testmod()







def        _lowerCamelCase(      lowerCAmelCase__					:		int = 99_8001   ):





				'''simple docstring'''







				for number in range(n - 1     ,     9999     ,     -1   ):
								SCREAMING_SNAKE_CASE_ :						int    				= str(lowerCAmelCase__   )

								# checks whether 'str_number' is a palindrome.
								if str_number == str_number[::-1]:
												SCREAMING_SNAKE_CASE_ :						str    				= 999

												# if 'number' is a product of two 3-digit numbers
												# then number is the answer otherwise fetch next number.
												while divisor != 99:
																if (number % divisor == 0) and (len(str(number // divisor   )   ) == 3.0):
																				return number
																divisor -= 1
				raise ValueError('That number is larger than our acceptable range.'   )


if __name__ == "__main__":
				print(f"""{solution() = }""")