



"""simple docstring"""
from math import sqrt

def    _snake_case		(		UpperCamelCase		:	int		):
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		) and (
     number >= 0
 ), "'number' must been an int and positive"

 UpperCAmelCase			:      List[str]			=			True

 # 0 and 1 are none primes.
 if number <= 1:
  UpperCAmelCase			:      Optional[Any]			=			False

 for divisor in range(2    ,	int(round(sqrt(UpperCamelCase		)		)		) + 1		):
  # if 'number' divisible by 'divisor' then sets 'status'
  # of false and break up the loop.
  if number % divisor == 0:
   UpperCAmelCase			:      int			=			False
   break

    # precondition
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		), "'status' must been from type bool"

 return status

def    _snake_case		(		UpperCamelCase		:	Dict		):
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		) and (n > 2), "'N' must been an int and > 2"

 # beginList: contains all natural numbers from 2 up to N
 UpperCAmelCase			:      List[Any]			=			list(range(2    ,	n + 1		)		)

 UpperCAmelCase			:      str			=			[]  # this list will be returns.

 # actual sieve of erathostenes
 for i in range(len(UpperCamelCase		)		):
  for j in range(i + 1    ,	len(UpperCamelCase		)		):
   if (begin_list[i] != 0) and (begin_list[j] % begin_list[i] == 0):
    UpperCAmelCase			:      List[Any]			=			0

    # filters actual prime numbers.
 UpperCAmelCase			:      Optional[int]			=			[x for x in begin_list if x != 0]

 # precondition
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		), "'ans' must been from type list"

 return ans

def    _snake_case		(		UpperCamelCase		:	int		):
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		) and (n > 2), "'N' must been an int and > 2"

 UpperCAmelCase			:      Optional[int]			=			[]

 # iterates over all numbers between 2 up to N+1
 # if a number is prime then appends to list 'ans'
 for number in range(2    ,	n + 1		):
  if is_prime(UpperCamelCase		):
   ans.append(UpperCamelCase		)

    # precondition
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		), "'ans' must been from type list"

 return ans

def    _snake_case		(		UpperCamelCase		:	Any		):
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		) and number >= 0, "'number' must been an int and >= 0"

 UpperCAmelCase			:      List[Any]			=			[]  # this list will be returns of the function.

 # potential prime number factors.

 UpperCAmelCase			:      Dict			=			2

 UpperCAmelCase			:      Union[str, Any]			=			number

 if number == 0 or number == 1:
  ans.append(UpperCamelCase		)

 # if 'number' not prime then builds the prime factorization of 'number'
 elif not is_prime(UpperCamelCase		):
  while quotient != 1:
   if is_prime(UpperCamelCase		) and (quotient % factor == 0):
    ans.append(UpperCamelCase		)
    quotient /= factor
   else:
    factor += 1

 else:
  ans.append(UpperCamelCase		)

 # precondition
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		), "'ans' must been from type list"

 return ans

def    _snake_case		(		UpperCamelCase		:	int		):
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		) and (
     number >= 0
 ), "'number' bust been an int and >= 0"

 UpperCAmelCase			:      Tuple			=			0

 # prime factorization of 'number'
 UpperCAmelCase			:      int			=			prime_factorization(UpperCamelCase		)

 UpperCAmelCase			:      Dict			=			max(UpperCamelCase		)

 # precondition
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		), "'ans' must been from type int"

 return ans

def    _snake_case		(		UpperCamelCase		:	Optional[int]		):
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		) and (
     number >= 0
 ), "'number' bust been an int and >= 0"

 UpperCAmelCase			:      Any			=			0

 # prime factorization of 'number'
 UpperCAmelCase			:      Dict			=			prime_factorization(UpperCamelCase		)

 UpperCAmelCase			:      Optional[int]			=			min(UpperCamelCase		)

 # precondition
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		), "'ans' must been from type int"

 return ans

def    _snake_case		(		UpperCamelCase		:	str		):
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		), "'number' must been an int"
 assert isinstance(number % 2 == 0    ,	UpperCamelCase		), "compare bust been from type bool"

 return number % 2 == 0

def    _snake_case		(		UpperCamelCase		:	Optional[Any]		):
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		), "'number' must been an int"
 assert isinstance(number % 2 != 0    ,	UpperCamelCase		), "compare bust been from type bool"

 return number % 2 != 0

