


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

UpperCAmelCase__     			=							'''K-MEANS-CLUST/ '''
def        UpperCAmelCase_      (							__snake_case  ,		__snake_case  ,		__snake_case=None		)  ->    List[Any]:







 """simple docstring"""


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

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

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

 return centroids
def        UpperCAmelCase_      (							__snake_case  ,		__snake_case		)  ->    Any:







 """simple docstring"""


 return pairwise_distances(__snake_case  ,		__snake_case  ,		metric='''euclidean'''		)
def        UpperCAmelCase_      (							__snake_case  ,		__snake_case		)  ->    Optional[Any]:







 """simple docstring"""


 _lowercase							   =centroid_pairwise_dist(__snake_case  ,		__snake_case		)

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

 return cluster_assignment
def        UpperCAmelCase_      (							__snake_case  ,		__snake_case  ,		__snake_case		)  ->    Tuple:







 """simple docstring"""


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

 return new_centroids
def        UpperCAmelCase_      (							__snake_case  ,		__snake_case  ,		__snake_case  ,		__snake_case		)  ->    Optional[Any]:







 """simple docstring"""


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

 return heterogeneity
def        UpperCAmelCase_      (							__snake_case  ,		__snake_case		)  ->    Optional[int]:







 """simple docstring"""


 plt.figure(figsize=(7, 4)		)
 plt.plot(__snake_case  ,		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        UpperCAmelCase_      (							__snake_case  ,		__snake_case  ,		__snake_case  ,		__snake_case=500  ,		__snake_case=None  ,		__snake_case=False		)  ->    Dict:







 """simple docstring"""


 _lowercase							   =initial_centroids[:]
 _lowercase							   =None

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

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

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

  # 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:
   _lowercase							   =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
   _lowercase							   =compute_heterogeneity(__snake_case  ,		__snake_case  ,		__snake_case  ,		__snake_case		)
   record_heterogeneity.append(__snake_case		)

  _lowercase							   =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

  UpperCAmelCase__     			=							ds.load_iris()
  UpperCAmelCase__     			=							3
  UpperCAmelCase__     			=							[]
  UpperCAmelCase__     			=							get_initial_centroids(dataset['''data'''], k, seed=0)
  UpperCAmelCase__			,UpperCAmelCase__     			=							kmeans(
      dataset['''data'''],
      k,
      initial_centroids,
      maxiter=400,
      record_heterogeneity=heterogeneity,
      verbose=True,
  )
  plot_heterogeneity(heterogeneity, k)
def        UpperCAmelCase_      (							__snake_case  ,		__snake_case  ,		__snake_case=None		)  ->    pd.DataFrame:







 """simple docstring"""


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


if __name__ == "__main__":
  import doctest

  doctest.testmod()





UpperCAmelCase__     			=							[0.33, 0.44, 0.55, 0.44, 0.33]
UpperCAmelCase__     			=							3
UpperCAmelCase__     			=							5

# Buffer Space (with Parameters Space)
UpperCAmelCase__     			=							[]
UpperCAmelCase__     			=							[]

# Machine Time
UpperCAmelCase__     			=							0
def        UpperCAmelCase_      (							__snake_case		)  ->    Tuple:







 """simple docstring"""


 global buffer_space, params_space, machine_time, K, m, t

 # Choosing Dynamical Systems (All)
 for key, value in enumerate(__snake_case		):
  # Evolution Parameter
  _lowercase							   =float(seed / value		)

  # Control Theory: Orbit Change
  _lowercase							   =(buffer_space[(key + 1) % m] + e) % 1

  # Control Theory: Trajectory Change
  _lowercase							   =(params_space[key] + e) % 1 + 3

  # Modification (Transition Function) - Jumps
  _lowercase							   =round(float(r * value * (1 - value)		)  ,		10		)
  _lowercase							   =r  # Saving to Parameters Space

 # Logistic Map
 assert max(__snake_case		) < 1
 assert max(__snake_case		) < 4

 # Machine Time
 machine_time += 1
def        UpperCAmelCase_      (							)  ->    Union[str, Any]:







 """simple docstring"""


 global buffer_space, params_space, machine_time, K, m, t

 # PRNG (Xorshift by George Marsaglia)
 def xorshift(__snake_case  ,		__snake_case		):
  x ^= y >> 13
  y ^= x << 17
  x ^= y >> 5
  return x

 # Choosing Dynamical Systems (Increment)
 _lowercase							   =machine_time % m

 # Evolution (Time Length)
 for _ in range(0  ,		__snake_case		):
  # Variables (Position + Parameters)
  _lowercase							   =params_space[key]
  _lowercase							   =buffer_space[key]

  # Modification (Transition Function) - Flow
  _lowercase							   =round(float(r * value * (1 - value)		)  ,		10		)
  _lowercase							   =(machine_time * 0.01 + r * 1.01) % 1 + 3

 # Choosing Chaotic Data
 _lowercase							   =int(buffer_space[(key + 2) % m] * (10**10)		)
 _lowercase							   =int(buffer_space[(key - 2) % m] * (10**10)		)

 # Machine Time
 machine_time += 1

 return xorshift(__snake_case  ,		__snake_case		) % 0XF_F_F_F_F_F_F_F
def        UpperCAmelCase_      (							)  ->    int:







 """simple docstring"""


 global buffer_space, params_space, machine_time, K, m, t

 _lowercase							   =K
 _lowercase							   =[0] * m
 _lowercase							   =0


if __name__ == "__main__":
  # Initialization
  reset()

  # Pushing Data (Input)
  import random

  UpperCAmelCase__     			=							random.sample(range(0xffff_ffff), 100)
  for chunk in message:
    push(chunk)

  # for controlling
  UpperCAmelCase__     			=							''''''

  # Pulling Data (Output)
  while inp in ("e", "E"):
    print(f'''{format(pull(), '#04x')}''')
    print(buffer_space)
    print(params_space)
    UpperCAmelCase__     			=							input('''(e)exit? ''').strip()

