
"""simple docstring"""

from __future__ import annotations

import time

_A						=			list[tuple[int, int]]

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






class 	_lowercase       :




	def __init__(			self		,			UpperCAmelCase_		,			UpperCAmelCase_		,			UpperCAmelCase_		,			UpperCAmelCase_		,			UpperCAmelCase_ )		->							Optional[int]:
			lowerCamelCase					:      Tuple          =   pos_x
			lowerCamelCase					:      List[str]          =   pos_y
			lowerCamelCase					:      Optional[int]          =   (pos_y, pos_x)
			lowerCamelCase					:      Tuple          =   goal_x
			lowerCamelCase					:      int          =   goal_y
			lowerCamelCase					:      Any          =   parent






class 	_lowercase       :




	def __init__(			self		,			UpperCAmelCase_		,			UpperCAmelCase_ )		->							int:
			lowerCamelCase					:      Optional[int]          =   Node(start[1]		,			start[0]		,			goal[1]		,			goal[0]		,			UpperCAmelCase_ )
			lowerCamelCase					:      Optional[Any]          =   Node(goal[1]		,			goal[0]		,			goal[1]		,			goal[0]		,			UpperCAmelCase_ )

			lowerCamelCase					:      Optional[int]          =   [self.start]
			lowerCamelCase					:      Dict          =   False




	def       _UpperCamelCase   (			self )		->							Path | None:
			while self.node_queue:
					lowerCamelCase					:      Optional[Any]          =   self.node_queue.pop(0 )

					if current_node.pos == self.target.pos:
							lowerCamelCase					:      List[str]          =   True
							return self.retrace_path(UpperCAmelCase_ )

					lowerCamelCase					:      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       _UpperCamelCase   (			self		,			UpperCAmelCase_ )		->							list[Node]:
			lowerCamelCase					:      Union[str, Any]          =   []
			for action in delta:
					lowerCamelCase					:      int          =   parent.pos_x + action[1]
					lowerCamelCase					:      Tuple          =   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       _UpperCamelCase   (			self		,			UpperCAmelCase_ )		->							Path:
			lowerCamelCase					:      str          =   node
			lowerCamelCase					:      List[str]          =   []
			while current_node is not None:
					path.append((current_node.pos_y, current_node.pos_x) )
					lowerCamelCase					:      str          =   current_node.parent
			path.reverse()
			return path






class 	_lowercase       :




	def __init__(			self		,			UpperCAmelCase_		,			UpperCAmelCase_ )		->							Optional[int]:
			lowerCamelCase					:      int          =   BreadthFirstSearch(UpperCAmelCase_		,			UpperCAmelCase_ )
			lowerCamelCase					:      Union[str, Any]          =   BreadthFirstSearch(UpperCAmelCase_		,			UpperCAmelCase_ )
			lowerCamelCase					:      Dict          =   False




	def       _UpperCamelCase   (			self )		->							Path | None:
			while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
					lowerCamelCase					:      Optional[int]          =   self.fwd_bfs.node_queue.pop(0 )
					lowerCamelCase					:      Optional[int]          =   self.bwd_bfs.node_queue.pop(0 )

					if current_bwd_node.pos == current_fwd_node.pos:
							lowerCamelCase					:      Dict          =   True
							return self.retrace_bidirectional_path(
							    UpperCAmelCase_		,			UpperCAmelCase_ )

					lowerCamelCase					:      Tuple          =   current_bwd_node
					lowerCamelCase					:      Optional[int]          =   current_fwd_node

					lowerCamelCase					:      Optional[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       _UpperCamelCase   (			self		,			UpperCAmelCase_		,			UpperCAmelCase_ )		->							Path:
			lowerCamelCase					:      str          =   self.fwd_bfs.retrace_path(UpperCAmelCase_ )
			lowerCamelCase					:      Any          =   self.bwd_bfs.retrace_path(UpperCAmelCase_ )
			bwd_path.pop()
			bwd_path.reverse()
			lowerCamelCase					:      List[Any]          =   fwd_path + bwd_path
			return path


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

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

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

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

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

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








"""simple docstring"""

def 		UpperCAmelCase (		a_,						a_      ):





		'''simple docstring'''


		while b:
				lowerCamelCase     ,   lowerCamelCase					:      Tuple          =   b, a % b
		return a
def 		UpperCAmelCase (		a_,						a_      ):





		'''simple docstring'''


		return a if b == 0 else euclidean_gcd_recursive(a_,						a % b      )
def 		UpperCAmelCase (		):





		'''simple docstring'''


		print(F"""euclidean_gcd(3, 5) = {euclidean_gcd(3,						5      )}"""      )
		print(F"""euclidean_gcd(5, 3) = {euclidean_gcd(5,						3      )}"""      )
		print(F"""euclidean_gcd(1, 3) = {euclidean_gcd(1,						3      )}"""      )
		print(F"""euclidean_gcd(3, 6) = {euclidean_gcd(3,						6      )}"""      )
		print(F"""euclidean_gcd(6, 3) = {euclidean_gcd(6,						3      )}"""      )

		print(F"""euclidean_gcd_recursive(3, 5) = {euclidean_gcd_recursive(3,						5      )}"""      )
		print(F"""euclidean_gcd_recursive(5, 3) = {euclidean_gcd_recursive(5,						3      )}"""      )
		print(F"""euclidean_gcd_recursive(1, 3) = {euclidean_gcd_recursive(1,						3      )}"""      )
		print(F"""euclidean_gcd_recursive(3, 6) = {euclidean_gcd_recursive(3,						6      )}"""      )
		print(F"""euclidean_gcd_recursive(6, 3) = {euclidean_gcd_recursive(6,						3      )}"""      )


if __name__ == "__main__":
					main()






