



import heapq
import sys

import numpy as np

__snake_case       :	int            =tuple[int, int]



class  lowerCamelCase__    :




		'''simple docstring'''



		def __init__(self				)  ->    Optional[Any]:

						"""simple docstring"""






						lowerCAmelCase__  :       Dict				=  []
						lowerCAmelCase__  :       int				=  set()



		def 	lowerCAmelCase__   (self				)  ->    int:

						"""simple docstring"""






						if not self.empty():
										return self.elements[0][0]
						else:
										return float('''inf'''				)



		def 	lowerCAmelCase__   (self				)  ->    List[Any]:

						"""simple docstring"""






						return len(self.elements				) == 0



		def 	lowerCAmelCase__   (self	,__lowerCamelCase	,__lowerCamelCase				)  ->    Union[str, Any]:

						"""simple docstring"""






						if item not in self.set:
										heapq.heappush(self.elements	,(priority, item)				)
										self.set.add(__lowerCamelCase				)
						else:
										# update
										# print("update", item)
										lowerCAmelCase__  :       List[str]				=  []
										((lowerCAmelCase__)		,	(lowerCAmelCase__))  :       List[Any]				=  heapq.heappop(self.elements				)
										while x != item:
														temp.append((pri, x)				)
														((lowerCAmelCase__)		,	(lowerCAmelCase__))  :       List[Any]				=  heapq.heappop(self.elements				)
										temp.append((priority, item)				)
										for pro, xxx in temp:
														heapq.heappush(self.elements	,(pro, xxx)				)



		def 	lowerCAmelCase__   (self	,__lowerCamelCase				)  ->    Optional[int]:

						"""simple docstring"""






						if item in self.set:
										self.set.remove(__lowerCamelCase				)
										lowerCAmelCase__  :       Optional[int]				=  []
										((lowerCAmelCase__)		,	(lowerCAmelCase__))  :       Optional[Any]				=  heapq.heappop(self.elements				)
										while x != item:
														temp.append((pro, x)				)
														((lowerCAmelCase__)		,	(lowerCAmelCase__))  :       int				=  heapq.heappop(self.elements				)
										for prito, yyy in temp:
														heapq.heappush(self.elements	,(prito, yyy)				)



		def 	lowerCAmelCase__   (self				)  ->    List[Any]:

						"""simple docstring"""






						return self.elements[0][1]



		def 	lowerCAmelCase__   (self				)  ->    Any:

						"""simple docstring"""






						((lowerCAmelCase__)		,	(lowerCAmelCase__))  :       Tuple				=  heapq.heappop(self.elements				)
						self.set.remove(__lowerCamelCase				)
						return (priority, item)






def 			lowerCAmelCase__	(					lowerCamelCase_	:	TPos ,lowerCamelCase_	:	TPos):





				'''simple docstring'''

				lowerCAmelCase__  :       List[str]				=  np.array(lowerCamelCase_)
				lowerCAmelCase__  :       Optional[Any]				=  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__  :       Optional[int]				=  g_function[start] + Wa * heuristics[i](lowerCamelCase_ ,lowerCamelCase_)
				return ans






