





from ..utils import DummyObject, requires_backends


class 						lowerCamelCase       (metaclass=__lowerCamelCase      ):







							"""simple docstring"""




							UpperCAmelCase_      						=   ["torch", "torchsde"]






							def __init__( self     :					Tuple,			*_UpperCAmelCase     :					List[str],			**_UpperCAmelCase     :					Dict						)				->			Any:





														"""simple docstring"""
														requires_backends(self,			["torch", "torchsde"]						)






							@classmethod
							def  A_     ( cls     :					Union[str, Any],			*_UpperCAmelCase     :					int,			**_UpperCAmelCase     :					int						)				->			str:





														"""simple docstring"""
														requires_backends(cls,			["torch", "torchsde"]						)






							@classmethod
							def  A_     ( cls     :					str,			*_UpperCAmelCase     :					int,			**_UpperCAmelCase     :					Union[str, Any]						)				->			Tuple:





														"""simple docstring"""
														requires_backends(cls,			["torch", "torchsde"]						)













from __future__ import annotations

import time

_lowerCamelCase :    Tuple  							= list[tuple[int, int]]

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


class 						lowerCamelCase       :







							"""simple docstring"""




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





														"""simple docstring"""
														SCREAMING_SNAKE_CASE__       :      List[Any]     =						pos_x
														SCREAMING_SNAKE_CASE__       :      List[Any]     =						pos_y
														SCREAMING_SNAKE_CASE__       :      str     =						(pos_y, pos_x)
														SCREAMING_SNAKE_CASE__       :      Dict     =						goal_x
														SCREAMING_SNAKE_CASE__       :      List[Any]     =						goal_y
														SCREAMING_SNAKE_CASE__       :      str     =						parent


class 						lowerCamelCase       :







							"""simple docstring"""




							def __init__( self     :					Dict,			_UpperCAmelCase     :					tuple[int, int],			_UpperCAmelCase     :					tuple[int, int]						)				->			Any:





														"""simple docstring"""
														SCREAMING_SNAKE_CASE__       :      str     =						Node(start[1],			start[0],			goal[1],			goal[0],			_UpperCAmelCase						)
														SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						Node(goal[1],			goal[0],			goal[1],			goal[0],			_UpperCAmelCase						)

														SCREAMING_SNAKE_CASE__       :      Optional[int]     =						[self.start]
														SCREAMING_SNAKE_CASE__       :      str     =						False






							def  A_     ( self     :					Dict						)				->			Path | None:





														"""simple docstring"""
														while self.node_queue:
																					SCREAMING_SNAKE_CASE__       :      int     =						self.node_queue.pop(0						)

																					if current_node.pos == self.target.pos:
																												SCREAMING_SNAKE_CASE__       :      Dict     =						True
																												return self.retrace_path(_UpperCAmelCase						)

																					SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						self.get_successors(_UpperCAmelCase						)

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

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






							def  A_     ( self     :					Any,			_UpperCAmelCase     :					Node						)				->			list[Node]:





														"""simple docstring"""
														SCREAMING_SNAKE_CASE__       :      Dict     =						[]
														for action in delta:
																					SCREAMING_SNAKE_CASE__       :      str     =						parent.pos_x + action[1]
																					SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						parent.pos_y + action[0]
																					if not (0 <= pos_x <= len(grid[0]						) - 1 and 0 <= pos_y <= len(_UpperCAmelCase						) - 1):
																												continue

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

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






							def  A_     ( self     :					List[str],			_UpperCAmelCase     :					Node | None						)				->			Path:





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


class 						lowerCamelCase       :







							"""simple docstring"""




							def __init__( self     :					List[str],			_UpperCAmelCase     :					Union[str, Any],			_UpperCAmelCase     :					List[str]						)				->			List[str]:





														"""simple docstring"""
														SCREAMING_SNAKE_CASE__       :      Any     =						BreadthFirstSearch(_UpperCAmelCase,			_UpperCAmelCase						)
														SCREAMING_SNAKE_CASE__       :      Optional[Any]     =						BreadthFirstSearch(_UpperCAmelCase,			_UpperCAmelCase						)
														SCREAMING_SNAKE_CASE__       :      Dict     =						False






							def  A_     ( self     :					List[str]						)				->			Path | None:





														"""simple docstring"""
														while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
																					SCREAMING_SNAKE_CASE__       :      int     =						self.fwd_bfs.node_queue.pop(0						)
																					SCREAMING_SNAKE_CASE__       :      Optional[int]     =						self.bwd_bfs.node_queue.pop(0						)

																					if current_bwd_node.pos == current_fwd_node.pos:
																												SCREAMING_SNAKE_CASE__       :      List[Any]     =						True
																												return self.retrace_bidirectional_path(
																												    _UpperCAmelCase,			_UpperCAmelCase						)

																					SCREAMING_SNAKE_CASE__       :      Optional[Any]     =						current_bwd_node
																					SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						current_fwd_node

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

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

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






							def  A_     ( self     :					int,			_UpperCAmelCase     :					Node,			_UpperCAmelCase     :					Node						)				->			Path:





														"""simple docstring"""
														SCREAMING_SNAKE_CASE__       :      str     =						self.fwd_bfs.retrace_path(_UpperCAmelCase						)
														SCREAMING_SNAKE_CASE__       :      Any     =						self.bwd_bfs.retrace_path(_UpperCAmelCase						)
														bwd_path.pop()
														bwd_path.reverse()
														SCREAMING_SNAKE_CASE__       :      List[Any]     =						fwd_path + bwd_path
														return path


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

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

		_lowerCamelCase :    Dict  							= time.time()
		_lowerCamelCase :    List[Any]  							= BreadthFirstSearch(init, goal)
		_lowerCamelCase :    Optional[Any]  							= bfs.search()
		_lowerCamelCase :    Dict  							= time.time() - start_bfs_time

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

		_lowerCamelCase :    str  							= time.time()
		_lowerCamelCase :    Dict  							= BidirectionalBreadthFirstSearch(init, goal)
		_lowerCamelCase :    Optional[Any]  							= bd_bfs.search()
		_lowerCamelCase :    Optional[Any]  							= time.time() - start_bd_bfs_time

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






