





'''simple docstring'''

import string

import numpy





def 			lowerCAmelCase_						(    a					:					Union[str, Any]   , a					:					List[str]				):
							return b if a == 0 else greatest_common_divisor(b % a   , __lowerCAmelCase				)






class       _UpperCamelCase      :






				'''simple docstring'''





				SCREAMING_SNAKE_CASE:Dict         =	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)
				SCREAMING_SNAKE_CASE:Any         =	numpy.vectorize(lambda _A			: x % 36			)

				SCREAMING_SNAKE_CASE:List[str]         =	numpy.vectorize(SCREAMING_SNAKE_CASE_			)






				def __init__(				self       ,					_a    ):
											"""simple docstring"""
											a__            =							self.modulus(_a    )  # mod36 calc's on the encrypt key
											self.check_determinant()  # validate the determinant of the encryption key
											a__            =							encrypt_key.shape[0]






				def        lowercase__   (				self       ,					_a    ):
											"""simple docstring"""
											return self.key_string.index(_a    )






				def        lowercase__   (				self       ,					_a    ):
											"""simple docstring"""
											return self.key_string[round(_a    )]






				def        lowercase__   (				self    ):
											"""simple docstring"""
											a__            =							round(numpy.linalg.det(self.encrypt_key    )    )

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

											a__            =							len(self.key_string    )
											if greatest_common_divisor(_a       ,					len(self.key_string    )    ) != 1:
																		a__            =							(
																		    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        lowercase__   (				self       ,					_a    ):
											"""simple docstring"""
											a__            =							[char for char in text.upper() if char in self.key_string]

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

											return "".join(_a    )






				def        lowercase__   (				self       ,					_a    ):
											"""simple docstring"""
											a__            =							self.process_text(text.upper()    )
											a__            =							''

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

											return encrypted






				def        lowercase__   (				self    ):
											"""simple docstring"""
											a__            =							round(numpy.linalg.det(self.encrypt_key    )    )

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

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

											return self.to_int(self.modulus(_a    )    )






				def        lowercase__   (				self       ,					_a    ):
											"""simple docstring"""
											a__            =							self.make_decrypt_key()
											a__            =							self.process_text(text.upper()    )
											a__            =							''

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

											return decrypted





def 			lowerCAmelCase_						(    ):
							a__            =							int(input('Enter the order of the encryption key: '				)				)
							a__            =							[]

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

							a__            =							HillCipher(numpy.array(__lowerCAmelCase				)				)

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


if __name__ == "__main__":
		import doctest

		doctest.testmod()

		main()










from __future__ import annotations

import time
from math import sqrt

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

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

_lowerCamelCase    :		Union[str, Any]		      =    tuple[int, int]


class 						lowercase    :
						'''simple docstring'''


						def __init__(  self    :				Optional[Any]       ,	snake_case    :				int       ,	snake_case    :				int       ,	snake_case    :				int       ,	snake_case    :				int       ,	snake_case    :				int       ,	snake_case    :				Node | None       ,	):



											'''simple docstring'''


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







						def       lowerCamelCase_				(  self    :				Optional[int]	):



											'''simple docstring'''


											SCREAMING_SNAKE_CASE							:     int						=				self.pos_x - self.goal_x
											SCREAMING_SNAKE_CASE							:     str						=				self.pos_y - self.goal_y
											if HEURISTIC == 1:
																return abs(snake_case	) + abs(snake_case	)
											else:
																return sqrt(dy**2 + dx**2	)







						def __lt__(  self    :				Any       ,	snake_case    :				Node	):



											'''simple docstring'''


											return self.f_cost < other.f_cost


class 						lowercase    :
						'''simple docstring'''


						def __init__(  self    :				Optional[Any]       ,	snake_case    :				TPosition       ,	snake_case    :				TPosition	):



											'''simple docstring'''


											SCREAMING_SNAKE_CASE							:     Union[str, Any]						=				Node(start[1]       ,	start[0]       ,	goal[1]       ,	goal[0]       ,	0       ,	snake_case	)
											SCREAMING_SNAKE_CASE							:     int						=				Node(goal[1]       ,	goal[0]       ,	goal[1]       ,	goal[0]       ,	99999       ,	snake_case	)

											SCREAMING_SNAKE_CASE							:     Any						=				[self.start]
											SCREAMING_SNAKE_CASE							:     list[Node]						=				[]

											SCREAMING_SNAKE_CASE							:     int						=				False







						def       lowerCamelCase_				(  self    :				str	):



											'''simple docstring'''


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

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

																self.closed_nodes.append(snake_case	)
																SCREAMING_SNAKE_CASE							:     int						=				self.get_successors(snake_case	)

																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(snake_case	)
																					else:
																										# retrieve the best current path
																										SCREAMING_SNAKE_CASE							:     Union[str, Any]						=				self.open_nodes.pop(self.open_nodes.index(snake_case	)	)

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

											return [self.start.pos]







						def       lowerCamelCase_				(  self    :				str       ,	snake_case    :				Node	):



											'''simple docstring'''


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

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

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







						def       lowerCamelCase_				(  self    :				Optional[int]       ,	snake_case    :				Node | None	):



											'''simple docstring'''


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


class 						lowercase    :
						'''simple docstring'''


						def __init__(  self    :				str       ,	snake_case    :				TPosition       ,	snake_case    :				TPosition	):



											'''simple docstring'''


											SCREAMING_SNAKE_CASE							:     Any						=				AStar(snake_case       ,	snake_case	)
											SCREAMING_SNAKE_CASE							:     Optional[int]						=				AStar(snake_case       ,	snake_case	)
											SCREAMING_SNAKE_CASE							:     str						=				False







						def       lowerCamelCase_				(  self    :				Optional[int]	):



											'''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()
																SCREAMING_SNAKE_CASE							:     Dict						=				self.fwd_astar.open_nodes.pop(0	)
																SCREAMING_SNAKE_CASE							:     Any						=				self.bwd_astar.open_nodes.pop(0	)

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

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

																SCREAMING_SNAKE_CASE							:     str						=				current_bwd_node
																SCREAMING_SNAKE_CASE							:     int						=				current_fwd_node

																SCREAMING_SNAKE_CASE							:     str						=				{
																    self.fwd_astar: self.fwd_astar.get_successors(snake_case	),
																    self.bwd_astar: self.bwd_astar.get_successors(snake_case	),
																}

																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(snake_case	)
																										else:
																															# retrieve the best current path
																															SCREAMING_SNAKE_CASE							:     List[Any]						=				astar.open_nodes.pop(
																															    astar.open_nodes.index(snake_case	)	)

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

											return [self.fwd_astar.start.pos]







						def       lowerCamelCase_				(  self    :				str       ,	snake_case    :				Node       ,	snake_case    :				Node	):



											'''simple docstring'''


											SCREAMING_SNAKE_CASE							:     Union[str, Any]						=				self.fwd_astar.retrace_path(snake_case	)
											SCREAMING_SNAKE_CASE							:     Optional[Any]						=				self.bwd_astar.retrace_path(snake_case	)
											bwd_path.pop()
											bwd_path.reverse()
											SCREAMING_SNAKE_CASE							:     Union[str, Any]						=				fwd_path + bwd_path
											return path


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

			_lowerCamelCase    :		Union[str, Any]		      =    time.time()
			_lowerCamelCase    :		List[str]		      =    AStar(init, goal)
			_lowerCamelCase    :		Optional[int]		      =    a_star.search()
			_lowerCamelCase    :		str		      =    time.time() - start_time
			print(f"""AStar execution time = {end_time:f} seconds""")

			_lowerCamelCase    :		Optional[Any]		      =    time.time()
			_lowerCamelCase    :		Union[str, Any]		      =    BidirectionalAStar(init, goal)
			_lowerCamelCase    :		List[Any]		      =    time.time() - bd_start_time
			print(f"""BidirectionalAStar execution time = {bd_end_time:f} seconds""")