






from __future__ import annotations

lowerCamelCase			:					Optional[Any]         =	list[tuple[int, int]]

lowerCamelCase			:					Tuple         =	[
    [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			:					Union[str, Any]         =	([-1, 0], [0, -1], [1, 0], [0, 1])  # up, left, down, right



class 							_UpperCamelCase			:


      def __init__(	self					,						__UpperCamelCase					,						__UpperCamelCase					,						__UpperCamelCase					,						__UpperCamelCase					,						__UpperCamelCase					,						__UpperCamelCase					,						)->	Dict:
           __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()


      def  __UpperCAmelCase		(	self	)->	float:
           __lowerCAmelCase								=					abs(self.pos_x - self.goal_x	)
           __lowerCAmelCase								=					abs(self.pos_y - self.goal_y	)
           return dx + dy


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



class 							_UpperCamelCase			:


      def __init__(	self					,						__UpperCamelCase					,						__UpperCamelCase	)->	str:
           __lowerCAmelCase								=					Node(start[1]					,						start[0]					,						goal[1]					,						goal[0]					,						0					,						__UpperCamelCase	)
           __lowerCAmelCase								=					Node(goal[1]					,						goal[0]					,						goal[1]					,						goal[0]					,						9_9_9_9_9					,						__UpperCamelCase	)

           __lowerCAmelCase								=					[self.start]
           __lowerCAmelCase								=					[]

           __lowerCAmelCase								=					False


      def  __UpperCAmelCase		(	self	)->	Path | None:
           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:
                     __lowerCAmelCase								=					True
                     return self.retrace_path(__UpperCamelCase	)

                self.closed_nodes.append(__UpperCamelCase	)
                __lowerCAmelCase								=					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
                          __lowerCAmelCase								=					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	)

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


      def  __UpperCAmelCase		(	self					,						__UpperCamelCase	)->	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(__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  __UpperCAmelCase		(	self					,						__UpperCamelCase	)->	Path:
           __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


if __name__ == "__main__":
 lowerCamelCase			:					Tuple         =	(0, 0)
 lowerCamelCase			:					Optional[int]         =	(len(grid) - 1, len(grid[0]) - 1)
 for elem in grid:
  print(elem)

 print('''------''')

 lowerCamelCase			:					Tuple         =	GreedyBestFirst(init, goal)
 lowerCamelCase			:					str         =	greedy_bf.search()
 if path:
  for pos_x, pos_y in path:
   lowerCamelCase			:					List[Any]         =	2

  for elem in grid:
   print(elem)














import random



class 							_UpperCamelCase			:


      @staticmethod
      def  __UpperCAmelCase		(	__UpperCamelCase	)->	tuple[list[int], list[int]]:
           __lowerCAmelCase								=					[ord(__UpperCamelCase	) for i in text]
           __lowerCAmelCase								=					[]
           __lowerCAmelCase								=					[]
           for i in plain:
                __lowerCAmelCase								=					random.randint(1					,						3_0_0	)
                __lowerCAmelCase								=					(i + k) * k
                cipher.append(__UpperCamelCase	)
                key.append(__UpperCamelCase	)
           return cipher, key


      @staticmethod
      def  __UpperCAmelCase		(	__UpperCamelCase					,						__UpperCamelCase	)->	str:
           __lowerCAmelCase								=					[]
           for i in range(len(__UpperCamelCase	)	):
                __lowerCAmelCase								=					int((cipher[i] - (key[i]) ** 2) / key[i]	)
                plain.append(chr(__UpperCamelCase	)	)
           return "".join(__UpperCamelCase	)


if __name__ == "__main__":
 lowerCamelCase      ,					lowerCamelCase			:					List[Any]         =	Onepad().encrypt('''Hello''')
 print(c, k)
 print(Onepad().decrypt(c, k))






