


from __future__ import annotations

import time

SCREAMING_SNAKE_CASE							    =							list[tuple[int, int]]

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

SCREAMING_SNAKE_CASE							    =							[[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right


class     __UpperCAmelCase							:


     """simple docstring"""


     def __init__(	self  ,       __A  ,       __A  ,       __A  ,       __A  ,       __A    ):
        __a					=  pos_x
        __a					=  pos_y
        __a					=  (pos_y, pos_x)
        __a					=  goal_x
        __a					=  goal_y
        __a					=  parent







class     __UpperCAmelCase							:


     """simple docstring"""


     def __init__(	self  ,       __A  ,       __A    ):
        __a					=  Node(start[1]  ,       start[0]  ,       goal[1]  ,       goal[0]  ,       __A    )
        __a					=  Node(goal[1]  ,       goal[0]  ,       goal[1]  ,       goal[0]  ,       __A    )

        __a					=  [self.start]
        __a					=  False


     def 	snake_case_  (	self    ):
        while self.node_queue:
           __a					=  self.node_queue.pop(0    )

           if current_node.pos == self.target.pos:
              __a					=  True
              return self.retrace_path(__A    )

           __a					=  self.get_successors(__A    )

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

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


     def 	snake_case_  (	self  ,       __A    ):
        __a					=  []
        for action in delta:
           __a					=  parent.pos_x + action[1]
           __a					=  parent.pos_y + action[0]
           if not (0 <= pos_x <= len(grid[0]    ) - 1 and 0 <= pos_y <= len(__A    ) - 1):
              continue

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

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


     def 	snake_case_  (	self  ,       __A    ):
        __a					=  node
        __a					=  []
        while current_node is not None:
           path.append((current_node.pos_y, current_node.pos_x)    )
           __a					=  current_node.parent
        path.reverse()
        return path







class     __UpperCAmelCase							:


     """simple docstring"""


     def __init__(	self  ,       __A  ,       __A    ):
        __a					=  BreadthFirstSearch(__A  ,       __A    )
        __a					=  BreadthFirstSearch(__A  ,       __A    )
        __a					=  False


     def 	snake_case_  (	self    ):
        while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
           __a					=  self.fwd_bfs.node_queue.pop(0    )
           __a					=  self.bwd_bfs.node_queue.pop(0    )

           if current_bwd_node.pos == current_fwd_node.pos:
              __a					=  True
              return self.retrace_bidirectional_path(
                  __A  ,       __A    )

           __a					=  current_bwd_node
           __a					=  current_fwd_node

           __a					=  {
               self.fwd_bfs: self.fwd_bfs.get_successors(__A    ),
               self.bwd_bfs: self.bwd_bfs.get_successors(__A    ),
           }

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

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


     def 	snake_case_  (	self  ,       __A  ,       __A    ):
        __a					=  self.fwd_bfs.retrace_path(__A    )
        __a					=  self.bwd_bfs.retrace_path(__A    )
        bwd_path.pop()
        bwd_path.reverse()
        __a					=  fwd_path + bwd_path
        return path


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

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

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

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

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

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







from collections.abc import Callable




def  a   (lowerCAmelCase__		,				lowerCAmelCase__		,				lowerCAmelCase__   ):
   __a					=  a
   __a					=  b
   if function(lowerCAmelCase__   ) == 0:  # one of the a or b is a root for the function
      return a
   elif function(lowerCAmelCase__   ) == 0:
      return b
   elif (
       function(lowerCAmelCase__   ) * function(lowerCAmelCase__   ) > 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:
      __a					=  start + (end - start) / 2.0
      while abs(start - mid   ) > 10**-7:  # until precisely equals to 10^-7
         if function(lowerCAmelCase__   ) == 0:
            return mid
         elif function(lowerCAmelCase__   ) * function(lowerCAmelCase__   ) < 0:
            __a					=  mid
         else:
            __a					=  mid
         __a					=  start + (end - start) / 2.0
      return mid




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


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

  import doctest

  doctest.testmod()



