



from __future__ import annotations

import time

SCREAMING_SNAKE_CASE__       =      list[tuple[int, int]]

SCREAMING_SNAKE_CASE__       =      [
    [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],
]

SCREAMING_SNAKE_CASE__       =      [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right


class      __lowerCAmelCase     :
					"""simple docstring"""






					def __init__(     self					:       Dict				,					_snake_case					:       int				,					_snake_case					:       int				,					_snake_case					:       int				,					_snake_case					:       int				,					_snake_case					:       Node | None					):






								"""simple docstring"""


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







class      __lowerCAmelCase     :
					"""simple docstring"""






					def __init__(     self					:       Any				,					_snake_case					:       tuple[int, int]				,					_snake_case					:       tuple[int, int]					):






								"""simple docstring"""


								A__       =    Node(start[1]				,					start[0]				,					goal[1]				,					goal[0]				,					_snake_case					)
								A__       =    Node(goal[1]				,					goal[0]				,					goal[1]				,					goal[0]				,					_snake_case					)

								A__       =    [self.start]
								A__       =    False



					def     _a							(     self					:       Tuple					):






								"""simple docstring"""


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

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

											A__       =    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     _a							(     self					:       List[str]				,					_snake_case					:       Node					):






								"""simple docstring"""


								A__       =    []
								for action in delta:
											A__       =    parent.pos_x + action[1]
											A__       =    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     _a							(     self					:       Dict				,					_snake_case					:       Node | None					):






								"""simple docstring"""


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







class      __lowerCAmelCase     :
					"""simple docstring"""






					def __init__(     self					:       str				,					_snake_case					:       str				,					_snake_case					:       int					):






								"""simple docstring"""


								A__       =    BreadthFirstSearch(_snake_case				,					_snake_case					)
								A__       =    BreadthFirstSearch(_snake_case				,					_snake_case					)
								A__       =    False



					def     _a							(     self					:       List[str]					):






								"""simple docstring"""


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

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

											A__       =    current_bwd_node
											A__       =    current_fwd_node

											A__       =    {
											    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     _a							(     self					:       Optional[Any]				,					_snake_case					:       Node				,					_snake_case					:       Node					):






								"""simple docstring"""


								A__       =    self.fwd_bfs.retrace_path(_snake_case					)
								A__       =    self.bwd_bfs.retrace_path(_snake_case					)
								bwd_path.pop()
								bwd_path.reverse()
								A__       =    fwd_path + bwd_path
								return path


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

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

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

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

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

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









def A						(       __UpperCamelCase					)						->      bool:
			return number & 1 == 0


if __name__ == "__main__":
							import doctest

							doctest.testmod()




