'''simple docstring'''




from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
__UpperCAmelCase												=0

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

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

__UpperCAmelCase												=tuple[int, int]




class    a__				:






     def __init__(			self		:		str  ,    a		:		Tuple  ,    a		:		List[str]  ,    a		:		List[str]  ,    a		:		List[Any]  ,    a		:		str  ,    a		:		Dict  ,    ):





         """simple docstring"""



         __lowerCamelCase          =  pos_x
         __lowerCamelCase          =  pos_y
         __lowerCamelCase          =  (pos_y, pos_x)
         __lowerCamelCase          =  goal_x
         __lowerCamelCase          =  goal_y
         __lowerCamelCase          =  g_cost
         __lowerCamelCase          =  parent
         __lowerCamelCase          =  self.calculate_heuristic()
         __lowerCamelCase          =  self.g_cost + self.h_cost






     def        SCREAMING_SNAKE_CASE__       (			self		:		List[Any]   ):





         """simple docstring"""



         __lowerCamelCase          =  self.pos_x - self.goal_x
         __lowerCamelCase          =  self.pos_y - self.goal_y
         if HEURISTIC == 1:
             return abs(lowercase_   ) + abs(lowercase_   )
         else:
             return sqrt(dy**2 + dx**2   )






     def __lt__(			self		:		Dict  ,    a		:		int   ):





         """simple docstring"""



         return self.f_cost < other.f_cost







class    a__				:






     def __init__(			self		:		Any  ,    a		:		str  ,    a		:		List[str]   ):





         """simple docstring"""



         __lowerCamelCase          =  Node(start[1]  ,    start[0]  ,    goal[1]  ,    goal[0]  ,    0  ,    lowercase_   )
         __lowerCamelCase          =  Node(goal[1]  ,    goal[0]  ,    goal[1]  ,    goal[0]  ,    9_99_99  ,    lowercase_   )

         __lowerCamelCase          =  [self.start]
         __lowerCamelCase          =  []

         __lowerCamelCase          =  False






     def        SCREAMING_SNAKE_CASE__       (			self		:		Union[str, Any]   ):





         """simple docstring"""



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

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

             self.closed_nodes.append(lowercase_   )
             __lowerCamelCase          =  self.get_successors(lowercase_   )

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

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

         return [self.start.pos]






     def        SCREAMING_SNAKE_CASE__       (			self		:		Tuple  ,    a		:		Any   ):





         """simple docstring"""



         __lowerCamelCase          =  []
         for action in delta:
             __lowerCamelCase          =  parent.pos_x + action[1]
             __lowerCamelCase          =  parent.pos_y + action[0]
             if not (0 <= pos_x <= len(grid[0]   ) - 1 and 0 <= pos_y <= len(lowercase_   ) - 1):
                 continue

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

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






     def        SCREAMING_SNAKE_CASE__       (			self		:		Optional[Any]  ,    a		:		List[Any]   ):





         """simple docstring"""



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







class    a__				:






     def __init__(			self		:		List[Any]  ,    a		:		Union[str, Any]  ,    a		:		Optional[Any]   ):





         """simple docstring"""



         __lowerCamelCase          =  AStar(lowercase_  ,    lowercase_   )
         __lowerCamelCase          =  AStar(lowercase_  ,    lowercase_   )
         __lowerCamelCase          =  False






     def        SCREAMING_SNAKE_CASE__       (			self		:		List[str]   ):





         """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()
             __lowerCamelCase          =  self.fwd_astar.open_nodes.pop(0   )
             __lowerCamelCase          =  self.bwd_astar.open_nodes.pop(0   )

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

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

             __lowerCamelCase          =  current_bwd_node
             __lowerCamelCase          =  current_fwd_node

             __lowerCamelCase          =  {
                 self.fwd_astar: self.fwd_astar.get_successors(lowercase_   ),
                 self.bwd_astar: self.bwd_astar.get_successors(lowercase_   ),
             }

             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(lowercase_   )
                     else:
                         # retrieve the best current path
                         __lowerCamelCase          =  astar.open_nodes.pop(
                             astar.open_nodes.index(lowercase_   )   )

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

         return [self.fwd_astar.start.pos]






     def        SCREAMING_SNAKE_CASE__       (			self		:		List[Any]  ,    a		:		int  ,    a		:		Dict   ):





         """simple docstring"""



         __lowerCamelCase          =  self.fwd_astar.retrace_path(lowercase_   )
         __lowerCamelCase          =  self.bwd_astar.retrace_path(lowercase_   )
         bwd_path.pop()
         bwd_path.reverse()
         __lowerCamelCase          =  fwd_path + bwd_path
         return path


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

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

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

'''simple docstring'''




def __lowerCAmelCase			(							UpperCamelCase__    )     ->   str:
    return "".join(chr(ord(UpperCamelCase__    ) - 32    ) if '''a''' <= char <= '''z''' else char for char in word    )


if __name__ == "__main__":
  from doctest import testmod

  testmod()
