"""simple docstring"""
from __future__ import annotations

import time

lowercase__					       =	list[tuple[int, int]]

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

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




class    __snake_case       :



      def __init__(						self    ,			lowercase    ,			lowercase    ,			lowercase    ,			lowercase    ,			lowercase)	->			Tuple:





        '''simple docstring'''





        a__:     int										=	pos_x
        a__:     Union[str, Any]										=	pos_y
        a__:     Any										=	(pos_y, pos_x)
        a__:     List[str]										=	goal_x
        a__:     Optional[Any]										=	goal_y
        a__:     Dict										=	parent







class    __snake_case       :



      def __init__(						self    ,			lowercase    ,			lowercase)	->			Tuple:





        '''simple docstring'''





        a__:     str										=	Node(start[1]    ,			start[0]    ,			goal[1]    ,			goal[0]    ,			lowercase)
        a__:     Tuple										=	Node(goal[1]    ,			goal[0]    ,			goal[1]    ,			goal[0]    ,			lowercase)

        a__:     int										=	[self.start]
        a__:     List[str]										=	False



      def   lowerCamelCase_   (						self)	->			Path | None:





        '''simple docstring'''





        while self.node_queue:
          a__:     int										=	self.node_queue.pop(0)

          if current_node.pos == self.target.pos:
            a__:     Optional[Any]										=	True
            return self.retrace_path(lowercase)

          a__:     Dict										=	self.get_successors(lowercase)

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

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



      def   lowerCamelCase_   (						self    ,			lowercase)	->			list[Node]:





        '''simple docstring'''





        a__:     Any										=	[]
        for action in delta:
          a__:     List[Any]										=	parent.pos_x + action[1]
          a__:     List[str]										=	parent.pos_y + action[0]
          if not (0 <= pos_x <= len(grid[0]) - 1 and 0 <= pos_y <= len(lowercase) - 1):
            continue

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

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



      def   lowerCamelCase_   (						self    ,			lowercase)	->			Path:





        '''simple docstring'''





        a__:     Tuple										=	node
        a__:     List[Any]										=	[]
        while current_node is not None:
          path.append((current_node.pos_y, current_node.pos_x))
          a__:     str										=	current_node.parent
        path.reverse()
        return path







class    __snake_case       :



      def __init__(						self    ,			lowercase    ,			lowercase)	->			Union[str, Any]:





        '''simple docstring'''





        a__:     Optional[Any]										=	BreadthFirstSearch(lowercase    ,			lowercase)
        a__:     Any										=	BreadthFirstSearch(lowercase    ,			lowercase)
        a__:     Dict										=	False



      def   lowerCamelCase_   (						self)	->			Path | None:





        '''simple docstring'''





        while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
          a__:     Optional[Any]										=	self.fwd_bfs.node_queue.pop(0)
          a__:     Optional[Any]										=	self.bwd_bfs.node_queue.pop(0)

          if current_bwd_node.pos == current_fwd_node.pos:
            a__:     List[Any]										=	True
            return self.retrace_bidirectional_path(
                lowercase    ,			lowercase)

          a__:     Optional[int]										=	current_bwd_node
          a__:     str										=	current_fwd_node

          a__:     Optional[Any]										=	{
              self.fwd_bfs: self.fwd_bfs.get_successors(lowercase),
              self.bwd_bfs: self.bwd_bfs.get_successors(lowercase),
          }

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

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



      def   lowerCamelCase_   (						self    ,			lowercase    ,			lowercase)	->			Path:





        '''simple docstring'''





        a__:     Optional[Any]										=	self.fwd_bfs.retrace_path(lowercase)
        a__:     List[str]										=	self.bwd_bfs.retrace_path(lowercase)
        bwd_path.pop()
        bwd_path.reverse()
        a__:     Dict										=	fwd_path + bwd_path
        return path


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

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

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

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

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

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



"""simple docstring"""
from math import pi, sqrt, tan







