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

__lowercase    =				'''K-MEANS-CLUST/ '''


def    lowerCAmelCase			(__UpperCamelCase							:    List[Any]							,					__UpperCamelCase							:    Any							,					__UpperCamelCase							:    List[str]=None			):
							"""simple docstring"""


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

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

							# 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			(__UpperCamelCase							:    List[str]							,					__UpperCamelCase							:    int			):
							"""simple docstring"""


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


def    lowerCAmelCase			(__UpperCamelCase							:    Union[str, Any]							,					__UpperCamelCase							:    Union[str, Any]			):
							"""simple docstring"""


							__UpperCamelCase							=centroid_pairwise_dist(__UpperCamelCase							,					__UpperCamelCase			)

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

							return cluster_assignment


def    lowerCAmelCase			(__UpperCamelCase							:    Optional[Any]							,					__UpperCamelCase							:    Tuple							,					__UpperCamelCase							:    Optional[Any]			):
							"""simple docstring"""


							__UpperCamelCase							=[]
							for i in range(__UpperCamelCase			):
														# 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(__UpperCamelCase			)
							__UpperCamelCase							=np.array(__UpperCamelCase			)

							return new_centroids


def    lowerCAmelCase			(__UpperCamelCase							:    str							,					__UpperCamelCase							:    List[Any]							,					__UpperCamelCase							:    Optional[int]							,					__UpperCamelCase							:    Dict			):
							"""simple docstring"""


							__UpperCamelCase							=0.0
							for i in range(__UpperCamelCase			):
														# 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(
																					    __UpperCamelCase							,					[centroids[i]]							,					metric='''euclidean'''			)
																					__UpperCamelCase							=distances**2
																					heterogeneity += np.sum(__UpperCamelCase			)

							return heterogeneity


def    lowerCAmelCase			(__UpperCamelCase							:    List[str]							,					__UpperCamelCase							:    Union[str, Any]			):
							"""simple docstring"""


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


def    lowerCAmelCase			(__UpperCamelCase							:    Any							,					__UpperCamelCase							:    List[str]							,					__UpperCamelCase							:    List[Any]							,					__UpperCamelCase							:    Tuple=5_0_0							,					__UpperCamelCase							:    int=None							,					__UpperCamelCase							:    str=False			):
							"""simple docstring"""


							__UpperCamelCase							=initial_centroids[:]
							__UpperCamelCase							=None

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

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

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

														# 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(__UpperCamelCase							,					__UpperCamelCase							,					__UpperCamelCase							,					__UpperCamelCase			)
																					record_heterogeneity.append(__UpperCamelCase			)

														__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

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


def    lowerCAmelCase			(__UpperCamelCase							:    pd.DataFrame							,					__UpperCamelCase							:    np.ndarray							,					__UpperCamelCase							:    str=None			):
							"""simple docstring"""


							if fill_missing_report:
														__UpperCamelCase							=df.fillna(value=__UpperCamelCase			)
							__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 __UpperCamelCase			: np.mean(np.nan_to_num(__UpperCamelCase			)			)),
							            ('''mean_without_zeros''', lambda __UpperCamelCase			: x.replace(0							,					np.NaN			).mean()),
							            (
							                '''mean_25-75''',
							                lambda __UpperCamelCase			: np.mean(
							                    np.nan_to_num(
							                        sorted(__UpperCamelCase			)[
							                            round(len(__UpperCamelCase			) * 2_5 / 1_0_0			) : round(len(__UpperCamelCase			) * 7_5 / 1_0_0			)
							                        ]			)			),
							            ),
							            ('''mean_with_na''', np.mean),
							            ('''min''', lambda __UpperCamelCase			: x.min()),
							            ('''5%''', lambda __UpperCamelCase			: x.quantile(0.0_5			)),
							            ('''25%''', lambda __UpperCamelCase			: x.quantile(0.2_5			)),
							            ('''50%''', lambda __UpperCamelCase			: x.quantile(0.5_0			)),
							            ('''75%''', lambda __UpperCamelCase			: x.quantile(0.7_5			)),
							            ('''95%''', lambda __UpperCamelCase			: x.quantile(0.9_5			)),
							            ('''max''', lambda __UpperCamelCase			: x.max()),
							            ('''count''', lambda __UpperCamelCase			: x.count()),
							            ('''stdev''', lambda __UpperCamelCase			: x.std()),
							            ('''mode''', lambda __UpperCamelCase			: x.mode()[0]),
							            ('''median''', lambda __UpperCamelCase			: x.median()),
							            ('''# > 0''', lambda __UpperCamelCase			: (x > 0).sum()),
							        ]			)
							    .T.reset_index()
							    .rename(index=__UpperCamelCase							,					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(__UpperCamelCase			)
							__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 __UpperCamelCase			: x.Type.map(__UpperCamelCase			)							,					Sortera=lambda __UpperCamelCase			: list(reversed(range(len(__UpperCamelCase			)			)			)			)							,					)
							    .sort_values(['''Sorter1''', '''Mark''', '''Sorter2''']							,					ascending=__UpperCamelCase			)
							    .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"""

def    lowerCAmelCase			(__UpperCamelCase							:    list							,					__UpperCamelCase							:    int			):
							"""simple docstring"""


							for index, item in enumerate(__UpperCamelCase			):
														if item == target:
																					return index
							return -1


def    lowerCAmelCase			(__UpperCamelCase							:    list							,					__UpperCamelCase							:    int							,					__UpperCamelCase							:    int							,					__UpperCamelCase							:    int			):
							"""simple docstring"""


							if not (0 <= high < len(__UpperCamelCase			) and 0 <= low < len(__UpperCamelCase			)):
														raise Exception('''Invalid upper or lower bound!'''			)
							if high < low:
														return -1
							if sequence[low] == target:
														return low
							if sequence[high] == target:
														return high
							return rec_linear_search(__UpperCamelCase							,					low + 1							,					high - 1							,					__UpperCamelCase			)


if __name__ == "__main__":
				__lowercase    =				input('''Enter numbers separated by comma:\n''').strip()
				__lowercase    =				[int(item.strip()) for item in user_input.split(''',''')]

				__lowercase    =				int(input('''Enter a single number to be found in the list:\n''').strip())
				__lowercase    =				linear_search(sequence, target)
				if result != -1:
								print(f'''linear_search({sequence}, {target}) = {result}''')
				else:
								print(f'''{target} was not found in {sequence}''')



