





from __future__ import annotations

import time

_lowerCAmelCase 				=     list[tuple[int, int]]

_lowerCAmelCase 				=     [
    [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 				=     [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

class    _UpperCAmelCase							:
      def __init__(		self      ,       a__      ,       a__      ,       a__      ,       a__      ,       a__       ):
         A_     :				List[Any]			      =	pos_x
         A_     :				Union[str, Any]			      =	pos_y
         A_     :				Optional[Any]			      =	(pos_y, pos_x)
         A_     :				Optional[Any]			      =	goal_x
         A_     :				Optional[int]			      =	goal_y
         A_     :				Optional[Any]			      =	parent






class    _UpperCAmelCase							:
      def __init__(		self      ,       a__      ,       a__       ):
         A_     :				List[str]			      =	Node(start[1]      ,       start[0]      ,       goal[1]      ,       goal[0]      ,       a__       )
         A_     :				str			      =	Node(goal[1]      ,       goal[0]      ,       goal[1]      ,       goal[0]      ,       a__       )

         A_     :				str			      =	[self.start]
         A_     :				List[str]			      =	False
      def 		_lowerCamelCase      (		self       ):
         while self.node_queue:
            A_     :				List[str]			      =	self.node_queue.pop(0       )

            if current_node.pos == self.target.pos:
               A_     :				Tuple			      =	True
               return self.retrace_path(a__       )

            A_     :				List[Any]			      =	self.get_successors(a__       )

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

         if not self.reached:
            return [self.start.pos]
         return None
      def 		_lowerCamelCase      (		self      ,       a__       ):
         A_     :				Any			      =	[]
         for action in delta:
            A_     :				Dict			      =	parent.pos_x + action[1]
            A_     :				Optional[Any]			      =	parent.pos_y + action[0]
            if not (0 <= pos_x <= len(grid[0]       ) - 1 and 0 <= pos_y <= len(a__       ) - 1):
               continue

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

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






      def 		_lowerCamelCase      (		self      ,       a__       ):
         A_     :				Dict			      =	node
         A_     :				Optional[Any]			      =	[]
         while current_node is not None:
            path.append((current_node.pos_y, current_node.pos_x)       )
            A_     :				int			      =	current_node.parent
         path.reverse()
         return path






class    _UpperCAmelCase							:
      def __init__(		self      ,       a__      ,       a__       ):
         A_     :				Any			      =	BreadthFirstSearch(a__      ,       a__       )
         A_     :				int			      =	BreadthFirstSearch(a__      ,       a__       )
         A_     :				Optional[int]			      =	False
      def 		_lowerCamelCase      (		self       ):
         while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
            A_     :				Optional[Any]			      =	self.fwd_bfs.node_queue.pop(0       )
            A_     :				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(
                   a__      ,       a__       )

            A_     :				int			      =	current_bwd_node
            A_     :				Dict			      =	current_fwd_node

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

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

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






      def 		_lowerCamelCase      (		self      ,       a__      ,       a__       ):
         A_     :				List[Any]			      =	self.fwd_bfs.retrace_path(a__       )
         A_     :				Union[str, Any]			      =	self.bwd_bfs.retrace_path(a__       )
         bwd_path.pop()
         bwd_path.reverse()
         A_     :				Any			      =	fwd_path + bwd_path
         return path


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

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

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

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

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

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













_lowerCAmelCase 				=     """ABCDEFGHIJKLMNOPQRSTUVWXYZ"""



def     _lowerCAmelCase		(  ):
   '''simple docstring'''


   A_     :				Any			      =	input("""Enter message: """     )
   A_     :				Dict			      =	input("""Enter key [alphanumeric]: """     )
   A_     :				Dict			      =	input("""Encrypt/Decrypt [e/d]: """     )

   if mode.lower().startswith("""e"""     ):
      A_     :				Union[str, Any]			      =	"""encrypt"""
      A_     :				Optional[int]			      =	encrypt_message(_lowerCAmelCase  ,_lowerCAmelCase     )
   elif mode.lower().startswith("""d"""     ):
      A_     :				str			      =	"""decrypt"""
      A_     :				Dict			      =	decrypt_message(_lowerCAmelCase  ,_lowerCAmelCase     )

   print(f"""\n{mode.title()}ed message:"""     )
   print(_lowerCAmelCase     )



def     _lowerCAmelCase		(  _lowerCAmelCase  ,_lowerCAmelCase     ):
   '''simple docstring'''


   return translate_message(_lowerCAmelCase  ,_lowerCAmelCase  ,"""encrypt"""     )



def     _lowerCAmelCase		(  _lowerCAmelCase  ,_lowerCAmelCase     ):
   '''simple docstring'''


   return translate_message(_lowerCAmelCase  ,_lowerCAmelCase  ,"""decrypt"""     )



def     _lowerCAmelCase		(  _lowerCAmelCase  ,_lowerCAmelCase  ,_lowerCAmelCase     ):
   '''simple docstring'''


   A_     :				Dict			      =	[]
   A_     :				List[Any]			      =	0
   A_     :				int			      =	key.upper()

   for symbol in message:
      A_     :				Optional[int]			      =	LETTERS.find(symbol.upper()     )
      if num != -1:
         if mode == "encrypt":
            num += LETTERS.find(key[key_index]     )
         elif mode == "decrypt":
            num -= LETTERS.find(key[key_index]     )

         num %= len(_lowerCAmelCase     )

         if symbol.isupper():
            translated.append(LETTERS[num]     )
         elif symbol.islower():
            translated.append(LETTERS[num].lower()     )

         key_index += 1
         if key_index == len(_lowerCAmelCase     ):
            A_     :				Dict			      =	0
      else:
         translated.append(_lowerCAmelCase     )
   return "".join(_lowerCAmelCase     )


if __name__ == "__main__":
      main()






