


'''simple docstring'''





import heapq
import sys

import numpy as np

__snake_case            =   tuple[int, int]




class    UpperCAmelCase					:




			def __init__(						self							:		Optional[int]						):







						"""simple docstring"""







						UpperCamelCase         =					[]
						UpperCamelCase         =					set()




			def   lowerCamelCase_					(						self							:		Optional[int]						):







						"""simple docstring"""







						if not self.empty():
									return self.elements[0][0]
						else:
									return float("""inf"""						)




			def   lowerCamelCase_					(						self							:		str						):







						"""simple docstring"""







						return len(self.elements						) == 0




			def   lowerCamelCase_					(						self							:		int       ,       __magic_name__							:		List[Any]       ,       __magic_name__							:		List[str]						):







						"""simple docstring"""







						if item not in self.set:
									heapq.heappush(self.elements       ,       (priority, item)						)
									self.set.add(_A						)
						else:
									# update
									# print("update", item)
									UpperCamelCase         =					[]
									((UpperCamelCase)  ,  (UpperCamelCase))         =					heapq.heappop(self.elements						)
									while x != item:
												temp.append((pri, x)						)
												((UpperCamelCase)  ,  (UpperCamelCase))         =					heapq.heappop(self.elements						)
									temp.append((priority, item)						)
									for pro, xxx in temp:
												heapq.heappush(self.elements       ,       (pro, xxx)						)




			def   lowerCamelCase_					(						self							:		Union[str, Any]       ,       __magic_name__							:		str						):







						"""simple docstring"""







						if item in self.set:
									self.set.remove(_A						)
									UpperCamelCase         =					[]
									((UpperCamelCase)  ,  (UpperCamelCase))         =					heapq.heappop(self.elements						)
									while x != item:
												temp.append((pro, x)						)
												((UpperCamelCase)  ,  (UpperCamelCase))         =					heapq.heappop(self.elements						)
									for prito, yyy in temp:
												heapq.heappush(self.elements       ,       (prito, yyy)						)




			def   lowerCamelCase_					(						self							:		Optional[Any]						):







						"""simple docstring"""







						return self.elements[0][1]





			def   lowerCamelCase_					(						self							:		str						):







						"""simple docstring"""







						((UpperCamelCase)  ,  (UpperCamelCase))         =					heapq.heappop(self.elements						)
						self.set.remove(_A						)
						return (priority, item)






def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		str       ,  SCREAMING_SNAKE_CASE_   :		Optional[int]	):





			"""simple docstring"""




			UpperCamelCase         =					np.array(UpperCAmelCase__	)
			UpperCamelCase         =					np.array(UpperCAmelCase__	)
			return np.linalg.norm(a - b	)






def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		List[Any]       ,  SCREAMING_SNAKE_CASE_   :		Optional[int]	):





			"""simple docstring"""




			return consistent_heuristic(UpperCAmelCase__       ,  UpperCAmelCase__	) // t






def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		List[str]       ,  SCREAMING_SNAKE_CASE_   :		str	):





			"""simple docstring"""




			return abs(p[0] - goal[0]	) + abs(p[1] - goal[1]	)






def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		Tuple       ,  SCREAMING_SNAKE_CASE_   :		Union[str, Any]       ,  SCREAMING_SNAKE_CASE_   :		List[str]       ,  SCREAMING_SNAKE_CASE_   :		str	):





			"""simple docstring"""




			UpperCamelCase         =					g_function[start] + Wa * heuristics[i](UpperCAmelCase__       ,  UpperCAmelCase__	)
			return ans






