
from __future__ import annotations

lowerCamelCase_    :			Tuple    =	tuple[int, int, int]
lowerCamelCase_    :			List[str]    =	tuple[str, str, str]


# used alphabet --------------------------
# from string.ascii_uppercase
lowerCamelCase_    :			Tuple    =	"""ABCDEFGHIJKLMNOPQRSTUVWXYZ"""

# -------------------------- default selection --------------------------
# rotors --------------------------
lowerCamelCase_    :			List[Any]    =	"""EGZWVONAHDCLFQMSIPJBYUKXTR"""
lowerCamelCase_    :			List[str]    =	"""FOBHMDKEXQNRAULPGSJVTYICZW"""
lowerCamelCase_    :			List[Any]    =	"""ZJXESIUQLHAVRMDOYGTNFWPBKC"""
# reflector --------------------------
lowerCamelCase_    :			Any    =	{
    """A""": """N""",
    """N""": """A""",
    """B""": """O""",
    """O""": """B""",
    """C""": """P""",
    """P""": """C""",
    """D""": """Q""",
    """Q""": """D""",
    """E""": """R""",
    """R""": """E""",
    """F""": """S""",
    """S""": """F""",
    """G""": """T""",
    """T""": """G""",
    """H""": """U""",
    """U""": """H""",
    """I""": """V""",
    """V""": """I""",
    """J""": """W""",
    """W""": """J""",
    """K""": """X""",
    """X""": """K""",
    """L""": """Y""",
    """Y""": """L""",
    """M""": """Z""",
    """Z""": """M""",
}

# -------------------------- extra rotors --------------------------
lowerCamelCase_    :			Optional[Any]    =	"""RMDJXFUWGISLHVTCQNKYPBEZOA"""
lowerCamelCase_    :			Union[str, Any]    =	"""SGLCPQWZHKXAREONTFBVIYJUDM"""
lowerCamelCase_    :			Optional[int]    =	"""HVSICLTYKQUBXDWAJZOMFGPREN"""
lowerCamelCase_    :			str    =	"""RZWQHFMVDBKICJLNTUXAGYPSOE"""
lowerCamelCase_    :			str    =	"""LFKIJODBEGAMQPXVUHYSTCZRWN"""
lowerCamelCase_    :			Optional[int]    =	"""KOAEGVDHXPQZMLFTYWJNBRCIUS"""







def 							A__       (    lowerCamelCase  ,     lowerCamelCase  ,     lowerCamelCase    )	->						tuple[RotorPositionT, RotorSelectionT, dict[str, str]]:
				# Checks if there are 3 unique rotors

				if (unique_rotsel := len(set(lowerCamelCase    )    )) < 3:
								UpperCamelCase_:				List[str]						=    F'''Please use 3 unique rotors (not {unique_rotsel})'''
								raise Exception(lowerCamelCase    )

				# Checks if rotor positions are valid
				UpperCamelCase_, UpperCamelCase_, UpperCamelCase_:				List[str]						=    rotpos
				if not 0 < rotorposa <= len(lowerCamelCase    ):
								UpperCamelCase_:				List[Any]						=    F'''First rotor position is not within range of 1..26 ({rotorposa}'''
								raise ValueError(lowerCamelCase    )
				if not 0 < rotorposa <= len(lowerCamelCase    ):
								UpperCamelCase_:				Dict						=    F'''Second rotor position is not within range of 1..26 ({rotorposa})'''
								raise ValueError(lowerCamelCase    )
				if not 0 < rotorposa <= len(lowerCamelCase    ):
								UpperCamelCase_:				Tuple						=    F'''Third rotor position is not within range of 1..26 ({rotorposa})'''
								raise ValueError(lowerCamelCase    )

				# Validates string and returns dict
				UpperCamelCase_:				Any						=    _plugboard(lowerCamelCase    )

				return rotpos, rotsel, pbdict







def 							A__       (    lowerCamelCase    )	->						dict[str, str]:

				# tests the input string if it
				# a) is type string
				# b) has even length (so pairs can be made)
				if not isinstance(lowerCamelCase  ,     lowerCamelCase    ):
								UpperCamelCase_:				Dict						=    F'''Plugboard setting isn\'t type string ({type(lowerCamelCase    )})'''
								raise TypeError(lowerCamelCase    )
				elif len(lowerCamelCase    ) % 2 != 0:
								UpperCamelCase_:				Any						=    F'''Odd number of symbols ({len(lowerCamelCase    )})'''
								raise Exception(lowerCamelCase    )
				elif pbstring == "":
								return {}

				pbstring.replace(""" """  ,     """"""    )

				# Checks if all characters are unique
				UpperCamelCase_:				str						=    set()
				for i in pbstring:
								if i not in abc:
												UpperCamelCase_:				Optional[Any]						=    F'''\'{i}\' not in list of symbols'''
												raise Exception(lowerCamelCase    )
								elif i in tmppbl:
												UpperCamelCase_:				Dict						=    F'''Duplicate symbol ({i})'''
												raise Exception(lowerCamelCase    )
								else:
												tmppbl.add(lowerCamelCase    )
				del tmppbl

				# Created the dictionary
				UpperCamelCase_:				Any						=    {}
				for j in range(0  ,     len(lowerCamelCase    ) - 1  ,     2    ):
								UpperCamelCase_:				int						=    pbstring[j + 1]
								UpperCamelCase_:				List[Any]						=    pbstring[j]

				return pb







