



from __future__ import annotations

import time

UpperCAmelCase__       =	list[tuple[int, int]]

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







class       __lowerCAmelCase   :



			def __init__(						self       :  List[str]			,		A       :  int			,		A       :  int			,		A       :  int			,		A       :  int			,		A       :  Node | None)       ->   Optional[int]:



						"""simple docstring"""






						_UpperCAmelCase			=       pos_x
						_UpperCAmelCase			=       pos_y
						_UpperCAmelCase			=       (pos_y, pos_x)
						_UpperCAmelCase			=       goal_x
						_UpperCAmelCase			=       goal_y
						_UpperCAmelCase			=       parent







class       __lowerCAmelCase   :



			def __init__(						self       :  Dict			,		A       :  tuple[int, int]			,		A       :  tuple[int, int])       ->   Tuple:



						"""simple docstring"""






						_UpperCAmelCase			=       Node(start[1]			,		start[0]			,		goal[1]			,		goal[0]			,		A)
						_UpperCAmelCase			=       Node(goal[1]			,		goal[0]			,		goal[1]			,		goal[0]			,		A)

						_UpperCAmelCase			=       [self.start]
						_UpperCAmelCase			=       False



			def    _lowerCamelCase	(						self       :  Optional[int])       ->   Path | None:



						"""simple docstring"""






						while self.node_queue:
									_UpperCAmelCase			=       self.node_queue.pop(0)

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

									_UpperCAmelCase			=       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       :  Optional[int]			,		A       :  Node)       ->   list[Node]:



						"""simple docstring"""






						_UpperCAmelCase			=       []
						for action in delta:
									_UpperCAmelCase			=       parent.pos_x + action[1]
									_UpperCAmelCase			=       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       :  List[Any]			,		A       :  Node | None)       ->   Path:



						"""simple docstring"""






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







class       __lowerCAmelCase   :



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



						"""simple docstring"""






						_UpperCAmelCase			=       BreadthFirstSearch(A			,		A)
						_UpperCAmelCase			=       BreadthFirstSearch(A			,		A)
						_UpperCAmelCase			=       False



			def    _lowerCamelCase	(						self       :  Optional[int])       ->   Path | None:



						"""simple docstring"""






						while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
									_UpperCAmelCase			=       self.fwd_bfs.node_queue.pop(0)
									_UpperCAmelCase			=       self.bwd_bfs.node_queue.pop(0)

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

									_UpperCAmelCase			=       current_bwd_node
									_UpperCAmelCase			=       current_fwd_node

									_UpperCAmelCase			=       {
									    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       :  Optional[Any]			,		A       :  Node			,		A       :  Node)       ->   Path:



						"""simple docstring"""






						_UpperCAmelCase			=       self.fwd_bfs.retrace_path(A)
						_UpperCAmelCase			=       self.bwd_bfs.retrace_path(A)
						bwd_path.pop()
						bwd_path.reverse()
						_UpperCAmelCase			=       fwd_path + bwd_path
						return path


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

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

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

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

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

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





import string

import numpy





def 							A     (					_UpperCAmelCase    :       int							,       _UpperCAmelCase    :       int   )    ->			int:







			'''simple docstring'''
			return b if a == 0 else greatest_common_divisor(b % a							,       _UpperCAmelCase   )







