
import heapq
import sys

import numpy as np

_A  =	tuple[int, int]





class       _lowerCAmelCase   :




				def __init__(   self	)							-> Tuple:
							lowerCAmelCase_         =      []
							lowerCAmelCase_         =      set()




				def 	__a		(   self	)							-> List[Any]:
							if not self.empty():
										return self.elements[0][0]
							else:
										return float("inf"	)




				def 	__a		(   self	)							-> List[str]:
							return len(self.elements	) == 0




				def 	__a		(   self							,							_UpperCamelCase							,							_UpperCamelCase	)							-> Any:
							if item not in self.set:
										heapq.heappush(self.elements							,							(priority, item)	)
										self.set.add(_UpperCamelCase	)
							else:
										# update
										# print("update", item)
										lowerCAmelCase_         =      []
										((lowerCAmelCase_)      ,    (lowerCAmelCase_))         =      heapq.heappop(self.elements	)
										while x != item:
													temp.append((pri, x)	)
													((lowerCAmelCase_)      ,    (lowerCAmelCase_))         =      heapq.heappop(self.elements	)
										temp.append((priority, item)	)
										for pro, xxx in temp:
													heapq.heappush(self.elements							,							(pro, xxx)	)




				def 	__a		(   self							,							_UpperCamelCase	)							-> Optional[Any]:
							if item in self.set:
										self.set.remove(_UpperCamelCase	)
										lowerCAmelCase_         =      []
										((lowerCAmelCase_)      ,    (lowerCAmelCase_))         =      heapq.heappop(self.elements	)
										while x != item:
													temp.append((pro, x)	)
													((lowerCAmelCase_)      ,    (lowerCAmelCase_))         =      heapq.heappop(self.elements	)
										for prito, yyy in temp:
													heapq.heappush(self.elements							,							(prito, yyy)	)




				def 	__a		(   self	)							-> List[Any]:
							return self.elements[0][1]




				def 	__a		(   self	)							-> Optional[Any]:
							((lowerCAmelCase_)      ,    (lowerCAmelCase_))         =      heapq.heappop(self.elements	)
							self.set.remove(_UpperCamelCase	)
							return (priority, item)






def   lowerCamelCase__							(							__lowerCAmelCase    :    TPos       ,				__lowerCAmelCase    :    TPos							):




			"""simple docstring"""


			lowerCAmelCase_         =      np.array(__lowerCAmelCase							)
			lowerCAmelCase_         =      np.array(__lowerCAmelCase							)
			return np.linalg.norm(a - b							)






def   lowerCamelCase__							(							__lowerCAmelCase    :    TPos       ,				__lowerCAmelCase    :    TPos							):




			"""simple docstring"""


			return consistent_heuristic(__lowerCAmelCase       ,				__lowerCAmelCase							) // t






def   lowerCamelCase__							(							__lowerCAmelCase    :    TPos       ,				__lowerCAmelCase    :    TPos							):




			"""simple docstring"""


			return abs(p[0] - goal[0]							) + abs(p[1] - goal[1]							)






def   lowerCamelCase__							(							__lowerCAmelCase    :    TPos       ,				__lowerCAmelCase    :    int       ,				__lowerCAmelCase    :    TPos       ,				__lowerCAmelCase    :    dict[TPos, float]							):




			"""simple docstring"""


			lowerCAmelCase_         =      g_function[start] + Wa * heuristics[i](__lowerCAmelCase       ,				__lowerCAmelCase							)
			return ans






def   lowerCamelCase__							(							__lowerCAmelCase    :    Dict       ,				__lowerCAmelCase    :    int       ,				__lowerCAmelCase    :    Tuple							):




			"""simple docstring"""


			lowerCAmelCase_         =      np.chararray((n, n)							)
			for i in range(__lowerCAmelCase							):
						for j in range(__lowerCAmelCase							):
									lowerCAmelCase_         =      "*"

			for i in range(__lowerCAmelCase							):
						for j in range(__lowerCAmelCase							):
									if (j, (n - 1) - i) in blocks:
												lowerCAmelCase_         =      "#"

			lowerCAmelCase_         =      "-"
			lowerCAmelCase_         =      back_pointer[goal]
			while x != start:
						((lowerCAmelCase_)      ,    (lowerCAmelCase_))         =      x
						# print(x)
						lowerCAmelCase_         =      "-"
						lowerCAmelCase_         =      back_pointer[x]
			lowerCAmelCase_         =      "-"

			for i in range(__lowerCAmelCase							):
						for j in range(__lowerCAmelCase							):
									if (i, j) == (0, n - 1):
												print(grid[i][j]       ,				end=" "							)
												print("<-- End position"       ,				end=" "							)
									else:
												print(grid[i][j]       ,				end=" "							)
						print()
			print("^"							)
			print("Start position"							)
			print()
			print("# is an obstacle"							)
			print("- is the path taken by algorithm"							)
			print("PATH TAKEN BY THE ALGORITHM IS:-"							)
			lowerCAmelCase_         =      back_pointer[goal]
			while x != start:
						print(__lowerCAmelCase       ,				end=" "							)
						lowerCAmelCase_         =      back_pointer[x]
			print(__lowerCAmelCase							)
			sys.exit()






