



"""simple docstring"""
from __future__ import annotations

import time

_UpperCAmelCase     =			list[tuple[int, int]]

_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





class 					a	:



  def __init__(						self :					Optional[int]       ,		lowerCAmelCase :					int       ,		lowerCAmelCase :					int       ,		lowerCAmelCase :					int       ,		lowerCAmelCase :					int       ,		lowerCAmelCase :					Node | None		)     ->					Tuple:


     '''simple docstring'''




     SCREAMING_SNAKE_CASE_: Dict     			=pos_x
     SCREAMING_SNAKE_CASE_: Optional[int]     			=pos_y
     SCREAMING_SNAKE_CASE_: List[str]     			=(pos_y, pos_x)
     SCREAMING_SNAKE_CASE_: Any     			=goal_x
     SCREAMING_SNAKE_CASE_: List[Any]     			=goal_y
     SCREAMING_SNAKE_CASE_: List[str]     			=parent







class 					a	:



  def __init__(						self :					int       ,		lowerCAmelCase :					tuple[int, int]       ,		lowerCAmelCase :					tuple[int, int]		)     ->					List[str]:


     '''simple docstring'''




     SCREAMING_SNAKE_CASE_: List[str]     			=Node(start[1]       ,		start[0]       ,		goal[1]       ,		goal[0]       ,		lowerCAmelCase		)
     SCREAMING_SNAKE_CASE_: Optional[int]     			=Node(goal[1]       ,		goal[0]       ,		goal[1]       ,		goal[0]       ,		lowerCAmelCase		)

     SCREAMING_SNAKE_CASE_: Dict     			=[self.start]
     SCREAMING_SNAKE_CASE_: Tuple     			=False



  def 	lowerCamelCase__       (						self :					str		)     ->					Path | None:


     '''simple docstring'''




     while self.node_queue:
        SCREAMING_SNAKE_CASE_: Dict     			=self.node_queue.pop(0		)

        if current_node.pos == self.target.pos:
           SCREAMING_SNAKE_CASE_: Optional[Any]     			=True
           return self.retrace_path(lowerCAmelCase		)

        SCREAMING_SNAKE_CASE_: Tuple     			=self.get_successors(lowerCAmelCase		)

        for node in successors:
           self.node_queue.append(lowerCAmelCase		)

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



  def 	lowerCamelCase__       (						self :					List[str]       ,		lowerCAmelCase :					Node		)     ->					list[Node]:


     '''simple docstring'''




     SCREAMING_SNAKE_CASE_: int     			=[]
     for action in delta:
        SCREAMING_SNAKE_CASE_: Optional[Any]     			=parent.pos_x + action[1]
        SCREAMING_SNAKE_CASE_: Dict     			=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       ,		lowerCAmelCase		)		)
     return successors





  def 	lowerCamelCase__       (						self :					Union[str, Any]       ,		lowerCAmelCase :					Node | None		)     ->					Path:


     '''simple docstring'''




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







class 					a	:



  def __init__(						self :					Union[str, Any]       ,		lowerCAmelCase :					int       ,		lowerCAmelCase :					List[Any]		)     ->					Tuple:


     '''simple docstring'''




     SCREAMING_SNAKE_CASE_: Optional[Any]     			=BreadthFirstSearch(lowerCAmelCase       ,		lowerCAmelCase		)
     SCREAMING_SNAKE_CASE_: List[str]     			=BreadthFirstSearch(lowerCAmelCase       ,		lowerCAmelCase		)
     SCREAMING_SNAKE_CASE_: List[Any]     			=False



  def 	lowerCamelCase__       (						self :					Union[str, Any]		)     ->					Path | None:


     '''simple docstring'''




     while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
        SCREAMING_SNAKE_CASE_: Optional[int]     			=self.fwd_bfs.node_queue.pop(0		)
        SCREAMING_SNAKE_CASE_: List[str]     			=self.bwd_bfs.node_queue.pop(0		)

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

        SCREAMING_SNAKE_CASE_: Optional[int]     			=current_bwd_node
        SCREAMING_SNAKE_CASE_: Dict     			=current_fwd_node

        SCREAMING_SNAKE_CASE_: List[str]     			={
            self.fwd_bfs: self.fwd_bfs.get_successors(lowerCAmelCase		),
            self.bwd_bfs: self.bwd_bfs.get_successors(lowerCAmelCase		),
        }

        for bfs in [self.fwd_bfs, self.bwd_bfs]:
           for node in successors[bfs]:
              bfs.node_queue.append(lowerCAmelCase		)

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





  def 	lowerCamelCase__       (						self :					Dict       ,		lowerCAmelCase :					Node       ,		lowerCAmelCase :					Node		)     ->					Path:


     '''simple docstring'''




     SCREAMING_SNAKE_CASE_: int     			=self.fwd_bfs.retrace_path(lowerCAmelCase		)
     SCREAMING_SNAKE_CASE_: Tuple     			=self.bwd_bfs.retrace_path(lowerCAmelCase		)
     bwd_path.pop()
     bwd_path.reverse()
     SCREAMING_SNAKE_CASE_: Any     			=fwd_path + bwd_path
     return path


if __name__ == "__main__":
   # all coordinates are given in format [y,x]
   import doctest

   doctest.testmod()
   _UpperCAmelCase     =			(0, 0)
   _UpperCAmelCase     =			(len(grid) - 1, len(grid[0]) - 1)
   for elem in grid:
      print(elem)

   _UpperCAmelCase     =			time.time()
   _UpperCAmelCase     =			BreadthFirstSearch(init, goal)
   _UpperCAmelCase     =			bfs.search()
   _UpperCAmelCase     =			time.time() - start_bfs_time

   print("""Unidirectional BFS computation time : """, bfs_time)

   _UpperCAmelCase     =			time.time()
   _UpperCAmelCase     =			BidirectionalBreadthFirstSearch(init, goal)
   _UpperCAmelCase     =			bd_bfs.search()
   _UpperCAmelCase     =			time.time() - start_bd_bfs_time

   print("""Bidirectional BFS computation time : """, bd_bfs_time)








"""simple docstring"""
def      __magic_name__				(							lowercase							,			lowercase ):
   return int((input_a, input_a).count(0 ) == 0 )





def      __magic_name__				(							):
   assert and_gate(0							,			0 ) == 0
   assert and_gate(0							,			1 ) == 0
   assert and_gate(1							,			0 ) == 0
   assert and_gate(1							,			1 ) == 1


if __name__ == "__main__":
   test_and_gate()
   print(and_gate(1, 0))
   print(and_gate(0, 0))
   print(and_gate(0, 1))
   print(and_gate(1, 1))



