


from multiprocessing import Lock, Pipe, Process

# lock used to ensure that two processes do not access a pipe at the same time
__lowerCamelCase        =     Lock()



def  _a			(						__UpperCamelCase  ,  __UpperCamelCase  ,  __UpperCamelCase  ,  __UpperCamelCase  ,  __UpperCamelCase  ,  __UpperCamelCase  ,  __UpperCamelCase ):
     global process_lock

     # we perform n swaps since after n swaps we know we are sorted
     # we *could* stop early if we are sorted already, but it takes as long to
     # find out we are sorted as it does to sort the list with this algorithm
     for i in range(0  ,  1_0 ):
          if (i + position) % 2 == 0 and r_send is not None:
               # send your value to your right neighbor
               process_lock.acquire()
               r_send[1].send(__UpperCamelCase )
               process_lock.release()

               # receive your right neighbor's value
               process_lock.acquire()
               a_    :     int										=    rr_cv[0].recv()
               process_lock.release()

               # take the lower value since you are on the left
               a_    :     int										=    min(__UpperCamelCase  ,  __UpperCamelCase )
          elif (i + position) % 2 != 0 and l_send is not None:
               # send your value to your left neighbor
               process_lock.acquire()
               l_send[1].send(__UpperCamelCase )
               process_lock.release()

               # receive your left neighbor's value
               process_lock.acquire()
               a_    :     Union[str, Any]										=    lr_cv[0].recv()
               process_lock.release()

               # take the higher value since you are on the right
               a_    :     int										=    max(__UpperCamelCase  ,  __UpperCamelCase )
    # after all swaps are performed, send the values back to main
     result_pipe[1].send(__UpperCamelCase )



def  _a			(						__UpperCamelCase ):
     a_    :     int										=    []
     a_    :     List[Any]										=    []
     # initialize the list of pipes where the values will be retrieved
     for _ in arr:
          result_pipe.append(Pipe() )
     # creates the processes
     # the first and last process only have one neighbor so they are made outside
     # of the loop
     a_    :     Dict										=    Pipe()
     a_    :     Optional[int]										=    Pipe()
     process_array_.append(
         Process(
             target=__UpperCamelCase  ,  args=(0, arr[0], None, temp_rs, None, temp_rr, result_pipe[0])  ,  ) )
     a_    :     Union[str, Any]										=    temp_rs
     a_    :     Optional[int]										=    temp_rr

     for i in range(1  ,  len(__UpperCamelCase ) - 1 ):
          a_    :     List[Any]										=    Pipe()
          a_    :     Union[str, Any]										=    Pipe()
          process_array_.append(
              Process(
                  target=__UpperCamelCase  ,  args=(i, arr[i], temp_ls, temp_rs, temp_lr, temp_rr, result_pipe[i])  ,  ) )
          a_    :     List[Any]										=    temp_rs
          a_    :     Optional[int]										=    temp_rr

     process_array_.append(
         Process(
             target=__UpperCamelCase  ,  args=(
                 len(__UpperCamelCase ) - 1,
                 arr[len(__UpperCamelCase ) - 1],
                 temp_ls,
                 None,
                 temp_lr,
                 None,
                 result_pipe[len(__UpperCamelCase ) - 1],
             )  ,  ) )

     # start the processes
     for p in process_array_:
          p.start()

     # wait for the processes to end and write their values to the list
     for p in range(0  ,  len(__UpperCamelCase ) ):
          a_    :     Dict										=    result_pipe[p][0].recv()
          process_array_[p].join()
     return arr



def  _a			(						):
     a_    :     Any										=    list(range(1_0  ,  0  ,  -1 ) )
     print("""Initial List""" )
     print(*__UpperCamelCase )
     a_    :     Tuple										=    odd_even_transposition(__UpperCamelCase )
     print("""Sorted List\n""" )
     print(*__UpperCamelCase )


if __name__ == "__main__":
  main()







from __future__ import annotations

import random

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



def  _a			(						__UpperCamelCase  ,  __UpperCamelCase ):
     a_    :     List[Any]										=    len([g for position, g in enumerate(__UpperCamelCase ) if g == main_target[position]] )
     return (item, float(__UpperCamelCase ))



def  _a			(						__UpperCamelCase  ,  __UpperCamelCase ):
     a_    :     List[Any]										=    random.randint(0  ,  len(__UpperCamelCase ) - 1 )
     a_    :     Tuple										=    parent_a[:random_slice] + parent_a[random_slice:]
     a_    :     Optional[Any]										=    parent_a[:random_slice] + parent_a[random_slice:]
     return (child_a, child_a)



def  _a			(						__UpperCamelCase  ,  __UpperCamelCase ):
     a_    :     Optional[int]										=    list(__UpperCamelCase )
     if random.uniform(0  ,  1 ) < MUTATION_PROBABILITY:
          a_    :     int										=    random.choice(__UpperCamelCase )
     return "".join(__UpperCamelCase )



def  _a			(						__UpperCamelCase  ,  __UpperCamelCase  ,  __UpperCamelCase  ,  ):
     a_    :     Tuple										=    []
     # Generate more children proportionally to the fitness score.
     a_    :     Any										=    int(parent_a[1] * 1_0_0 ) + 1
     a_    :     int										=    1_0 if child_n >= 1_0 else child_n
     for _ in range(__UpperCamelCase ):
          a_    :     Tuple										=    population_score[random.randint(0  ,  __UpperCamelCase )][0]

          a_			,			a_    :     List[str]										=    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  _a			(						__UpperCamelCase  ,  __UpperCamelCase  ,  __UpperCamelCase = True ):

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

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

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



