





'''simple docstring'''




import math




class       UpperCamelCase__			:




					"""simple docstring"""


					def __init__(		self							:	Union[str, Any]     ,		lowerCamelCase_							:	int     ,		lowerCamelCase_							:	int     ,		lowerCamelCase_							:	int     ,		lowerCamelCase_							:	Optional[int]		):

							'''simple docstring'''



							SCREAMING_SNAKE_CASE				:							List[str]						=	x
							SCREAMING_SNAKE_CASE				:							Dict						=	y
							SCREAMING_SNAKE_CASE				:							Any						=	step_size
							SCREAMING_SNAKE_CASE				:							Dict						=	function_to_optimize


					def lowerCamelCase_	(		self							:	Optional[int]		):

							'''simple docstring'''



							return self.function(self.x     ,		self.y		)


					def lowerCamelCase_	(		self							:	Optional[int]		):

							'''simple docstring'''



							SCREAMING_SNAKE_CASE				:							Union[str, Any]						=	self.step_size
							return [
							    SearchProblem(lowerCamelCase_     ,		lowerCamelCase_     ,		lowerCamelCase_     ,		self.function		)
							    for x, y in (
							        (self.x - step_size, self.y - step_size),
							        (self.x - step_size, self.y),
							        (self.x - step_size, self.y + step_size),
							        (self.x, self.y - step_size),
							        (self.x, self.y + step_size),
							        (self.x + step_size, self.y - step_size),
							        (self.x + step_size, self.y),
							        (self.x + step_size, self.y + step_size),
							    )
							]


					def __hash__(		self							:	Optional[int]		):

							'''simple docstring'''



							return hash(str(self		)		)


					def __eq__(		self							:	List[Any]     ,		lowerCamelCase_							:	str		):

							'''simple docstring'''



							if isinstance(lowerCamelCase_     ,		lowerCamelCase_		):
									return hash(str(self		)		) == hash(str(lowerCamelCase_		)		)
							return False



					def __str__(		self							:	List[Any]		):

							'''simple docstring'''



							return f'''x: {self.x} y: {self.y}'''







def 						__A						(       lowerCamelCase_	,	lowerCamelCase_ = True	,	lowerCamelCase_ = math.inf	,	lowerCamelCase_ = -math.inf	,	lowerCamelCase_ = math.inf	,	lowerCamelCase_ = -math.inf	,	lowerCamelCase_ = False	,	lowerCamelCase_ = 1_00_00	,	):


		"""simple docstring"""



		SCREAMING_SNAKE_CASE				:							int						=	search_prob
		SCREAMING_SNAKE_CASE				:							Any						=	[]  # list to store the current score at each iteration
		SCREAMING_SNAKE_CASE				:							int						=	0
		SCREAMING_SNAKE_CASE				:							str						=	False
		SCREAMING_SNAKE_CASE				:							int						=	set()
		while not solution_found and iterations < max_iter:
				visited.add(lowerCamelCase_					)
				iterations += 1
				SCREAMING_SNAKE_CASE				:							int						=	current_state.score()
				scores.append(lowerCamelCase_					)
				SCREAMING_SNAKE_CASE				:							str						=	current_state.get_neighbors()
				SCREAMING_SNAKE_CASE				:							Optional[Any]						=	-math.inf
				SCREAMING_SNAKE_CASE				:							Any						=	math.inf
				SCREAMING_SNAKE_CASE				:							Optional[int]						=	None  # to hold the next best neighbor
				for neighbor in neighbors:
						if neighbor in visited:
								continue  # do not want to visit the same state again
						if (
						    neighbor.x > max_x
						    or neighbor.x < min_x
						    or neighbor.y > max_y
						    or neighbor.y < min_y
						):
								continue  # neighbor outside our bounds
						SCREAMING_SNAKE_CASE				:							Any						=	neighbor.score() - current_score
						if find_max:  # finding max
								# going to direction with greatest ascent
								if change > max_change and change > 0:
										SCREAMING_SNAKE_CASE				:							Tuple						=	change
										SCREAMING_SNAKE_CASE				:							List[Any]						=	neighbor
						else:  # finding min
								# to direction with greatest descent
								if change < min_change and change < 0:
										SCREAMING_SNAKE_CASE				:							Optional[int]						=	change
										SCREAMING_SNAKE_CASE				:							Dict						=	neighbor
				if next_state is not None:
						# we found at least one neighbor which improved the current state
						SCREAMING_SNAKE_CASE				:							int						=	next_state
				else:
						# since we have no neighbor that improves the solution we stop the search
						SCREAMING_SNAKE_CASE				:							List[str]						=	True

		if visualization:
				from matplotlib import pyplot as plt

				plt.plot(range(lowerCamelCase_					)	,	lowerCamelCase_					)
				plt.xlabel("""Iterations"""					)
				plt.ylabel("""Function values"""					)
				plt.show()

		return current_state


