





"""simple docstring"""





from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
SCREAMING_SNAKE_CASE__					=   0

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

SCREAMING_SNAKE_CASE__					=   tuple[int, int]

class 		lowercase					:





      def __init__(       self      ,						lowercase      ,						lowercase      ,						lowercase      ,						lowercase      ,						lowercase      ,						lowercase      ,						)		->     None:
            lowerCAmelCase  						=       pos_x
            lowerCAmelCase  						=       pos_y
            lowerCAmelCase  						=       (pos_y, pos_x)
            lowerCAmelCase  						=       goal_x
            lowerCAmelCase  						=       goal_y
            lowerCAmelCase  						=       g_cost
            lowerCAmelCase  						=       parent
            lowerCAmelCase  						=       self.calculate_heuristic()
            lowerCAmelCase  						=       self.g_cost + self.h_cost





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





      def __lt__(       self      ,						lowercase )		->     bool:
            return self.f_cost < other.f_cost







class 		lowercase					:





      def __init__(       self      ,						lowercase      ,						lowercase )		->     List[Any]:
            lowerCAmelCase  						=       Node(start[1]      ,						start[0]      ,						goal[1]      ,						goal[0]      ,						0      ,						lowercase )
            lowerCAmelCase  						=       Node(goal[1]      ,						goal[0]      ,						goal[1]      ,						goal[0]      ,						99_999      ,						lowercase )

            lowerCAmelCase  						=       [self.start]
            lowerCAmelCase  						=       []

            lowerCAmelCase  						=       False





      def     _snake_case			(       self )		->     list[TPosition]:
            while self.open_nodes:
                  # Open Nodes are sorted using __lt__
                  self.open_nodes.sort()
                  lowerCAmelCase  						=       self.open_nodes.pop(0 )

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

                  self.closed_nodes.append(lowercase )
                  lowerCAmelCase  						=       self.get_successors(lowercase )

                  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(lowercase )
                        else:
                              # retrieve the best current path
                              lowerCAmelCase  						=       self.open_nodes.pop(self.open_nodes.index(lowercase ) )

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

            return [self.start.pos]





      def     _snake_case			(       self      ,						lowercase )		->     list[Node]:
            lowerCAmelCase  						=       []
            for action in delta:
                  lowerCAmelCase  						=       parent.pos_x + action[1]
                  lowerCAmelCase  						=       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      ,						parent.g_cost + 1      ,						lowercase      ,						) )
            return successors





      def     _snake_case			(       self      ,						lowercase )		->     list[TPosition]:
            lowerCAmelCase  						=       node
            lowerCAmelCase  						=       []
            while current_node is not None:
                  path.append((current_node.pos_y, current_node.pos_x) )
                  lowerCAmelCase  						=       current_node.parent
            path.reverse()
            return path







class 		lowercase					:





      def __init__(       self      ,						lowercase      ,						lowercase )		->     None:
            lowerCAmelCase  						=       AStar(lowercase      ,						lowercase )
            lowerCAmelCase  						=       AStar(lowercase      ,						lowercase )
            lowerCAmelCase  						=       False





      def     _snake_case			(       self )		->     list[TPosition]:
            while self.fwd_astar.open_nodes or self.bwd_astar.open_nodes:
                  self.fwd_astar.open_nodes.sort()
                  self.bwd_astar.open_nodes.sort()
                  lowerCAmelCase  						=       self.fwd_astar.open_nodes.pop(0 )
                  lowerCAmelCase  						=       self.bwd_astar.open_nodes.pop(0 )

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

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

                  lowerCAmelCase  						=       current_bwd_node
                  lowerCAmelCase  						=       current_fwd_node

                  lowerCAmelCase  						=       {
                      self.fwd_astar: self.fwd_astar.get_successors(lowercase ),
                      self.bwd_astar: self.bwd_astar.get_successors(lowercase ),
                  }

                  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(lowercase )
                              else:
                                    # retrieve the best current path
                                    lowerCAmelCase  						=       astar.open_nodes.pop(
                                        astar.open_nodes.index(lowercase ) )

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

            return [self.fwd_astar.start.pos]





      def     _snake_case			(       self      ,						lowercase      ,						lowercase )		->     list[TPosition]:
            lowerCAmelCase  						=       self.fwd_astar.retrace_path(lowercase )
            lowerCAmelCase  						=       self.bwd_astar.retrace_path(lowercase )
            bwd_path.pop()
            bwd_path.reverse()
            lowerCAmelCase  						=       fwd_path + bwd_path
            return path


if __name__ == "__main__":
       # all coordinates are given in format [y,x]
       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__					=   AStar(init, goal)
       SCREAMING_SNAKE_CASE__					=   a_star.search()
       SCREAMING_SNAKE_CASE__					=   time.time() - start_time
       print(f'AStar execution time = {end_time:f} seconds')

       SCREAMING_SNAKE_CASE__					=   time.time()
       SCREAMING_SNAKE_CASE__					=   BidirectionalAStar(init, goal)
       SCREAMING_SNAKE_CASE__					=   time.time() - bd_start_time
       print(f'BidirectionalAStar execution time = {bd_end_time:f} seconds')








'''simple docstring'''




def 		lowerCAmelCase_				(   snake_case__ = 10						):




    '''simple docstring'''



    if not isinstance(snake_case__		,				snake_case__						) or n < 0:
        raise ValueError('''Invalid input'''						)
    A       :   List[str]					=						10**n
    A       :   Tuple					=						2_8433 * (pow(2		,				783_0457		,				snake_case__						)) + 1
    return str(number % modulus						)


if __name__ == "__main__":
      from doctest import testmod

      testmod()
      print(f'''{solution(10) = }''')




