






"""simple docstring"""




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






      def __init__(    self     ,     a_     ,     a_     ,     a_     ,     a_     ,     a_	)	->str:







        '''simple docstring'''


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







class    lowercase_    :






      def __init__(    self     ,     a_     ,     a_	)	->Any:







        '''simple docstring'''


        _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 			lowerCamelCase__    (    self	)	->Path | None:







        '''simple docstring'''


        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 			lowerCamelCase__    (    self     ,     a_	)	->list[Node]:







        '''simple docstring'''


        _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 			lowerCamelCase__    (    self     ,     a_	)	->Path:







        '''simple docstring'''


        _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    lowercase_    :






      def __init__(    self     ,     a_     ,     a_	)	->Any:







        '''simple docstring'''


        _a							=	BreadthFirstSearch(a_     ,     a_	)
        _a							=	BreadthFirstSearch(a_     ,     a_	)
        _a							=	False






      def 			lowerCamelCase__    (    self	)	->Path | None:







        '''simple docstring'''


        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 			lowerCamelCase__    (    self     ,     a_     ,     a_	)	->Path:







        '''simple docstring'''


        _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()
       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)










"""simple docstring"""




def        lowerCAmelCase (      UpperCamelCase_:							Optional[int]     , UpperCamelCase_:							str					)       ->							List[Any]:







  '''simple docstring'''







  _a							=	(boundary[1] - boundary[0]) / steps
  _a							=	boundary[0]
  _a							=	boundary[1]
  _a							=	make_points(UpperCamelCase_     , UpperCamelCase_     , UpperCamelCase_					)
  _a							=	0.0
  y += (h / 2.0) * f(UpperCamelCase_					)
  for i in x_i:
    # print(i)
    y += h * f(UpperCamelCase_					)
  y += (h / 2.0) * f(UpperCamelCase_					)
  return y






def        lowerCAmelCase (      UpperCamelCase_:							str     , UpperCamelCase_:							Any     , UpperCamelCase_:							Any					)       ->							str:







  '''simple docstring'''







  _a							=	a + h
  while x < (b - h):
    yield x
    _a							=	x + h






def        lowerCAmelCase (      UpperCamelCase_:							List[str]					)       ->							int:  # enter your function here







  '''simple docstring'''







  _a							=	(x - 0) * (x - 0)
  return y






def        lowerCAmelCase (      )       ->							Tuple:







  '''simple docstring'''







  _a							=	0.0  # Lower bound of integration
  _a							=	1.0  # Upper bound of integration
  _a							=	10.0  # define number of steps or resolution
  _a							=	[a, b]  # define boundary of integration
  _a							=	method_a(UpperCamelCase_     , UpperCamelCase_					)
  print(f'''y = {y}'''					)


if __name__ == "__main__":
     main()