def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		Union[str, Any]       ,  SCREAMING_SNAKE_CASE_   :		int       ,  SCREAMING_SNAKE_CASE_   :		Optional[int]	):





			"""simple docstring"""




			UpperCamelCase         =					np.chararray((n, n)	)
			for i in range(UpperCAmelCase__	):
						for j in range(UpperCAmelCase__	):
									UpperCamelCase         =					"""*"""

			for i in range(UpperCAmelCase__	):
						for j in range(UpperCAmelCase__	):
									if (j, (n - 1) - i) in blocks:
												UpperCamelCase         =					"""#"""

			UpperCamelCase         =					"""-"""
			UpperCamelCase         =					back_pointer[goal]
			while x != start:
						((UpperCamelCase)  ,  (UpperCamelCase))         =					x
						# print(x)
						UpperCamelCase         =					"""-"""
						UpperCamelCase         =					back_pointer[x]
			UpperCamelCase         =					"""-"""

			for i in range(UpperCAmelCase__	):
						for j in range(UpperCAmelCase__	):
									if (i, j) == (0, n - 1):
												print(grid[i][j]       ,  end=""" """	)
												print("""<-- End position"""       ,  end=""" """	)
									else:
												print(grid[i][j]       ,  end=""" """	)
						print()
			print("""^"""	)
			print("""Start position"""	)
			print()
			print("""# is an obstacle"""	)
			print("""- is the path taken by algorithm"""	)
			print("""PATH TAKEN BY THE ALGORITHM IS:-"""	)
			UpperCamelCase         =					back_pointer[goal]
			while x != start:
						print(UpperCAmelCase__       ,  end=""" """	)
						UpperCamelCase         =					back_pointer[x]
			print(UpperCAmelCase__	)
			sys.exit()






def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		List[str]	):





			"""simple docstring"""




			if p[0] < 0 or p[0] > n - 1:
						return False
			if p[1] < 0 or p[1] > n - 1:
						return False
			return True






def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		str       ,  SCREAMING_SNAKE_CASE_   :		int       ,  SCREAMING_SNAKE_CASE_   :		Optional[Any]       ,  SCREAMING_SNAKE_CASE_   :		int       ,  SCREAMING_SNAKE_CASE_   :		Any       ,  SCREAMING_SNAKE_CASE_   :		int       ,  SCREAMING_SNAKE_CASE_   :		int       ,  SCREAMING_SNAKE_CASE_   :		str       ,  ):





			"""simple docstring"""




			for itera in range(UpperCAmelCase__	):
						open_list[itera].remove_element(UpperCAmelCase__	)
			# print("s", s)
			# print("j", j)
			((UpperCamelCase)  ,  (UpperCamelCase))         =					s
			UpperCamelCase         =					(x - 1, y)
			UpperCamelCase         =					(x + 1, y)
			UpperCamelCase         =					(x, y + 1)
			UpperCamelCase         =					(x, y - 1)

			for neighbours in [left, right, up, down]:
						if neighbours not in blocks:
									if valid(UpperCAmelCase__	) and neighbours not in visited:
												# print("neighbour", neighbours)
												visited.add(UpperCAmelCase__	)
												UpperCamelCase         =					-1
												UpperCamelCase         =					float("""inf"""	)

									if valid(UpperCAmelCase__	) and g_function[neighbours] > g_function[s] + 1:
												UpperCamelCase         =					g_function[s] + 1
												UpperCamelCase         =					s
												if neighbours not in close_list_anchor:
															open_list[0].put(UpperCAmelCase__       ,  key(UpperCAmelCase__       ,  0       ,  UpperCAmelCase__       ,  UpperCAmelCase__	)	)
															if neighbours not in close_list_inad:
																		for var in range(1       ,  UpperCAmelCase__	):
																					if key(UpperCAmelCase__       ,  UpperCAmelCase__       ,  UpperCAmelCase__       ,  UpperCAmelCase__	) <= Wa * key(
																					    UpperCAmelCase__       ,  0       ,  UpperCAmelCase__       ,  UpperCAmelCase__	):
																								open_list[j].put(
																								    UpperCAmelCase__       ,  key(UpperCAmelCase__       ,  UpperCAmelCase__       ,  UpperCAmelCase__       ,  UpperCAmelCase__	)	)