if __name__ == "__main__":
							import doctest

							doctest.testmod()



							def 						__A						(       lowerCamelCase_	,	lowerCamelCase_					):


									"""simple docstring"""



									return (x**2) + (y**2)

							# starting the problem with initial coordinates (3, 4)
							__UpperCAmelCase         =   SearchProblem(x=3, y=4, step_size=1, function_to_optimize=test_fa)
							__UpperCAmelCase         =   hill_climbing(prob, find_max=False)
							print(
							    """The minimum score for f(x, y) = x^2 + y^2 found via hill climbing: """
							    f'''{local_min.score()}'''
							)

							# starting the problem with initial coordinates (12, 47)
							__UpperCAmelCase         =   SearchProblem(x=12, y=47, step_size=1, function_to_optimize=test_fa)
							__UpperCAmelCase         =   hill_climbing(
							    prob, find_max=False, max_x=100, min_x=5, max_y=50, min_y=-5, visualization=True
							)
							print(
							    """The minimum score for f(x, y) = x^2 + y^2 with the domain 100 > x > 5 """
							    f'''and 50 > y > - 5 found via hill climbing: {local_min.score()}'''
							)



							def 						__A						(       lowerCamelCase_	,	lowerCamelCase_					):


									"""simple docstring"""



									return (3 * x**2) - (6 * y)

							__UpperCAmelCase         =   SearchProblem(x=3, y=4, step_size=1, function_to_optimize=test_fa)
							__UpperCAmelCase         =   hill_climbing(prob, find_max=True)


							print(
							    """The maximum score for f(x, y) = x^2 + y^2 found via hill climbing: """
							    f'''{local_min.score()}'''
							)










'''simple docstring'''




from __future__ import annotations

from collections import Counter



def 						__A						(       lowerCamelCase_					):


		"""simple docstring"""



		SCREAMING_SNAKE_CASE				:							int						=	[True] * n
		SCREAMING_SNAKE_CASE				:							Optional[Any]						=	False
		SCREAMING_SNAKE_CASE				:							Optional[Any]						=	False
		SCREAMING_SNAKE_CASE				:							Optional[int]						=	True

		for i in range(3	,	int(n**0.5 + 1					)	,	2					):
				SCREAMING_SNAKE_CASE				:							List[Any]						=	i * 2
				while index < n:
						SCREAMING_SNAKE_CASE				:							Union[str, Any]						=	False
						SCREAMING_SNAKE_CASE				:							Optional[Any]						=	index + i

		SCREAMING_SNAKE_CASE				:							Dict						=	[2]

		for i in range(3	,	lowerCamelCase_	,	2					):
				if is_prime[i]:
						primes.append(lowerCamelCase_					)

		return primes



def 						__A						(       lowerCamelCase_					):


		"""simple docstring"""



		SCREAMING_SNAKE_CASE				:							List[str]						=	str(lowerCamelCase_					)
		SCREAMING_SNAKE_CASE				:							List[str]						=	[]
		SCREAMING_SNAKE_CASE				:							Optional[int]						=	["""0""", """1""", """2""", """3""", """4""", """5""", """6""", """7""", """8""", """9"""]

		for duplicate in Counter(lowerCamelCase_					) - Counter(set(lowerCamelCase_					)					):
				SCREAMING_SNAKE_CASE				:							Tuple						=	[int(number_str.replace(lowerCamelCase_	,	lowerCamelCase_					)					) for digit in digits]
				replacements.append(lowerCamelCase_					)

		return replacements



def 						__A						(       lowerCamelCase_ = 8					):


		"""simple docstring"""



		SCREAMING_SNAKE_CASE				:							Tuple						=	set()

		# Filter primes with less than 3 replaceable digits
		SCREAMING_SNAKE_CASE				:							Union[str, Any]						=	{
		    x for x in set(prime_sieve(1_00_00_00					)					) if len(str(lowerCamelCase_					)					) - len(set(str(lowerCamelCase_					)					)					) >= 3
		}

		for prime in primes:
				if prime in numbers_checked:
						continue

				SCREAMING_SNAKE_CASE				:							int						=	digit_replacements(lowerCamelCase_					)

				for family in replacements:
						numbers_checked.update(lowerCamelCase_					)
						SCREAMING_SNAKE_CASE				:							Dict						=	primes.intersection(lowerCamelCase_					)

						if len(lowerCamelCase_					) != family_length:
								continue

						return min(lowerCamelCase_					)

		return -1


if __name__ == "__main__":
							print(solution())



