'''simple docstring'''







from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
UpperCamelCase_      	=	0

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

UpperCamelCase_      	=	tuple[int, int]




class _SCREAMING_SNAKE_CASE:




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




						def      __lowerCamelCase       (    self :       int      )     ->				float:
													SCREAMING_SNAKE_CASE__     :List[Any]						    = self.pos_x - self.goal_x
													SCREAMING_SNAKE_CASE__     :List[str]						    = self.pos_y - self.goal_y
													if HEURISTIC == 1:
																				return abs(UpperCamelCase_      ) + abs(UpperCamelCase_      )
													else:
																				return sqrt(dy**2 + dx**2      )




						def __lt__(    self :       Tuple							,							UpperCamelCase_ :       Node      )     ->				bool:
													return self.f_cost < other.f_cost




class _SCREAMING_SNAKE_CASE:




						def __init__(    self :       Any							,							UpperCamelCase_ :       TPosition							,							UpperCamelCase_ :       TPosition      )     ->				str:
													SCREAMING_SNAKE_CASE__     :int						    = Node(start[1]							,							start[0]							,							goal[1]							,							goal[0]							,							0							,							UpperCamelCase_      )
													SCREAMING_SNAKE_CASE__     :Dict						    = Node(goal[1]							,							goal[0]							,							goal[1]							,							goal[0]							,							9_99_99							,							UpperCamelCase_      )

													SCREAMING_SNAKE_CASE__     :List[str]						    = [self.start]
													SCREAMING_SNAKE_CASE__     :list[Node]						    = []

													SCREAMING_SNAKE_CASE__     :Union[str, Any]						    = False




						def      __lowerCamelCase       (    self :       Union[str, Any]      )     ->				list[TPosition]:
													while self.open_nodes:
																				# Open Nodes are sorted using __lt__
																				self.open_nodes.sort()
																				SCREAMING_SNAKE_CASE__     :int						    = self.open_nodes.pop(0      )

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

																				self.closed_nodes.append(UpperCamelCase_      )
																				SCREAMING_SNAKE_CASE__     :Optional[Any]						    = self.get_successors(UpperCamelCase_      )

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

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

													return [self.start.pos]




						def      __lowerCamelCase       (    self :       str							,							UpperCamelCase_ :       Node      )     ->				list[Node]:
													SCREAMING_SNAKE_CASE__     :Union[str, Any]						    = []
													for action in delta:
																				SCREAMING_SNAKE_CASE__     :List[str]						    = parent.pos_x + action[1]
																				SCREAMING_SNAKE_CASE__     :Tuple						    = parent.pos_y + action[0]
																				if not (0 <= pos_x <= len(grid[0]      ) - 1 and 0 <= pos_y <= len(UpperCamelCase_      ) - 1):
																											continue

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

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




						def      __lowerCamelCase       (    self :       Optional[Any]							,							UpperCamelCase_ :       Node | None      )     ->				list[TPosition]:
													SCREAMING_SNAKE_CASE__     :Dict						    = node
													SCREAMING_SNAKE_CASE__     :Tuple						    = []
													while current_node is not None:
																				path.append((current_node.pos_y, current_node.pos_x)      )
																				SCREAMING_SNAKE_CASE__     :str						    = current_node.parent
													path.reverse()
													return path




class _SCREAMING_SNAKE_CASE:




						def __init__(    self :       Any							,							UpperCamelCase_ :       TPosition							,							UpperCamelCase_ :       TPosition      )     ->				None:
													SCREAMING_SNAKE_CASE__     :str						    = AStar(UpperCamelCase_							,							UpperCamelCase_      )
													SCREAMING_SNAKE_CASE__     :Tuple						    = AStar(UpperCamelCase_							,							UpperCamelCase_      )
													SCREAMING_SNAKE_CASE__     :int						    = False




						def      __lowerCamelCase       (    self :       Dict      )     ->				list[TPosition]:
													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__     :Any						    = self.fwd_astar.open_nodes.pop(0      )
																				SCREAMING_SNAKE_CASE__     :str						    = self.bwd_astar.open_nodes.pop(0      )

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

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

																				SCREAMING_SNAKE_CASE__     :Dict						    = current_bwd_node
																				SCREAMING_SNAKE_CASE__     :List[str]						    = current_fwd_node

																				SCREAMING_SNAKE_CASE__     :Optional[Any]						    = {
																				    self.fwd_astar: self.fwd_astar.get_successors(UpperCamelCase_      ),
																				    self.bwd_astar: self.bwd_astar.get_successors(UpperCamelCase_      ),
																				}

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

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

													return [self.fwd_astar.start.pos]




						def      __lowerCamelCase       (    self :       Optional[Any]							,							UpperCamelCase_ :       Node							,							UpperCamelCase_ :       Node      )     ->				list[TPosition]:
													SCREAMING_SNAKE_CASE__     :Optional[int]						    = self.fwd_astar.retrace_path(UpperCamelCase_      )
													SCREAMING_SNAKE_CASE__     :Dict						    = self.bwd_astar.retrace_path(UpperCamelCase_      )
													bwd_path.pop()
													bwd_path.reverse()
													SCREAMING_SNAKE_CASE__     :Optional[Any]						    = fwd_path + bwd_path
													return path


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

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

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