def   lowerCamelCase__							(							__lowerCAmelCase    :    TPos							):




			"""simple docstring"""


			if p[0] < 0 or p[0] > n - 1:
						return False
			if p[1] < 0 or p[1] > n - 1:
						return False
			return True






def   lowerCamelCase__							(							__lowerCAmelCase    :    List[str]       ,				__lowerCAmelCase    :    Tuple       ,				__lowerCAmelCase    :    Optional[Any]       ,				__lowerCAmelCase    :    Dict       ,				__lowerCAmelCase    :    int       ,				__lowerCAmelCase    :    Optional[int]       ,				__lowerCAmelCase    :    Any       ,				__lowerCAmelCase    :    Dict       ,				):




			"""simple docstring"""


			for itera in range(__lowerCAmelCase							):
						open_list[itera].remove_element(__lowerCAmelCase							)
			# print("s", s)
			# print("j", j)
			((lowerCAmelCase_)      ,    (lowerCAmelCase_))         =      s
			lowerCAmelCase_         =      (x - 1, y)
			lowerCAmelCase_         =      (x + 1, y)
			lowerCAmelCase_         =      (x, y + 1)
			lowerCAmelCase_         =      (x, y - 1)

			for neighbours in [left, right, up, down]:
						if neighbours not in blocks:
									if valid(__lowerCAmelCase							) and neighbours not in visited:
												# print("neighbour", neighbours)
												visited.add(__lowerCAmelCase							)
												lowerCAmelCase_         =      -1
												lowerCAmelCase_         =      float("inf"							)

									if valid(__lowerCAmelCase							) and g_function[neighbours] > g_function[s] + 1:
												lowerCAmelCase_         =      g_function[s] + 1
												lowerCAmelCase_         =      s
												if neighbours not in close_list_anchor:
															open_list[0].put(__lowerCAmelCase       ,				key(__lowerCAmelCase       ,				0       ,				__lowerCAmelCase       ,				__lowerCAmelCase							)							)
															if neighbours not in close_list_inad:
																		for var in range(1       ,				__lowerCAmelCase							):
																					if key(__lowerCAmelCase       ,				__lowerCAmelCase       ,				__lowerCAmelCase       ,				__lowerCAmelCase							) <= Wa * key(
																					    __lowerCAmelCase       ,				0       ,				__lowerCAmelCase       ,				__lowerCAmelCase							):
																								open_list[j].put(
																								    __lowerCAmelCase       ,				key(__lowerCAmelCase       ,				__lowerCAmelCase       ,				__lowerCAmelCase       ,				__lowerCAmelCase							)							)






def   lowerCamelCase__							(							):




			"""simple docstring"""


			lowerCAmelCase_         =      []
			for x in range(1       ,				5							):
						for y in range(1       ,				6							):
									some_list.append((x, y)							)

			for x in range(15       ,				20							):
						some_list.append((x, 17)							)

			for x in range(10       ,				19							):
						for y in range(1       ,				15							):
									some_list.append((x, y)							)

    # L block
			for x in range(1       ,				4							):
						for y in range(12       ,				19							):
									some_list.append((x, y)							)
			for x in range(3       ,				13							):
						for y in range(16       ,				19							):
									some_list.append((x, y)							)
			return some_list


_A  =	{0: consistent_heuristic, 1: heuristic_a, 2: heuristic_a}

_A  =	[
    (0, 1),
    (1, 1),
    (2, 1),
    (3, 1),
    (4, 1),
    (5, 1),
    (6, 1),
    (7, 1),
    (8, 1),
    (9, 1),
    (10, 1),
    (11, 1),
    (12, 1),
    (13, 1),
    (14, 1),
    (15, 1),
    (16, 1),
    (17, 1),
    (18, 1),
    (19, 1),
]
_A  =	make_common_ground()


_A  =	blocks_blk
# hyper parameters
_A  =	1
_A  =	1
_A  =	20
_A  =	3  # one consistent and two other inconsistent

