






'''simple docstring'''
import math


class     _UpperCAmelCase  :




    def __init__(     self					:    Any					,       a					:    int					,       a					:    int					,       a					:    int					,       a					:    Dict     ):






       '''simple docstring'''






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




    def 			lowerCAmelCase__			(     self					:    List[str]     ):






       '''simple docstring'''






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




    def 			lowerCAmelCase__			(     self					:    Optional[int]     ):






       '''simple docstring'''






       lowercase_		:      str          =       self.step_size
       return [
           SearchProblem(a					,       a					,       a					,       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[Any]     ):






       '''simple docstring'''






       return hash(str(self     )     )




    def __eq__(     self					:    Optional[int]					,       a					:    Optional[Any]     ):






       '''simple docstring'''






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





    def __str__(     self					:    str     ):






       '''simple docstring'''






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




def 						__SCREAMING_SNAKE_CASE   (					_UpperCamelCase  ,						_UpperCamelCase = True  ,						_UpperCamelCase = math.inf  ,						_UpperCamelCase = -math.inf  ,						_UpperCamelCase = math.inf  ,						_UpperCamelCase = -math.inf  ,						_UpperCamelCase = False  ,						_UpperCamelCase = 1_0000  ,						):


   """simple docstring"""




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


    """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 						__SCREAMING_SNAKE_CASE   (					_UpperCamelCase  ,						_UpperCamelCase							):


    """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'''
def 						__SCREAMING_SNAKE_CASE   (					_UpperCamelCase  ,						_UpperCamelCase							):


   """simple docstring"""




   sequence.append(_UpperCamelCase							)

   lowercase_		:      Union[str, Any]          =       0
   while sequence[index] != target:
      index += 1

   sequence.pop()

   if index == len(_UpperCamelCase							):
      return None

   return index


if __name__ == "__main__":
 UpperCamelCase__	=     input('Enter numbers separated by comma:\n').strip()
 UpperCamelCase__	=     [int(item) for item in user_input.split(',')]

 UpperCamelCase__	=     input('Enter a single number to be found in the list:\n')
 UpperCamelCase__	=     int(target_input)
 UpperCamelCase__	=     sentinel_linear_search(sequence, target)
 if result is not None:
  print(f"""{target} found at positions: {result}""")
 else:
  print('Not found')