def    _snake_case		(		UpperCamelCase		:	Union[str, Any]		):
 assert (
     isinstance(UpperCamelCase    ,	UpperCamelCase		) and (number > 2) and is_even(UpperCamelCase		)
 ), "'number' must been an int, even and > 2"

 UpperCAmelCase			:      Any			=			[]  # this list will returned

 # creates a list of prime numbers between 2 up to 'number'
 UpperCAmelCase			:      Any			=			get_prime_numbers(UpperCamelCase		)
 UpperCAmelCase			:      Union[str, Any]			=			len(UpperCamelCase		)

 # run variable for while-loops.
 UpperCAmelCase			:      int			=			0
 UpperCAmelCase			:      str			=			None

 # exit variable. for break up the loops
 UpperCAmelCase			:      List[str]			=			True

 while i < len_pn and loop:
  UpperCAmelCase			:      Tuple			=			i + 1

  while j < len_pn and loop:
   if prime_numbers[i] + prime_numbers[j] == number:
    UpperCAmelCase			:      Optional[Any]			=			False
    ans.append(prime_numbers[i]		)
    ans.append(prime_numbers[j]		)

   j += 1

  i += 1

 # precondition
 assert (
     isinstance(UpperCamelCase    ,	UpperCamelCase		)
     and (len(UpperCamelCase		) == 2)
     and (ans[0] + ans[1] == number)
     and is_prime(ans[0]		)
     and is_prime(ans[1]		)
 ), "'ans' must contains two primes. And sum of elements must been eq 'number'"

 return ans

def    _snake_case		(		UpperCamelCase		:	List[str]    ,	UpperCamelCase		:	Union[str, Any]		):
 assert (
     isinstance(UpperCamelCase    ,	UpperCamelCase		)
     and isinstance(UpperCamelCase    ,	UpperCamelCase		)
     and (numbera >= 0)
     and (numbera >= 0)
 ), "'number1' and 'number2' must been positive integer."

 UpperCAmelCase			:      Optional[Any]			=			0

 while numbera != 0:
  UpperCAmelCase			:      Dict			=			numbera % numbera
  UpperCAmelCase			:      str			=			numbera
  UpperCAmelCase			:      List[str]			=			rest

 # precondition
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		) and (
     numbera >= 0
 ), "'number' must been from type int and positive"

 return numbera

def    _snake_case		(		UpperCamelCase		:	Optional[Any]    ,	UpperCamelCase		:	Union[str, Any]		):
 assert (
     isinstance(UpperCamelCase    ,	UpperCamelCase		)
     and isinstance(UpperCamelCase    ,	UpperCamelCase		)
     and (numbera >= 1)
     and (numbera >= 1)
 ), "'number1' and 'number2' must been positive integer."

 UpperCAmelCase			:      Union[str, Any]			=			1  # actual answer that will be return.

 # for kgV (x,1)
 if numbera > 1 and numbera > 1:
  # builds the prime factorization of 'number1' and 'number2'
  UpperCAmelCase			:      int			=			prime_factorization(UpperCamelCase		)
  UpperCAmelCase			:      List[Any]			=			prime_factorization(UpperCamelCase		)

 elif numbera == 1 or numbera == 1:
  UpperCAmelCase			:      List[Any]			=			[]
  UpperCAmelCase			:      Any			=			[]
  UpperCAmelCase			:      Optional[int]			=			max(UpperCamelCase    ,	UpperCamelCase		)

 UpperCAmelCase			:      Tuple			=			0
 UpperCAmelCase			:      Union[str, Any]			=			0

 UpperCAmelCase			:      Union[str, Any]			=			[]  # captured numbers int both 'primeFac1' and 'primeFac2'

 # iterates through primeFac1
 for n in prime_fac_a:
  if n not in done:
   if n in prime_fac_a:
    UpperCAmelCase			:      Dict			=			prime_fac_a.count(UpperCamelCase		)
    UpperCAmelCase			:      Dict			=			prime_fac_a.count(UpperCamelCase		)

    for _ in range(max(UpperCamelCase    ,	UpperCamelCase		)		):
     ans *= n

   else:
    UpperCAmelCase			:      Optional[int]			=			prime_fac_a.count(UpperCamelCase		)

    for _ in range(UpperCamelCase		):
     ans *= n

   done.append(UpperCamelCase		)

    # iterates through primeFac2
 for n in prime_fac_a:
  if n not in done:
   UpperCAmelCase			:      Tuple			=			prime_fac_a.count(UpperCamelCase		)

   for _ in range(UpperCamelCase		):
    ans *= n

   done.append(UpperCamelCase		)

    # precondition
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		) and (
     ans >= 0
 ), "'ans' must been from type int and positive"

 return ans

