


'''simple docstring'''




from __future__ import annotations

import random

# Maximum size of the population.  Bigger could be faster but is more memory expensive.
__snake_case    						=200
# Number of elements selected in every generation of evolution. The selection takes
# place from best to worst of that generation and must be smaller than N_POPULATION.
__snake_case    						=50
# Probability that an element of a generation can mutate, changing one of its genes.
# This will guarantee that all genes will be used during evolution.
__snake_case    						=0.4
# Just a seed to improve randomness required by the algorithm.
random.seed(random.randint(0, 1_000))





def 	a_					( lowerCamelCase	:     str	, lowerCamelCase	:     str				):
   lowerCAmelCase     =			len([g for position, g in enumerate(lowerCamelCase				) if g == main_target[position]]				)
   return (item, float(lowerCamelCase				))





def 	a_					( lowerCamelCase	:     str	, lowerCamelCase	:     str				):
   lowerCAmelCase     =			random.randint(0	, len(lowerCamelCase				) - 1				)
   lowerCAmelCase     =			parent_a[:random_slice] + parent_a[random_slice:]
   lowerCAmelCase     =			parent_a[:random_slice] + parent_a[random_slice:]
   return (child_a, child_a)





def 	a_					( lowerCamelCase	:     str	, lowerCamelCase	:     list[str]				):
   lowerCAmelCase     =			list(lowerCamelCase				)
   if random.uniform(0	, 1				) < MUTATION_PROBABILITY:
      lowerCAmelCase     =			random.choice(lowerCamelCase				)
   return "".join(lowerCamelCase				)





def 	a_					( lowerCamelCase	:     tuple[str, float]	, lowerCamelCase	:     list[tuple[str, float]]	, lowerCamelCase	:     list[str]	, ):
   lowerCAmelCase     =			[]
   # Generate more children proportionally to the fitness score.
   lowerCAmelCase     =			int(parent_a[1] * 100				) + 1
   lowerCAmelCase     =			10 if child_n >= 10 else child_n
   for _ in range(lowerCamelCase				):
      lowerCAmelCase     =			population_score[random.randint(0	, lowerCamelCase				)][0]

      lowerCAmelCase     ,  lowerCAmelCase     =			crossover(parent_a[0]	, lowerCamelCase				)
      # Append new string to the population list.
      pop.append(mutate(lowerCamelCase	, lowerCamelCase				)				)
      pop.append(mutate(lowerCamelCase	, lowerCamelCase				)				)
   return pop





def 	a_					( lowerCamelCase	:     str	, lowerCamelCase	:     list[str]	, lowerCamelCase	:     bool = True				):

   # Verify if N_POPULATION is bigger than N_SELECTED
   if N_POPULATION < N_SELECTED:
      lowerCAmelCase     =			f'''{N_POPULATION} must be bigger than {N_SELECTED}'''
      raise ValueError(lowerCamelCase				)
   # Verify that the target contains no genes besides the ones inside genes variable.
   lowerCAmelCase     =			sorted({c for c in target if c not in genes}				)
   if not_in_genes_list:
      lowerCAmelCase     =			f'''{not_in_genes_list} is not in genes list, evolution cannot converge'''
      raise ValueError(lowerCamelCase				)

   # Generate random starting population.
   lowerCAmelCase     =			[]
   for _ in range(lowerCamelCase				):
      population.append(''.join([random.choice(lowerCamelCase				) for i in range(len(lowerCamelCase				)				)]				)				)

   # Just some logs to know what the algorithms is doing.
   lowerCAmelCase     ,  lowerCAmelCase     =			0, 0

   # This loop will end when we find a perfect match for our target.
   while True:
      generation += 1
      total_population += len(lowerCamelCase				)

      # Random population created. Now it's time to evaluate.

      # Adding a bit of concurrency can make everything faster,
      #
      # import concurrent.futures
      # population_score: list[tuple[str, float]] = []
      # with concurrent.futures.ThreadPoolExecutor(
      #                                   max_workers=NUM_WORKERS) as executor:
      #     futures = {executor.submit(evaluate, item) for item in population}
      #     concurrent.futures.wait(futures)
      #     population_score = [item.result() for item in futures]
      #
      # but with a simple algorithm like this, it will probably be slower.
      # We just need to call evaluate for every item inside the population.
      lowerCAmelCase     =			[evaluate(lowerCamelCase	, lowerCamelCase				) for item in population]

      # Check if there is a matching evolution.
      lowerCAmelCase     =			sorted(lowerCamelCase	, key=lambda lowerCamelCase				: x[1]	, reverse=lowerCamelCase				)
      if population_score[0][0] == target:
         return (generation, total_population, population_score[0][0])

      # Print the best result every 10 generation.
      # Just to know that the algorithm is working.
      if debug and generation % 10 == 0:
         print(
             f'''\nGeneration: {generation}'''
             f'''\nTotal Population:{total_population}'''
             f'''\nBest score: {population_score[0][1]}'''
             f'''\nBest string: {population_score[0][0]}'''				)

      # Flush the old population, keeping some of the best evolutions.
      # Keeping this avoid regression of evolution.
      lowerCAmelCase     =			population[: int(N_POPULATION / 3				)]
      population.clear()
      population.extend(lowerCamelCase				)
      # Normalize population score to be between 0 and 1.
      lowerCAmelCase     =			[
          (item, score / len(lowerCamelCase				)) for item, score in population_score
      ]

      # This is selection
      for i in range(lowerCamelCase				):
         population.extend(select(population_score[int(lowerCamelCase				)]	, lowerCamelCase	, lowerCamelCase				)				)
         # Check if the population has already reached the maximum value and if so,
         # break the cycle.  If this check is disabled, the algorithm will take
         # forever to compute large strings, but will also calculate small strings in
         # a far fewer generations.
         if len(lowerCamelCase				) > N_POPULATION:
            break


