



'''simple docstring'''





def lowerCAmelCase  (__A  ,	__A):



     """simple docstring"""



     return price * (1 + tax_rate)


if __name__ == "__main__":
  print(F"""{price_plus_tax(100, 0.25) = }""")
  print(F"""{price_plus_tax(125.50, 0.05) = }""")









from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
snake_case_ : str    		=       0

snake_case_ : Union[str, Any]    		=       [
    [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],
]

snake_case_ : str    		=       [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

snake_case_ : List[Any]    		=       tuple[int, int]







class __snake_case			:







   def __init__(      self		:						Any					,						_snake_case		:						int					,						_snake_case		:						int					,						_snake_case		:						int					,						_snake_case		:						int					,						_snake_case		:						int					,						_snake_case		:						Node | None					,						):

        """simple docstring"""


        UpperCAmelCase_          =							pos_x
        UpperCAmelCase_          =							pos_y
        UpperCAmelCase_          =							(pos_y, pos_x)
        UpperCAmelCase_          =							goal_x
        UpperCAmelCase_          =							goal_y
        UpperCAmelCase_          =							g_cost
        UpperCAmelCase_          =							parent
        UpperCAmelCase_          =							self.calculate_heuristic()
        UpperCAmelCase_          =							self.g_cost + self.h_cost







   def lowerCamelCase						(      self		:						List[str]):

        """simple docstring"""


        UpperCAmelCase_          =							self.pos_x - self.goal_x
        UpperCAmelCase_          =							self.pos_y - self.goal_y
        if HEURISTIC == 1:
             return abs(_snake_case) + abs(_snake_case)
        else:
             return sqrt(dy**2 + dx**2)







   def __lt__(      self		:						Union[str, Any]					,						_snake_case		:						Node):

        """simple docstring"""


        return self.f_cost < other.f_cost







class __snake_case			:







   def __init__(      self		:						str					,						_snake_case		:						TPosition					,						_snake_case		:						TPosition):

        """simple docstring"""


        UpperCAmelCase_          =							Node(start[1]					,						start[0]					,						goal[1]					,						goal[0]					,						0					,						_snake_case)
        UpperCAmelCase_          =							Node(goal[1]					,						goal[0]					,						goal[1]					,						goal[0]					,						99999					,						_snake_case)

        UpperCAmelCase_          =							[self.start]
        UpperCAmelCase_          =							[]

        UpperCAmelCase_          =							False







   def lowerCamelCase						(      self		:						Optional[int]):

        """simple docstring"""


        while self.open_nodes:
             # Open Nodes are sorted using __lt__
             self.open_nodes.sort()
             UpperCAmelCase_          =							self.open_nodes.pop(0)

             if current_node.pos == self.target.pos:
                  return self.retrace_path(_snake_case)

             self.closed_nodes.append(_snake_case)
             UpperCAmelCase_          =							self.get_successors(_snake_case)

             for child_node in successors:
                  if child_node in self.closed_nodes:
                       continue

                  if child_node not in self.open_nodes:
                       self.open_nodes.append(_snake_case)
                  else:
                       # retrieve the best current path
                       UpperCAmelCase_          =							self.open_nodes.pop(self.open_nodes.index(_snake_case))

                       if child_node.g_cost < better_node.g_cost:
                            self.open_nodes.append(_snake_case)
                       else:
                            self.open_nodes.append(_snake_case)

        return [self.start.pos]







   def lowerCamelCase						(      self		:						Tuple					,						_snake_case		:						Node):

        """simple docstring"""


        UpperCAmelCase_          =							[]
        for action in delta:
             UpperCAmelCase_          =							parent.pos_x + action[1]
             UpperCAmelCase_          =							parent.pos_y + action[0]
             if not (0 <= pos_x <= len(grid[0]) - 1 and 0 <= pos_y <= len(_snake_case) - 1):
                  continue

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

             successors.append(
                 Node(
                     _snake_case					,						_snake_case					,						self.target.pos_y					,						self.target.pos_x					,						parent.g_cost + 1					,						_snake_case					,						))
        return successors







   def lowerCamelCase						(      self		:						Any					,						_snake_case		:						Node | None):

        """simple docstring"""


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







class __snake_case			:







   def __init__(      self		:						Any					,						_snake_case		:						TPosition					,						_snake_case		:						TPosition):

        """simple docstring"""


        UpperCAmelCase_          =							AStar(_snake_case					,						_snake_case)
        UpperCAmelCase_          =							AStar(_snake_case					,						_snake_case)
        UpperCAmelCase_          =							False







   def lowerCamelCase						(      self		:						List[Any]):

        """simple docstring"""


        while self.fwd_astar.open_nodes or self.bwd_astar.open_nodes:
             self.fwd_astar.open_nodes.sort()
             self.bwd_astar.open_nodes.sort()
             UpperCAmelCase_          =							self.fwd_astar.open_nodes.pop(0)
             UpperCAmelCase_          =							self.bwd_astar.open_nodes.pop(0)

             if current_bwd_node.pos == current_fwd_node.pos:
                  return self.retrace_bidirectional_path(
                      _snake_case					,						_snake_case)

             self.fwd_astar.closed_nodes.append(_snake_case)
             self.bwd_astar.closed_nodes.append(_snake_case)

             UpperCAmelCase_          =							current_bwd_node
             UpperCAmelCase_          =							current_fwd_node

             UpperCAmelCase_          =							{
                 self.fwd_astar: self.fwd_astar.get_successors(_snake_case),
                 self.bwd_astar: self.bwd_astar.get_successors(_snake_case),
             }

             for astar in [self.fwd_astar, self.bwd_astar]:
                  for child_node in successors[astar]:
                       if child_node in astar.closed_nodes:
                            continue

                       if child_node not in astar.open_nodes:
                            astar.open_nodes.append(_snake_case)
                       else:
                            # retrieve the best current path
                            UpperCAmelCase_          =							astar.open_nodes.pop(
                                astar.open_nodes.index(_snake_case))

                            if child_node.g_cost < better_node.g_cost:
                                 astar.open_nodes.append(_snake_case)
                            else:
                                 astar.open_nodes.append(_snake_case)

        return [self.fwd_astar.start.pos]







   def lowerCamelCase						(      self		:						int					,						_snake_case		:						Node					,						_snake_case		:						Node):

        """simple docstring"""


        UpperCAmelCase_          =							self.fwd_astar.retrace_path(_snake_case)
        UpperCAmelCase_          =							self.bwd_astar.retrace_path(_snake_case)
        bwd_path.pop()
        bwd_path.reverse()
        UpperCAmelCase_          =							fwd_path + bwd_path
        return path


if __name__ == "__main__":
    # all coordinates are given in format [y,x]
    snake_case_ : Any    		=       (0, 0)
    snake_case_ : Union[str, Any]    		=       (len(grid) - 1, len(grid[0]) - 1)
    for elem in grid:
        print(elem)

    snake_case_ : str    		=       time.time()
    snake_case_ : List[str]    		=       AStar(init, goal)
    snake_case_ : Optional[int]    		=       a_star.search()
    snake_case_ : Optional[Any]    		=       time.time() - start_time
    print(f"AStar execution time = {end_time:f} seconds")

    snake_case_ : int    		=       time.time()
    snake_case_ : Dict    		=       BidirectionalAStar(init, goal)
    snake_case_ : str    		=       time.time() - bd_start_time
    print(f"BidirectionalAStar execution time = {bd_end_time:f} seconds")






