from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
__UpperCamelCase		:       int									=     0

__UpperCamelCase		:       int									=     [
    [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		:       List[str]									=     [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

__UpperCamelCase		:       Optional[Any]									=     tuple[int, int]





class 					lowercase__						:


						def __init__(       self	:				List[str]    ,		UpperCamelCase__	:				int    ,		UpperCamelCase__	:				int    ,		UpperCamelCase__	:				int    ,		UpperCamelCase__	:				int    ,		UpperCamelCase__	:				int    ,		UpperCamelCase__	:				Node | None    ,		):





												'''simple docstring'''





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


						def        __A       (       self	:				Union[str, Any]						):





												'''simple docstring'''





												SCREAMING_SNAKE_CASE							:    Union[str, Any]							=							self.pos_x - self.goal_x
												SCREAMING_SNAKE_CASE							:    Dict							=							self.pos_y - self.goal_y
												if HEURISTIC == 1:
																		return abs(UpperCamelCase__						) + abs(UpperCamelCase__						)
												else:
																		return sqrt(dy**2 + dx**2						)



						def __lt__(       self	:				Optional[int]    ,		UpperCamelCase__	:				Node						):





												'''simple docstring'''





												return self.f_cost < other.f_cost






class 					lowercase__						:


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





												'''simple docstring'''





												SCREAMING_SNAKE_CASE							:    str							=							Node(start[1]    ,		start[0]    ,		goal[1]    ,		goal[0]    ,		0    ,		UpperCamelCase__						)
												SCREAMING_SNAKE_CASE							:    str							=							Node(goal[1]    ,		goal[0]    ,		goal[1]    ,		goal[0]    ,		9_9999    ,		UpperCamelCase__						)

												SCREAMING_SNAKE_CASE							:    Union[str, Any]							=							[self.start]
												SCREAMING_SNAKE_CASE							:    list[Node]							=							[]

												SCREAMING_SNAKE_CASE							:    Tuple							=							False


						def        __A       (       self	:				Tuple						):





												'''simple docstring'''





												while self.open_nodes:
																		# Open Nodes are sorted using __lt__
																		self.open_nodes.sort()
																		SCREAMING_SNAKE_CASE							:    Union[str, Any]							=							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							:    Tuple							=							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							:    int							=							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        __A       (       self	:				List[Any]    ,		UpperCamelCase__	:				Node						):





												'''simple docstring'''





												SCREAMING_SNAKE_CASE							:    Optional[Any]							=							[]
												for action in delta:
																		SCREAMING_SNAKE_CASE							:    Union[str, Any]							=							parent.pos_x + action[1]
																		SCREAMING_SNAKE_CASE							:    Optional[int]							=							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        __A       (       self	:				str    ,		UpperCamelCase__	:				Node | None						):





												'''simple docstring'''





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






class 					lowercase__						:


						def __init__(       self	:				List[Any]    ,		UpperCamelCase__	:				TPosition    ,		UpperCamelCase__	:				TPosition						):





												'''simple docstring'''





												SCREAMING_SNAKE_CASE							:    List[Any]							=							AStar(UpperCamelCase__    ,		UpperCamelCase__						)
												SCREAMING_SNAKE_CASE							:    Optional[int]							=							AStar(UpperCamelCase__    ,		UpperCamelCase__						)
												SCREAMING_SNAKE_CASE							:    Dict							=							False


						def        __A       (       self	:				Any						):





												'''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							:    Tuple							=							self.fwd_astar.open_nodes.pop(0						)
																		SCREAMING_SNAKE_CASE							:    int							=							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							:    Any							=							current_bwd_node
																		SCREAMING_SNAKE_CASE							:    Union[str, Any]							=							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							:    List[str]							=							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        __A       (       self	:				Union[str, Any]    ,		UpperCamelCase__	:				Node    ,		UpperCamelCase__	:				Node						):





												'''simple docstring'''





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


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

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

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






import itertools
import string
from collections.abc import Generator, Iterable
def       A	(    _lowercase		,  _lowercase						):
						SCREAMING_SNAKE_CASE							:    Union[str, Any]							=							iter(_lowercase						)
						while True:
												SCREAMING_SNAKE_CASE							:    Optional[Any]							=							tuple(itertools.islice(_lowercase		,  _lowercase						)						)
												if not chunk:
																		return
												yield chunk
def       A	(    _lowercase						):
						SCREAMING_SNAKE_CASE							:    int							=							''''''.join([c.upper() for c in dirty if c in string.ascii_letters]						)
						SCREAMING_SNAKE_CASE							:    List[str]							=							''''''

						if len(_lowercase						) < 2:
												return dirty

						for i in range(len(_lowercase						) - 1						):
												clean += dirty[i]

												if dirty[i] == dirty[i + 1]:
																		clean += "X"

						clean += dirty[-1]

						if len(_lowercase						) & 1:
												clean += "X"

						return clean
def       A	(    _lowercase						):
						# I and J are used interchangeably to allow
						# us to use a 5x5 table (25 letters)
						SCREAMING_SNAKE_CASE							:    Optional[Any]							=							'''ABCDEFGHIKLMNOPQRSTUVWXYZ'''
						# we're using a list instead of a '2d' array because it makes the math
						# for setting up the table and doing the actual encoding/decoding simpler
						SCREAMING_SNAKE_CASE							:    List[Any]							=							[]

						# copy key chars into the table if they are in `alphabet` ignoring duplicates
						for char in key.upper():
												if char not in table and char in alphabet:
																		table.append(_lowercase						)

    # fill the rest of the table in with the remaining alphabet chars
						for char in alphabet:
												if char not in table:
																		table.append(_lowercase						)

						return table
def       A	(    _lowercase		,  _lowercase						):
						SCREAMING_SNAKE_CASE							:    Any							=							generate_table(_lowercase						)
						SCREAMING_SNAKE_CASE							:    Any							=							prepare_input(_lowercase						)
						SCREAMING_SNAKE_CASE							:    Union[str, Any]							=							''''''

						# https://en.wikipedia.org/wiki/Playfair_cipher#Description
						for chara, chara in chunker(_lowercase		,  2						):
												SCREAMING_SNAKE_CASE				,  SCREAMING_SNAKE_CASE							:    int							=							divmod(table.index(_lowercase						)		,  5						)
												SCREAMING_SNAKE_CASE				,  SCREAMING_SNAKE_CASE							:    Union[str, Any]							=							divmod(table.index(_lowercase						)		,  5						)

												if rowa == rowa:
																		ciphertext += table[rowa * 5 + (cola + 1) % 5]
																		ciphertext += table[rowa * 5 + (cola + 1) % 5]
												elif cola == cola:
																		ciphertext += table[((rowa + 1) % 5) * 5 + cola]
																		ciphertext += table[((rowa + 1) % 5) * 5 + cola]
												else:  # rectangle
																		ciphertext += table[rowa * 5 + cola]
																		ciphertext += table[rowa * 5 + cola]

						return ciphertext



def       A	(    _lowercase		,  _lowercase						):
						SCREAMING_SNAKE_CASE							:    Any							=							generate_table(_lowercase						)
						SCREAMING_SNAKE_CASE							:    List[Any]							=							''''''

						# https://en.wikipedia.org/wiki/Playfair_cipher#Description
						for chara, chara in chunker(_lowercase		,  2						):
												SCREAMING_SNAKE_CASE				,  SCREAMING_SNAKE_CASE							:    List[str]							=							divmod(table.index(_lowercase						)		,  5						)
												SCREAMING_SNAKE_CASE				,  SCREAMING_SNAKE_CASE							:    Optional[Any]							=							divmod(table.index(_lowercase						)		,  5						)

												if rowa == rowa:
																		plaintext += table[rowa * 5 + (cola - 1) % 5]
																		plaintext += table[rowa * 5 + (cola - 1) % 5]
												elif cola == cola:
																		plaintext += table[((rowa - 1) % 5) * 5 + cola]
																		plaintext += table[((rowa - 1) % 5) * 5 + cola]
												else:  # rectangle
																		plaintext += table[rowa * 5 + cola]
																		plaintext += table[rowa * 5 + cola]

						return plaintext





