


from __future__ import annotations

import time

UpperCamelCase__ =						list[tuple[int, int]]

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

UpperCamelCase__ =						[[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right
class 			_lowerCAmelCase   :






			"""simple docstring"""





			def __init__(				self	:       List[Any]			,     lowercase	:       str			,     lowercase	:       str			,     lowercase	:       Union[str, Any]			,     lowercase	:       Tuple			,     lowercase	:       Optional[int]   )						->					Dict:
									"""simple docstring"""







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





class 			_lowerCAmelCase   :






			"""simple docstring"""





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







									__lowercase					=				Node(start[1]			,     start[0]			,     goal[1]			,     goal[0]			,     _SCREAMING_SNAKE_CASE   )
									__lowercase					=				Node(goal[1]			,     goal[0]			,     goal[1]			,     goal[0]			,     _SCREAMING_SNAKE_CASE   )

									__lowercase					=				[self.start]
									__lowercase					=				False





			def 		snake_case__			(				self	:       int   )						->					Path | None:
									"""simple docstring"""







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

															if current_node.pos == self.target.pos:
																					__lowercase					=				True
																					return self.retrace_path(_SCREAMING_SNAKE_CASE   )

															__lowercase					=				self.get_successors(_SCREAMING_SNAKE_CASE   )

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

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





			def 		snake_case__			(				self	:       Optional[Any]			,     lowercase	:       Optional[Any]   )						->					list[Node]:
									"""simple docstring"""







									__lowercase					=				[]
									for action in delta:
															__lowercase					=				parent.pos_x + action[1]
															__lowercase					=				parent.pos_y + action[0]
															if not (0 <= pos_x <= len(grid[0]   ) - 1 and 0 <= pos_y <= len(_SCREAMING_SNAKE_CASE   ) - 1):
																					continue

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

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







			def 		snake_case__			(				self	:       List[Any]			,     lowercase	:       Dict   )						->					Path:
									"""simple docstring"""







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





class 			_lowerCAmelCase   :






			"""simple docstring"""





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







									__lowercase					=				BreadthFirstSearch(_SCREAMING_SNAKE_CASE			,     _SCREAMING_SNAKE_CASE   )
									__lowercase					=				BreadthFirstSearch(_SCREAMING_SNAKE_CASE			,     _SCREAMING_SNAKE_CASE   )
									__lowercase					=				False





			def 		snake_case__			(				self	:       Optional[Any]   )						->					Path | None:
									"""simple docstring"""







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

															if current_bwd_node.pos == current_fwd_node.pos:
																					__lowercase					=				True
																					return self.retrace_bidirectional_path(
																					    _SCREAMING_SNAKE_CASE			,     _SCREAMING_SNAKE_CASE   )

															__lowercase					=				current_bwd_node
															__lowercase					=				current_fwd_node

															__lowercase					=				{
															    self.fwd_bfs: self.fwd_bfs.get_successors(_SCREAMING_SNAKE_CASE   ),
															    self.bwd_bfs: self.bwd_bfs.get_successors(_SCREAMING_SNAKE_CASE   ),
															}

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

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







			def 		snake_case__			(				self	:       Any			,     lowercase	:       Dict			,     lowercase	:       List[str]   )						->					Path:
									"""simple docstring"""







									__lowercase					=				self.fwd_bfs.retrace_path(_SCREAMING_SNAKE_CASE   )
									__lowercase					=				self.bwd_bfs.retrace_path(_SCREAMING_SNAKE_CASE   )
									bwd_path.pop()
									bwd_path.reverse()
									__lowercase					=				fwd_path + bwd_path
									return path


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

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

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

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

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

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










import unittest

import numpy as np






def  UpperCAmelCase__    (    lowercase__						,       lowercase__						,       lowercase__						,       lowercase__ = None						,       ) ->      np.ndarray:
						__lowercase					=				np.shape(lowercase__   )
						__lowercase					=				np.shape(lowercase__   )
						__lowercase					=				np.shape(lowercase__   )

						if shape_a[0] != shape_b[0]:
												__lowercase					=				(
												    """Expected the same number of rows for A and B. """
												    F"Instead found A of size {shape_a} and B of size {shape_b}"
												)
												raise ValueError(lowercase__   )

						if shape_b[1] != shape_c[1]:
												__lowercase					=				(
												    """Expected the same number of columns for B and C. """
												    F"Instead found B of size {shape_b} and C of size {shape_c}"
												)
												raise ValueError(lowercase__   )

						__lowercase					=				pseudo_inv
						if a_inv is None:
												try:
																		__lowercase					=				np.linalg.inv(lowercase__   )
												except np.linalg.LinAlgError:
																		raise ValueError(
																		    """Input matrix A is not invertible. Cannot compute Schur complement."""   )

						return mat_c - mat_b.T @ a_inv @ mat_b
class 			_lowerCAmelCase   ( unittest.TestCase			):






			"""simple docstring"""





			def 		snake_case__			(				self	:       Dict   )						->					None:
									"""simple docstring"""







									__lowercase					=				np.array([[1, 2, 1], [2, 1, 2], [3, 2, 4]]   )
									__lowercase					=				np.array([[0, 3], [3, 0], [2, 3]]   )
									__lowercase					=				np.array([[2, 1], [6, 3]]   )

									__lowercase					=				schur_complement(lowercase			,     lowercase			,     lowercase   )

									__lowercase					=				np.block([[a, b], [b.T, c]]   )

									__lowercase					=				np.linalg.det(lowercase   )
									__lowercase					=				np.linalg.det(lowercase   )
									__lowercase					=				np.linalg.det(lowercase   )

									self.assertAlmostEqual(lowercase			,     det_a * det_s   )





			def 		snake_case__			(				self	:       Tuple   )						->					None:
									"""simple docstring"""







									__lowercase					=				np.array([[1, 2, 1], [2, 1, 2], [3, 2, 4]]   )
									__lowercase					=				np.array([[0, 3], [3, 0], [2, 3]]   )
									__lowercase					=				np.array([[2, 1], [6, 3]]   )

									with self.assertRaises(lowercase   ):
															schur_complement(lowercase			,     lowercase			,     lowercase   )







			def 		snake_case__			(				self	:       Tuple   )						->					None:
									"""simple docstring"""







									__lowercase					=				np.array([[1, 2, 1], [2, 1, 2], [3, 2, 4]]   )
									__lowercase					=				np.array([[0, 3], [3, 0], [2, 3]]   )
									__lowercase					=				np.array([[2, 1, 3], [6, 3, 5]]   )

									with self.assertRaises(lowercase   ):
															schur_complement(lowercase			,     lowercase			,     lowercase   )


if __name__ == "__main__":
			import doctest

			doctest.testmod()
			unittest.main()





