



from random import shuffle

import tensorflow as tf
from numpy import array






def 	_lowerCAmelCase						(				__lowerCamelCase   :     Optional[int]		,	__lowerCamelCase   :     Optional[Any]     ):



 """simple docstring"""





 __SCREAMING_SNAKE_CASE       :    Optional[Any]       =	int(__lowerCamelCase     )
 assert noofclusters < len(__lowerCamelCase     )

 # Find out the dimensionality
 __SCREAMING_SNAKE_CASE       :    List[str]       =	len(vectors[0]     )

 # Will help select random centroids from among the available vectors
 __SCREAMING_SNAKE_CASE       :    List[Any]       =	list(range(len(__lowerCamelCase     )     )     )
 shuffle(__lowerCamelCase     )

 # GRAPH OF COMPUTATION
 # We initialize a new graph and set it as the default during each run
 # of this algorithm. This ensures that as this function is called
 # multiple times, the default graph doesn't keep getting crowded with
 # unused ops and Variables from previous function calls.

 __SCREAMING_SNAKE_CASE       :    Optional[int]       =	tf.Graph()

 with graph.as_default():
  # SESSION OF COMPUTATION

  __SCREAMING_SNAKE_CASE       :    str       =	tf.Session()

  ##CONSTRUCTING THE ELEMENTS OF COMPUTATION

  ##First lets ensure we have a Variable vector for each centroid,
  ##initialized to one of the vectors from the available data points
  __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	[
      tf.Variable(vectors[vector_indices[i]]     ) for i in range(__lowerCamelCase     )
  ]
  ##These nodes will assign the centroid Variables the appropriate
  ##values
  __SCREAMING_SNAKE_CASE       :    List[Any]       =	tf.placeholder("float64"		,	[dim]     )
  __SCREAMING_SNAKE_CASE       :    int       =	[]
  for centroid in centroids:
   cent_assigns.append(tf.assign(__lowerCamelCase		,	__lowerCamelCase     )     )

  ##Variables for cluster assignments of individual vectors(initialized
  ##to 0 at first)
  __SCREAMING_SNAKE_CASE       :    Dict       =	[tf.Variable(0     ) for i in range(len(__lowerCamelCase     )     )]
  ##These nodes will assign an assignment Variable the appropriate
  ##value
  __SCREAMING_SNAKE_CASE       :    Tuple       =	tf.placeholder("int32"     )
  __SCREAMING_SNAKE_CASE       :    str       =	[]
  for assignment in assignments:
   cluster_assigns.append(tf.assign(__lowerCamelCase		,	__lowerCamelCase     )     )

  ##Now lets construct the node that will compute the mean
  # The placeholder for the input
  __SCREAMING_SNAKE_CASE       :    Tuple       =	tf.placeholder("float"		,	[None, dim]     )
  # The Node/op takes the input and computes a mean along the 0th
  # dimension, i.e. the list of input vectors
  __SCREAMING_SNAKE_CASE       :    Any       =	tf.reduce_mean(__lowerCamelCase		,	0     )

  ##Node for computing Euclidean distances
  # Placeholders for input
  __SCREAMING_SNAKE_CASE       :    List[Any]       =	tf.placeholder("float"		,	[dim]     )
  __SCREAMING_SNAKE_CASE       :    Optional[int]       =	tf.placeholder("float"		,	[dim]     )
  __SCREAMING_SNAKE_CASE       :    Any       =	tf.sqrt(tf.reduce_sum(tf.pow(tf.sub(__lowerCamelCase		,	__lowerCamelCase     )		,	2     )     )     )

  ##This node will figure out which cluster to assign a vector to,
  ##based on Euclidean distances of the vector from the centroids.
  # Placeholder for input
  __SCREAMING_SNAKE_CASE       :    Tuple       =	tf.placeholder("float"		,	[noofclusters]     )
  __SCREAMING_SNAKE_CASE       :    Optional[int]       =	tf.argmin(__lowerCamelCase		,	0     )

  ##INITIALIZING STATE VARIABLES

  ##This will help initialization of all Variables defined with respect
  ##to the graph. The Variable-initializer should be defined after
  ##all the Variables have been constructed, so that each of them
  ##will be included in the initialization.
  __SCREAMING_SNAKE_CASE       :    Optional[int]       =	tf.initialize_all_variables()

  # Initialize all variables
  sess.run(__lowerCamelCase     )

  ##CLUSTERING ITERATIONS

  # Now perform the Expectation-Maximization steps of K-Means clustering
  # iterations. To keep things simple, we will only do a set number of
  # iterations, instead of using a Stopping Criterion.
  __SCREAMING_SNAKE_CASE       :    Optional[Any]       =	100
  for _ in range(__lowerCamelCase     ):
   ##EXPECTATION STEP
   ##Based on the centroid locations till last iteration, compute
   ##the _expected_ centroid assignments.
   # Iterate over each vector
   for vector_n in range(len(__lowerCamelCase     )     ):
    __SCREAMING_SNAKE_CASE       :    List[Any]       =	vectors[vector_n]
    # Compute Euclidean distance between this vector and each
    # centroid. Remember that this list cannot be named
    #'centroid_distances', since that is the input to the
    # cluster assignment node.
    __SCREAMING_SNAKE_CASE       :    Tuple       =	[
        sess.run(__lowerCamelCase		,	feed_dict={va: vect, va: sess.run(__lowerCamelCase     )}     )
        for centroid in centroids
    ]
    # Now use the cluster assignment node, with the distances
    # as the input
    __SCREAMING_SNAKE_CASE       :    Optional[Any]       =	sess.run(
        __lowerCamelCase		,	feed_dict={centroid_distances: distances}     )
    # Now assign the value to the appropriate state variable
    sess.run(
        cluster_assigns[vector_n]		,	feed_dict={assignment_value: assignment}     )

   ##MAXIMIZATION STEP
   # Based on the expected state computed from the Expectation Step,
   # compute the locations of the centroids so as to maximize the
   # overall objective of minimizing within-cluster Sum-of-Squares
   for cluster_n in range(__lowerCamelCase     ):
    # Collect all the vectors assigned to this cluster
    __SCREAMING_SNAKE_CASE       :    Any       =	[
        vectors[i]
        for i in range(len(__lowerCamelCase     )     )
        if sess.run(assignments[i]     ) == cluster_n
    ]
    # Compute new centroid location
    __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	sess.run(
        __lowerCamelCase		,	feed_dict={mean_input: array(__lowerCamelCase     )}     )
    # Assign value to appropriate variable
    sess.run(
        cent_assigns[cluster_n]		,	feed_dict={centroid_value: new_location}     )

        # Return centroids and assignments
  __SCREAMING_SNAKE_CASE       :    List[Any]       =	sess.run(__lowerCamelCase     )
  __SCREAMING_SNAKE_CASE       :    Dict       =	sess.run(__lowerCamelCase     )
  return centroids, assignments