def 						__a   (	_SCREAMING_SNAKE_CASE   )	->float:
  if side_length < 0:
    raise ValueError('surface_area_cube() only accepts non-negative values'   )
  return 6 * side_length**2







def 						__a   (	_SCREAMING_SNAKE_CASE		,     _SCREAMING_SNAKE_CASE		,     _SCREAMING_SNAKE_CASE   )	->float:
  if length < 0 or breadth < 0 or height < 0:
    raise ValueError('surface_area_cuboid() only accepts non-negative values'   )
  return 2 * ((length * breadth) + (breadth * height) + (length * height))







def 						__a   (	_SCREAMING_SNAKE_CASE   )	->float:
  if radius < 0:
    raise ValueError('surface_area_sphere() only accepts non-negative values'   )
  return 4 * pi * radius**2







def 						__a   (	_SCREAMING_SNAKE_CASE   )	->float:
  if radius < 0:
    raise ValueError('surface_area_hemisphere() only accepts non-negative values'   )
  return 3 * pi * radius**2







def 						__a   (	_SCREAMING_SNAKE_CASE		,     _SCREAMING_SNAKE_CASE   )	->float:
  if radius < 0 or height < 0:
    raise ValueError('surface_area_cone() only accepts non-negative values'   )
  return pi * radius * (radius + (height**2 + radius**2) ** 0.5)







def 						__a   (	_SCREAMING_SNAKE_CASE		,     _SCREAMING_SNAKE_CASE		,     _SCREAMING_SNAKE_CASE   )	->float:
  if radius_a < 0 or radius_a < 0 or height < 0:
    raise ValueError(
        'surface_area_conical_frustum() only accepts non-negative values'   )
  a__:     List[Any]										=	(height**2 + (radius_a - radius_a) ** 2) ** 0.5
  return pi * ((slant_height * (radius_a + radius_a)) + radius_a**2 + radius_a**2)







def 						__a   (	_SCREAMING_SNAKE_CASE		,     _SCREAMING_SNAKE_CASE   )	->float:
  if radius < 0 or height < 0:
    raise ValueError('surface_area_cylinder() only accepts non-negative values'   )
  return 2 * pi * radius * (height + radius)







def 						__a   (	_SCREAMING_SNAKE_CASE		,     _SCREAMING_SNAKE_CASE   )	->float:
  if torus_radius < 0 or tube_radius < 0:
    raise ValueError('surface_area_torus() only accepts non-negative values'   )
  if torus_radius < tube_radius:
    raise ValueError(
        'surface_area_torus() does not support spindle or self intersecting tori'   )
  return 4 * pow(_SCREAMING_SNAKE_CASE		,     2   ) * torus_radius * tube_radius







def 						__a   (	_SCREAMING_SNAKE_CASE		,     _SCREAMING_SNAKE_CASE   )	->float:
  if length < 0 or width < 0:
    raise ValueError('area_rectangle() only accepts non-negative values'   )
  return length * width







def 						__a   (	_SCREAMING_SNAKE_CASE   )	->float:
  if side_length < 0:
    raise ValueError('area_square() only accepts non-negative values'   )
  return side_length**2







def 						__a   (	_SCREAMING_SNAKE_CASE		,     _SCREAMING_SNAKE_CASE   )	->float:
  if base < 0 or height < 0:
    raise ValueError('area_triangle() only accepts non-negative values'   )
  return (base * height) / 2







def 						__a   (	_SCREAMING_SNAKE_CASE		,     _SCREAMING_SNAKE_CASE		,     _SCREAMING_SNAKE_CASE   )	->float:
  if sidea < 0 or sidea < 0 or sidea < 0:
    raise ValueError('area_triangle_three_sides() only accepts non-negative values'   )
  elif sidea + sidea < sidea or sidea + sidea < sidea or sidea + sidea < sidea:
    raise ValueError('Given three sides do not form a triangle'   )
  a__:     int										=	(sidea + sidea + sidea) / 2
  a__:     Tuple										=	sqrt(
      semi_perimeter
      * (semi_perimeter - sidea)
      * (semi_perimeter - sidea)
      * (semi_perimeter - sidea)   )
  return area