def 							_lowercase    (		):





			"""simple docstring"""




			UpperCamelCase         =					[]
			for x in range(1       ,  5	):
						for y in range(1       ,  6	):
									some_list.append((x, y)	)

			for x in range(15       ,  20	):
						some_list.append((x, 17)	)

			for x in range(10       ,  19	):
						for y in range(1       ,  15	):
									some_list.append((x, y)	)

    # L block
			for x in range(1       ,  4	):
						for y in range(12       ,  19	):
									some_list.append((x, y)	)
			for x in range(3       ,  13	):
						for y in range(16       ,  19	):
									some_list.append((x, y)	)
			return some_list


__snake_case            =   {0: consistent_heuristic, 1: heuristic_a, 2: heuristic_a}

__snake_case            =   [
    (0, 1),
    (1, 1),
    (2, 1),
    (3, 1),
    (4, 1),
    (5, 1),
    (6, 1),
    (7, 1),
    (8, 1),
    (9, 1),
    (10, 1),
    (11, 1),
    (12, 1),
    (13, 1),
    (14, 1),
    (15, 1),
    (16, 1),
    (17, 1),
    (18, 1),
    (19, 1),
]
__snake_case            =   make_common_ground()


__snake_case            =   blocks_blk
# hyper parameters
__snake_case            =   1
__snake_case            =   1
__snake_case            =   20
__snake_case            =   3  # one consistent and two other inconsistent

# start and end destination
__snake_case            =   (0, 0)
__snake_case            =   (n - 1, n - 1)

__snake_case            =   1






def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		Union[str, Any]       ,  SCREAMING_SNAKE_CASE_   :		str       ,  SCREAMING_SNAKE_CASE_   :		int	):





			"""simple docstring"""




			UpperCamelCase         =					{start: 0, goal: float("""inf"""	)}
			UpperCamelCase         =					{start: -1, goal: -1}
			UpperCamelCase         =					[]
			UpperCamelCase         =					set()

			for i in range(UpperCAmelCase__	):
						open_list.append(PriorityQueue()	)
						open_list[i].put(UpperCAmelCase__       ,  key(UpperCAmelCase__       ,  UpperCAmelCase__       ,  UpperCAmelCase__       ,  UpperCAmelCase__	)	)

			UpperCamelCase         =					[]
			UpperCamelCase         =					[]
			while open_list[0].minkey() < float("""inf"""	):
						for i in range(1       ,  UpperCAmelCase__	):
									# print(open_list[0].minkey(), open_list[i].minkey())
									if open_list[i].minkey() <= Wa * open_list[0].minkey():
												global t
												t += 1
												if g_function[goal] <= open_list[i].minkey():
															if g_function[goal] < float("""inf"""	):
																		do_something(UpperCAmelCase__       ,  UpperCAmelCase__       ,  UpperCAmelCase__	)
												else:
															UpperCamelCase  ,  UpperCamelCase         =					open_list[i].top_show()
															visited.add(UpperCAmelCase__	)
															expand_state(
															    UpperCAmelCase__       ,  UpperCAmelCase__       ,  UpperCAmelCase__       ,  UpperCAmelCase__       ,  UpperCAmelCase__       ,  UpperCAmelCase__       ,  UpperCAmelCase__       ,  UpperCAmelCase__       ,  )
															close_list_inad.append(UpperCAmelCase__	)
									else:
												if g_function[goal] <= open_list[0].minkey():
															if g_function[goal] < float("""inf"""	):
																		do_something(UpperCAmelCase__       ,  UpperCAmelCase__       ,  UpperCAmelCase__	)
												else:
															UpperCamelCase         =					open_list[0].top_show()
															visited.add(UpperCAmelCase__	)
															expand_state(
															    UpperCAmelCase__       ,  0       ,  UpperCAmelCase__       ,  UpperCAmelCase__       ,  UpperCAmelCase__       ,  UpperCAmelCase__       ,  UpperCAmelCase__       ,  UpperCAmelCase__       ,  )
															close_list_anchor.append(UpperCAmelCase__	)
			print("""No path found to goal"""	)
			print()
			for i in range(n - 1       ,  -1       ,  -1	):
						for j in range(UpperCAmelCase__	):
									if (j, i) in blocks:
												print("""#"""       ,  end=""" """	)
									elif (j, i) in back_pointer:
												if (j, i) == (n - 1, n - 1):
															print("""*"""       ,  end=""" """	)
												else:
															print("""-"""       ,  end=""" """	)
									else:
												print("""*"""       ,  end=""" """	)
									if (j, i) == (n - 1, n - 1):
												print("""<-- End position"""       ,  end=""" """	)
						print()
			print("""^"""	)
			print("""Start position"""	)
			print()
			print("""# is an obstacle"""	)
			print("""- is the path taken by algorithm"""	)