from collections.abc import Generator
from math import sin






def 	_lowerCAmelCase						(				__lowerCamelCase   :     bytes     ):



 """simple docstring"""





 if len(__lowerCamelCase     ) != 32:
  raise ValueError("Input must be of length 32"     )

 __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	b""
 for i in [3, 2, 1, 0]:
  little_endian += string_aa[8 * i : 8 * i + 8]
 return little_endian






def 	_lowerCAmelCase						(				__lowerCamelCase   :     int     ):



 """simple docstring"""





 if i < 0:
  raise ValueError("Input must be non-negative"     )

 __SCREAMING_SNAKE_CASE       :    Any       =	format(__lowerCamelCase		,	"08x"     )[-8:]
 __SCREAMING_SNAKE_CASE       :    Optional[Any]       =	b""
 for i in [3, 2, 1, 0]:
  little_endian_hex += hex_rep[2 * i : 2 * i + 2].encode("utf-8"     )
 return little_endian_hex






def 	_lowerCAmelCase						(				__lowerCamelCase   :     bytes     ):



 """simple docstring"""





 __SCREAMING_SNAKE_CASE       :    Any       =	b""
 for char in message:
  bit_string += format(__lowerCamelCase		,	"08b"     ).encode("utf-8"     )
 __SCREAMING_SNAKE_CASE       :    List[str]       =	format(len(__lowerCamelCase     )		,	"064b"     ).encode("utf-8"     )

 # Pad bit_string to a multiple of 512 chars
 bit_string += b"1"
 while len(__lowerCamelCase     ) % 512 != 448:
  bit_string += b"0"
 bit_string += to_little_endian(start_len[32:]     ) + to_little_endian(start_len[:32]     )

 return bit_string






def 	_lowerCAmelCase						(				__lowerCamelCase   :     bytes     ):



 """simple docstring"""





 if len(__lowerCamelCase     ) % 512 != 0:
  raise ValueError("Input must have length that's a multiple of 512"     )

 for pos in range(0		,	len(__lowerCamelCase     )		,	512     ):
  __SCREAMING_SNAKE_CASE       :    int       =	bit_string[pos : pos + 512]
  __SCREAMING_SNAKE_CASE       :    Tuple       =	[]
  for i in range(0		,	512		,	32     ):
   block_words.append(int(to_little_endian(block[i : i + 32]     )		,	2     )     )
  yield block_words






def 	_lowerCAmelCase						(				__lowerCamelCase   :     int     ):



 """simple docstring"""





 if i < 0:
  raise ValueError("Input must be non-negative"     )

 __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	format(__lowerCamelCase		,	"032b"     )
 __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	""
 for c in i_str:
  new_str += "1" if c == "0" else "0"
 return int(__lowerCamelCase		,	2     )






