

"""simple docstring"""






from __future__ import annotations

_lowerCAmelCase       						=		list[tuple[int, int]]

_lowerCAmelCase       						=		[
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
]

_lowerCAmelCase       						=		([-1, 0], [0, -1], [1, 0], [0, 1])  # up, left, down, right







class 						__UpperCamelCase     :

  def __init__(		self     ,_A     ,_A     ,_A     ,_A     ,_A     ,_A     ,):
      '''simple docstring'''

      _lowerCAmelCase							: int	=     pos_x
      _lowerCAmelCase							: str	=     pos_y
      _lowerCAmelCase							: Any	=     (pos_y, pos_x)
      _lowerCAmelCase							: Optional[Any]	=     goal_x
      _lowerCAmelCase							: List[Any]	=     goal_y
      _lowerCAmelCase							: str	=     g_cost
      _lowerCAmelCase							: Any	=     parent
      _lowerCAmelCase							: int	=     self.calculate_heuristic()

  def __lowerCamelCase		(		self   ):
      '''simple docstring'''

      _lowerCAmelCase							: List[Any]	=     abs(self.pos_x - self.goal_x   )
      _lowerCAmelCase							: List[Any]	=     abs(self.pos_y - self.goal_y   )
      return dx + dy







  def __lt__(		self     ,_A   ):
      '''simple docstring'''

      return self.f_cost < other.f_cost







class 						__UpperCamelCase     :

  def __init__(		self     ,_A     ,_A   ):
      '''simple docstring'''

      _lowerCAmelCase							: Any	=     Node(start[1]     ,start[0]     ,goal[1]     ,goal[0]     ,0     ,__lowerCamelCase   )
      _lowerCAmelCase							: int	=     Node(goal[1]     ,goal[0]     ,goal[1]     ,goal[0]     ,9_9999     ,__lowerCamelCase   )

      _lowerCAmelCase							: str	=     [self.start]
      _lowerCAmelCase							: int	=     []

      _lowerCAmelCase							: str	=     False

  def __lowerCamelCase		(		self   ):
      '''simple docstring'''

      while self.open_nodes:
          # Open Nodes are sorted using __lt__
          self.open_nodes.sort()
          _lowerCAmelCase							: Dict	=     self.open_nodes.pop(0   )

          if current_node.pos == self.target.pos:
              _lowerCAmelCase							: int	=     True
              return self.retrace_path(__lowerCamelCase   )

          self.closed_nodes.append(__lowerCamelCase   )
          _lowerCAmelCase							: Any	=     self.get_successors(__lowerCamelCase   )

          for child_node in successors:
              if child_node in self.closed_nodes:
                  continue

              if child_node not in self.open_nodes:
                  self.open_nodes.append(__lowerCamelCase   )
              else:
                  # retrieve the best current path
                  _lowerCAmelCase							: Dict	=     self.open_nodes.pop(self.open_nodes.index(__lowerCamelCase   )   )

                  if child_node.g_cost < better_node.g_cost:
                      self.open_nodes.append(__lowerCamelCase   )
                  else:
                      self.open_nodes.append(__lowerCamelCase   )

      if not self.reached:
          return [self.start.pos]
      return None

  def __lowerCamelCase		(		self     ,_A   ):
      '''simple docstring'''

      _lowerCAmelCase							: Optional[int]	=     []
      for action in delta:
          _lowerCAmelCase							: List[str]	=     parent.pos_x + action[1]
          _lowerCAmelCase							: Any	=     parent.pos_y + action[0]

          if not (0 <= pos_x <= len(grid[0]   ) - 1 and 0 <= pos_y <= len(__lowerCamelCase   ) - 1):
              continue

          if grid[pos_y][pos_x] != 0:
              continue

          successors.append(
              Node(
                  __lowerCamelCase     ,__lowerCamelCase     ,self.target.pos_y     ,self.target.pos_x     ,parent.g_cost + 1     ,__lowerCamelCase     ,)   )
      return successors







  def __lowerCamelCase		(		self     ,_A   ):
      '''simple docstring'''

      _lowerCAmelCase							: Any	=     node
      _lowerCAmelCase							: Dict	=     []
      while current_node is not None:
          path.append((current_node.pos_y, current_node.pos_x)   )
          _lowerCAmelCase							: int	=     current_node.parent
      path.reverse()
      return path


if __name__ == "__main__":
 _lowerCAmelCase       						=		(0, 0)
 _lowerCAmelCase       						=		(len(grid) - 1, len(grid[0]) - 1)
 for elem in grid:
  print(elem)

 print("""------""")

 _lowerCAmelCase       						=		GreedyBestFirst(init, goal)
 _lowerCAmelCase       						=		greedy_bf.search()
 if path:
  for pos_x, pos_y in path:
   _lowerCAmelCase       						=		2

  for elem in grid:
   print(elem)








from collections.abc import Callable

import numpy as np





def 	__a     (      A__			:  Callable			,  A__			:  float			,  A__			:  float			,  A__			:  float			,  A__			:  float       ):
    SCREAMING_SNAKE_CASE										=   int(np.ceil((x_end - xa) / step_size       )       )
    SCREAMING_SNAKE_CASE										=   np.zeros((n + 1,)       )
    SCREAMING_SNAKE_CASE										=   ya
    SCREAMING_SNAKE_CASE										=   xa

    for k in range(A__       ):
        SCREAMING_SNAKE_CASE										=   y[k] + step_size * ode_func(A__			,  y[k]       )
        SCREAMING_SNAKE_CASE										=   y[k] + (
            (step_size / 2) * (ode_func(A__			,  y[k]       ) + ode_func(x + step_size			,  A__       ))
        )
        x += step_size

    return y


if __name__ == "__main__":
    import doctest

    doctest.testmod()