'''simple docstring'''







def    lowerCamelCase       (			UpperCAmelCase__				:  str				,						UpperCAmelCase__				:  int		)			->	str:


							'''simple docstring'''






							SCREAMING_SNAKE_CASE__     :list[list[str]]						    = [[] for _ in range(UpperCAmelCase__		)]
							SCREAMING_SNAKE_CASE__     :Any						    = key - 1

							if key <= 0:
														raise ValueError('Height of grid can\'t be 0 or negative'		)
							if key == 1 or len(UpperCAmelCase__		) <= key:
														return input_string

							for position, character in enumerate(UpperCAmelCase__		):
														SCREAMING_SNAKE_CASE__     :Dict						    = position % (lowest * 2)  # puts it in bounds
														SCREAMING_SNAKE_CASE__     :Tuple						    = min(UpperCAmelCase__				,						lowest * 2 - num		)  # creates zigzag pattern
														temp_grid[num].append(UpperCAmelCase__		)
							SCREAMING_SNAKE_CASE__     :int						    = [''.join(UpperCAmelCase__		) for row in temp_grid]
							SCREAMING_SNAKE_CASE__     :str						    = ''.join(UpperCAmelCase__		)

							return output_string


def    lowerCamelCase       (			UpperCAmelCase__				:  str				,						UpperCAmelCase__				:  int		)			->	str:


							'''simple docstring'''






							SCREAMING_SNAKE_CASE__     :List[Any]						    = []
							SCREAMING_SNAKE_CASE__     :str						    = key - 1

							if key <= 0:
														raise ValueError('Height of grid can\'t be 0 or negative'		)
							if key == 1:
														return input_string

							SCREAMING_SNAKE_CASE__     :list[list[str]]						    = [[] for _ in range(UpperCAmelCase__		)]  # generates template
							for position in range(len(UpperCAmelCase__		)		):
														SCREAMING_SNAKE_CASE__     :Optional[int]						    = position % (lowest * 2)  # puts it in bounds
														SCREAMING_SNAKE_CASE__     :Dict						    = min(UpperCAmelCase__				,						lowest * 2 - num		)  # creates zigzag pattern
														temp_grid[num].append('*'		)

							SCREAMING_SNAKE_CASE__     :Any						    = 0
							for row in temp_grid:  # fills in the characters
														SCREAMING_SNAKE_CASE__     :int						    = input_string[counter : counter + len(UpperCAmelCase__		)]
														grid.append(list(UpperCAmelCase__		)		)
														counter += len(UpperCAmelCase__		)

							SCREAMING_SNAKE_CASE__     :Tuple						    = ''  # reads as zigzag
							for position in range(len(UpperCAmelCase__		)		):
														SCREAMING_SNAKE_CASE__     :Union[str, Any]						    = position % (lowest * 2)  # puts it in bounds
														SCREAMING_SNAKE_CASE__     :Any						    = min(UpperCAmelCase__				,						lowest * 2 - num		)  # creates zigzag pattern
														output_string += grid[num][0]
														grid[num].pop(0		)
							return output_string


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


							'''simple docstring'''






							SCREAMING_SNAKE_CASE__     :int						    = {}
							for key_guess in range(1				,						len(UpperCAmelCase__		)		):  # tries every key
														SCREAMING_SNAKE_CASE__     :List[str]						    = decrypt(UpperCAmelCase__				,						UpperCAmelCase__		)
							return results


if __name__ == "__main__":
		import doctest

		doctest.testmod()






