




"""simple docstring"""

import math

class 							lowercase   :







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



					"""simple docstring"""

					A_	:					Any						 =		x
					A_	:					Dict						 =		y
					A_	:					Optional[int]						 =		step_size
					A_	:					int						 =		function_to_optimize







				def        a_	(				self :       Optional[int]							):



					"""simple docstring"""

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







				def        a_	(				self :       List[Any]							):



					"""simple docstring"""

					A_	:					Tuple						 =		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 :       int							):



					"""simple docstring"""

					return hash(str(self							)							)







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



					"""simple docstring"""

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







				def __str__(				self :       Union[str, Any]							):



					"""simple docstring"""

					return F"""x: {self.x} y: {self.y}"""

def 		lowercase_   (		_UpperCAmelCase	,   _UpperCAmelCase = True	,   _UpperCAmelCase = math.inf	,   _UpperCAmelCase = -math.inf	,   _UpperCAmelCase = math.inf	,   _UpperCAmelCase = -math.inf	,   _UpperCAmelCase = False	,   _UpperCAmelCase = 1_0000	,   ):




	"""simple docstring"""






	A_	:					List[str]						 =		search_prob
	A_	:					List[str]						 =		[]  # list to store the current score at each iteration
	A_	:					List[Any]						 =		0
	A_	:					str						 =		False
	A_	:					Union[str, Any]						 =		set()
	while not solution_found and iterations < max_iter:
		visited.add(_UpperCAmelCase						)
		iterations += 1
		A_	:					Dict						 =		current_state.score()
		scores.append(_UpperCAmelCase						)
		A_	:					Dict						 =		current_state.get_neighbors()
		A_	:					int						 =		-math.inf
		A_	:					List[str]						 =		math.inf
		A_	:					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
			A_	:					Any						 =		neighbor.score() - current_score
			if find_max:  # finding max
				# going to direction with greatest ascent
				if change > max_change and change > 0:
					A_	:					int						 =		change
					A_	:					str						 =		neighbor
			else:  # finding min
				# to direction with greatest descent
				if change < min_change and change < 0:
					A_	:					Union[str, Any]						 =		change
					A_	:					Dict						 =		neighbor
		if next_state is not None:
			# we found at least one neighbor which improved the current state
			A_	:					int						 =		next_state
		else:
			# since we have no neighbor that improves the solution we stop the search
			A_	:					Dict						 =		True

	if visualization:
		from matplotlib import pyplot as plt

		plt.plot(range(_UpperCAmelCase						)	,   _UpperCAmelCase						)
		plt.xlabel('''Iterations'''						)
		plt.ylabel('''Function values'''						)
		plt.show()

	return current_state


if __name__ == "__main__":
		import doctest

		doctest.testmod()

		def 		lowercase_   (		_UpperCAmelCase	,   _UpperCAmelCase						):




			"""simple docstring"""






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

		# starting the problem with initial coordinates (3, 4)
		_lowerCamelCase	:      List[Any]   =							SearchProblem(x=3, y=4, step_size=1, function_to_optimize=test_fa)
		_lowerCamelCase	:      List[str]   =							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)
		_lowerCamelCase	:      Tuple   =							SearchProblem(x=12, y=47, step_size=1, function_to_optimize=test_fa)
		_lowerCamelCase	:      Tuple   =							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 		lowercase_   (		_UpperCAmelCase	,   _UpperCAmelCase						):




			"""simple docstring"""






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

		_lowerCamelCase	:      Tuple   =							SearchProblem(x=3, y=4, step_size=1, function_to_optimize=test_fa)
		_lowerCamelCase	:      Any   =							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

def 		lowercase_   (		_UpperCAmelCase	,   _UpperCAmelCase	,   _UpperCAmelCase						):




	"""simple docstring"""






	assert (
	    c % greatest_common_divisor(_UpperCAmelCase	,   _UpperCAmelCase						) == 0
	)  # greatest_common_divisor(a,b) function implemented below
	((A_) ,			(A_) ,			(A_))	:					List[Any]						 =		extended_gcd(_UpperCAmelCase	,   _UpperCAmelCase						)  # extended_gcd(a,b) function implemented below
	A_	:					int						 =		c / d
	return (r * x, r * y)

def 		lowercase_   (		_UpperCAmelCase	,   _UpperCAmelCase	,   _UpperCAmelCase	,   _UpperCAmelCase = 2						):




	"""simple docstring"""






	((A_) ,			(A_))	:					Any						 =		diophantine(_UpperCAmelCase	,   _UpperCAmelCase	,   _UpperCAmelCase						)  # Initial value
	A_	:					Union[str, Any]						 =		greatest_common_divisor(_UpperCAmelCase	,   _UpperCAmelCase						)
	A_	:					List[str]						 =		a // d
	A_	:					str						 =		b // d

	for i in range(_UpperCAmelCase						):
		A_	:					int						 =		xa + i * q
		A_	:					str						 =		ya - i * p
		print(_UpperCAmelCase	,   _UpperCAmelCase						)

def 		lowercase_   (		_UpperCAmelCase	,   _UpperCAmelCase						):




	"""simple docstring"""






	if a < b:
		A_ ,			A_	:					Tuple						 =		b, a

	while a % b != 0:
		A_ ,			A_	:					int						 =		b, a % b

	return b

def 		lowercase_   (		_UpperCAmelCase	,   _UpperCAmelCase						):




	"""simple docstring"""






	assert a >= 0 and b >= 0

	if b == 0:
		A_ ,			A_ ,			A_	:					str						 =		a, 1, 0
	else:
		((A_) ,			(A_) ,			(A_))	:					List[str]						 =		extended_gcd(_UpperCAmelCase	,   a % b						)
		A_	:					Optional[int]						 =		q
		A_	:					Tuple						 =		p - q * (a // b)

	assert a % d == 0 and b % d == 0
	assert d == a * x + b * y

	return (d, x, y)


if __name__ == "__main__":
		from doctest import testmod

		testmod(name='diophantine', verbose=True)
		testmod(name='diophantine_all_soln', verbose=True)
		testmod(name='extended_gcd', verbose=True)
		testmod(name='greatest_common_divisor', verbose=True)