def 						__a   (	_SCREAMING_SNAKE_CASE		,     _SCREAMING_SNAKE_CASE   )	->float:
  if base < 0 or height < 0:
    raise ValueError('area_parallelogram() only accepts non-negative values'   )
  return base * height







def 						__a   (	_SCREAMING_SNAKE_CASE		,     _SCREAMING_SNAKE_CASE		,     _SCREAMING_SNAKE_CASE   )	->float:
  if basea < 0 or basea < 0 or height < 0:
    raise ValueError('area_trapezium() only accepts non-negative values'   )
  return 1 / 2 * (basea + basea) * height







def 						__a   (	_SCREAMING_SNAKE_CASE   )	->float:
  if radius < 0:
    raise ValueError('area_circle() only accepts non-negative values'   )
  return pi * radius**2







def 						__a   (	_SCREAMING_SNAKE_CASE		,     _SCREAMING_SNAKE_CASE   )	->float:
  if radius_x < 0 or radius_y < 0:
    raise ValueError('area_ellipse() only accepts non-negative values'   )
  return pi * radius_x * radius_y







def 						__a   (	_SCREAMING_SNAKE_CASE		,     _SCREAMING_SNAKE_CASE   )	->float:
  if diagonal_a < 0 or diagonal_a < 0:
    raise ValueError('area_rhombus() only accepts non-negative values'   )
  return 1 / 2 * diagonal_a * diagonal_a







def 						__a   (	_SCREAMING_SNAKE_CASE		,     _SCREAMING_SNAKE_CASE   )	->float:
  if not isinstance(_SCREAMING_SNAKE_CASE		,     _SCREAMING_SNAKE_CASE   ) or sides < 3:
    raise ValueError(
        'area_reg_polygon() only accepts integers greater than or \
equal to three as number of sides'   )
  elif length < 0:
    raise ValueError(
        'area_reg_polygon() only accepts non-negative values as \
length of a side'   )
  return (sides * length**2) / (4 * tan(pi / sides   ))
  return (sides * length**2) / (4 * tan(pi / sides   ))


if __name__ == "__main__":
 import doctest

 doctest.testmod(verbose=True)  # verbose so we can see methods missing tests

 print('[DEMO] Areas of various geometric shapes: \n')
 print(f"Rectangle: {area_rectangle(10, 20) = }")
 print(f"Square: {area_square(10) = }")
 print(f"Triangle: {area_triangle(10, 10) = }")
 print(f"Triangle: {area_triangle_three_sides(5, 12, 13) = }")
 print(f"Parallelogram: {area_parallelogram(10, 20) = }")
 print(f"Rhombus: {area_rhombus(10, 20) = }")
 print(f"Trapezium: {area_trapezium(10, 20, 30) = }")
 print(f"Circle: {area_circle(20) = }")
 print(f"Ellipse: {area_ellipse(10, 20) = }")
 print('\nSurface Areas of various geometric shapes: \n')
 print(f"Cube: {surface_area_cube(20) = }")
 print(f"Cuboid: {surface_area_cuboid(10, 20, 30) = }")
 print(f"Sphere: {surface_area_sphere(20) = }")
 print(f"Hemisphere: {surface_area_hemisphere(20) = }")
 print(f"Cone: {surface_area_cone(10, 20) = }")
 print(f"Conical Frustum: {surface_area_conical_frustum(10, 20, 30) = }")
 print(f"Cylinder: {surface_area_cylinder(10, 20) = }")
 print(f"Torus: {surface_area_torus(20, 10) = }")
 print(f"Equilateral Triangle: {area_reg_polygon(3, 10) = }")
 print(f"Square: {area_reg_polygon(4, 10) = }")
 print(f"Reqular Pentagon: {area_reg_polygon(5, 10) = }")