def    _snake_case		(		UpperCamelCase		:	List[str]		):
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		) and (n >= 0), "'number' must been a positive int"

 UpperCAmelCase			:      Any			=			0
 UpperCAmelCase			:      int			=			2  # this variable holds the answer

 while index < n:
  index += 1

  ans += 1  # counts to the next number

  # if ans not prime then
  # runs to the next prime number.
  while not is_prime(UpperCamelCase		):
   ans += 1

    # precondition
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		) and is_prime(
     UpperCamelCase		), "'ans' must been a prime number and from type int"

 return ans

def    _snake_case		(		UpperCamelCase		:	str    ,	UpperCamelCase		:	int		):
 assert (
     is_prime(UpperCamelCase		) and is_prime(UpperCamelCase		) and (p_number_a < p_number_a)
 ), "The arguments must been prime numbers and 'pNumber1' < 'pNumber2'"

 UpperCAmelCase			:      Any			=			p_number_a + 1  # jump to the next number

 UpperCAmelCase			:      Dict			=			[]  # this list will be returns.

 # if number is not prime then
 # fetch the next prime number.
 while not is_prime(UpperCamelCase		):
  number += 1

 while number < p_number_a:
  ans.append(UpperCamelCase		)

  number += 1

  # fetch the next prime number.
  while not is_prime(UpperCamelCase		):
   number += 1

    # precondition
 assert (
     isinstance(UpperCamelCase    ,	UpperCamelCase		)
     and ans[0] != p_number_a
     and ans[len(UpperCamelCase		) - 1] != p_number_a
 ), "'ans' must been a list without the arguments"

 # 'ans' contains not 'pNumber1' and 'pNumber2' !
 return ans

def    _snake_case		(		UpperCamelCase		:	List[str]		):
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		) and (n >= 1), "'n' must been int and >= 1"

 UpperCAmelCase			:      Union[str, Any]			=			[]  # will be returned.

 for divisor in range(1    ,	n + 1		):
  if n % divisor == 0:
   ans.append(UpperCamelCase		)

    # precondition
 assert ans[0] == 1 and ans[len(UpperCamelCase		) - 1] == n, "Error in function getDivisiors(...)"

 return ans

def    _snake_case		(		UpperCamelCase		:	Optional[int]		):
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		) and (
     number > 1
 ), "'number' must been an int and >= 1"

 UpperCAmelCase			:      Tuple			=			get_divisors(UpperCamelCase		)

 # precondition
 assert (
     isinstance(UpperCamelCase    ,	UpperCamelCase		)
     and (divisors[0] == 1)
     and (divisors[len(UpperCamelCase		) - 1] == number)
 ), "Error in help-function getDivisiors(...)"

 # summed all divisors up to 'number' (exclusive), hence [:-1]
 return sum(divisors[:-1]		) == number

def    _snake_case		(		UpperCamelCase		:	List[str]    ,	UpperCamelCase		:	Optional[int]		):
 assert (
     isinstance(UpperCamelCase    ,	UpperCamelCase		)
     and isinstance(UpperCamelCase    ,	UpperCamelCase		)
     and (denominator != 0)
 ), "The arguments must been from type int and 'denominator' != 0"

 # build the greatest common divisor of numerator and denominator.
 UpperCAmelCase			:      Optional[int]			=			gcd(abs(UpperCamelCase		)    ,	abs(UpperCamelCase		)		)

 # precondition
 assert (
     isinstance(UpperCamelCase    ,	UpperCamelCase		)
     and (numerator % gcd_of_fraction == 0)
     and (denominator % gcd_of_fraction == 0)
 ), "Error in function gcd(...,...)"

 return (numerator // gcd_of_fraction, denominator // gcd_of_fraction)

def    _snake_case		(		UpperCamelCase		:	List[str]		):
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		) and (n >= 0), "'n' must been a int and >= 0"

 UpperCAmelCase			:      Dict			=			1  # this will be return.

 for factor in range(1    ,	n + 1		):
  ans *= factor

 return ans

