





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 			UpperCamelCase_		:




     def __init__(		self				,						lowerCAmelCase_				,						lowerCAmelCase_				,						lowerCAmelCase_				,						lowerCAmelCase_				,						lowerCAmelCase_  )		->							Dict:
          _snake_case									=				pos_x
          _snake_case									=				pos_y
          _snake_case									=				(pos_y, pos_x)
          _snake_case									=				goal_x
          _snake_case									=				goal_y
          _snake_case									=				parent





class 			UpperCamelCase_		:




     def __init__(		self				,						lowerCAmelCase_				,						lowerCAmelCase_  )		->							str:
          _snake_case									=				Node(start[1]				,						start[0]				,						goal[1]				,						goal[0]				,						_SCREAMING_SNAKE_CASE  )
          _snake_case									=				Node(goal[1]				,						goal[0]				,						goal[1]				,						goal[0]				,						_SCREAMING_SNAKE_CASE  )

          _snake_case									=				[self.start]
          _snake_case									=				False




     def 	lowerCAmelCase			(		self  )		->							Path | None:
          while self.node_queue:
               _snake_case									=				self.node_queue.pop(0  )

               if current_node.pos == self.target.pos:
                    _snake_case									=				True
                    return self.retrace_path(_SCREAMING_SNAKE_CASE  )

               _snake_case									=				self.get_successors(_SCREAMING_SNAKE_CASE  )

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

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




     def 	lowerCAmelCase			(		self				,						lowerCAmelCase_  )		->							list[Node]:
          _snake_case									=				[]
          for action in delta:
               _snake_case									=				parent.pos_x + action[1]
               _snake_case									=				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				,						_SCREAMING_SNAKE_CASE  )  )
          return successors






     def 	lowerCAmelCase			(		self				,						lowerCAmelCase_  )		->							Path:
          _snake_case									=				node
          _snake_case									=				[]
          while current_node is not None:
               path.append((current_node.pos_y, current_node.pos_x)  )
               _snake_case									=				current_node.parent
          path.reverse()
          return path





class 			UpperCamelCase_		:




     def __init__(		self				,						lowerCAmelCase_				,						lowerCAmelCase_  )		->							Any:
          _snake_case									=				BreadthFirstSearch(_SCREAMING_SNAKE_CASE				,						_SCREAMING_SNAKE_CASE  )
          _snake_case									=				BreadthFirstSearch(_SCREAMING_SNAKE_CASE				,						_SCREAMING_SNAKE_CASE  )
          _snake_case									=				False




     def 	lowerCAmelCase			(		self  )		->							Path | None:
          while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
               _snake_case									=				self.fwd_bfs.node_queue.pop(0  )
               _snake_case									=				self.bwd_bfs.node_queue.pop(0  )

               if current_bwd_node.pos == current_fwd_node.pos:
                    _snake_case									=				True
                    return self.retrace_bidirectional_path(
                        _SCREAMING_SNAKE_CASE				,						_SCREAMING_SNAKE_CASE  )

               _snake_case									=				current_bwd_node
               _snake_case									=				current_fwd_node

               _snake_case									=				{
                   self.fwd_bfs: self.fwd_bfs.get_successors(_SCREAMING_SNAKE_CASE  ),
                   self.bwd_bfs: self.bwd_bfs.get_successors(_SCREAMING_SNAKE_CASE  ),
               }

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

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






     def 	lowerCAmelCase			(		self				,						lowerCAmelCase_				,						lowerCAmelCase_  )		->							Path:
          _snake_case									=				self.fwd_bfs.retrace_path(_SCREAMING_SNAKE_CASE  )
          _snake_case									=				self.bwd_bfs.retrace_path(_SCREAMING_SNAKE_CASE  )
          bwd_path.pop()
          bwd_path.reverse()
          _snake_case									=				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)










import random





def 						lowerCamelCase__     (     UpperCamelCase__			:       list       ,    UpperCamelCase__			:       List[Any]						)			-> tuple:



					'''simple docstring'''




					_snake_case							,     _snake_case							,     _snake_case									=				[], [], []
					for element in data:
										if element < pivot:
															less.append(UpperCamelCase__						)
										elif element > pivot:
															greater.append(UpperCamelCase__						)
										else:
															equal.append(UpperCamelCase__						)
					return less, equal, greater





def 						lowerCamelCase__     (     UpperCamelCase__			:       list       ,    UpperCamelCase__			:       int						)			-> Dict:



					'''simple docstring'''




					if index >= len(UpperCamelCase__						) or index < 0:
										return None

					_snake_case									=				items[random.randint(0       ,    len(UpperCamelCase__						) - 1						)]
					_snake_case									=				0
					_snake_case							,     _snake_case							,     _snake_case									=				_partition(UpperCamelCase__       ,    UpperCamelCase__						)
					_snake_case									=				len(UpperCamelCase__						)
					_snake_case									=				len(UpperCamelCase__						)

					# index is the pivot
					if m <= index < m + count:
										return pivot
					# must be in smaller
					elif m > index:
										return quick_select(UpperCamelCase__       ,    UpperCamelCase__						)
					# must be in larger
					else:
										return quick_select(UpperCamelCase__       ,    index - (m + count)						)