if __name__ == "__main__":
       __snake_case    						=(
           """This is a genetic algorithm to evaluate, combine, evolve, and mutate a string!"""
       )
       __snake_case    						=list(
           """ ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklm"""
           """nopqrstuvwxyz.,;!?+-*#@^'èéòà€ù=)(&%$£/\\"""
       )
       __snake_case						,			__snake_case						,			__snake_case    						=basic(target_str, genes_list)
       print(
           F'''\nGeneration: {generation}\nTotal Population: {population}\nTarget: {target}'''
       )









'''simple docstring'''




from __future__ import annotations

from typing import Any

class 		UpperCAmelCase_      :





     def __init__( self       :      Optional[int]    ,      UpperCAmelCase__       :      int    ,      UpperCAmelCase__       :      int    ,      UpperCAmelCase__       :      float = 0    )				->  None:
        lowerCAmelCase     ,  lowerCAmelCase     =			row, column
        lowerCAmelCase     =			[[default_value for c in range(UpperCAmelCase__    )] for r in range(UpperCAmelCase__    )]





     def __str__( self       :      List[str]    )				->  str:
        lowerCAmelCase     =			F'''Matrix consist of {self.row} rows and {self.column} columns\n'''

        # Make string identifier
        lowerCAmelCase     =			0
        for row_vector in self.array:
           for obj in row_vector:
              lowerCAmelCase     =			max(UpperCAmelCase__    ,      len(str(UpperCAmelCase__    )    )    )
        lowerCAmelCase     =			F'''%{max_element_length}s'''

        # Make string and return
        def single_line(UpperCAmelCase__       :      list[float]    ) -> str:
           nonlocal string_format_identifier
           lowerCAmelCase     =			'['
           line += ", ".join(string_format_identifier % (obj,) for obj in row_vector    )
           line += "]"
           return line

        s += "\n".join(single_line(UpperCAmelCase__    ) for row_vector in self.array    )
        return s





     def __repr__( self       :      List[str]    )				->  str:
        return str(self    )





     def 							__UpperCAmelCase      ( self       :      Optional[int]    ,      UpperCAmelCase__       :      tuple[int, int]    )				->  bool:
        if not (isinstance(UpperCAmelCase__    ,      (list, tuple)    ) and len(UpperCAmelCase__    ) == 2):
           return False
        elif not (0 <= loc[0] < self.row and 0 <= loc[1] < self.column):
           return False
        else:
           return True





     def __getitem__( self       :      Any    ,      UpperCAmelCase__       :      tuple[int, int]    )				->  Any:
        assert self.validate_indicies(UpperCAmelCase__    )
        return self.array[loc[0]][loc[1]]





     def __setitem__( self       :      Dict    ,      UpperCAmelCase__       :      tuple[int, int]    ,      UpperCAmelCase__       :      float    )				->  None:
        assert self.validate_indicies(UpperCAmelCase__    )
        lowerCAmelCase     =			value





     def __add__( self       :      Any    ,      UpperCAmelCase__       :      Matrix    )				->  Matrix:
        assert isinstance(UpperCAmelCase__    ,      UpperCAmelCase__    )
        assert self.row == another.row and self.column == another.column

        # Add
        lowerCAmelCase     =			Matrix(self.row    ,      self.column    )
        for r in range(self.row    ):
           for c in range(self.column    ):
              lowerCAmelCase     =			self[r, c] + another[r, c]
        return result





     def __neg__( self       :      int    )				->  Matrix:
        lowerCAmelCase     =			Matrix(self.row    ,      self.column    )
        for r in range(self.row    ):
           for c in range(self.column    ):
              lowerCAmelCase     =			-self[r, c]
        return result





     def __sub__( self       :      str    ,      UpperCAmelCase__       :      Matrix    )				->  Matrix:
        return self + (-another)





     def __mul__( self       :      str    ,      UpperCAmelCase__       :      int | float | Matrix    )				->  Matrix:

        if isinstance(UpperCAmelCase__    ,      (int, float)    ):  # Scalar multiplication
           lowerCAmelCase     =			Matrix(self.row    ,      self.column    )
           for r in range(self.row    ):
              for c in range(self.column    ):
                 lowerCAmelCase     =			self[r, c] * another
           return result
        elif isinstance(UpperCAmelCase__    ,      UpperCAmelCase__    ):  # Matrix multiplication
           assert self.column == another.row
           lowerCAmelCase     =			Matrix(self.row    ,      another.column    )
           for r in range(self.row    ):
              for c in range(another.column    ):
                 for i in range(self.column    ):
                    result[r, c] += self[r, i] * another[i, c]
           return result
        else:
           lowerCAmelCase     =			F'''Unsupported type given for another ({type(UpperCAmelCase__    )})'''
           raise TypeError(UpperCAmelCase__    )





     def 							__UpperCAmelCase      ( self       :      Optional[Any]    )				->  Matrix:
        lowerCAmelCase     =			Matrix(self.column    ,      self.row    )
        for r in range(self.row    ):
           for c in range(self.column    ):
              lowerCAmelCase     =			self[r, c]
        return result





     def 							__UpperCAmelCase      ( self       :      List[str]    ,      UpperCAmelCase__       :      Matrix    ,      UpperCAmelCase__       :      Matrix    )				->  Any:
        assert isinstance(UpperCAmelCase__    ,      UpperCAmelCase__    ) and isinstance(UpperCAmelCase__    ,      UpperCAmelCase__    )
        assert self.row == self.column == u.row == v.row  # u, v should be column vector
        assert u.column == v.column == 1  # u, v should be column vector

        # Calculate
        lowerCAmelCase     =			v.transpose()
        lowerCAmelCase     =			(v_t * self * u)[0, 0] + 1
        if numerator_factor == 0:
           return None  # It's not invertable
        return self - ((self * u) * (v_t * self) * (1.0 / numerator_factor))


# Testing
if __name__ == "__main__":





       def 	a_					( ):
          # a^(-1)
          lowerCAmelCase     =			Matrix(3	, 3	, 0				)
          for i in range(3				):
             lowerCAmelCase     =			1
          print(f'''a^(-1) is {ainv}'''				)
          # u, v
          lowerCAmelCase     =			Matrix(3	, 1	, 0				)
          lowerCAmelCase     ,  lowerCAmelCase     ,  lowerCAmelCase     =			1, 2, -3
          lowerCAmelCase     =			Matrix(3	, 1	, 0				)
          lowerCAmelCase     ,  lowerCAmelCase     ,  lowerCAmelCase     =			4, -2, 5
          print(f'''u is {u}'''				)
          print(f'''v is {v}'''				)
          print(f'''uv^T is {u * v.transpose()}'''				)
          # Sherman Morrison
          print(f'''(a + uv^T)^(-1) is {ainv.sherman_morrison(lowerCamelCase	, lowerCamelCase				)}'''				)





       def 	a_					( ):
          import doctest

          doctest.testmod()




       testa()





