"""simple docstring"""


from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
lowerCAmelCase_:					List[str]     =					0

lowerCAmelCase_:					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],
]

lowerCAmelCase_:					Dict     =					[[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

lowerCAmelCase_:					int     =					tuple[int, int]






class    a__    :


   def __init__(     self,				_UpperCAmelCase,				_UpperCAmelCase,				_UpperCAmelCase,				_UpperCAmelCase,				_UpperCAmelCase,				_UpperCAmelCase,				):
        '''simple docstring'''



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


   def 	snake_case__	(     self  ):
        '''simple docstring'''



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


   def __lt__(     self,				_UpperCAmelCase  ):
        '''simple docstring'''



        return self.f_cost < other.f_cost






class    a__    :


   def __init__(     self,				_UpperCAmelCase,				_UpperCAmelCase  ):
        '''simple docstring'''



        lowercase__				 =							Node(start[1],				start[0],				goal[1],				goal[0],				0,				_UpperCAmelCase  )
        lowercase__				 =							Node(goal[1],				goal[0],				goal[1],				goal[0],				9_9999,				_UpperCAmelCase  )

        lowercase__				 =							[self.start]
        lowercase__				 =							[]

        lowercase__				 =							False


   def 	snake_case__	(     self  ):
        '''simple docstring'''



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

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

             self.closed_nodes.append(_UpperCAmelCase  )
             lowercase__				 =							self.get_successors(_UpperCAmelCase  )

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

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

        return [self.start.pos]


   def 	snake_case__	(     self,				_UpperCAmelCase  ):
        '''simple docstring'''



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

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

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


   def 	snake_case__	(     self,				_UpperCAmelCase  ):
        '''simple docstring'''



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






class    a__    :


   def __init__(     self,				_UpperCAmelCase,				_UpperCAmelCase  ):
        '''simple docstring'''



        lowercase__				 =							AStar(_UpperCAmelCase,				_UpperCAmelCase  )
        lowercase__				 =							AStar(_UpperCAmelCase,				_UpperCAmelCase  )
        lowercase__				 =							False


   def 	snake_case__	(     self  ):
        '''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()
             lowercase__				 =							self.fwd_astar.open_nodes.pop(0  )
             lowercase__				 =							self.bwd_astar.open_nodes.pop(0  )

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

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

             lowercase__				 =							current_bwd_node
             lowercase__				 =							current_fwd_node

             lowercase__				 =							{
                 self.fwd_astar: self.fwd_astar.get_successors(_UpperCAmelCase  ),
                 self.bwd_astar: self.bwd_astar.get_successors(_UpperCAmelCase  ),
             }

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

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

        return [self.fwd_astar.start.pos]


   def 	snake_case__	(     self,				_UpperCAmelCase,				_UpperCAmelCase  ):
        '''simple docstring'''



        lowercase__				 =							self.fwd_astar.retrace_path(_UpperCAmelCase  )
        lowercase__				 =							self.bwd_astar.retrace_path(_UpperCAmelCase  )
        bwd_path.pop()
        bwd_path.reverse()
        lowercase__				 =							fwd_path + bwd_path
        return path


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

 lowerCAmelCase_:					List[str]     =					time.time()
 lowerCAmelCase_:					Union[str, Any]     =					AStar(init, goal)
 lowerCAmelCase_:					str     =					a_star.search()
 lowerCAmelCase_:					List[Any]     =					time.time() - start_time
 print(F'AStar execution time = {end_time:f} seconds')

 lowerCAmelCase_:					Any     =					time.time()
 lowerCAmelCase_:					Dict     =					BidirectionalAStar(init, goal)
 lowerCAmelCase_:					Tuple     =					time.time() - bd_start_time
 print(F'BidirectionalAStar execution time = {bd_end_time:f} seconds')





"""simple docstring"""


lowerCAmelCase_:					Any     =					"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"







def 					__a   (		A      ):






     '''simple docstring'''



     if not isinstance(A    ,				A      ):
          lowercase__				 =							f'''a bytes-like object is required, not \'{data.__class__.__name__}\''''
          raise TypeError(A      )

     lowercase__				 =							"".join(bin(A      )[2:].zfill(8      ) for byte in data      )

     lowercase__				 =							len(A      ) % 6 != 0

     if padding_needed:
          # The padding that will be added later
          lowercase__				 =							b"=" * ((6 - len(A      ) % 6) // 2)

          # Append binary_stream with arbitrary binary digits (0's by default) to make its
          # length a multiple of 6.
          binary_stream += "0" * (6 - len(A      ) % 6)
     else:
          lowercase__				 =							b""

     # Encode every 6 binary digits to their corresponding Base64 character
     return (
         "".join(
             B64_CHARSET[int(binary_stream[index : index + 6]    ,				2      )]
             for index in range(0    ,				len(A      )    ,				6      )      ).encode()
         + padding
     )







def 					__a   (		A      ):






     '''simple docstring'''



     if not isinstance(A    ,				A      ) and not isinstance(A    ,				A      ):
          lowercase__				 =							(
              "argument should be a bytes-like object or ASCII string, "
              f'''not \'{encoded_data.__class__.__name__}\''''
          )
          raise TypeError(A      )

     # In case encoded_data is a bytes-like object, make sure it contains only
     # ASCII characters so we convert it to a string object
     if isinstance(A    ,				A      ):
          try:
               lowercase__				 =							encoded_data.decode("utf-8"      )
          except UnicodeDecodeError:
               raise ValueError("base64 encoded data should only contain ASCII characters"      )

     lowercase__				 =							encoded_data.count("="      )

     # Check if the encoded string contains non base64 characters
     if padding:
          assert all(
              char in B64_CHARSET for char in encoded_data[:-padding]      ), "Invalid base64 character(s) found."
     else:
          assert all(
              char in B64_CHARSET for char in encoded_data      ), "Invalid base64 character(s) found."

     # Check the padding
     assert len(A      ) % 4 == 0 and padding < 3, "Incorrect padding"

     if padding:
          # Remove padding if there is one
          lowercase__				 =							encoded_data[:-padding]

          lowercase__				 =							"".join(
              bin(B64_CHARSET.index(A      )      )[2:].zfill(6      ) for char in encoded_data      )[: -padding * 2]
     else:
          lowercase__				 =							"".join(
              bin(B64_CHARSET.index(A      )      )[2:].zfill(6      ) for char in encoded_data      )

     lowercase__				 =							[
         int(binary_stream[index : index + 8]    ,				2      )
         for index in range(0    ,				len(A      )    ,				8      )
     ]

     return bytes(A      )


if __name__ == "__main__":
 import doctest

 doctest.testmod()




