




'''simple docstring'''


from __future__ import annotations

import random

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





							'''simple docstring'''


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





							'''simple docstring'''


							_a     					=    random.randint(0			,						len(UpperCamelCase				) - 1				)
							_a     					=    parent_a[:random_slice] + parent_a[random_slice:]
							_a     					=    parent_a[:random_slice] + parent_a[random_slice:]
							return (child_a, child_a)
def 		snake_case_   (UpperCamelCase	:  str			,						UpperCamelCase	:  list[str]				):





							'''simple docstring'''


							_a     					=    list(UpperCamelCase				)
							if random.uniform(0			,						1				) < MUTATION_PROBABILITY:
														_a     					=    random.choice(UpperCamelCase				)
							return "".join(UpperCamelCase				)
def 		snake_case_   (UpperCamelCase	:  tuple[str, float]			,						UpperCamelCase	:  list[tuple[str, float]]			,						UpperCamelCase	:  list[str]			,						):





							'''simple docstring'''


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

														_a					,							_a     					=    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				):





							'''simple docstring'''


							if N_POPULATION < N_SELECTED:
														_a     					=    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     					=    sorted({c for c in target if c not in genes}				)
							if not_in_genes_list:
														_a     					=    f'{not_in_genes_list} is not in genes list, evolution cannot converge'
														raise ValueError(UpperCamelCase				)

							# Generate random starting population.
							_a     					=    []
							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     					=    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     					=    [evaluate(UpperCamelCase			,						UpperCamelCase				) for item in population]

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







'''simple docstring'''


def 		snake_case_   (UpperCamelCase	:  str			,						UpperCamelCase	:  Any				):





							'''simple docstring'''


							return (pointa[0] - pointa[0]) ** 2 + (pointa[1] - pointa[1]) ** 2
def 		snake_case_   (UpperCamelCase	:  Any			,						UpperCamelCase	:  str=0				):





							'''simple docstring'''


							return sorted(UpperCamelCase			,						key=lambda UpperCamelCase				: x[column]				)
def 		snake_case_   (UpperCamelCase	:  Optional[int]			,						UpperCamelCase	:  Any			,						UpperCamelCase	:  Union[str, Any]=float('''inf'''				)				):





							'''simple docstring'''


							for i in range(points_counts - 1				):
														for j in range(i + 1			,						UpperCamelCase				):
																					_a     					=    euclidean_distance_sqr(points[i]			,						points[j]				)
																					if current_dis < min_dis:
																												_a     					=    current_dis
							return min_dis
def 		snake_case_   (UpperCamelCase	:  int			,						UpperCamelCase	:  Tuple			,						UpperCamelCase	:  List[str]=float('''inf'''				)				):





							'''simple docstring'''


							for i in range(min(6			,						points_counts - 1				)			,						UpperCamelCase				):
														for j in range(max(0			,						i - 6				)			,						UpperCamelCase				):
																					_a     					=    euclidean_distance_sqr(points[i]			,						points[j]				)
																					if current_dis < min_dis:
																												_a     					=    current_dis
							return min_dis
def 		snake_case_   (UpperCamelCase	:  int			,						UpperCamelCase	:  List[Any]			,						UpperCamelCase	:  int				):





							'''simple docstring'''


							if points_counts <= 3:
														return dis_between_closest_pair(UpperCamelCase			,						UpperCamelCase				)

							# recursion
							_a     					=    points_counts // 2
							_a     					=    closest_pair_of_points_sqr(
							    UpperCamelCase			,						points_sorted_on_y[:mid]			,						UpperCamelCase				)
							_a     					=    closest_pair_of_points_sqr(
							    UpperCamelCase			,						points_sorted_on_y[mid:]			,						points_counts - mid				)
							_a     					=    min(UpperCamelCase			,						UpperCamelCase				)
							_a     					=    []
							for point in points_sorted_on_x:
														if abs(point[0] - points_sorted_on_x[mid][0]				) < closest_pair_dis:
																					cross_strip.append(UpperCamelCase				)

							_a     					=    dis_between_closest_in_strip(
							    UpperCamelCase			,						len(UpperCamelCase				)			,						UpperCamelCase				)
							return min(UpperCamelCase			,						UpperCamelCase				)
def 		snake_case_   (UpperCamelCase	:  Optional[int]			,						UpperCamelCase	:  List[str]				):





							'''simple docstring'''


							_a     					=    column_based_sort(UpperCamelCase			,						column=0				)
							_a     					=    column_based_sort(UpperCamelCase			,						column=1				)
							return (
							    closest_pair_of_points_sqr(
							        UpperCamelCase			,						UpperCamelCase			,						UpperCamelCase				)
							) ** 0.5


if __name__ == "__main__":
				_snake_case				:				int       							=		[(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
				print('Distance:', closest_pair_of_points(points, len(points)))

