



'''simple docstring'''
import math



class _A  :





		def __init__(     self ,       __UpperCAmelCase ,       __UpperCAmelCase ,       __UpperCAmelCase ,       __UpperCAmelCase				)       ->     List[Any]:

					'''simple docstring'''
					__UpperCAmelCase   :      int										=     x
					__UpperCAmelCase   :      int										=     y
					__UpperCAmelCase   :      Union[str, Any]										=     step_size
					__UpperCAmelCase   :      Optional[Any]										=     function_to_optimize





		def 							__A       (     self				)       ->     int:

					'''simple docstring'''
					return self.function(self.x ,       self.y				)





		def 							__A       (     self				)       ->     List[str]:

					'''simple docstring'''
					__UpperCAmelCase   :      Dict										=     self.step_size
					return [
					    SearchProblem(__UpperCAmelCase ,       __UpperCAmelCase ,       __UpperCAmelCase ,       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				)       ->     Tuple:

					'''simple docstring'''
					return hash(str(self				)				)





		def __eq__(     self ,       __UpperCAmelCase				)       ->     Dict:

					'''simple docstring'''
					if isinstance(__UpperCAmelCase ,       __UpperCAmelCase				):
								return hash(str(self				)				) == hash(str(__UpperCAmelCase				)				)
					return False





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

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


def   lowercase_	(   lowerCAmelCase__	:  Any			,							lowerCAmelCase__	:  bool = True			,							lowerCAmelCase__	:  float = math.inf			,							lowerCAmelCase__	:  float = -math.inf			,							lowerCAmelCase__	:  float = math.inf			,							lowerCAmelCase__	:  float = -math.inf			,							lowerCAmelCase__	:  bool = False			,							lowerCAmelCase__	:  int = 10000			,							):

			"""simple docstring"""





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

								"""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   lowercase_	(   lowerCAmelCase__	:  Any			,							lowerCAmelCase__	:  Union[str, Any] ):

								"""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'''
import numpy as np
from cva import destroyAllWindows, imread, imshow, waitKey



class _A  :





		def __init__(     self ,       __UpperCAmelCase ,       __UpperCAmelCase				)       ->     Union[str, Any]:

					'''simple docstring'''
					__UpperCAmelCase   :      Optional[int]										=     0
					# max greyscale value for #FFFFFF
					__UpperCAmelCase   :      List[Any]										=     int(self.get_greyscale(255 ,       255 ,       255				)				)

					if not self.min_threshold < threshold < self.max_threshold:
								__UpperCAmelCase   :      str										=     f'Factor value should be from 0 to {self.max_threshold}'
								raise ValueError(__UpperCAmelCase				)

					__UpperCAmelCase   :      Tuple										=     input_img
					__UpperCAmelCase   :      Optional[Any]										=     threshold
					__UpperCAmelCase				,  __UpperCAmelCase   :      List[Any]										=     self.input_img.shape[1], self.input_img.shape[0]

					# error table size (+4 columns and +1 row) greater than input image because of
					# lack of if statements
					__UpperCAmelCase   :      Optional[Any]										=     [
					    [0 for _ in range(self.height + 4				)] for __ in range(self.width + 1				)
					]
					__UpperCAmelCase   :      Any										=     np.ones((self.width, self.height, 3) ,       np.uinta				) * 255





		@classmethod
		def 							__A       (     cls ,       __UpperCAmelCase ,       __UpperCAmelCase ,       __UpperCAmelCase				)       ->     float:

					'''simple docstring'''
					return 0.114 * blue + 0.587 * green + 0.2126 * red





		def 							__A       (     self				)       ->     None:

					'''simple docstring'''
					for y in range(self.height				):
								for x in range(self.width				):
											__UpperCAmelCase   :      Optional[Any]										=     int(self.get_greyscale(*self.input_img[y][x]				)				)
											if self.threshold > greyscale + self.error_table[y][x]:
														__UpperCAmelCase   :      List[Any]										=     (0, 0, 0)
														__UpperCAmelCase   :      Union[str, Any]										=     greyscale + self.error_table[x][y]
											else:
														__UpperCAmelCase   :      Optional[Any]										=     (255, 255, 255)
														__UpperCAmelCase   :      Dict										=     greyscale + self.error_table[x][y] - 255
											self.error_table[y][x + 1] += int(8 / 32 * current_error				)
											self.error_table[y][x + 2] += int(4 / 32 * current_error				)
											self.error_table[y + 1][x] += int(8 / 32 * current_error				)
											self.error_table[y + 1][x + 1] += int(4 / 32 * current_error				)
											self.error_table[y + 1][x + 2] += int(2 / 32 * current_error				)
											self.error_table[y + 1][x - 1] += int(4 / 32 * current_error				)
											self.error_table[y + 1][x - 2] += int(2 / 32 * current_error				)


if __name__ == "__main__":
					# create Burke's instances with original images in greyscale
					_UpperCamelCase											=			[
					    Burkes(imread('''image_data/lena.jpg''', 1), threshold)
					    for threshold in (1, 126, 130, 140)
					]

					for burkes in burkes_instances:
										burkes.process()

					for burkes in burkes_instances:
										imshow(
										    F'Original image with dithering threshold: {burkes.threshold}',
										    burkes.output_img,
										)

					waitKey(0)
					destroyAllWindows()