def 							A__       (    lowerCamelCase  ,     lowerCamelCase  ,     lowerCamelCase = (rotora, rotora, rotora)  ,     lowerCamelCase = ""  ,     )	->						str:
				UpperCamelCase_:				Tuple						=    text.upper()
				UpperCamelCase_, UpperCamelCase_, UpperCamelCase_:				Any						=    _validator(
				    lowerCamelCase  ,     lowerCamelCase  ,     plugb.upper()    )

				UpperCamelCase_, UpperCamelCase_, UpperCamelCase_:				int						=    rotor_position
				UpperCamelCase_, UpperCamelCase_, UpperCamelCase_:				List[Any]						=    rotor_selection
				rotorposa -= 1
				rotorposa -= 1
				rotorposa -= 1

				UpperCamelCase_:				Any						=    []

				# encryption/decryption process --------------------------
				for symbol in text:
								if symbol in abc:
												# 1st plugboard --------------------------
												if symbol in plugboard:
																UpperCamelCase_:				Optional[int]						=    plugboard[symbol]

												# rotor ra --------------------------
												UpperCamelCase_:				Union[str, Any]						=    abc.index(lowerCamelCase    ) + rotorposa
												UpperCamelCase_:				Any						=    rotora[index % len(lowerCamelCase    )]

												# rotor rb --------------------------
												UpperCamelCase_:				Union[str, Any]						=    abc.index(lowerCamelCase    ) + rotorposa
												UpperCamelCase_:				Optional[int]						=    rotora[index % len(lowerCamelCase    )]

												# rotor rc --------------------------
												UpperCamelCase_:				Dict						=    abc.index(lowerCamelCase    ) + rotorposa
												UpperCamelCase_:				Optional[int]						=    rotora[index % len(lowerCamelCase    )]

												# reflector --------------------------
												# this is the reason you don't need another machine to decipher

												UpperCamelCase_:				List[Any]						=    reflector[symbol]

												# 2nd rotors
												UpperCamelCase_:				Any						=    abc[rotora.index(lowerCamelCase    ) - rotorposa]
												UpperCamelCase_:				List[str]						=    abc[rotora.index(lowerCamelCase    ) - rotorposa]
												UpperCamelCase_:				List[Any]						=    abc[rotora.index(lowerCamelCase    ) - rotorposa]

												# 2nd plugboard
												if symbol in plugboard:
																UpperCamelCase_:				Any						=    plugboard[symbol]

												# moves/resets rotor positions
												rotorposa += 1
												if rotorposa >= len(lowerCamelCase    ):
																UpperCamelCase_:				Any						=    0
																rotorposa += 1
												if rotorposa >= len(lowerCamelCase    ):
																UpperCamelCase_:				Optional[Any]						=    0
																rotorposa += 1
												if rotorposa >= len(lowerCamelCase    ):
																UpperCamelCase_:				Any						=    0

        # else:
        #    pass
        #    Error could be also raised
        #    raise ValueError(
        #       'Invalid symbol('+repr(symbol)+')')
								result.append(lowerCamelCase    )

				return "".join(lowerCamelCase    )


if __name__ == "__main__":
							lowerCamelCase_    :			Union[str, Any]    =	"""This is my Python script that emulates the Enigma machine from WWII."""
							lowerCamelCase_    :			str    =	(1, 1, 1)
							lowerCamelCase_    :			Optional[Any]    =	"""pictures"""
							lowerCamelCase_    :			Optional[int]    =	(rotora, rotora, rotora)
							lowerCamelCase_    :			int    =	enigma(message, rotor_pos, rotor_sel, pb)

							print("""Encrypted message:""", en)
							print("""Decrypted message:""", enigma(en, rotor_pos, rotor_sel, pb))








from __future__ import annotations

import time

lowerCamelCase_    :			Union[str, Any]    =	list[tuple[int, int]]

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

class 							_UpperCamelCase					:






			'''simple docstring'''

			def __init__(							self			:							Dict    ,						snake_case_			:							int    ,						snake_case_			:							int    ,						snake_case_			:							int    ,						snake_case_			:							int    ,						snake_case_			:							Node | None   ):
							UpperCamelCase_:				str						=    pos_x
							UpperCamelCase_:				List[str]						=    pos_y
							UpperCamelCase_:				str						=    (pos_y, pos_x)
							UpperCamelCase_:				Any						=    goal_x
							UpperCamelCase_:				Optional[int]						=    goal_y
							UpperCamelCase_:				Union[str, Any]						=    parent




