


'''simple docstring'''





import math




class 							UpperCAmelCase :


 def __init__(			self       :  Tuple ,					__lowerCamelCase       :  int ,					__lowerCamelCase       :  int ,					__lowerCamelCase       :  int ,					__lowerCamelCase       :  List[str]   ):
    UpperCAmelCase__  :List[Any]            =			x
    UpperCAmelCase__  :Optional[int]            =			y
    UpperCAmelCase__  :Optional[int]            =			step_size
    UpperCAmelCase__  :List[Any]            =			function_to_optimize


 def 					__SCREAMING_SNAKE_CASE				(			self       :  Optional[Any]   ):
    return self.function(self.x ,					self.y   )


 def 					__SCREAMING_SNAKE_CASE				(			self       :  Optional[Any]   ):
    UpperCAmelCase__  :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       :  Dict   ):
    return hash(str(self   )   )


 def __eq__(			self       :  Dict ,					__lowerCamelCase       :  Optional[int]   ):
    if isinstance(__lowerCamelCase ,					__lowerCamelCase   ):
       return hash(str(self   )   ) == hash(str(__lowerCamelCase   )   )
    return False





 def __str__(			self       :  List[Any]   ):
    return f'''x: {self.x} y: {self.y}'''


def 					a__    (				UpperCamelCase_	:			int,      UpperCamelCase_	:			bool = True,      UpperCamelCase_	:			float = math.inf,      UpperCamelCase_	:			float = -math.inf,      UpperCamelCase_	:			float = math.inf,      UpperCamelCase_	:			float = -math.inf,      UpperCamelCase_	:			bool = False,      UpperCamelCase_	:			int = 10_000,      ):
   UpperCAmelCase__  :List[Any]            =			search_prob
   UpperCAmelCase__  :str            =			[]  # list to store the current score at each iteration
   UpperCAmelCase__  :Union[str, Any]            =			0
   UpperCAmelCase__  :int            =			False
   UpperCAmelCase__  :List[str]            =			set()
   while not solution_found and iterations < max_iter:
      visited.add(UpperCamelCase_	)
      iterations += 1
      UpperCAmelCase__  :Optional[Any]            =			current_state.score()
      scores.append(UpperCamelCase_	)
      UpperCAmelCase__  :str            =			current_state.get_neighbors()
      UpperCAmelCase__  :int            =			-math.inf
      UpperCAmelCase__  :Any            =			math.inf
      UpperCAmelCase__  :Optional[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__  :List[Any]            =			change
               UpperCAmelCase__  :Dict            =			neighbor
         else:  # finding min
            # to direction with greatest descent
            if change < min_change and change < 0:
               UpperCAmelCase__  :int            =			change
               UpperCAmelCase__  :List[str]            =			neighbor
      if next_state is not None:
         # we found at least one neighbor which improved the current state
         UpperCAmelCase__  :Optional[Any]            =			next_state
      else:
         # since we have no neighbor that improves the solution we stop the search
         UpperCAmelCase__  :Union[str, Any]            =			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 					a__    (				UpperCamelCase_	:			List[Any],      UpperCamelCase_	:			List[str]	):
       return (x**2) + (y**2)

    # starting the problem with initial coordinates (3, 4)
    __lowerCamelCase       				=	SearchProblem(x=3, y=4, step_size=1, function_to_optimize=test_fa)
    __lowerCamelCase       				=	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       				=	SearchProblem(x=12, y=47, step_size=1, function_to_optimize=test_fa)
    __lowerCamelCase       				=	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__    (				UpperCamelCase_	:			List[Any],      UpperCamelCase_	:			Optional[int]	):
       return (3 * x**2) - (6 * y)

    __lowerCamelCase       				=	SearchProblem(x=3, y=4, step_size=1, function_to_optimize=test_fa)
    __lowerCamelCase       				=	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 heapq


def 					a__    (				UpperCamelCase_	:			Dict,      UpperCamelCase_	:			Tuple,      UpperCamelCase_	:			Dict	):
   UpperCAmelCase__  :List[Any]            =			[(0, start)]  # cost from start node,end node
   UpperCAmelCase__  :Optional[int]            =			set()
   while heap:
      ((UpperCAmelCase__)      ,	(UpperCAmelCase__))  :Optional[Any]            =			heapq.heappop(UpperCamelCase_	)
      if u in visited:
         continue
      visited.add(UpperCamelCase_	)
      if u == end:
         return cost
      for v, c in graph[u]:
         if v in visited:
            continue
         UpperCAmelCase__  :int            =			cost + c
         heapq.heappush(UpperCamelCase_,      (next_item, v)	)
   return -1


__lowerCamelCase       				=	{
    '''A''': [['''B''', 2], ['''C''', 5]],
    '''B''': [['''A''', 2], ['''D''', 3], ['''E''', 1], ['''F''', 1]],
    '''C''': [['''A''', 5], ['''F''', 3]],
    '''D''': [['''B''', 3]],
    '''E''': [['''B''', 4], ['''F''', 3]],
    '''F''': [['''C''', 3], ['''E''', 3]],
}
__lowerCamelCase       				=	{
    '''B''': [['''C''', 1]],
    '''C''': [['''D''', 1]],
    '''D''': [['''F''', 1]],
    '''E''': [['''B''', 1], ['''F''', 3]],
    '''F''': [],
}
__lowerCamelCase       				=	{
    '''B''': [['''C''', 1]],
    '''C''': [['''D''', 1]],
    '''D''': [['''F''', 1]],
    '''E''': [['''B''', 1], ['''G''', 2]],
    '''F''': [],
    '''G''': [['''F''', 1]],
}

__lowerCamelCase       				=	dijkstra(G, '''E''', '''C''')
print(short_distance)  # E -- 3 --> F -- 3 --> C == 6

__lowerCamelCase       				=	dijkstra(Ga, '''E''', '''F''')
print(short_distance)  # E -- 3 --> F == 3

__lowerCamelCase       				=	dijkstra(Ga, '''E''', '''F''')
print(short_distance)  # E -- 2 --> G -- 1 --> F == 3

if __name__ == "__main__":
    import doctest

    doctest.testmod()



