

from __future__ import annotations

import time

a_    :						str    		=      list[tuple[int, int]]

a_    :						Optional[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],
]

a_    :						int    		=      [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right




class      UpperCamelCase :

    def __init__(			self :      List[str]							,    snake_case__ :      int							,    snake_case__ :      int							,    snake_case__ :      int							,    snake_case__ :      int							,    snake_case__ :      Node | None    ):

     """simple docstring"""






     SCREAMING_SNAKE_CASE								=			pos_x
     SCREAMING_SNAKE_CASE								=			pos_y
     SCREAMING_SNAKE_CASE								=			(pos_y, pos_x)
     SCREAMING_SNAKE_CASE								=			goal_x
     SCREAMING_SNAKE_CASE								=			goal_y
     SCREAMING_SNAKE_CASE								=			parent




class      UpperCamelCase :

    def __init__(			self :      str							,    snake_case__ :      tuple[int, int]							,    snake_case__ :      tuple[int, int]    ):

     """simple docstring"""






     SCREAMING_SNAKE_CASE								=			Node(start[1]							,    start[0]							,    goal[1]							,    goal[0]							,    snake_case__    )
     SCREAMING_SNAKE_CASE								=			Node(goal[1]							,    goal[0]							,    goal[1]							,    goal[0]							,    snake_case__    )

     SCREAMING_SNAKE_CASE								=			[self.start]
     SCREAMING_SNAKE_CASE								=			False

    def UpperCamelCase			(			self :      Optional[Any]    ):

     """simple docstring"""






     while self.node_queue:
      SCREAMING_SNAKE_CASE								=			self.node_queue.pop(0    )

      if current_node.pos == self.target.pos:
       SCREAMING_SNAKE_CASE								=			True
       return self.retrace_path(snake_case__    )

      SCREAMING_SNAKE_CASE								=			self.get_successors(snake_case__    )

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

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

    def UpperCamelCase			(			self :      List[Any]							,    snake_case__ :      Node    ):

     """simple docstring"""






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

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

      successors.append(
          Node(snake_case__							,    snake_case__							,    self.target.pos_y							,    self.target.pos_x							,    snake_case__    )    )
     return successors




    def UpperCamelCase			(			self :      Optional[Any]							,    snake_case__ :      Node | None    ):

     """simple docstring"""






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




class      UpperCamelCase :

    def __init__(			self :      Optional[int]							,    snake_case__ :      Optional[Any]							,    snake_case__ :      int    ):

     """simple docstring"""






     SCREAMING_SNAKE_CASE								=			BreadthFirstSearch(snake_case__							,    snake_case__    )
     SCREAMING_SNAKE_CASE								=			BreadthFirstSearch(snake_case__							,    snake_case__    )
     SCREAMING_SNAKE_CASE								=			False

    def UpperCamelCase			(			self :      int    ):

     """simple docstring"""






     while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
      SCREAMING_SNAKE_CASE								=			self.fwd_bfs.node_queue.pop(0    )
      SCREAMING_SNAKE_CASE								=			self.bwd_bfs.node_queue.pop(0    )

      if current_bwd_node.pos == current_fwd_node.pos:
       SCREAMING_SNAKE_CASE								=			True
       return self.retrace_bidirectional_path(
           snake_case__							,    snake_case__    )

      SCREAMING_SNAKE_CASE								=			current_bwd_node
      SCREAMING_SNAKE_CASE								=			current_fwd_node

      SCREAMING_SNAKE_CASE								=			{
          self.fwd_bfs: self.fwd_bfs.get_successors(snake_case__    ),
          self.bwd_bfs: self.bwd_bfs.get_successors(snake_case__    ),
      }

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

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




    def UpperCamelCase			(			self :      Optional[Any]							,    snake_case__ :      Node							,    snake_case__ :      Node    ):

     """simple docstring"""






     SCREAMING_SNAKE_CASE								=			self.fwd_bfs.retrace_path(snake_case__    )
     SCREAMING_SNAKE_CASE								=			self.bwd_bfs.retrace_path(snake_case__    )
     bwd_path.pop()
     bwd_path.reverse()
     SCREAMING_SNAKE_CASE								=			fwd_path + bwd_path
     return path


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

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

      a_    :						str    		=      time.time()
      a_    :						Optional[int]    		=      BreadthFirstSearch(init, goal)
      a_    :						List[str]    		=      bfs.search()
      a_    :						Tuple    		=      time.time() - start_bfs_time

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

      a_    :						Optional[int]    		=      time.time()
      a_    :						Optional[Any]    		=      BidirectionalBreadthFirstSearch(init, goal)
      a_    :						Optional[Any]    		=      bd_bfs.search()
      a_    :						int    		=      time.time() - start_bd_bfs_time

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




import random


def        __lowerCAmelCase    (       _UpperCamelCase		:  int		,							_UpperCamelCase		:  float		,							_UpperCamelCase		:  bool = False	)		->							dict:
 '''simple docstring'''


 SCREAMING_SNAKE_CASE								=			{i: [] for i in range(_UpperCamelCase	)}

 # if probability is greater or equal than 1, then generate a complete graph
 if probability >= 1:
  return complete_graph(_UpperCamelCase	)
 # if probability is lower or equal than 0, then return a graph without edges
 if probability <= 0:
  return graph

 # for each couple of nodes, add an edge from u to v
 # if the number randomly generated is greater than probability probability
 for i in range(_UpperCamelCase	):
  for j in range(i + 1		,							_UpperCamelCase	):
   if random.random() < probability:
    graph[i].append(_UpperCamelCase	)
    if not directed:
     # if the graph is undirected, add an edge in from j to i, either
     graph[j].append(_UpperCamelCase	)
 return graph


def        __lowerCAmelCase    (       _UpperCamelCase		:  int	)		->							dict:
 '''simple docstring'''


 return {
     i: [j for j in range(_UpperCamelCase	) if i != j] for i in range(_UpperCamelCase	)
 }


if __name__ == "__main__":
      import doctest

      doctest.testmod()