# start and end destination
_A  =	(0, 0)
_A  =	(n - 1, n - 1)

_A  =	1






def   lowerCamelCase__							(							__lowerCAmelCase    :    TPos       ,				__lowerCAmelCase    :    TPos       ,				__lowerCAmelCase    :    int							):




			"""simple docstring"""


			lowerCAmelCase_         =      {start: 0, goal: float("inf"							)}
			lowerCAmelCase_         =      {start: -1, goal: -1}
			lowerCAmelCase_         =      []
			lowerCAmelCase_         =      set()

			for i in range(__lowerCAmelCase							):
						open_list.append(PriorityQueue()							)
						open_list[i].put(__lowerCAmelCase       ,				key(__lowerCAmelCase       ,				__lowerCAmelCase       ,				__lowerCAmelCase       ,				__lowerCAmelCase							)							)

			lowerCAmelCase_         =      []
			lowerCAmelCase_         =      []
			while open_list[0].minkey() < float("inf"							):
						for i in range(1       ,				__lowerCAmelCase							):
									# print(open_list[0].minkey(), open_list[i].minkey())
									if open_list[i].minkey() <= Wa * open_list[0].minkey():
												global t
												t += 1
												if g_function[goal] <= open_list[i].minkey():
															if g_function[goal] < float("inf"							):
																		do_something(__lowerCAmelCase       ,				__lowerCAmelCase       ,				__lowerCAmelCase							)
												else:
															lowerCAmelCase_      ,    lowerCAmelCase_         =      open_list[i].top_show()
															visited.add(__lowerCAmelCase							)
															expand_state(
															    __lowerCAmelCase       ,				__lowerCAmelCase       ,				__lowerCAmelCase       ,				__lowerCAmelCase       ,				__lowerCAmelCase       ,				__lowerCAmelCase       ,				__lowerCAmelCase       ,				__lowerCAmelCase       ,				)
															close_list_inad.append(__lowerCAmelCase							)
									else:
												if g_function[goal] <= open_list[0].minkey():
															if g_function[goal] < float("inf"							):
																		do_something(__lowerCAmelCase       ,				__lowerCAmelCase       ,				__lowerCAmelCase							)
												else:
															lowerCAmelCase_         =      open_list[0].top_show()
															visited.add(__lowerCAmelCase							)
															expand_state(
															    __lowerCAmelCase       ,				0       ,				__lowerCAmelCase       ,				__lowerCAmelCase       ,				__lowerCAmelCase       ,				__lowerCAmelCase       ,				__lowerCAmelCase       ,				__lowerCAmelCase       ,				)
															close_list_anchor.append(__lowerCAmelCase							)
			print("No path found to goal"							)
			print()
			for i in range(n - 1       ,				-1       ,				-1							):
						for j in range(__lowerCAmelCase							):
									if (j, i) in blocks:
												print("#"       ,				end=" "							)
									elif (j, i) in back_pointer:
												if (j, i) == (n - 1, n - 1):
															print("*"       ,				end=" "							)
												else:
															print("-"       ,				end=" "							)
									else:
												print("*"       ,				end=" "							)
									if (j, i) == (n - 1, n - 1):
												print("<-- End position"       ,				end=" "							)
						print()
			print("^"							)
			print("Start position"							)
			print()
			print("# is an obstacle"							)
			print("- is the path taken by algorithm"							)


if __name__ == "__main__":
			multi_a_star(start, goal, n_heuristic)





def   lowerCamelCase__							(							__lowerCAmelCase    :    list							):




			"""simple docstring"""


			for i in range(len(__lowerCAmelCase							) - 1       ,				0       ,				-1							):
						lowerCAmelCase_         =      False

						for j in range(__lowerCAmelCase       ,				0       ,				-1							):
									if unsorted[j] < unsorted[j - 1]:
												lowerCAmelCase_      ,    lowerCAmelCase_         =      unsorted[j - 1], unsorted[j]
												lowerCAmelCase_         =      True

						for j in range(__lowerCAmelCase							):
									if unsorted[j] > unsorted[j + 1]:
												lowerCAmelCase_      ,    lowerCAmelCase_         =      unsorted[j + 1], unsorted[j]
												lowerCAmelCase_         =      True

						if not swapped:
									break
			return unsorted


if __name__ == "__main__":
			import doctest

			doctest.testmod()
			_A  =	input("Enter numbers separated by a comma:\n").strip()
			_A  =	[int(item) for item in user_input.split(",")]
			print(f"""{cocktail_shaker_sort(unsorted) = }""")



