
from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
lowerCamelCase__    :		Optional[int]          =   0

lowerCamelCase__    :		int          =   [
    [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__    :		List[str]          =   [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

lowerCamelCase__    :		Any          =   tuple[int, int]



class       _snake_case   :


 def __init__(					self					,  SCREAMING_SNAKE_CASE_					,  SCREAMING_SNAKE_CASE_					,  SCREAMING_SNAKE_CASE_					,  SCREAMING_SNAKE_CASE_					,  SCREAMING_SNAKE_CASE_					,  SCREAMING_SNAKE_CASE_					,  ):


   '''simple docstring'''




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


 def      lowercase__     (					self):


   '''simple docstring'''




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



 def __lt__(					self					,  SCREAMING_SNAKE_CASE_):


   '''simple docstring'''




   return self.f_cost < other.f_cost



class       _snake_case   :


 def __init__(					self					,  SCREAMING_SNAKE_CASE_					,  SCREAMING_SNAKE_CASE_):


   '''simple docstring'''




   lowercase__  :   List[Any]    		=      Node(start[1]					,  start[0]					,  goal[1]					,  goal[0]					,  0					,  SCREAMING_SNAKE_CASE_)
   lowercase__  :   str    		=      Node(goal[1]					,  goal[0]					,  goal[1]					,  goal[0]					,  9_99_99					,  SCREAMING_SNAKE_CASE_)

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

   lowercase__  :   Optional[int]    		=      False


 def      lowercase__     (					self):


   '''simple docstring'''




   while self.open_nodes:
     # Open Nodes are sorted using __lt__
     self.open_nodes.sort()
     lowercase__  :   Optional[Any]    		=      self.open_nodes.pop(0)

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

     self.closed_nodes.append(SCREAMING_SNAKE_CASE_)
     lowercase__  :   Optional[Any]    		=      self.get_successors(SCREAMING_SNAKE_CASE_)

     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(SCREAMING_SNAKE_CASE_)
       else:
         # retrieve the best current path
         lowercase__  :   List[str]    		=      self.open_nodes.pop(self.open_nodes.index(SCREAMING_SNAKE_CASE_))

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

   return [self.start.pos]


 def      lowercase__     (					self					,  SCREAMING_SNAKE_CASE_):


   '''simple docstring'''




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

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

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



 def      lowercase__     (					self					,  SCREAMING_SNAKE_CASE_):


   '''simple docstring'''




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



class       _snake_case   :


 def __init__(					self					,  SCREAMING_SNAKE_CASE_					,  SCREAMING_SNAKE_CASE_):


   '''simple docstring'''




   lowercase__  :   List[Any]    		=      AStar(SCREAMING_SNAKE_CASE_					,  SCREAMING_SNAKE_CASE_)
   lowercase__  :   Optional[Any]    		=      AStar(SCREAMING_SNAKE_CASE_					,  SCREAMING_SNAKE_CASE_)
   lowercase__  :   List[str]    		=      False


 def      lowercase__     (					self):


   '''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()
     lowercase__  :   Tuple    		=      self.fwd_astar.open_nodes.pop(0)
     lowercase__  :   Union[str, Any]    		=      self.bwd_astar.open_nodes.pop(0)

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

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

     lowercase__  :   Optional[int]    		=      current_bwd_node
     lowercase__  :   Optional[Any]    		=      current_fwd_node

     lowercase__  :   Optional[Any]    		=      {
         self.fwd_astar: self.fwd_astar.get_successors(SCREAMING_SNAKE_CASE_),
         self.bwd_astar: self.bwd_astar.get_successors(SCREAMING_SNAKE_CASE_),
     }

     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(SCREAMING_SNAKE_CASE_)
         else:
           # retrieve the best current path
           lowercase__  :   Optional[Any]    		=      astar.open_nodes.pop(
               astar.open_nodes.index(SCREAMING_SNAKE_CASE_))

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

   return [self.fwd_astar.start.pos]



 def      lowercase__     (					self					,  SCREAMING_SNAKE_CASE_					,  SCREAMING_SNAKE_CASE_):


   '''simple docstring'''




   lowercase__  :   Any    		=      self.fwd_astar.retrace_path(SCREAMING_SNAKE_CASE_)
   lowercase__  :   Tuple    		=      self.bwd_astar.retrace_path(SCREAMING_SNAKE_CASE_)
   bwd_path.pop()
   bwd_path.reverse()
   lowercase__  :   Optional[int]    		=      fwd_path + bwd_path
   return path


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

     lowerCamelCase__    :		Union[str, Any]          =   time.time()
     lowerCamelCase__    :		Optional[int]          =   AStar(init, goal)
     lowerCamelCase__    :		Union[str, Any]          =   a_star.search()
     lowerCamelCase__    :		str          =   time.time() - start_time
     print(f'''AStar execution time = {end_time:f} seconds''')

     lowerCamelCase__    :		int          =   time.time()
     lowerCamelCase__    :		int          =   BidirectionalAStar(init, goal)
     lowerCamelCase__    :		List[Any]          =   time.time() - bd_start_time
     print(f'''BidirectionalAStar execution time = {bd_end_time:f} seconds''')






from __future__ import annotations

from collections.abc import Iterator
from typing import Any



class       _snake_case   :


 def __init__(					self					,  SCREAMING_SNAKE_CASE_):


   '''simple docstring'''




   lowercase__  :   Any    		=      data
   lowercase__  :   Node | None    		=      None



class       _snake_case   :


 def __init__(					self):


   '''simple docstring'''




   lowercase__  :   List[Any]    		=      None
   lowercase__  :   int    		=      None


 def __iter__(					self):


   '''simple docstring'''




   lowercase__  :   List[str]    		=      self.head
   while self.head:
     yield node.data
     lowercase__  :   str    		=      node.next
     if node == self.head:
       break


 def __len__(					self):


   '''simple docstring'''




   return sum(1 for _ in self)


 def __repr__(					self):


   '''simple docstring'''




   return "->".join(str(SCREAMING_SNAKE_CASE_) for item in iter(self))


 def      lowercase__     (					self					,  SCREAMING_SNAKE_CASE_):


   '''simple docstring'''




   self.insert_nth(len(self)					,  SCREAMING_SNAKE_CASE_)


 def      lowercase__     (					self					,  SCREAMING_SNAKE_CASE_):


   '''simple docstring'''




   self.insert_nth(0					,  SCREAMING_SNAKE_CASE_)


 def      lowercase__     (					self					,  SCREAMING_SNAKE_CASE_					,  SCREAMING_SNAKE_CASE_):


   '''simple docstring'''




   if index < 0 or index > len(self):
     raise IndexError("""list index out of range.""")
   lowercase__  :   Optional[int]    		=      Node(SCREAMING_SNAKE_CASE_)
   if self.head is None:
     lowercase__  :   Union[str, Any]    		=      new_node  # first node points itself
     lowercase__  :   Dict    		=      new_node
   elif index == 0:  # insert at head
     lowercase__  :   int    		=      self.head
     lowercase__  :   int    		=      new_node
   else:
     lowercase__  :   List[str]    		=      self.head
     for _ in range(index - 1):
       lowercase__  :   Union[str, Any]    		=      temp.next
     lowercase__  :   int    		=      temp.next
     lowercase__  :   Optional[Any]    		=      new_node
     if index == len(self) - 1:  # insert at tail
       lowercase__  :   Union[str, Any]    		=      new_node


 def      lowercase__     (					self):


   '''simple docstring'''




   return self.delete_nth(0)


 def      lowercase__     (					self):


   '''simple docstring'''




   return self.delete_nth(len(self) - 1)


 def      lowercase__     (					self					,  SCREAMING_SNAKE_CASE_ = 0):


   '''simple docstring'''




   if not 0 <= index < len(self):
     raise IndexError("""list index out of range.""")
   lowercase__  :   str    		=      self.head
   if self.head == self.tail:  # just one node
     lowercase__  :   List[Any]    		=      None
   elif index == 0:  # delete head node
     lowercase__  :   str    		=      self.tail.next.next
     lowercase__  :   List[Any]    		=      self.head.next
   else:
     lowercase__  :   Optional[int]    		=      self.head
     for _ in range(index - 1):
       lowercase__  :   List[Any]    		=      temp.next
     lowercase__  :   Optional[Any]    		=      temp.next
     lowercase__  :   Dict    		=      temp.next.next
     if index == len(self) - 1:  # delete at tail
       lowercase__  :   Tuple    		=      temp
   return delete_node.data



 def      lowercase__     (					self):


   '''simple docstring'''




   return len(self) == 0

def 		UpperCamelCase	(      )		->	None:


  '''simple docstring'''






  lowercase__  :   int    		=      CircularLinkedList()
  assert len(lowercase_   ) == 0
  assert circular_linked_list.is_empty() is True
  assert str(lowercase_   ) == ""

  try:
    circular_linked_list.delete_front()
    raise AssertionError  # This should not happen
  except IndexError:
    assert True  # This should happen

  try:
    circular_linked_list.delete_tail()
    raise AssertionError  # This should not happen
  except IndexError:
    assert True  # This should happen

  try:
    circular_linked_list.delete_nth(-1   )
    raise AssertionError
  except IndexError:
    assert True

  try:
    circular_linked_list.delete_nth(0   )
    raise AssertionError
  except IndexError:
    assert True

  assert circular_linked_list.is_empty() is True
  for i in range(5   ):
    assert len(lowercase_   ) == i
    circular_linked_list.insert_nth(lowercase_ , i + 1   )
  assert str(lowercase_   ) == "->".join(str(lowercase_   ) for i in range(1 , 6   )   )

  circular_linked_list.insert_tail(6   )
  assert str(lowercase_   ) == "->".join(str(lowercase_   ) for i in range(1 , 7   )   )
  circular_linked_list.insert_head(0   )
  assert str(lowercase_   ) == "->".join(str(lowercase_   ) for i in range(0 , 7   )   )

  assert circular_linked_list.delete_front() == 0
  assert circular_linked_list.delete_tail() == 6
  assert str(lowercase_   ) == "->".join(str(lowercase_   ) for i in range(1 , 6   )   )
  assert circular_linked_list.delete_nth(2   ) == 3

  circular_linked_list.insert_nth(2 , 3   )
  assert str(lowercase_   ) == "->".join(str(lowercase_   ) for i in range(1 , 6   )   )

  assert circular_linked_list.is_empty() is False


if __name__ == "__main__":
     import doctest

     doctest.testmod()






