






from __future__ import annotations

from typing import Any


class    _lowerCAmelCase			:



				"""simple docstring"""



				def __init__(      self    :    int			,		UpperCamelCase__    :    int			,		UpperCamelCase__    :    int			,		UpperCamelCase__    :    float = 0):






											'''simple docstring'''







											snake_case__  , snake_case__	  =       row, column
											snake_case__	  =       [[default_value for c in range(UpperCamelCase__)] for r in range(UpperCamelCase__)]



				def __str__(      self    :    List[str]):






											'''simple docstring'''







											snake_case__	  =       F'''Matrix consist of {self.row} rows and {self.column} columns\n'''

											# Make string identifier
											snake_case__	  =       0
											for row_vector in self.array:
																		for obj in row_vector:
																									snake_case__	  =       max(UpperCamelCase__			,		len(str(UpperCamelCase__)))
											snake_case__	  =       F'''%{max_element_length}s'''

											# Make string and return
											def single_line(UpperCamelCase__    :    list[float]) -> str:
																		nonlocal string_format_identifier
																		snake_case__	  =       """["""
																		line += ", ".join(string_format_identifier % (obj,) for obj in row_vector)
																		line += "]"
																		return line

											s += "\n".join(single_line(UpperCamelCase__) for row_vector in self.array)
											return s



				def __repr__(      self    :    int):






											'''simple docstring'''







											return str(self)



				def 					__magic_name__							(      self    :    Tuple			,		UpperCamelCase__    :    tuple[int, int]):






											'''simple docstring'''







											if not (isinstance(UpperCamelCase__			,		(list, tuple)) and len(UpperCamelCase__) == 2):
																		return False
											elif not (0 <= loc[0] < self.row and 0 <= loc[1] < self.column):
																		return False
											else:
																		return True



				def __getitem__(      self    :    str			,		UpperCamelCase__    :    tuple[int, int]):






											'''simple docstring'''







											assert self.validate_indicies(UpperCamelCase__)
											return self.array[loc[0]][loc[1]]



				def __setitem__(      self    :    Dict			,		UpperCamelCase__    :    tuple[int, int]			,		UpperCamelCase__    :    float):






											'''simple docstring'''







											assert self.validate_indicies(UpperCamelCase__)
											snake_case__	  =       value



				def __add__(      self    :    Optional[int]			,		UpperCamelCase__    :    Matrix):






											'''simple docstring'''







											assert isinstance(UpperCamelCase__			,		UpperCamelCase__)
											assert self.row == another.row and self.column == another.column

											# Add
											snake_case__	  =       Matrix(self.row			,		self.column)
											for r in range(self.row):
																		for c in range(self.column):
																									snake_case__	  =       self[r, c] + another[r, c]
											return result



				def __neg__(      self    :    Optional[int]):






											'''simple docstring'''







											snake_case__	  =       Matrix(self.row			,		self.column)
											for r in range(self.row):
																		for c in range(self.column):
																									snake_case__	  =       -self[r, c]
											return result



				def __sub__(      self    :    List[str]			,		UpperCamelCase__    :    Matrix):






											'''simple docstring'''







											return self + (-another)



				def __mul__(      self    :    Any			,		UpperCamelCase__    :    int | float | Matrix):






											'''simple docstring'''







											if isinstance(UpperCamelCase__			,		(int, float)):  # Scalar multiplication
																		snake_case__	  =       Matrix(self.row			,		self.column)
																		for r in range(self.row):
																									for c in range(self.column):
																																snake_case__	  =       self[r, c] * another
																		return result
											elif isinstance(UpperCamelCase__			,		UpperCamelCase__):  # Matrix multiplication
																		assert self.column == another.row
																		snake_case__	  =       Matrix(self.row			,		another.column)
																		for r in range(self.row):
																									for c in range(another.column):
																																for i in range(self.column):
																																							result[r, c] += self[r, i] * another[i, c]
																		return result
											else:
																		snake_case__	  =       F'''Unsupported type given for another ({type(UpperCamelCase__)})'''
																		raise TypeError(UpperCamelCase__)



				def 					__magic_name__							(      self    :    List[str]):






											'''simple docstring'''







											snake_case__	  =       Matrix(self.column			,		self.row)
											for r in range(self.row):
																		for c in range(self.column):
																									snake_case__	  =       self[r, c]
											return result



				def 					__magic_name__							(      self    :    Dict			,		UpperCamelCase__    :    Matrix			,		UpperCamelCase__    :    Matrix):






											'''simple docstring'''







											assert isinstance(UpperCamelCase__			,		UpperCamelCase__) and isinstance(UpperCamelCase__			,		UpperCamelCase__)
											assert self.row == self.column == u.row == v.row  # u, v should be column vector
											assert u.column == v.column == 1  # u, v should be column vector

											# Calculate
											snake_case__	  =       v.transpose()
											snake_case__	  =       (v_t * self * u)[0, 0] + 1
											if numerator_factor == 0:
																		return None  # It's not invertable
											return self - ((self * u) * (v_t * self) * (1.0 / numerator_factor))


