


from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
__UpperCamelCase				:				int  				= 0

__UpperCamelCase				:				List[str]  				= [
    [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				:				Optional[Any]  				= [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

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

class 					__magic_name__		:


     def __init__(					self							:   int							,		lowerCamelCase__							:   Tuple							,		lowerCamelCase__							:   List[Any]							,		lowerCamelCase__							:   Optional[int]							,		lowerCamelCase__							:   Union[str, Any]							,		lowerCamelCase__							:   Any							,		lowerCamelCase__							:   Any							,		)     ->					None:





      '''simple docstring'''






      UpperCamelCase__    :			Any      				=      pos_x
      UpperCamelCase__    :			List[Any]      				=      pos_y
      UpperCamelCase__    :			List[str]      				=      (pos_y, pos_x)
      UpperCamelCase__    :			Optional[int]      				=      goal_x
      UpperCamelCase__    :			Union[str, Any]      				=      goal_y
      UpperCamelCase__    :			Any      				=      g_cost
      UpperCamelCase__    :			Tuple      				=      parent
      UpperCamelCase__    :			int      				=      self.calculate_heuristic()
      UpperCamelCase__    :			Optional[int]      				=      self.g_cost + self.h_cost


     def    UpperCAmelCase__		(					self							:   str	)     ->					float:





      '''simple docstring'''






      UpperCamelCase__    :			Union[str, Any]      				=      self.pos_x - self.goal_x
      UpperCamelCase__    :			Any      				=      self.pos_y - self.goal_y
      if HEURISTIC == 1:
       return abs(__lowerCAmelCase	) + abs(__lowerCAmelCase	)
      else:
       return sqrt(dy**2 + dx**2	)


     def __lt__(					self							:   Any							,		lowerCamelCase__							:   Tuple	)     ->					bool:





      '''simple docstring'''






      return self.f_cost < other.f_cost



class 					__magic_name__		:


     def __init__(					self							:   List[Any]							,		lowerCamelCase__							:   Optional[int]							,		lowerCamelCase__							:   int	)     ->					Optional[Any]:





      '''simple docstring'''






      UpperCamelCase__    :			Optional[Any]      				=      Node(start[1]							,		start[0]							,		goal[1]							,		goal[0]							,		0							,		__lowerCAmelCase	)
      UpperCamelCase__    :			Tuple      				=      Node(goal[1]							,		goal[0]							,		goal[1]							,		goal[0]							,		99999							,		__lowerCAmelCase	)

      UpperCamelCase__    :			str      				=      [self.start]
      UpperCamelCase__    :			list[Node]      				=      []

      UpperCamelCase__    :			Dict      				=      False


     def    UpperCAmelCase__		(					self							:   List[Any]	)     ->					list[TPosition]:





      '''simple docstring'''






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

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

       self.closed_nodes.append(__lowerCAmelCase	)
       UpperCamelCase__    :			List[Any]      				=      self.get_successors(__lowerCAmelCase	)

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

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

      return [self.start.pos]


     def    UpperCAmelCase__		(					self							:   Tuple							,		lowerCamelCase__							:   Optional[int]	)     ->					list[Node]:





      '''simple docstring'''






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

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

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


     def    UpperCAmelCase__		(					self							:   Tuple							,		lowerCamelCase__							:   Tuple	)     ->					list[TPosition]:





      '''simple docstring'''






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



class 					__magic_name__		:


     def __init__(					self							:   Dict							,		lowerCamelCase__							:   Optional[Any]							,		lowerCamelCase__							:   Union[str, Any]	)     ->					None:





      '''simple docstring'''






      UpperCamelCase__    :			Tuple      				=      AStar(__lowerCAmelCase							,		__lowerCAmelCase	)
      UpperCamelCase__    :			Union[str, Any]      				=      AStar(__lowerCAmelCase							,		__lowerCAmelCase	)
      UpperCamelCase__    :			int      				=      False


     def    UpperCAmelCase__		(					self							:   Union[str, Any]	)     ->					list[TPosition]:





      '''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__    :			Optional[int]      				=      self.fwd_astar.open_nodes.pop(0	)
       UpperCamelCase__    :			Dict      				=      self.bwd_astar.open_nodes.pop(0	)

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

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

       UpperCamelCase__    :			Any      				=      current_bwd_node
       UpperCamelCase__    :			Optional[int]      				=      current_fwd_node

       UpperCamelCase__    :			str      				=      {
           self.fwd_astar: self.fwd_astar.get_successors(__lowerCAmelCase	),
           self.bwd_astar: self.bwd_astar.get_successors(__lowerCAmelCase	),
       }

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

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

      return [self.fwd_astar.start.pos]


     def    UpperCAmelCase__		(					self							:   Union[str, Any]							,		lowerCamelCase__							:   Tuple							,		lowerCamelCase__							:   Any	)     ->					list[TPosition]:





      '''simple docstring'''






      UpperCamelCase__    :			Dict      				=      self.fwd_astar.retrace_path(__lowerCAmelCase	)
      UpperCamelCase__    :			Dict      				=      self.bwd_astar.retrace_path(__lowerCAmelCase	)
      bwd_path.pop()
      bwd_path.reverse()
      UpperCamelCase__    :			Optional[int]      				=      fwd_path + bwd_path
      return path


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

       __UpperCamelCase				:				Tuple  				= time.time()
       __UpperCamelCase				:				Dict  				= AStar(init, goal)
       __UpperCamelCase				:				str  				= a_star.search()
       __UpperCamelCase				:				int  				= time.time() - start_time
       print(f"AStar execution time = {end_time:f} seconds")

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



'''simple docstring'''

def 			__UpperCamelCase       (   UpperCAmelCase = 1		,     UpperCAmelCase = 1000     ):
 lowercase__				:    Dict  =					1
 lowercase__				:    Dict  =					0

 for divide_by_number in range(UpperCAmelCase		,     digit + 1     ):
  lowercase__				:    list[int]  =					[]
  lowercase__				:    Union[str, Any]  =					numerator
  for _ in range(1		,     digit + 1     ):
   if now_divide in has_been_divided:
    if longest_list_length < len(UpperCAmelCase     ):
     lowercase__				:    Dict  =					len(UpperCAmelCase     )
     lowercase__				:    Optional[Any]  =					divide_by_number
   else:
    has_been_divided.append(UpperCAmelCase     )
    lowercase__				:    int  =					now_divide * 10 % divide_by_number

 return the_digit


# Tests
if __name__ == "__main__":
  import doctest

  doctest.testmod()

