





'''simple docstring'''






from __future__ import annotations

import time

A   : Any             =			list[tuple[int, int]]

A   : Optional[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],
]

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







class 			lowerCamelCase					:


					def __init__(					self	:  Optional[Any]       ,     __snake_case	:  int       ,     __snake_case	:  int       ,     __snake_case	:  int       ,     __snake_case	:  int       ,     __snake_case	:  Node | None       ):





											'''simple docstring'''





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







class 			lowerCamelCase					:


					def __init__(					self	:  Union[str, Any]       ,     __snake_case	:  tuple[int, int]       ,     __snake_case	:  tuple[int, int]       ):





											'''simple docstring'''





											_snake_case:   Optional[int]  					=		Node(start[1]       ,     start[0]       ,     goal[1]       ,     goal[0]       ,     __snake_case       )
											_snake_case:   List[str]  					=		Node(goal[1]       ,     goal[0]       ,     goal[1]       ,     goal[0]       ,     __snake_case       )

											_snake_case:   Union[str, Any]  					=		[self.start]
											_snake_case:   Any  					=		False


					def    SCREAMING_SNAKE_CASE_		(					self	:  Union[str, Any]       ):





											'''simple docstring'''





											while self.node_queue:
																	_snake_case:   int  					=		self.node_queue.pop(0       )

																	if current_node.pos == self.target.pos:
																							_snake_case:   Union[str, Any]  					=		True
																							return self.retrace_path(__snake_case       )

																	_snake_case:   int  					=		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    SCREAMING_SNAKE_CASE_		(					self	:  Optional[Any]       ,     __snake_case	:  Node       ):





											'''simple docstring'''





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





											'''simple docstring'''





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







class 			lowerCamelCase					:


					def __init__(					self	:  Dict       ,     __snake_case	:  List[Any]       ,     __snake_case	:  int       ):





											'''simple docstring'''





											_snake_case:   Optional[int]  					=		BreadthFirstSearch(__snake_case       ,     __snake_case       )
											_snake_case:   Union[str, Any]  					=		BreadthFirstSearch(__snake_case       ,     __snake_case       )
											_snake_case:   str  					=		False


					def    SCREAMING_SNAKE_CASE_		(					self	:  Tuple       ):





											'''simple docstring'''





											while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
																	_snake_case:   Union[str, Any]  					=		self.fwd_bfs.node_queue.pop(0       )
																	_snake_case:   str  					=		self.bwd_bfs.node_queue.pop(0       )

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

																	_snake_case:   Optional[int]  					=		current_bwd_node
																	_snake_case:   List[Any]  					=		current_fwd_node

																	_snake_case:   Any  					=		{
																	    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    SCREAMING_SNAKE_CASE_		(					self	:  List[Any]       ,     __snake_case	:  Node       ,     __snake_case	:  Node       ):





											'''simple docstring'''





											_snake_case:   Optional[int]  					=		self.fwd_bfs.retrace_path(__snake_case       )
											_snake_case:   List[str]  					=		self.bwd_bfs.retrace_path(__snake_case       )
											bwd_path.pop()
											bwd_path.reverse()
											_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()
		A   : str             =			(0, 0)
		A   : str             =			(len(grid) - 1, len(grid[0]) - 1)
		for elem in grid:
				print(elem)

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

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

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

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












'''simple docstring'''






from __future__ import annotations

A   : Union[str, Any]             =			[-10, -5, 0, 5, 5.1, 11, 13, 21, 3, 4, -21, -10, -5, -1, 0]
A   : Optional[int]             =			[-5, 0, 5, 5.1, 11, 13, 21, -1, 4, -1, -10, -5, -1, 0, -1]





def       lowercase_      (		lowercase__						)   ->list[float]:
						_snake_case:   Tuple  					=		[]
						_snake_case:   List[Any]  					=		len(lowercase__						)

						for i in range(lowercase__						):
												_snake_case:   float  					=		-1
												for j in range(i + 1				,  lowercase__						):
																		if arr[i] < arr[j]:
																								_snake_case:   List[str]  					=		arr[j]
																								break
												result.append(lowercase__						)
						return result





def       lowercase_      (		lowercase__						)   ->list[float]:
						_snake_case:   Tuple  					=		[]
						for i, outer in enumerate(lowercase__						):
												_snake_case:   float  					=		-1
												for inner in arr[i + 1 :]:
																		if outer < inner:
																								_snake_case:   List[Any]  					=		inner
																								break
												result.append(lowercase__						)
						return result





def       lowercase_      (		lowercase__						)   ->list[float]:
						_snake_case:   int  					=		len(lowercase__						)
						_snake_case:   list[float]  					=		[]
						_snake_case:   list[float]  					=		[-1] * arr_size

						for index in reversed(range(lowercase__						)						):
												if stack:
																		while stack[-1] <= arr[index]:
																								stack.pop()
																								if not stack:
																														break
												if stack:
																		_snake_case:   Dict  					=		stack[-1]
												stack.append(arr[index]						)
						return result


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

		testmod()
		print(next_greatest_element_slow(arr))
		print(next_greatest_element_fast(arr))
		print(next_greatest_element(arr))

		A   : Union[str, Any]             =			(
		    'from __main__ import arr, next_greatest_element_slow, '
		    'next_greatest_element_fast, next_greatest_element'
		)
		print(
		    'next_greatest_element_slow():',
		    timeit('next_greatest_element_slow(arr)', setup=setup),
		)
		print(
		    'next_greatest_element_fast():',
		    timeit('next_greatest_element_fast(arr)', setup=setup),
		)
		print(
		    '     next_greatest_element():',
		    timeit('next_greatest_element(arr)', setup=setup),
		)