# Testing
if __name__ == "__main__":

	def _UpperCAmelCase   (	):
								# a^(-1)
								snake_case__	  =       Matrix(3  ,					3  ,					0 )
								for i in range(3 ):
															snake_case__	  =       1
								print(F'''a^(-1) is {ainv}''' )
								# u, v
								snake_case__	  =       Matrix(3  ,					1  ,					0 )
								snake_case__  , snake_case__  , snake_case__	  =       1, 2, -3
								snake_case__	  =       Matrix(3  ,					1  ,					0 )
								snake_case__  , snake_case__  , snake_case__	  =       4, -2, 5
								print(F'''u is {u}''' )
								print(F'''v is {v}''' )
								print(F'''uv^T is {u * v.transpose()}''' )
								# Sherman Morrison
								print(F'''(a + uv^T)^(-1) is {ainv.sherman_morrison(a  ,					a )}''' )

	def _UpperCAmelCase   (	):
								import doctest

								doctest.testmod()



	testa()








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    _lowerCAmelCase			:



				"""simple docstring"""



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






											'''simple docstring'''







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


class    _lowerCAmelCase			:



				"""simple docstring"""



				def __init__(      self    :    Optional[int]			,		UpperCamelCase__    :    tuple[int, int]			,		UpperCamelCase__    :    tuple[int, int]):






											'''simple docstring'''







											snake_case__	  =       Node(start[1]			,		start[0]			,		goal[1]			,		goal[0]			,		UpperCamelCase__)
											snake_case__	  =       Node(goal[1]			,		goal[0]			,		goal[1]			,		goal[0]			,		UpperCamelCase__)

											snake_case__	  =       [self.start]
											snake_case__	  =       False



				def 					__magic_name__							(      self    :    List[Any]):






											'''simple docstring'''







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

																		if current_node.pos == self.target.pos:
																									snake_case__	  =       True
																									return self.retrace_path(UpperCamelCase__)

																		snake_case__	  =       self.get_successors(UpperCamelCase__)

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

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



				def 					__magic_name__							(      self    :    Any			,		UpperCamelCase__    :    Node):






											'''simple docstring'''







											snake_case__	  =       []
											for action in delta:
																		snake_case__	  =       parent.pos_x + action[1]
																		snake_case__	  =       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 					__magic_name__							(      self    :    str			,		UpperCamelCase__    :    Node | None):






											'''simple docstring'''







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


class    _lowerCAmelCase			:



				"""simple docstring"""



				def __init__(      self    :    str			,		UpperCamelCase__    :    Optional[Any]			,		UpperCamelCase__    :    Any):






											'''simple docstring'''







											snake_case__	  =       BreadthFirstSearch(UpperCamelCase__			,		UpperCamelCase__)
											snake_case__	  =       BreadthFirstSearch(UpperCamelCase__			,		UpperCamelCase__)
											snake_case__	  =       False



				def 					__magic_name__							(      self    :    Any):






											'''simple docstring'''







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

																		if current_bwd_node.pos == current_fwd_node.pos:
																									snake_case__	  =       True
																									return self.retrace_bidirectional_path(
																									    UpperCamelCase__			,		UpperCamelCase__)

																		snake_case__	  =       current_bwd_node
																		snake_case__	  =       current_fwd_node

																		snake_case__	  =       {
																		    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 					__magic_name__							(      self    :    Union[str, Any]			,		UpperCamelCase__    :    Node			,		UpperCamelCase__    :    Node):






											'''simple docstring'''







											snake_case__	  =       self.fwd_bfs.retrace_path(UpperCamelCase__)
											snake_case__	  =       self.bwd_bfs.retrace_path(UpperCamelCase__)
											bwd_path.pop()
											bwd_path.reverse()
											snake_case__	  =       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)