def    _snake_case		(		UpperCamelCase		:	Union[str, Any]		):
 assert isinstance(UpperCamelCase    ,	UpperCamelCase		) and (n >= 0), "'n' must been an int and >= 0"

 UpperCAmelCase			:      List[Any]			=			0
 UpperCAmelCase			:      Any			=			1
 UpperCAmelCase			:      List[Any]			=			1  # this will be return

 for _ in range(n - 1		):
  UpperCAmelCase			:      str			=			ans
  ans += fiba
  UpperCAmelCase			:      Optional[int]			=			tmp

 return ans





"""simple docstring"""
from __future__ import annotations

import random

# Maximum size of the population.  Bigger could be faster but is more memory expensive.
A:     Union[str, Any]										=	2_0_0
# 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.
A:     int										=	5_0
# 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.
A:     Tuple										=	0.4
# Just a seed to improve randomness required by the algorithm.
random.seed(random.randint(0, 1_0_0_0))

def    _snake_case		(		UpperCamelCase		:	str    ,	UpperCamelCase		:	str		):
 UpperCAmelCase			:      Tuple			=			len([g for position, g in enumerate(UpperCamelCase		) if g == main_target[position]]		)
 return (item, float(UpperCamelCase		))

def    _snake_case		(		UpperCamelCase		:	str    ,	UpperCamelCase		:	str		):
 UpperCAmelCase			:      List[str]			=			random.randint(0    ,	len(UpperCamelCase		) - 1		)
 UpperCAmelCase			:      List[str]			=			parent_a[:random_slice] + parent_a[random_slice:]
 UpperCAmelCase			:      List[str]			=			parent_a[:random_slice] + parent_a[random_slice:]
 return (child_a, child_a)

def    _snake_case		(		UpperCamelCase		:	str    ,	UpperCamelCase		:	list[str]		):
 UpperCAmelCase			:      str			=			list(UpperCamelCase		)
 if random.uniform(0    ,	1		) < MUTATION_PROBABILITY:
  UpperCAmelCase			:      int			=			random.choice(UpperCamelCase		)
 return "".join(UpperCamelCase		)

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

  UpperCAmelCase			,	UpperCAmelCase			:      Any			=			crossover(parent_a[0]    ,	UpperCamelCase		)
  # Append new string to the population list.
  pop.append(mutate(UpperCamelCase    ,	UpperCamelCase		)		)
  pop.append(mutate(UpperCamelCase    ,	UpperCamelCase		)		)
 return pop

def    _snake_case		(		UpperCamelCase		:	str    ,	UpperCamelCase		:	list[str]    ,	UpperCamelCase		:	bool = True		):

 # Verify if N_POPULATION is bigger than N_SELECTED
 if N_POPULATION < N_SELECTED:
  UpperCAmelCase			:      Dict			=			F"{N_POPULATION} must be bigger than {N_SELECTED}"
  raise ValueError(UpperCamelCase		)
 # Verify that the target contains no genes besides the ones inside genes variable.
 UpperCAmelCase			:      str			=			sorted({c for c in target if c not in genes}		)
 if not_in_genes_list:
  UpperCAmelCase			:      Optional[Any]			=			F"{not_in_genes_list} is not in genes list, evolution cannot converge"
  raise ValueError(UpperCamelCase		)

 # Generate random starting population.
 UpperCAmelCase			:      Optional[int]			=			[]
 for _ in range(UpperCamelCase		):
  population.append("""""".join([random.choice(UpperCamelCase		) for i in range(len(UpperCamelCase		)		)]		)		)

 # Just some logs to know what the algorithms is doing.
 UpperCAmelCase			,	UpperCAmelCase			:      Any			=			0, 0

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

  # 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.
  UpperCAmelCase			:      str			=			[evaluate(UpperCamelCase    ,	UpperCamelCase		) for item in population]

  # Check if there is a matching evolution.
  UpperCAmelCase			:      Union[str, Any]			=			sorted(UpperCamelCase    ,	key=lambda UpperCamelCase		: x[1]    ,	reverse=UpperCamelCase		)
  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.
  UpperCAmelCase			:      Tuple			=			population[: int(N_POPULATION / 3		)]
  population.clear()
  population.extend(UpperCamelCase		)
  # Normalize population score to be between 0 and 1.
  UpperCAmelCase			:      List[str]			=			[
      (item, score / len(UpperCamelCase		)) for item, score in population_score
  ]

  # This is selection
  for i in range(UpperCamelCase		):
   population.extend(select(population_score[int(UpperCamelCase		)]    ,	UpperCamelCase    ,	UpperCamelCase		)		)
   # 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(UpperCamelCase		) > N_POPULATION:
    break


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