


from __future__ import annotations

import random

# Maximum size of the population.  Bigger could be faster but is more memory expensive.
UpperCAmelCase_				:			Any   =	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.
UpperCAmelCase_				:			int   =	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.
UpperCAmelCase_				:			int   =	0.4
# Just a seed to improve randomness required by the algorithm.
random.seed(random.randint(0, 1000))







def 	SCREAMING_SNAKE_CASE_						(      __A			:      Any  ,   __A			:      Union[str, Any]    )     ->		tuple[str, float]:
       a_ :		Union[str, Any]							=  len([g for position, g in enumerate(_lowerCAmelCase    ) if g == main_target[position]]    )
       return (item, float(_lowerCAmelCase    ))







def 	SCREAMING_SNAKE_CASE_						(      __A			:      List[str]  ,   __A			:      List[str]    )     ->		tuple[str, str]:
       a_ :		Any							=  random.randint(0  ,   len(_lowerCAmelCase    ) - 1    )
       a_ :		Dict							=  parent_a[:random_slice] + parent_a[random_slice:]
       a_ :		Dict							=  parent_a[:random_slice] + parent_a[random_slice:]
       return (child_a, child_a)







def 	SCREAMING_SNAKE_CASE_						(      __A			:      List[Any]  ,   __A			:      str    )     ->		str:
       a_ :		str							=  list(_lowerCAmelCase    )
       if random.uniform(0  ,   1    ) < MUTATION_PROBABILITY:
              a_ :		int							=  random.choice(_lowerCAmelCase    )
       return "".join(_lowerCAmelCase    )







def 	SCREAMING_SNAKE_CASE_						(      __A			:      int  ,   __A			:      Union[str, Any]  ,   __A			:      Tuple  ,   )     ->		list[str]:
       a_ :		Dict							=  []
       # Generate more children proportionally to the fitness score.
       a_ :		int							=  int(parent_a[1] * 1_00    ) + 1
       a_ :		List[str]							=  10 if child_n >= 10 else child_n
       for _ in range(_lowerCAmelCase    ):
              a_ :		str							=  population_score[random.randint(0  ,   _lowerCAmelCase    )][0]

              a_ :		Any							=  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 	SCREAMING_SNAKE_CASE_						(      __A			:      Dict  ,   __A			:      str  ,   __A			:      int = True    )     ->		tuple[int, int, str]:

       # Verify if N_POPULATION is bigger than N_SELECTED
       if N_POPULATION < N_SELECTED:
              a_ :		List[Any]							=  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.
       a_ :		Dict							=  sorted({c for c in target if c not in genes}    )
       if not_in_genes_list:
              a_ :		Optional[int]							=  F"""{not_in_genes_list} is not in genes list, evolution cannot converge"""
              raise ValueError(_lowerCAmelCase    )

       # Generate random starting population.
       a_ :		str							=  []
       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.
       a_ :		Tuple							=  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.
              a_ :		str							=  [evaluate(_lowerCAmelCase  ,   _lowerCAmelCase    ) for item in population]

              # Check if there is a matching evolution.
              a_ :		str							=  sorted(_lowerCAmelCase  ,   key=lambda __A    : 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.
              a_ :		List[str]							=  population[: int(N_POPULATION / 3    )]
              population.clear()
              population.extend(_lowerCAmelCase    )
              # Normalize population score to be between 0 and 1.
              a_ :		Optional[int]							=  [
                  (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__":
   UpperCAmelCase_				:			List[str]   =	(
       'This is a genetic algorithm to evaluate, combine, evolve, and mutate a string!'
   )
   UpperCAmelCase_				:			Any   =	list(
       ' ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklm'
       'nopqrstuvwxyz.,;!?+-*#@^\'èéòà€ù=)(&%$£/\\'
   )
   UpperCAmelCase_ ,       UpperCAmelCase_ ,       UpperCAmelCase_				:			Any   =	basic(target_str, genes_list)
   print(
       F'\nGeneration: {generation}\nTotal Population: {population}\nTarget: {target}'
   )






def 	SCREAMING_SNAKE_CASE_						(      __A			:      int    )     ->		int:

       """simple docstring"""

       if not isinstance(__A  ,   __A    ):
              raise ValueError('Input must be an integer'    )
       if input_num <= 0:
              raise ValueError('Input must be positive'    )
       return sum(
           divisor for divisor in range(1  ,   input_num // 2 + 1    ) if input_num % divisor == 0    )


if __name__ == "__main__":
   import doctest

   doctest.testmod()


