






from collections.abc import Callable

def _UpperCAmelCase   (	a						:	Callable[[float], float]  ,					a						:	float  ,					a						:	float ):
							snake_case__	  =       a
							snake_case__	  =       b
							if function(a ) == 0:  # one of the a or b is a root for the function
														return a
							elif function(a ) == 0:
														return b
							elif (
							    function(a ) * function(a ) > 0
							):  # if none of these are root and they are both positive or negative,
														# then this algorithm can't find the root
														raise ValueError("""could not find root in given interval.""" )
							else:
														snake_case__	  =       start + (end - start) / 2.0
														while abs(start - mid ) > 10**-7:  # until precisely equals to 10^-7
																					if function(a ) == 0:
																												return mid
																					elif function(a ) * function(a ) < 0:
																												snake_case__	  =       mid
																					else:
																												snake_case__	  =       mid
																					snake_case__	  =       start + (end - start) / 2.0
														return mid

def _UpperCAmelCase   (	a						:	float ):
							return x**3 - 2 * x - 5


if __name__ == "__main__":
	print(bisection(f, 1, 1_0_0_0))

	import doctest

	doctest.testmod()








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)