def 	_lowerCAmelCase						(				__lowerCamelCase   :     int		,	__lowerCamelCase   :     int     ):



 """simple docstring"""





 return (a + b) % 2**32






def 	_lowerCAmelCase						(				__lowerCamelCase   :     int		,	__lowerCamelCase   :     int     ):



 """simple docstring"""





 if i < 0:
  raise ValueError("Input must be non-negative"     )
 if shift < 0:
  raise ValueError("Shift must be non-negative"     )
 return ((i << shift) ^ (i >> (32 - shift))) % 2**32






def 	_lowerCAmelCase						(				__lowerCamelCase   :     bytes     ):



 """simple docstring"""





 __SCREAMING_SNAKE_CASE       :    Tuple       =	preprocess(__lowerCamelCase     )

 __SCREAMING_SNAKE_CASE       :    List[Any]       =	[int(2**32 * abs(sin(i + 1     )     )     ) for i in range(64     )]

 # Starting states
 __SCREAMING_SNAKE_CASE       :    Tuple       =	0X67452301
 __SCREAMING_SNAKE_CASE       :    Optional[Any]       =	0Xefcdab89
 __SCREAMING_SNAKE_CASE       :    Optional[int]       =	0X98badcfe
 __SCREAMING_SNAKE_CASE       :    Optional[Any]       =	0X10325476

 __SCREAMING_SNAKE_CASE       :    List[Any]       =	[
     7,
     12,
     17,
     22,
     7,
     12,
     17,
     22,
     7,
     12,
     17,
     22,
     7,
     12,
     17,
     22,
     5,
     9,
     14,
     20,
     5,
     9,
     14,
     20,
     5,
     9,
     14,
     20,
     5,
     9,
     14,
     20,
     4,
     11,
     16,
     23,
     4,
     11,
     16,
     23,
     4,
     11,
     16,
     23,
     4,
     11,
     16,
     23,
     6,
     10,
     15,
     21,
     6,
     10,
     15,
     21,
     6,
     10,
     15,
     21,
     6,
     10,
     15,
     21,
 ]

 # Process bit string in chunks, each with 16 32-char words
 for block_words in get_block_words(__lowerCamelCase     ):
  __SCREAMING_SNAKE_CASE       :    Any       =	aa
  __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	ba
  __SCREAMING_SNAKE_CASE       :    str       =	ca
  __SCREAMING_SNAKE_CASE       :    Dict       =	da

  # Hash current chunk
  for i in range(64     ):
   if i <= 15:
    # f = (b & c) | (not_32(b) & d)     # Alternate definition for f
    __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	d ^ (b & (c ^ d))
    __SCREAMING_SNAKE_CASE       :    Optional[Any]       =	i
   elif i <= 31:
    # f = (d & b) | (not_32(d) & c)     # Alternate definition for f
    __SCREAMING_SNAKE_CASE       :    int       =	c ^ (d & (b ^ c))
    __SCREAMING_SNAKE_CASE       :    int       =	(5 * i + 1) % 16
   elif i <= 47:
    __SCREAMING_SNAKE_CASE       :    List[str]       =	b ^ c ^ d
    __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	(3 * i + 5) % 16
   else:
    __SCREAMING_SNAKE_CASE       :    Any       =	c ^ (b | not_aa(__lowerCamelCase     ))
    __SCREAMING_SNAKE_CASE       :    str       =	(7 * i) % 16
   __SCREAMING_SNAKE_CASE       :    List[str]       =	(f + a + added_consts[i] + block_words[g]) % 2**32
   __SCREAMING_SNAKE_CASE       :    Dict       =	d
   __SCREAMING_SNAKE_CASE       :    str       =	c
   __SCREAMING_SNAKE_CASE       :    Tuple       =	b
   __SCREAMING_SNAKE_CASE       :    Optional[int]       =	sum_aa(__lowerCamelCase		,	left_rotate_aa(__lowerCamelCase		,	shift_amounts[i]     )     )

  # Add hashed chunk to running total
  __SCREAMING_SNAKE_CASE       :    Dict       =	sum_aa(__lowerCamelCase		,	__lowerCamelCase     )
  __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	sum_aa(__lowerCamelCase		,	__lowerCamelCase     )
  __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	sum_aa(__lowerCamelCase		,	__lowerCamelCase     )
  __SCREAMING_SNAKE_CASE       :    str       =	sum_aa(__lowerCamelCase		,	__lowerCamelCase     )

 __SCREAMING_SNAKE_CASE       :    List[str]       =	reformat_hex(__lowerCamelCase     ) + reformat_hex(__lowerCamelCase     ) + reformat_hex(__lowerCamelCase     ) + reformat_hex(__lowerCamelCase     )
 return digest


if __name__ == "__main__":
      import doctest

      doctest.testmod()






