



'''simple docstring'''





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        _SCREAMING_SNAKE_CASE  (	UpperCamelCase							,   UpperCamelCase      ):



    """simple docstring"""





    lowerCAmelCase__			:  List[Any]											= len([g for position, g in enumerate(__lowerCAmelCase      ) if g == main_target[position]]      )
    return (item, float(__lowerCAmelCase      ))
def        _SCREAMING_SNAKE_CASE  (	UpperCamelCase							,   UpperCamelCase      ):



    """simple docstring"""





    lowerCAmelCase__			:  Tuple											= random.randint(0							,   len(__lowerCAmelCase      ) - 1      )
    lowerCAmelCase__			:  Optional[Any]											= parent_a[:random_slice] + parent_a[random_slice:]
    lowerCAmelCase__			:  Any											= parent_a[:random_slice] + parent_a[random_slice:]
    return (child_a, child_a)
def        _SCREAMING_SNAKE_CASE  (	UpperCamelCase							,   UpperCamelCase      ):



    """simple docstring"""





    lowerCAmelCase__			:  Dict											= list(__lowerCAmelCase      )
    if random.uniform(0							,   1      ) < MUTATION_PROBABILITY:
        lowerCAmelCase__			:  List[str]											= random.choice(__lowerCAmelCase      )
    return "".join(__lowerCAmelCase      )
def        _SCREAMING_SNAKE_CASE  (	UpperCamelCase							,   UpperCamelCase							,   UpperCamelCase							,   ):



    """simple docstring"""





    lowerCAmelCase__			:  Dict											= []
    # Generate more children proportionally to the fitness score.
    lowerCAmelCase__			:  List[str]											= int(parent_a[1] * 100      ) + 1
    lowerCAmelCase__			:  Optional[int]											= 10 if child_n >= 10 else child_n
    for _ in range(__lowerCAmelCase      ):
        lowerCAmelCase__			:  List[str]											= population_score[random.randint(0							,   __lowerCAmelCase      )][0]

        lowerCAmelCase__			:  Union[str, 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  (	UpperCamelCase							,   UpperCamelCase							,   UpperCamelCase = True      ):



    """simple docstring"""





    if N_POPULATION < N_SELECTED:
        lowerCAmelCase__			:  List[str]											= 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__			:  List[Any]											= sorted({c for c in target if c not in genes}      )
    if not_in_genes_list:
        lowerCAmelCase__			:  List[str]											= f"""{not_in_genes_list} is not in genes list, evolution cannot converge"""
        raise ValueError(__lowerCAmelCase      )

    # Generate random starting population.
    lowerCAmelCase__			:  Tuple											= []
    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__			:  Union[str, Any]											= 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__			:  str											= [evaluate(__lowerCAmelCase							,   __lowerCAmelCase      ) for item in population]

        # Check if there is a matching evolution.
        lowerCAmelCase__			:  str											= sorted(__lowerCAmelCase							,   key=lambda UpperCamelCase      : 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__			:  Optional[Any]											= population[: int(N_POPULATION / 3      )]
        population.clear()
        population.extend(__lowerCAmelCase      )
        # Normalize population score to be between 0 and 1.
        lowerCAmelCase__			:  Dict											= [
            (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__":
 _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}"""
 )







'''simple docstring'''





def        _SCREAMING_SNAKE_CASE  (	UpperCamelCase      ):



    """simple docstring"""





    if any(not isinstance(UpperCamelCase							,   UpperCamelCase      ) or x < 0 for x in sequence      ):
        raise TypeError("""Sequence must be list of non-negative integers"""      )
    for _ in range(len(UpperCamelCase      )      ):
        for i, (rod_upper, rod_lower) in enumerate(zip(UpperCamelCase							,   sequence[1:]      )      ):
            if rod_upper > rod_lower:
                sequence[i] -= rod_upper - rod_lower
                sequence[i + 1] += rod_upper - rod_lower
    return sequence


if __name__ == "__main__":
 assert bead_sort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]
 assert bead_sort([7, 9, 4, 3, 5]) == [3, 4, 5, 7, 9]


