

"""simple docstring"""


from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
snake_case_    					=	0

snake_case_    					=	[
    [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],
]

snake_case_    					=	[[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

snake_case_    					=	tuple[int, int]







class 				A_      :



						"""simple docstring"""






						def __init__( self			:List[str]       ,  lowercase_			:int       ,  lowercase_			:int       ,  lowercase_			:int       ,  lowercase_			:int       ,  lowercase_			:int       ,  lowercase_			:Node | None       ,  )    ->      Optional[Any]:
												UpperCAmelCase					=			pos_x
												UpperCAmelCase					=			pos_y
												UpperCAmelCase					=			(pos_y, pos_x)
												UpperCAmelCase					=			goal_x
												UpperCAmelCase					=			goal_y
												UpperCAmelCase					=			g_cost
												UpperCAmelCase					=			parent
												UpperCAmelCase					=			self.calculate_heuristic()
												UpperCAmelCase					=			self.g_cost + self.h_cost






						def      UpperCAmelCase__					( self			:int )    ->      List[Any]:
												UpperCAmelCase					=			self.pos_x - self.goal_x
												UpperCAmelCase					=			self.pos_y - self.goal_y
												if HEURISTIC == 1:
																		return abs(lowercase__ ) + abs(lowercase__ )
												else:
																		return sqrt(dy**2 + dx**2 )






						def __lt__( self			:Dict       ,  lowercase_			:Node )    ->      Union[str, Any]:
												return self.f_cost < other.f_cost







class 				A_      :



						"""simple docstring"""






						def __init__( self			:str       ,  lowercase_			:TPosition       ,  lowercase_			:TPosition )    ->      Optional[int]:
												UpperCAmelCase					=			Node(start[1]       ,  start[0]       ,  goal[1]       ,  goal[0]       ,  0       ,  lowercase__ )
												UpperCAmelCase					=			Node(goal[1]       ,  goal[0]       ,  goal[1]       ,  goal[0]       ,  9_99_99       ,  lowercase__ )

												UpperCAmelCase					=			[self.start]
												UpperCAmelCase					=			[]

												UpperCAmelCase					=			False






						def      UpperCAmelCase__					( self			:Optional[Any] )    ->      Optional[Any]:
												while self.open_nodes:
																		# Open Nodes are sorted using __lt__
																		self.open_nodes.sort()
																		UpperCAmelCase					=			self.open_nodes.pop(0 )

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

																		self.closed_nodes.append(lowercase__ )
																		UpperCAmelCase					=			self.get_successors(lowercase__ )

																		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(lowercase__ )
																								else:
																														# retrieve the best current path
																														UpperCAmelCase					=			self.open_nodes.pop(self.open_nodes.index(lowercase__ ) )

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

												return [self.start.pos]






						def      UpperCAmelCase__					( self			:Union[str, Any]       ,  lowercase_			:Node )    ->      List[Any]:
												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(lowercase__ ) - 1):
																								continue

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

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






						def      UpperCAmelCase__					( self			:Any       ,  lowercase_			:Node | None )    ->      List[Any]:
												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 				A_      :



						"""simple docstring"""






						def __init__( self			:Optional[int]       ,  lowercase_			:TPosition       ,  lowercase_			:TPosition )    ->      str:
												UpperCAmelCase					=			AStar(lowercase__       ,  lowercase__ )
												UpperCAmelCase					=			AStar(lowercase__       ,  lowercase__ )
												UpperCAmelCase					=			False






						def      UpperCAmelCase__					( self			:List[Any] )    ->      Tuple:
												while self.fwd_astar.open_nodes or self.bwd_astar.open_nodes:
																		self.fwd_astar.open_nodes.sort()
																		self.bwd_astar.open_nodes.sort()
																		UpperCAmelCase					=			self.fwd_astar.open_nodes.pop(0 )
																		UpperCAmelCase					=			self.bwd_astar.open_nodes.pop(0 )

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

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

																		UpperCAmelCase					=			current_bwd_node
																		UpperCAmelCase					=			current_fwd_node

																		UpperCAmelCase					=			{
																		    self.fwd_astar: self.fwd_astar.get_successors(lowercase__ ),
																		    self.bwd_astar: self.bwd_astar.get_successors(lowercase__ ),
																		}

																		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(lowercase__ )
																														else:
																																				# retrieve the best current path
																																				UpperCAmelCase					=			astar.open_nodes.pop(
																																				    astar.open_nodes.index(lowercase__ ) )

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

												return [self.fwd_astar.start.pos]






						def      UpperCAmelCase__					( self			:Tuple       ,  lowercase_			:Node       ,  lowercase_			:Node )    ->      Optional[int]:
												UpperCAmelCase					=			self.fwd_astar.retrace_path(lowercase__ )
												UpperCAmelCase					=			self.bwd_astar.retrace_path(lowercase__ )
												bwd_path.pop()
												bwd_path.reverse()
												UpperCAmelCase					=			fwd_path + bwd_path
												return path


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

				snake_case_    					=	time.time()
				snake_case_    					=	AStar(init, goal)
				snake_case_    					=	a_star.search()
				snake_case_    					=	time.time() - start_time
				print(f'''AStar execution time = {end_time:f} seconds''')

				snake_case_    					=	time.time()
				snake_case_    					=	BidirectionalAStar(init, goal)
				snake_case_    					=	time.time() - bd_start_time
				print(f'''BidirectionalAStar execution time = {bd_end_time:f} seconds''')










"""simple docstring"""


import os
import random
import sys

from . import cryptomath_module as cryptomath
from . import rabin_miller

snake_case_    					=	3

def 			_lowerCAmelCase				(       lowercase_						):
						print('Generating primitive root of p'						)
						while True:
												UpperCAmelCase					=			random.randrange(3		,     lowercase_						)
												if pow(lowercase_		,     2		,     lowercase_						) == 1:
																		continue
												if pow(lowercase_		,     lowercase_		,     lowercase_						) == 1:
																		continue
												return g

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

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

						return public_key, private_key

def 			_lowerCAmelCase				(       lowercase_		,     lowercase_						):
						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(lowercase_						)
						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 			_lowerCAmelCase				(       ):
						print('Making key files...'						)
						make_key_files('elgamal'		,     2048						)
						print('Key files generation successful'						)


if __name__ == "__main__":
				main()