class       __lowerCAmelCase   :
			UpperCamelCase        =					string.ascii_uppercase + string.digits
			# This cipher takes alphanumerics into account
			# i.e. a total of 36 characters

			# take x and return x % len(key_string)
			UpperCamelCase        =					numpy.vectorize(lambda A						: x % 3_6						)

			UpperCamelCase        =					numpy.vectorize(A						)



			def __init__(						self       :  Tuple			,		A       :  numpy.ndarray)       ->   None:



						"""simple docstring"""






						_UpperCAmelCase			=       self.modulus(A)  # mod36 calc's on the encrypt key
						self.check_determinant()  # validate the determinant of the encryption key
						_UpperCAmelCase			=       encrypt_key.shape[0]



			def    _lowerCamelCase	(						self       :  str			,		A       :  str)       ->   int:



						"""simple docstring"""






						return self.key_string.index(A)



			def    _lowerCamelCase	(						self       :  Any			,		A       :  int)       ->   str:



						"""simple docstring"""






						return self.key_string[round(A)]



			def    _lowerCamelCase	(						self       :  Union[str, Any])       ->   None:



						"""simple docstring"""






						_UpperCAmelCase			=       round(numpy.linalg.det(self.encrypt_key))

						if det < 0:
									_UpperCAmelCase			=       det % len(self.key_string)

						_UpperCAmelCase			=       len(self.key_string)
						if greatest_common_divisor(A			,		len(self.key_string)) != 1:
									_UpperCAmelCase			=       (
									    F"determinant modular {req_l} of encryption key({det}) "
									    F"is not co prime w.r.t {req_l}.\nTry another key."
									)
									raise ValueError(A)



			def    _lowerCamelCase	(						self       :  Union[str, Any]			,		A       :  str)       ->   str:



						"""simple docstring"""






						_UpperCAmelCase			=       [char for char in text.upper() if char in self.key_string]

						_UpperCAmelCase			=       chars[-1]
						while len(A) % self.break_key != 0:
									chars.append(A)

						return "".join(A)



			def    _lowerCamelCase	(						self       :  Union[str, Any]			,		A       :  str)       ->   str:



						"""simple docstring"""






						_UpperCAmelCase			=       self.process_text(text.upper())
						_UpperCAmelCase			=       ''

						for i in range(0			,		len(A) - self.break_key + 1			,		self.break_key):
									_UpperCAmelCase			=       text[i : i + self.break_key]
									_UpperCAmelCase			=       [self.replace_letters(A) for char in batch]
									_UpperCAmelCase			=       numpy.array([vec]).T
									_UpperCAmelCase			=       self.modulus(self.encrypt_key.dot(A)).T.tolist()[
									    0
									]
									_UpperCAmelCase			=       ''.join(
									    self.replace_digits(A) for num in batch_encrypted)
									encrypted += encrypted_batch

						return encrypted



			def    _lowerCamelCase	(						self       :  Optional[Any])       ->   numpy.ndarray:



						"""simple docstring"""






						_UpperCAmelCase			=       round(numpy.linalg.det(self.encrypt_key))

						if det < 0:
									_UpperCAmelCase			=       det % len(self.key_string)
						_UpperCAmelCase			=       None
						for i in range(len(self.key_string)):
									if (det * i) % len(self.key_string) == 1:
												_UpperCAmelCase			=       i
												break

						_UpperCAmelCase			=       (
						    det_inv
						    * numpy.linalg.det(self.encrypt_key)
						    * numpy.linalg.inv(self.encrypt_key)
						)

						return self.to_int(self.modulus(A))



			def    _lowerCamelCase	(						self       :  Tuple			,		A       :  str)       ->   str:



						"""simple docstring"""






						_UpperCAmelCase			=       self.make_decrypt_key()
						_UpperCAmelCase			=       self.process_text(text.upper())
						_UpperCAmelCase			=       ''

						for i in range(0			,		len(A) - self.break_key + 1			,		self.break_key):
									_UpperCAmelCase			=       text[i : i + self.break_key]
									_UpperCAmelCase			=       [self.replace_letters(A) for char in batch]
									_UpperCAmelCase			=       numpy.array([vec]).T
									_UpperCAmelCase			=       self.modulus(decrypt_key.dot(A)).T.tolist()[0]
									_UpperCAmelCase			=       ''.join(
									    self.replace_digits(A) for num in batch_decrypted)
									decrypted += decrypted_batch

						return decrypted





def 							A     (					)    ->			None:







			'''simple docstring'''
			_UpperCAmelCase			=       int(input('Enter the order of the encryption key: '   )   )
			_UpperCAmelCase			=       []

			print('Enter each row of the encryption key with space separated integers'   )
			for _ in range(_UpperCAmelCase   ):
						_UpperCAmelCase			=       [int(_UpperCAmelCase   ) for x in input().split()]
						hill_matrix.append(_UpperCAmelCase   )

			_UpperCAmelCase			=       HillCipher(numpy.array(_UpperCAmelCase   )   )

			print('Would you like to encrypt or decrypt some text? (1 or 2)'   )
			_UpperCAmelCase			=       input('\n1. Encrypt\n2. Decrypt\n'   )
			if option == "1":
						_UpperCAmelCase			=       input('What text would you like to encrypt?: '   )
						print('Your encrypted text is:'   )
						print(hc.encrypt(_UpperCAmelCase   )   )
			elif option == "2":
						_UpperCAmelCase			=       input('What text would you like to decrypt?: '   )
						print('Your decrypted text is:'   )
						print(hc.decrypt(_UpperCAmelCase   )   )


if __name__ == "__main__":
							import doctest

							doctest.testmod()

							main()
