






from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
__UpperCamelCase   :   List[Any]      =    0

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

__UpperCamelCase   :   Dict      =    tuple[int, int]


class 							__UpperCamelCase     :







	def __init__(	self   :				Tuple							,					_lowerCAmelCase   :				int							,					_lowerCAmelCase   :				int							,					_lowerCAmelCase   :				int							,					_lowerCAmelCase   :				int							,					_lowerCAmelCase   :				int							,					_lowerCAmelCase   :				Node | None							,					)		->			None:
		"""simple docstring"""







		__lowercase   							=	pos_x
		__lowercase   							=	pos_y
		__lowercase   							=	(pos_y, pos_x)
		__lowercase   							=	goal_x
		__lowercase   							=	goal_y
		__lowercase   							=	g_cost
		__lowercase   							=	parent
		__lowercase   							=	self.calculate_heuristic()
		__lowercase   							=	self.g_cost + self.h_cost







	def 			_a (	self   :				Optional[Any]      )		->			float:
		"""simple docstring"""







		__lowercase   							=	self.pos_x - self.goal_x
		__lowercase   							=	self.pos_y - self.goal_y
		if HEURISTIC == 1:
			return abs(_lowerCAmelCase      ) + abs(_lowerCAmelCase      )
		else:
			return sqrt(dy**2 + dx**2      )







	def __lt__(	self   :				int							,					_lowerCAmelCase   :				Node      )		->			bool:
		"""simple docstring"""







		return self.f_cost < other.f_cost


class 							__UpperCamelCase     :







	def __init__(	self   :				Optional[Any]							,					_lowerCAmelCase   :				TPosition							,					_lowerCAmelCase   :				TPosition      )		->			List[Any]:
		"""simple docstring"""







		__lowercase   							=	Node(start[1]							,					start[0]							,					goal[1]							,					goal[0]							,					0							,					_lowerCAmelCase      )
		__lowercase   							=	Node(goal[1]							,					goal[0]							,					goal[1]							,					goal[0]							,					9_9999							,					_lowerCAmelCase      )

		__lowercase   							=	[self.start]
		__lowercase   							=	[]

		__lowercase   							=	False







	def 			_a (	self   :				Optional[int]      )		->			list[TPosition]:
		"""simple docstring"""







		while self.open_nodes:
			# Open Nodes are sorted using __lt__
			self.open_nodes.sort()
			__lowercase   							=	self.open_nodes.pop(0      )

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

			self.closed_nodes.append(_lowerCAmelCase      )
			__lowercase   							=	self.get_successors(_lowerCAmelCase      )

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

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

		return [self.start.pos]







	def 			_a (	self   :				Dict							,					_lowerCAmelCase   :				Node      )		->			list[Node]:
		"""simple docstring"""







		__lowercase   							=	[]
		for action in delta:
			__lowercase   							=	parent.pos_x + action[1]
			__lowercase   							=	parent.pos_y + action[0]
			if not (0 <= pos_x <= len(grid[0]      ) - 1 and 0 <= pos_y <= len(_lowerCAmelCase      ) - 1):
				continue

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

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







	def 			_a (	self   :				List[Any]							,					_lowerCAmelCase   :				Node | None      )		->			list[TPosition]:
		"""simple docstring"""







		__lowercase   							=	node
		__lowercase   							=	[]
		while current_node is not None:
			path.append((current_node.pos_y, current_node.pos_x)      )
			__lowercase   							=	current_node.parent
		path.reverse()
		return path


class 							__UpperCamelCase     :







	def __init__(	self   :				List[Any]							,					_lowerCAmelCase   :				TPosition							,					_lowerCAmelCase   :				TPosition      )		->			None:
		"""simple docstring"""







		__lowercase   							=	AStar(_lowerCAmelCase							,					_lowerCAmelCase      )
		__lowercase   							=	AStar(_lowerCAmelCase							,					_lowerCAmelCase      )
		__lowercase   							=	False







	def 			_a (	self   :				Any      )		->			list[TPosition]:
		"""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()
			__lowercase   							=	self.fwd_astar.open_nodes.pop(0      )
			__lowercase   							=	self.bwd_astar.open_nodes.pop(0      )

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

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

			__lowercase   							=	current_bwd_node
			__lowercase   							=	current_fwd_node

			__lowercase   							=	{
			    self.fwd_astar: self.fwd_astar.get_successors(_lowerCAmelCase      ),
			    self.bwd_astar: self.bwd_astar.get_successors(_lowerCAmelCase      ),
			}

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

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

		return [self.fwd_astar.start.pos]







	def 			_a (	self   :				int							,					_lowerCAmelCase   :				Node							,					_lowerCAmelCase   :				Node      )		->			list[TPosition]:
		"""simple docstring"""







		__lowercase   							=	self.fwd_astar.retrace_path(_lowerCAmelCase      )
		__lowercase   							=	self.bwd_astar.retrace_path(_lowerCAmelCase      )
		bwd_path.pop()
		bwd_path.reverse()
		__lowercase   							=	fwd_path + bwd_path
		return path


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

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

						__UpperCamelCase   :   Union[str, Any]      =    time.time()
						__UpperCamelCase   :   Dict      =    BidirectionalAStar(init, goal)
						__UpperCamelCase   :   int      =    time.time() - bd_start_time
						print(F'''BidirectionalAStar execution time = {bd_end_time:f} seconds''')


'''simple docstring'''


def    lowerCAmelCase       (		UpperCamelCase__					: list							):


	"""simple docstring"""
	__UpperCAmelCase      					=      False
	while is_sorted is False:  # Until all the indices are traversed keep looping
		__UpperCAmelCase      					=      True
		for i in range(0     ,       len(UpperCamelCase__							) - 1     ,       2							):  # iterating over all even indices
			if input_list[i] > input_list[i + 1]:
				__UpperCAmelCase					,      __UpperCAmelCase      					=      input_list[i + 1], input_list[i]
				# swapping if elements not in order
				__UpperCAmelCase      					=      False

		for i in range(1     ,       len(UpperCamelCase__							) - 1     ,       2							):  # iterating over all odd indices
			if input_list[i] > input_list[i + 1]:
				__UpperCAmelCase					,      __UpperCAmelCase      					=      input_list[i + 1], input_list[i]
				# swapping if elements not in order
				__UpperCAmelCase      					=      False
	return input_list


if __name__ == "__main__":
					print("Enter list to be sorted")
					__lowerCAmelCase						:							List[str]    							=						[int(x) for x in input().split()]
					# inputing elements of the list in one line
					__lowerCAmelCase						:							Dict    							=						odd_even_sort(input_list)
					print("The sorted list is")
					print(sorted_list)