if __name__ == "__main__":
			multi_a_star(start, goal, n_heuristic)








import os
import random
import sys

from . import cryptomath_module as cryptomath
from . import rabin_miller

__snake_case            =   3






def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		int	):





			"""simple docstring"""




			print("""Generating primitive root of p"""	)
			while True:
						UpperCamelCase         =					random.randrange(3       ,  SCREAMING_SNAKE_CASE_	)
						if pow(SCREAMING_SNAKE_CASE_       ,  2       ,  SCREAMING_SNAKE_CASE_	) == 1:
									continue
						if pow(SCREAMING_SNAKE_CASE_       ,  SCREAMING_SNAKE_CASE_       ,  SCREAMING_SNAKE_CASE_	) == 1:
									continue
						return g






def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		int	):





			"""simple docstring"""




			print("""Generating prime p..."""	)
			UpperCamelCase         =					rabin_miller.generate_large_prime(SCREAMING_SNAKE_CASE_	)  # select large prime number.
			UpperCamelCase         =					primitive_root(SCREAMING_SNAKE_CASE_	)  # one primitive root on modulo p.
			UpperCamelCase         =					random.randrange(3       ,  SCREAMING_SNAKE_CASE_	)  # private_key -> have to be greater than 2 for safety.
			UpperCamelCase         =					cryptomath.find_mod_inverse(pow(SCREAMING_SNAKE_CASE_       ,  SCREAMING_SNAKE_CASE_       ,  SCREAMING_SNAKE_CASE_	)       ,  SCREAMING_SNAKE_CASE_	)

			UpperCamelCase         =					(key_size, e_a, e_a, p)
			UpperCamelCase         =					(key_size, d)

			return public_key, private_key






def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		str       ,  SCREAMING_SNAKE_CASE_   :		int	):





			"""simple docstring"""




			if os.path.exists(f'{name}_pubkey.txt'	) or os.path.exists(f'{name}_privkey.txt'	):
						print("""\nWARNING:"""	)
						print(
						    f'"{name}_pubkey.txt" or "{name}_privkey.txt" already exists. \n'
						    """Use a different name or delete these files and re-run this program."""	)
						sys.exit()

			UpperCamelCase  ,  UpperCamelCase         =					generate_key(SCREAMING_SNAKE_CASE_	)
			print(f'\nWriting public key to file {name}_pubkey.txt...'	)
			with open(f'{name}_pubkey.txt'       ,  """w"""	) as fo:
						fo.write(f'{public_key[0]},{public_key[1]},{public_key[2]},{public_key[3]}'	)

			print(f'Writing private key to file {name}_privkey.txt...'	)
			with open(f'{name}_privkey.txt'       ,  """w"""	) as fo:
						fo.write(f'{private_key[0]},{private_key[1]}'	)






def 							_lowercase    (		):





			"""simple docstring"""




			print("""Making key files..."""	)
			make_key_files("""elgamal"""       ,  2_048	)
			print("""Key files generation successful"""	)


if __name__ == "__main__":
			main()