class 							_UpperCamelCase					:






			'''simple docstring'''

			def __init__(							self			:							str    ,						snake_case_			:							tuple[int, int]    ,						snake_case_			:							tuple[int, int]   ):
							UpperCamelCase_:				Optional[Any]						=    Node(start[1]    ,						start[0]    ,						goal[1]    ,						goal[0]    ,						snake_case_   )
							UpperCamelCase_:				List[str]						=    Node(goal[1]    ,						goal[0]    ,						goal[1]    ,						goal[0]    ,						snake_case_   )

							UpperCamelCase_:				Any						=    [self.start]
							UpperCamelCase_:				Dict						=    False

			def    lowerCAmelCase__						(							self			:							str   ):
							while self.node_queue:
											UpperCamelCase_:				int						=    self.node_queue.pop(0   )

											if current_node.pos == self.target.pos:
															UpperCamelCase_:				List[str]						=    True
															return self.retrace_path(snake_case_   )

											UpperCamelCase_:				List[str]						=    self.get_successors(snake_case_   )

											for node in successors:
															self.node_queue.append(snake_case_   )

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

			def    lowerCAmelCase__						(							self			:							Dict    ,						snake_case_			:							Node   ):
							UpperCamelCase_:				int						=    []
							for action in delta:
											UpperCamelCase_:				Union[str, Any]						=    parent.pos_x + action[1]
											UpperCamelCase_:				str						=    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    ,						snake_case_   )   )
							return successors




			def    lowerCAmelCase__						(							self			:							int    ,						snake_case_			:							Node | None   ):
							UpperCamelCase_:				int						=    node
							UpperCamelCase_:				Tuple						=    []
							while current_node is not None:
											path.append((current_node.pos_y, current_node.pos_x)   )
											UpperCamelCase_:				List[Any]						=    current_node.parent
							path.reverse()
							return path




class 							_UpperCamelCase					:






			'''simple docstring'''

			def __init__(							self			:							Optional[Any]    ,						snake_case_			:							Optional[Any]    ,						snake_case_			:							Optional[Any]   ):
							UpperCamelCase_:				Tuple						=    BreadthFirstSearch(snake_case_    ,						snake_case_   )
							UpperCamelCase_:				Dict						=    BreadthFirstSearch(snake_case_    ,						snake_case_   )
							UpperCamelCase_:				int						=    False

			def    lowerCAmelCase__						(							self			:							int   ):
							while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
											UpperCamelCase_:				List[Any]						=    self.fwd_bfs.node_queue.pop(0   )
											UpperCamelCase_:				Optional[Any]						=    self.bwd_bfs.node_queue.pop(0   )

											if current_bwd_node.pos == current_fwd_node.pos:
															UpperCamelCase_:				List[Any]						=    True
															return self.retrace_bidirectional_path(
															    snake_case_    ,						snake_case_   )

											UpperCamelCase_:				Optional[Any]						=    current_bwd_node
											UpperCamelCase_:				List[Any]						=    current_fwd_node

											UpperCamelCase_:				List[str]						=    {
											    self.fwd_bfs: self.fwd_bfs.get_successors(snake_case_   ),
											    self.bwd_bfs: self.bwd_bfs.get_successors(snake_case_   ),
											}

											for bfs in [self.fwd_bfs, self.bwd_bfs]:
															for node in successors[bfs]:
																			bfs.node_queue.append(snake_case_   )

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




			def    lowerCAmelCase__						(							self			:							List[str]    ,						snake_case_			:							Node    ,						snake_case_			:							Node   ):
							UpperCamelCase_:				List[str]						=    self.fwd_bfs.retrace_path(snake_case_   )
							UpperCamelCase_:				Tuple						=    self.bwd_bfs.retrace_path(snake_case_   )
							bwd_path.pop()
							bwd_path.reverse()
							UpperCamelCase_:				List[str]						=    fwd_path + bwd_path
							return path


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

							doctest.testmod()
							lowerCamelCase_    :			Tuple    =	(0, 0)
							lowerCamelCase_    :			Union[str, Any]    =	(len(grid) - 1, len(grid[0]) - 1)
							for elem in grid:
														print(elem)

							lowerCamelCase_    :			Optional[int]    =	time.time()
							lowerCamelCase_    :			Tuple    =	BreadthFirstSearch(init, goal)
							lowerCamelCase_    :			List[str]    =	bfs.search()
							lowerCamelCase_    :			Optional[int]    =	time.time() - start_bfs_time

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

							lowerCamelCase_    :			Optional[int]    =	time.time()
							lowerCamelCase_    :			Optional[int]    =	BidirectionalBreadthFirstSearch(init, goal)
							lowerCamelCase_    :			str    =	bd_bfs.search()
							lowerCamelCase_    :			Tuple    =	time.time() - start_bd_bfs_time

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






