


from __future__ import annotations

import random

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

def 						_UpperCAmelCase				(			SCREAMING_SNAKE_CASE__			:					str			,     SCREAMING_SNAKE_CASE__			:					str				):
     __UpperCamelCase    							=len([g for position, g in enumerate(SCREAMING_SNAKE_CASE__				) if g == main_target[position]]				)
     return (item, float(SCREAMING_SNAKE_CASE__				))

def 						_UpperCAmelCase				(			SCREAMING_SNAKE_CASE__			:					str			,     SCREAMING_SNAKE_CASE__			:					str				):
     __UpperCamelCase    							=random.randint(0			,     len(SCREAMING_SNAKE_CASE__				) - 1				)
     __UpperCamelCase    							=parent_a[:random_slice] + parent_a[random_slice:]
     __UpperCamelCase    							=parent_a[:random_slice] + parent_a[random_slice:]
     return (child_a, child_a)

def 						_UpperCAmelCase				(			SCREAMING_SNAKE_CASE__			:					str			,     SCREAMING_SNAKE_CASE__			:					list[str]				):
     __UpperCamelCase    							=list(SCREAMING_SNAKE_CASE__				)
     if random.uniform(0			,     1				) < MUTATION_PROBABILITY:
          __UpperCamelCase    							=random.choice(SCREAMING_SNAKE_CASE__				)
     return "".join(SCREAMING_SNAKE_CASE__				)

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

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

def 						_UpperCAmelCase				(			SCREAMING_SNAKE_CASE__			:					str			,     SCREAMING_SNAKE_CASE__			:					list[str]			,     SCREAMING_SNAKE_CASE__			:					bool = True				):

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

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

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

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

          # 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    							=[evaluate(SCREAMING_SNAKE_CASE__			,     SCREAMING_SNAKE_CASE__				) for item in population]

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

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


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









_A		       =						{0: [2, 3], 1: [0], 2: [1], 3: [4], 4: []}

_A		       =						{0: [1, 2, 3], 1: [2], 2: [0], 3: [4], 4: [5], 5: [3]}

def 						_UpperCAmelCase				(			SCREAMING_SNAKE_CASE__			:					dict[int, list[int]]			,     SCREAMING_SNAKE_CASE__			:					int			,     SCREAMING_SNAKE_CASE__			:					list[bool]				):
     __UpperCamelCase    							=True
     __UpperCamelCase    							=[]

     for neighbour in graph[vert]:
          if not visited[neighbour]:
               order += topology_sort(SCREAMING_SNAKE_CASE__			,     SCREAMING_SNAKE_CASE__			,     SCREAMING_SNAKE_CASE__				)

     order.append(SCREAMING_SNAKE_CASE__				)

     return order

def 						_UpperCAmelCase				(			SCREAMING_SNAKE_CASE__			:					dict[int, list[int]]			,     SCREAMING_SNAKE_CASE__			:					int			,     SCREAMING_SNAKE_CASE__			:					list[bool]				):
     __UpperCamelCase    							=True
     __UpperCamelCase    							=[vert]

     for neighbour in reversed_graph[vert]:
          if not visited[neighbour]:
               component += find_components(SCREAMING_SNAKE_CASE__			,     SCREAMING_SNAKE_CASE__			,     SCREAMING_SNAKE_CASE__				)

     return component





def 						_UpperCAmelCase				(			SCREAMING_SNAKE_CASE__			:					dict[int, list[int]]				):
     __UpperCamelCase    							=len(SCREAMING_SNAKE_CASE__				) * [False]
     __UpperCamelCase    							={vert: [] for vert in range(len(SCREAMING_SNAKE_CASE__				)				)}

     for vert, neighbours in graph.items():
          for neighbour in neighbours:
               reversed_graph[neighbour].append(SCREAMING_SNAKE_CASE__				)

     __UpperCamelCase    							=[]
     for i, was_visited in enumerate(SCREAMING_SNAKE_CASE__				):
          if not was_visited:
               order += topology_sort(SCREAMING_SNAKE_CASE__			,     SCREAMING_SNAKE_CASE__			,     SCREAMING_SNAKE_CASE__				)

     __UpperCamelCase    							=[]
     __UpperCamelCase    							=len(SCREAMING_SNAKE_CASE__				) * [False]

     for i in range(len(SCREAMING_SNAKE_CASE__				)				):
          __UpperCamelCase    							=order[len(SCREAMING_SNAKE_CASE__				) - i - 1]
          if not visited[vert]:
               __UpperCamelCase    							=find_components(SCREAMING_SNAKE_CASE__			,     SCREAMING_SNAKE_CASE__			,     SCREAMING_SNAKE_CASE__				)
               components_list.append(SCREAMING_SNAKE_CASE__				)

     return components_list





