
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  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     )				->		tuple[str, float]:
			lowerCAmelCase__      :      str         =		len([g for position, g in enumerate(SCREAMING_SNAKE_CASE_     ) if g == main_target[position]]     )
			return (item, float(SCREAMING_SNAKE_CASE_     ))
def  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     )				->		tuple[str, str]:
			lowerCAmelCase__      :      int         =		random.randint(0       ,							len(SCREAMING_SNAKE_CASE_     ) - 1     )
			lowerCAmelCase__      :      Any         =		parent_a[:random_slice] + parent_a[random_slice:]
			lowerCAmelCase__      :      List[str]         =		parent_a[:random_slice] + parent_a[random_slice:]
			return (child_a, child_a)
def  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     )				->		str:
			lowerCAmelCase__      :      int         =		list(SCREAMING_SNAKE_CASE_     )
			if random.uniform(0       ,							1     ) < MUTATION_PROBABILITY:
						lowerCAmelCase__      :      Dict         =		random.choice(SCREAMING_SNAKE_CASE_     )
			return "".join(SCREAMING_SNAKE_CASE_     )
def  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							)				->		list[str]:
			lowerCAmelCase__      :      Union[str, Any]         =		[]
			# Generate more children proportionally to the fitness score.
			lowerCAmelCase__      :      Tuple         =		int(parent_a[1] * 100     ) + 1
			lowerCAmelCase__      :      Dict         =		10 if child_n >= 10 else child_n
			for _ in range(SCREAMING_SNAKE_CASE_     ):
						lowerCAmelCase__      :      Tuple         =		population_score[random.randint(0       ,							SCREAMING_SNAKE_CASE_     )][0]

						lowerCAmelCase__      ,				lowerCAmelCase__      :      Any         =		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  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_ = True     )				->		tuple[int, int, str]:

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

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

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

from __future__ import annotations

lowerCamelCase__          =		list[list[int]]

# assigning initial values to the grid
lowerCamelCase__          =		[
    [3, 0, 6, 5, 0, 8, 4, 0, 0],
    [5, 2, 0, 0, 0, 0, 0, 0, 0],
    [0, 8, 7, 0, 0, 0, 0, 3, 1],
    [0, 0, 3, 0, 1, 0, 0, 8, 0],
    [9, 0, 0, 8, 6, 3, 0, 0, 5],
    [0, 5, 0, 0, 9, 0, 6, 0, 0],
    [1, 3, 0, 0, 0, 0, 2, 5, 0],
    [0, 0, 0, 0, 0, 0, 0, 7, 4],
    [0, 0, 5, 2, 0, 6, 3, 0, 0],
]

# a grid with no solution
lowerCamelCase__          =		[
    [5, 0, 6, 5, 0, 8, 4, 0, 3],
    [5, 2, 0, 0, 0, 0, 0, 0, 2],
    [1, 8, 7, 0, 0, 0, 0, 3, 1],
    [0, 0, 3, 0, 1, 0, 0, 8, 0],
    [9, 0, 0, 8, 6, 3, 0, 0, 5],
    [0, 5, 0, 0, 9, 0, 6, 0, 0],
    [1, 3, 0, 0, 0, 0, 2, 5, 0],
    [0, 0, 0, 0, 0, 0, 0, 7, 4],
    [0, 0, 5, 2, 0, 6, 3, 0, 0],
]
def  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     )				->		bool:
			for i in range(9     ):
						if grid[row][i] == n or grid[i][column] == n:
									return False

			for i in range(3     ):
						for j in range(3     ):
									if grid[(row - row % 3) + i][(column - column % 3) + j] == n:
												return False

			return True
def  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_     )				->		tuple[int, int] | None:
			for i in range(9     ):
						for j in range(9     ):
									if grid[i][j] == 0:
												return i, j
			return None
def  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_     )				->		Matrix | None:
			if location := find_empty_location(SCREAMING_SNAKE_CASE_     ):
						lowerCAmelCase__      ,				lowerCAmelCase__      :      Any         =		location
			else:
						# If the location is ``None``, then the grid is solved.
						return grid

			for digit in range(1       ,							10     ):
						if is_safe(SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     ):
									lowerCAmelCase__      :      Optional[Any]         =		digit

									if sudoku(SCREAMING_SNAKE_CASE_     ) is not None:
												return grid

									lowerCAmelCase__      :      List[Any]         =		0

			return None
def  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_     )				->		None:
			for row in grid:
						for cell in row:
									print(SCREAMING_SNAKE_CASE_       ,							end=' '     )
						print()


if __name__ == "__main__":
					# make a copy of grid so that you can compare with the unmodified grid
					for example_grid in (initial_grid, no_solution):
										print("""\nExample grid:\n""" + """=""" * 20)
										print_solution(example_grid)
										print("""\nExample grid solution:""")
										lowerCamelCase__          =		sudoku(example_grid)
										if solution is not None:
															print_solution(solution)
										else:
															print("""Cannot find a solution.""")