






'''simple docstring'''






from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
__A    	=   0

__A    	=   [
    [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],
]

__A    	=   [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

__A    	=   tuple[int, int]




class a_    :







   def __init__(self					,   __a					,   __a					,   __a					,   __a					,   __a					,   __a					,   )			->      Union[str, Any]:
      """simple docstring"""






      __snake_case				:      str     							= pos_x
      __snake_case				:      int     							= pos_y
      __snake_case				:      int     							= (pos_y, pos_x)
      __snake_case				:      List[str]     							= goal_x
      __snake_case				:      Tuple     							= goal_y
      __snake_case				:      str     							= g_cost
      __snake_case				:      Optional[Any]     							= parent
      __snake_case				:      Dict     							= self.calculate_heuristic()
      __snake_case				:      Dict     							= self.g_cost + self.h_cost







   def     SCREAMING_SNAKE_CASE__					(self)			->      Union[str, Any]:
      """simple docstring"""






      __snake_case				:      Optional[Any]     							= self.pos_x - self.goal_x
      __snake_case				:      List[Any]     							= self.pos_y - self.goal_y
      if HEURISTIC == 1:
         return abs(UpperCAmelCase__) + abs(UpperCAmelCase__)
      else:
         return sqrt(dy**2 + dx**2)







   def __lt__(self					,   __a)			->      str:
      """simple docstring"""






      return self.f_cost < other.f_cost




class a_    :







   def __init__(self					,   __a					,   __a)			->      Dict:
      """simple docstring"""






      __snake_case				:      List[Any]     							= Node(start[1]					,   start[0]					,   goal[1]					,   goal[0]					,   0					,   UpperCAmelCase__)
      __snake_case				:      Optional[Any]     							= Node(goal[1]					,   goal[0]					,   goal[1]					,   goal[0]					,   9_9_9_9_9					,   UpperCAmelCase__)

      __snake_case				:      Tuple     							= [self.start]
      __snake_case				:      list[Node]     							= []

      __snake_case				:      Tuple     							= False







   def     SCREAMING_SNAKE_CASE__					(self)			->      Any:
      """simple docstring"""






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

         if current_node.pos == self.target.pos:
            return self.retrace_path(UpperCAmelCase__)

         self.closed_nodes.append(UpperCAmelCase__)
         __snake_case				:      str     							= self.get_successors(UpperCAmelCase__)

         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(UpperCAmelCase__)
            else:
               # retrieve the best current path
               __snake_case				:      Tuple     							= self.open_nodes.pop(self.open_nodes.index(UpperCAmelCase__))

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

      return [self.start.pos]







   def     SCREAMING_SNAKE_CASE__					(self					,   __a)			->      Any:
      """simple docstring"""






      __snake_case				:      Dict     							= []
      for action in delta:
         __snake_case				:      List[Any]     							= parent.pos_x + action[1]
         __snake_case				:      int     							= parent.pos_y + action[0]
         if not (0 <= pos_x <= len(grid[0]) - 1 and 0 <= pos_y <= len(UpperCAmelCase__) - 1):
            continue

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

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







   def     SCREAMING_SNAKE_CASE__					(self					,   __a)			->      Tuple:
      """simple docstring"""






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




class a_    :







   def __init__(self					,   __a					,   __a)			->      Optional[Any]:
      """simple docstring"""






      __snake_case				:      str     							= AStar(UpperCAmelCase__					,   UpperCAmelCase__)
      __snake_case				:      str     							= AStar(UpperCAmelCase__					,   UpperCAmelCase__)
      __snake_case				:      Dict     							= False







   def     SCREAMING_SNAKE_CASE__					(self)			->      List[Any]:
      """simple docstring"""






      while self.fwd_astar.open_nodes or self.bwd_astar.open_nodes:
         self.fwd_astar.open_nodes.sort()
         self.bwd_astar.open_nodes.sort()
         __snake_case				:      Dict     							= self.fwd_astar.open_nodes.pop(0)
         __snake_case				:      Tuple     							= self.bwd_astar.open_nodes.pop(0)

         if current_bwd_node.pos == current_fwd_node.pos:
            return self.retrace_bidirectional_path(
                UpperCAmelCase__					,   UpperCAmelCase__)

         self.fwd_astar.closed_nodes.append(UpperCAmelCase__)
         self.bwd_astar.closed_nodes.append(UpperCAmelCase__)

         __snake_case				:      int     							= current_bwd_node
         __snake_case				:      Dict     							= current_fwd_node

         __snake_case				:      List[Any]     							= {
             self.fwd_astar: self.fwd_astar.get_successors(UpperCAmelCase__),
             self.bwd_astar: self.bwd_astar.get_successors(UpperCAmelCase__),
         }

         for astar in [self.fwd_astar, self.bwd_astar]:
            for child_node in successors[astar]:
               if child_node in astar.closed_nodes:
                  continue

               if child_node not in astar.open_nodes:
                  astar.open_nodes.append(UpperCAmelCase__)
               else:
                  # retrieve the best current path
                  __snake_case				:      str     							= astar.open_nodes.pop(
                      astar.open_nodes.index(UpperCAmelCase__))

                  if child_node.g_cost < better_node.g_cost:
                     astar.open_nodes.append(UpperCAmelCase__)
                  else:
                     astar.open_nodes.append(UpperCAmelCase__)

      return [self.fwd_astar.start.pos]







   def     SCREAMING_SNAKE_CASE__					(self					,   __a					,   __a)			->      List[str]:
      """simple docstring"""






      __snake_case				:      Union[str, Any]     							= self.fwd_astar.retrace_path(UpperCAmelCase__)
      __snake_case				:      List[str]     							= self.bwd_astar.retrace_path(UpperCAmelCase__)
      bwd_path.pop()
      bwd_path.reverse()
      __snake_case				:      str     							= fwd_path + bwd_path
      return path


if __name__ == "__main__":
      # all coordinates are given in format [y,x]
      __A    	=   (0, 0)
      __A    	=   (len(grid) - 1, len(grid[0]) - 1)
      for elem in grid:
            print(elem)

      __A    	=   time.time()
      __A    	=   AStar(init, goal)
      __A    	=   a_star.search()
      __A    	=   time.time() - start_time
      print(f'''AStar execution time = {end_time:f} seconds''')

      __A    	=   time.time()
      __A    	=   BidirectionalAStar(init, goal)
      __A    	=   time.time() - bd_start_time
      print(f'''BidirectionalAStar execution time = {bd_end_time:f} seconds''')







'''simple docstring'''






from __future__ import annotations

from collections import deque
from collections.abc import Sequence
from dataclasses import dataclass
from typing import Any




@dataclass
class a_    :
   _snake_case        =							42
   _snake_case        =							None
   _snake_case        =							None




def        _SCREAMING_SNAKE_CASE  (				)    -> Node | None:







   """simple docstring"""
   __snake_case				:      str     							= Node(1  )
   __snake_case				:      Tuple     							= Node(2  )
   __snake_case				:      Optional[int]     							= Node(3  )
   __snake_case				:      List[str]     							= Node(4  )
   __snake_case				:      List[str]     							= Node(5  )
   return tree




def        _SCREAMING_SNAKE_CASE  (				A  :       Node | None  )    -> list[int]:







   """simple docstring"""
   return [root.data, *preorder(root.left  ), *preorder(root.right  )] if root else []




def        _SCREAMING_SNAKE_CASE  (				A  :       Node | None  )    -> list[int]:







   """simple docstring"""
   return postorder(root.left  ) + postorder(root.right  ) + [root.data] if root else []




def        _SCREAMING_SNAKE_CASE  (				A  :       Node | None  )    -> list[int]:







   """simple docstring"""
   return [*inorder(root.left  ), root.data, *inorder(root.right  )] if root else []




def        _SCREAMING_SNAKE_CASE  (				A  :       Node | None  )    -> int:







   """simple docstring"""
   return (max(height(root.left  )  ,		height(root.right  )  ) + 1) if root else 0




def        _SCREAMING_SNAKE_CASE  (				A  :       Node | None  )    -> Sequence[Node | None]:







   """simple docstring"""
   __snake_case				:      list[Any]     							= []

   if root is None:
      return output

   __snake_case				:      Optional[int]     							= deque([root]  )

   while process_queue:
      __snake_case				:      List[str]     							= process_queue.popleft()
      output.append(node.data  )

      if node.left:
         process_queue.append(node.left  )
      if node.right:
         process_queue.append(node.right  )
   return output




def        _SCREAMING_SNAKE_CASE  (				A  :       Node | None  ,		A  :       int  )    -> Sequence[Node | None]:







   """simple docstring"""
   __snake_case				:      list[Any]     							= []

   def populate_output(A  :       Node | None  ,		A  :       int  ) -> None:
      if not root:
         return
      if level == 1:
         output.append(root.data  )
      elif level > 1:
         populate_output(root.left  ,		level - 1  )
         populate_output(root.right  ,		level - 1  )

   populate_output(A  ,		A  )
   return output




def        _SCREAMING_SNAKE_CASE  (				A  :       Node | None  ,		A  :       int  )    -> Sequence[Node | None]:







   """simple docstring"""
   __snake_case				:      list[Any]     							= []

   def populate_output(A  :       Node | None  ,		A  :       int  ) -> None:
      if root is None:
         return
      if level == 1:
         output.append(root.data  )
      elif level > 1:
         populate_output(root.right  ,		level - 1  )
         populate_output(root.left  ,		level - 1  )

   populate_output(A  ,		A  )
   return output




def        _SCREAMING_SNAKE_CASE  (				A  :       Node | None  )    -> Sequence[Node | None] | list[Any]:







   """simple docstring"""
   if root is None:
      return []

   __snake_case				:      list[Sequence[Node | None]]     							= []

   __snake_case				:      List[Any]     							= 0
   __snake_case				:      int     							= height(A  )

   for h in range(1  ,		height_tree + 1  ):
      if not flag:
         output.append(get_nodes_from_left_to_right(A  ,		A  )  )
         __snake_case				:      int     							= 1
      else:
         output.append(get_nodes_from_right_to_left(A  ,		A  )  )
         __snake_case				:      Tuple     							= 0

   return output




def        _SCREAMING_SNAKE_CASE  (				)    -> None:  # Main function for testing.







   """simple docstring"""
   __snake_case				:      Optional[int]     							= make_tree()
   print(F"""In-order Traversal: {inorder(A  )}"""  )
   print(F"""Pre-order Traversal: {preorder(A  )}"""  )
   print(F"""Post-order Traversal: {postorder(A  )}"""  ,		'\n'  )

   print(F"""Height of Tree: {height(A  )}"""  ,		'\n'  )

   print('Complete Level Order Traversal: '  )
   print(level_order(A  )  ,		'\n'  )

   print('Level-wise order Traversal: '  )

   for level in range(1  ,		height(A  ) + 1  ):
      print(F"""Level {level}:"""  ,		get_nodes_from_left_to_right(A  ,		level=A  )  )

   print('\nZigZag order Traversal: '  )
   print(zigzag(A  )  )


if __name__ == "__main__":
      import doctest

      doctest.testmod()
      main()