



from __future__ import annotations

import time

_lowercase						: Optional[Any]     						=list[tuple[int, int]]

_lowercase						: List[str]     						=[
    [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],
]

_lowercase						: Any     						=[[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

class   snake_case__							:







						"""simple docstring"""




						def __init__(  self   ,  __lowercase   ,  __lowercase   ,  __lowercase   ,  __lowercase   ,  __lowercase    )   -> List[Any]:
									"""simple docstring"""




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




class   snake_case__							:







						"""simple docstring"""




						def __init__(  self   ,  __lowercase   ,  __lowercase    )   -> Any:
									"""simple docstring"""




									a__  :		List[str]					=    Node(start[1]   ,  start[0]   ,  goal[1]   ,  goal[0]   ,  __UpperCAmelCase    )
									a__  :		Any					=    Node(goal[1]   ,  goal[0]   ,  goal[1]   ,  goal[0]   ,  __UpperCAmelCase    )

									a__  :		Any					=    [self.start]
									a__  :		Optional[Any]					=    False

						def 				SCREAMING_SNAKE_CASE__(  self    )   -> Optional[Any]:
									"""simple docstring"""




									while self.node_queue:
												a__  :		List[Any]					=    self.node_queue.pop(0    )

												if current_node.pos == self.target.pos:
															a__  :		Dict					=    True
															return self.retrace_path(__UpperCAmelCase    )

												a__  :		Dict					=    self.get_successors(__UpperCAmelCase    )

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

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

						def 				SCREAMING_SNAKE_CASE__(  self   ,  __lowercase    )   -> Union[str, Any]:
									"""simple docstring"""




									a__  :		List[str]					=    []
									for action in delta:
												a__  :		str					=    parent.pos_x + action[1]
												a__  :		Optional[int]					=    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 				SCREAMING_SNAKE_CASE__(  self   ,  __lowercase    )   -> List[str]:
									"""simple docstring"""




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




class   snake_case__							:







						"""simple docstring"""




						def __init__(  self   ,  __lowercase   ,  __lowercase    )   -> Optional[Any]:
									"""simple docstring"""




									a__  :		int					=    BreadthFirstSearch(__UpperCAmelCase   ,  __UpperCAmelCase    )
									a__  :		Union[str, Any]					=    BreadthFirstSearch(__UpperCAmelCase   ,  __UpperCAmelCase    )
									a__  :		Union[str, Any]					=    False

						def 				SCREAMING_SNAKE_CASE__(  self    )   -> Optional[Any]:
									"""simple docstring"""




									while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
												a__  :		List[Any]					=    self.fwd_bfs.node_queue.pop(0    )
												a__  :		List[str]					=    self.bwd_bfs.node_queue.pop(0    )

												if current_bwd_node.pos == current_fwd_node.pos:
															a__  :		Dict					=    True
															return self.retrace_bidirectional_path(
															    __UpperCAmelCase   ,  __UpperCAmelCase    )

												a__  :		Tuple					=    current_bwd_node
												a__  :		int					=    current_fwd_node

												a__  :		Any					=    {
												    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 				SCREAMING_SNAKE_CASE__(  self   ,  __lowercase   ,  __lowercase    )   -> Any:
									"""simple docstring"""




									a__  :		Dict					=    self.fwd_bfs.retrace_path(__UpperCAmelCase    )
									a__  :		Union[str, Any]					=    self.bwd_bfs.retrace_path(__UpperCAmelCase    )
									bwd_path.pop()
									bwd_path.reverse()
									a__  :		List[Any]					=    fwd_path + bwd_path
									return path


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

		doctest.testmod()
		_lowercase						: Union[str, Any]     						=(0, 0)
		_lowercase						: List[Any]     						=(len(grid) - 1, len(grid[0]) - 1)
		for elem in grid:
				print(elem)

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

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

		_lowercase						: List[Any]     						=time.time()
		_lowercase						: Any     						=BidirectionalBreadthFirstSearch(init, goal)
		_lowercase						: Any     						=bd_bfs.search()
		_lowercase						: List[str]     						=time.time() - start_bd_bfs_time

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











"""simple docstring"""





def 					__A  (_SCREAMING_SNAKE_CASE     )   ->str:





  """simple docstring"""


  lowerCAmelCase__     :List[Any]											=				int(_SCREAMING_SNAKE_CASE     )
  if decimal in (0, 1):  # Exit cases for the recursion
    return str(_SCREAMING_SNAKE_CASE     )
  lowerCAmelCase__				,							lowerCAmelCase__     :int											=				divmod(_SCREAMING_SNAKE_CASE	,  2     )
  return binary_recursive(_SCREAMING_SNAKE_CASE     ) + str(_SCREAMING_SNAKE_CASE     )
def 					__A  (_SCREAMING_SNAKE_CASE     )   ->str:





  """simple docstring"""


  lowerCAmelCase__     :str											=				str(_SCREAMING_SNAKE_CASE     ).strip()
  if not number:
    raise ValueError('No input value was provided'     )
  lowerCAmelCase__     :Dict											=				'-' if number.startswith('-'     ) else ''
  lowerCAmelCase__     :int											=				number.lstrip('-'     )
  if not number.isnumeric():
    raise ValueError('Input value is not an integer'     )
  return F"{negative}0b{binary_recursive(int(_SCREAMING_SNAKE_CASE     )     )}"


if __name__ == "__main__":
  from doctest import testmod

  testmod()