def 			lowerCAmelCase__	(					lowerCamelCase_	:	Tuple ,lowerCamelCase_	:	Optional[int] ,lowerCamelCase_	:	Optional[Any]):





				'''simple docstring'''

				lowerCAmelCase__  :       List[str]				=  np.chararray((n, n))
				for i in range(lowerCamelCase_):
								for j in range(lowerCamelCase_):
												lowerCAmelCase__  :       Any				=  '''*'''

				for i in range(lowerCamelCase_):
								for j in range(lowerCamelCase_):
												if (j, (n - 1) - i) in blocks:
																lowerCAmelCase__  :       Tuple				=  '''#'''

				lowerCAmelCase__  :       List[Any]				=  '''-'''
				lowerCAmelCase__  :       Optional[int]				=  back_pointer[goal]
				while x != start:
								((lowerCAmelCase__)		,	(lowerCAmelCase__))  :       Union[str, Any]				=  x
								# print(x)
								lowerCAmelCase__  :       Tuple				=  '''-'''
								lowerCAmelCase__  :       Any				=  back_pointer[x]
				lowerCAmelCase__  :       str				=  '''-'''

				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__  :       List[Any]				=  back_pointer[goal]
				while x != start:
								print(lowerCamelCase_ ,end=''' ''')
								lowerCAmelCase__  :       int				=  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[Any] ,lowerCamelCase_	:	int ,lowerCamelCase_	:	List[Any] ,lowerCamelCase_	:	List[Any] ,lowerCamelCase_	:	Tuple ,lowerCamelCase_	:	Union[str, Any] ,lowerCamelCase_	:	List[Any] ,lowerCamelCase_	:	Optional[Any] ,):





				'''simple docstring'''

				for itera in range(lowerCamelCase_):
								open_list[itera].remove_element(lowerCamelCase_)
				# print("s", s)
				# print("j", j)
				((lowerCAmelCase__)		,	(lowerCAmelCase__))  :       Any				=  s
				lowerCAmelCase__  :       Any				=  (x - 1, y)
				lowerCAmelCase__  :       Optional[int]				=  (x + 1, y)
				lowerCAmelCase__  :       Optional[int]				=  (x, y + 1)
				lowerCAmelCase__  :       int				=  (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__  :       int				=  -1
																lowerCAmelCase__  :       Optional[int]				=  float('''inf''')

												if valid(lowerCamelCase_) and g_function[neighbours] > g_function[s] + 1:
																lowerCAmelCase__  :       Optional[Any]				=  g_function[s] + 1
																lowerCAmelCase__  :       Tuple				=  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__  :       Any				=  []
				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


__snake_case       :	Dict            ={0: consistent_heuristic, 1: heuristic_a, 2: heuristic_a}

__snake_case       :	Any            =[
    (0, 1),
    (1, 1),
    (2, 1),
    (3, 1),
    (4, 1),
    (5, 1),
    (6, 1),
    (7, 1),
    (8, 1),
    (9, 1),
    (1_0, 1),
    (1_1, 1),
    (1_2, 1),
    (1_3, 1),
    (1_4, 1),
    (1_5, 1),
    (1_6, 1),
    (1_7, 1),
    (1_8, 1),
    (1_9, 1),
]
__snake_case       :	Optional[int]            =make_common_ground()


__snake_case       :	Optional[int]            =blocks_blk
# hyper parameters
__snake_case       :	List[Any]            =1
__snake_case       :	str            =1
__snake_case       :	Tuple            =2_0
__snake_case       :	int            =3  # one consistent and two other inconsistent

# start and end destination
__snake_case       :	Optional[int]            =(0, 0)
__snake_case       :	Optional[int]            =(n - 1, n - 1)

__snake_case       :	Union[str, Any]            =1






def 			lowerCAmelCase__	(					lowerCamelCase_	:	TPos ,lowerCamelCase_	:	TPos ,lowerCamelCase_	:	int):





				'''simple docstring'''

				lowerCAmelCase__  :       Union[str, Any]				=  {start: 0, goal: float('''inf''')}
				lowerCAmelCase__  :       List[Any]				=  {start: -1, goal: -1}
				lowerCAmelCase__  :       List[Any]				=  []
				lowerCAmelCase__  :       Dict				=  set()

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

				lowerCAmelCase__  :       list[int]				=  []
				lowerCAmelCase__  :       list[int]				=  []
				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__  :       List[Any]				=  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__  :       Any				=  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_	:	int):





				'''simple docstring'''

				if length <= 0 or not isinstance(lowerCamelCase_ ,lowerCamelCase_):
								raise ValueError('''Length must be a positive integer.''')
				return [n * (2 * n - 1) for n in range(lowerCamelCase_)]


if __name__ == "__main__":
							print(hexagonal_numbers(length=5))
							print(hexagonal_numbers(length=1_0))

