




import heapq
import sys

import numpy as np

_lowerCamelCase      :  Optional[int]      						=						tuple[int, int]
class        __snake_case  :



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





								'''simple docstring'''




								_lowerCAmelCase    :    int										=      []
								_lowerCAmelCase    :    Union[str, Any]										=      set()



				def       SCREAMING_SNAKE_CASE       (      self      :		str      )  ->    Tuple:





								'''simple docstring'''




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



				def       SCREAMING_SNAKE_CASE       (      self      :		Any      )  ->    str:





								'''simple docstring'''




								return len(self.elements      ) == 0



				def       SCREAMING_SNAKE_CASE       (      self      :		Union[str, Any]		,	_UpperCAmelCase      :		Optional[int]		,	_UpperCAmelCase      :		str      )  ->    Optional[int]:





								'''simple docstring'''




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



				def       SCREAMING_SNAKE_CASE       (      self      :		Optional[int]		,	_UpperCAmelCase      :		Optional[int]      )  ->    List[str]:





								'''simple docstring'''




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



				def       SCREAMING_SNAKE_CASE       (      self      :		List[str]      )  ->    Optional[Any]:





								'''simple docstring'''




								return self.elements[0][1]



				def       SCREAMING_SNAKE_CASE       (      self      :		Optional[Any]      )  ->    List[str]:





								'''simple docstring'''




								((_lowerCAmelCase)					,    (_lowerCAmelCase))    :    Optional[int]										=      heapq.heappop(self.elements      )
								self.set.remove(_UpperCAmelCase      )
								return (priority, item)






def 							_UpperCAmelCase  (UpperCamelCase_ : TPos      ,    UpperCamelCase_ : TPos       ):
				'''simple docstring'''
				# euclidean distance
				_lowerCAmelCase    :    Union[str, Any]										=      np.array(UpperCamelCase_       )
				_lowerCAmelCase    :    Tuple										=      np.array(UpperCamelCase_       )
				return np.linalg.norm(a - b       )




def 							_UpperCAmelCase  (UpperCamelCase_ : TPos      ,    UpperCamelCase_ : TPos       ):
				'''simple docstring'''
				# integer division by time variable
				return consistent_heuristic(UpperCamelCase_      ,    UpperCamelCase_       ) // t




def 							_UpperCAmelCase  (UpperCamelCase_ : TPos      ,    UpperCamelCase_ : TPos       ):
				'''simple docstring'''
				# manhattan distance
				return abs(p[0] - goal[0]       ) + abs(p[1] - goal[1]       )




def 							_UpperCAmelCase  (UpperCamelCase_ : TPos      ,    UpperCamelCase_ : int      ,    UpperCamelCase_ : TPos      ,    UpperCamelCase_ : dict[TPos, float]       ):
				'''simple docstring'''
				_lowerCAmelCase    :    Optional[Any]										=      g_function[start] + Wa * heuristics[i](UpperCamelCase_      ,    UpperCamelCase_       )
				return ans




def 							_UpperCAmelCase  (UpperCamelCase_ : Tuple      ,    UpperCamelCase_ : Dict      ,    UpperCamelCase_ : Optional[int]       ):
				'''simple docstring'''
				_lowerCAmelCase    :    int										=      np.chararray((n, n)       )
				for i in range(UpperCamelCase_       ):
								for j in range(UpperCamelCase_       ):
												_lowerCAmelCase    :    Any										=      """*"""

				for i in range(UpperCamelCase_       ):
								for j in range(UpperCamelCase_       ):
												if (j, (n - 1) - i) in blocks:
																_lowerCAmelCase    :    str										=      """#"""

				_lowerCAmelCase    :    List[str]										=      """-"""
				_lowerCAmelCase    :    int										=      back_pointer[goal]
				while x != start:
								((_lowerCAmelCase)					,    (_lowerCAmelCase))    :    int										=      x
								# print(x)
								_lowerCAmelCase    :    Dict										=      """-"""
								_lowerCAmelCase    :    int										=      back_pointer[x]
				_lowerCAmelCase    :    Dict										=      """-"""

				for i in range(UpperCamelCase_       ):
								for j in range(UpperCamelCase_       ):
												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    :    Union[str, Any]										=      back_pointer[goal]
				while x != start:
								print(UpperCamelCase_      ,    end=""" """       )
								_lowerCAmelCase    :    str										=      back_pointer[x]
				print(UpperCamelCase_       )
				sys.exit()




def 							_UpperCAmelCase  (UpperCamelCase_ : 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 							_UpperCAmelCase  (UpperCamelCase_ : str      ,    UpperCamelCase_ : str      ,    UpperCamelCase_ : List[str]      ,    UpperCamelCase_ : Optional[Any]      ,    UpperCamelCase_ : List[Any]      ,    UpperCamelCase_ : Union[str, Any]      ,    UpperCamelCase_ : int      ,    UpperCamelCase_ : int      ,    ):
				'''simple docstring'''
				for itera in range(UpperCamelCase_       ):
								open_list[itera].remove_element(UpperCamelCase_       )
				# print("s", s)
				# print("j", j)
				((_lowerCAmelCase)					,    (_lowerCAmelCase))    :    int										=      s
				_lowerCAmelCase    :    Any										=      (x - 1, y)
				_lowerCAmelCase    :    int										=      (x + 1, y)
				_lowerCAmelCase    :    Any										=      (x, y + 1)
				_lowerCAmelCase    :    str										=      (x, y - 1)

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

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




def 							_UpperCAmelCase  ():
				'''simple docstring'''
				_lowerCAmelCase    :    str										=      []
				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


_lowerCamelCase      :  List[str]      						=						{0: consistent_heuristic, 1: heuristic_a, 2: heuristic_a}

_lowerCamelCase      :  Optional[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),
]
_lowerCamelCase      :  Optional[Any]      						=						make_common_ground()


_lowerCamelCase      :  List[str]      						=						blocks_blk
# hyper parameters
_lowerCamelCase      :  int      						=						1
_lowerCamelCase      :  Any      						=						1
_lowerCamelCase      :  List[Any]      						=						2_0
_lowerCamelCase      :  Union[str, Any]      						=						3  # one consistent and two other inconsistent

# start and end destination
_lowerCamelCase      :  str      						=						(0, 0)
_lowerCamelCase      :  List[Any]      						=						(n - 1, n - 1)

_lowerCamelCase      :  Any      						=						1




def 							_UpperCAmelCase  (UpperCamelCase_ : TPos      ,    UpperCamelCase_ : TPos      ,    UpperCamelCase_ : int       ):
				'''simple docstring'''
				_lowerCAmelCase    :    Tuple										=      {start: 0, goal: float("""inf"""       )}
				_lowerCAmelCase    :    Union[str, Any]										=      {start: -1, goal: -1}
				_lowerCAmelCase    :    Union[str, Any]										=      []
				_lowerCAmelCase    :    List[Any]										=      set()

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

				_lowerCAmelCase    :    list[int]										=      []
				_lowerCAmelCase    :    list[int]										=      []
				while open_list[0].minkey() < float("""inf"""       ):
								for i in range(1      ,    UpperCamelCase_       ):
												# 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(UpperCamelCase_      ,    UpperCamelCase_      ,    UpperCamelCase_       )
																else:
																				_lowerCAmelCase					,    _lowerCAmelCase    :    List[Any]										=      open_list[i].top_show()
																				visited.add(UpperCamelCase_       )
																				expand_state(
																				    UpperCamelCase_      ,    UpperCamelCase_      ,    UpperCamelCase_      ,    UpperCamelCase_      ,    UpperCamelCase_      ,    UpperCamelCase_      ,    UpperCamelCase_      ,    UpperCamelCase_      ,    )
																				close_list_inad.append(UpperCamelCase_       )
												else:
																if g_function[goal] <= open_list[0].minkey():
																				if g_function[goal] < float("""inf"""       ):
																								do_something(UpperCamelCase_      ,    UpperCamelCase_      ,    UpperCamelCase_       )
																else:
																				_lowerCAmelCase    :    Dict										=      open_list[0].top_show()
																				visited.add(UpperCamelCase_       )
																				expand_state(
																				    UpperCamelCase_      ,    0      ,    UpperCamelCase_      ,    UpperCamelCase_      ,    UpperCamelCase_      ,    UpperCamelCase_      ,    UpperCamelCase_      ,    UpperCamelCase_      ,    )
																				close_list_anchor.append(UpperCamelCase_       )
				print("""No path found to goal"""       )
				print()
				for i in range(n - 1      ,    -1      ,    -1       ):
								for j in range(UpperCamelCase_       ):
												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)







from __future__ import annotations

from collections.abc import Iterator
from typing import Any
class        __snake_case  :



				def __init__(      self      :		List[Any]		,	_UpperCAmelCase      :		Any      )  ->    Dict:





								'''simple docstring'''




								_lowerCAmelCase    :    Any										=      data
								_lowerCAmelCase    :    Node | None										=      None






class        __snake_case  :



				def __init__(      self      :		Tuple      )  ->    Tuple:





								'''simple docstring'''




								_lowerCAmelCase    :    str										=      None
								_lowerCAmelCase    :    List[Any]										=      None



				def __iter__(      self      :		str      )  ->    Iterator[Any]:





								'''simple docstring'''




								_lowerCAmelCase    :    Optional[int]										=      self.head
								while self.head:
												yield node.data
												_lowerCAmelCase    :    List[str]										=      node.next
												if node == self.head:
																break



				def __len__(      self      :		Union[str, Any]      )  ->    int:





								'''simple docstring'''




								return sum(1 for _ in self      )



				def __repr__(      self      :		Optional[int]      )  ->    str:





								'''simple docstring'''




								return "->".join(str(_UpperCAmelCase      ) for item in iter(self      )      )



				def       SCREAMING_SNAKE_CASE       (      self      :		Any		,	_UpperCAmelCase      :		Any      )  ->    None:





								'''simple docstring'''




								self.insert_nth(len(self      )		,	_UpperCAmelCase      )



				def       SCREAMING_SNAKE_CASE       (      self      :		Dict		,	_UpperCAmelCase      :		Any      )  ->    None:





								'''simple docstring'''




								self.insert_nth(0		,	_UpperCAmelCase      )



				def       SCREAMING_SNAKE_CASE       (      self      :		List[str]		,	_UpperCAmelCase      :		int		,	_UpperCAmelCase      :		Any      )  ->    None:





								'''simple docstring'''




								if index < 0 or index > len(self      ):
												raise IndexError("""list index out of range."""      )
								_lowerCAmelCase    :    Optional[int]										=      Node(_UpperCAmelCase      )
								if self.head is None:
												_lowerCAmelCase    :    Tuple										=      new_node  # first node points itself
												_lowerCAmelCase    :    int										=      new_node
								elif index == 0:  # insert at head
												_lowerCAmelCase    :    Tuple										=      self.head
												_lowerCAmelCase    :    int										=      new_node
								else:
												_lowerCAmelCase    :    Union[str, Any]										=      self.head
												for _ in range(index - 1      ):
																_lowerCAmelCase    :    Optional[Any]										=      temp.next
												_lowerCAmelCase    :    Optional[int]										=      temp.next
												_lowerCAmelCase    :    Optional[int]										=      new_node
												if index == len(self      ) - 1:  # insert at tail
																_lowerCAmelCase    :    Optional[Any]										=      new_node



				def       SCREAMING_SNAKE_CASE       (      self      :		Dict      )  ->    str:





								'''simple docstring'''




								return self.delete_nth(0      )



				def       SCREAMING_SNAKE_CASE       (      self      :		List[str]      )  ->    Any:





								'''simple docstring'''




								return self.delete_nth(len(self      ) - 1      )



				def       SCREAMING_SNAKE_CASE       (      self      :		str		,	_UpperCAmelCase      :		int = 0      )  ->    Any:





								'''simple docstring'''




								if not 0 <= index < len(self      ):
												raise IndexError("""list index out of range."""      )
								_lowerCAmelCase    :    Optional[Any]										=      self.head
								if self.head == self.tail:  # just one node
												_lowerCAmelCase    :    Optional[Any]										=      None
								elif index == 0:  # delete head node
												_lowerCAmelCase    :    str										=      self.tail.next.next
												_lowerCAmelCase    :    List[str]										=      self.head.next
								else:
												_lowerCAmelCase    :    List[str]										=      self.head
												for _ in range(index - 1      ):
																_lowerCAmelCase    :    List[Any]										=      temp.next
												_lowerCAmelCase    :    List[str]										=      temp.next
												_lowerCAmelCase    :    Dict										=      temp.next.next
												if index == len(self      ) - 1:  # delete at tail
																_lowerCAmelCase    :    Optional[int]										=      temp
								return delete_node.data



				def       SCREAMING_SNAKE_CASE       (      self      :		int      )  ->    bool:





								'''simple docstring'''




								return len(self      ) == 0






def 							_UpperCAmelCase  ():
				'''simple docstring'''
				_lowerCAmelCase    :    Dict										=      CircularLinkedList()
				assert len(UpperCamelCase_       ) == 0
				assert circular_linked_list.is_empty() is True
				assert str(UpperCamelCase_       ) == ""

				try:
								circular_linked_list.delete_front()
								raise AssertionError  # This should not happen
				except IndexError:
								assert True  # This should happen

				try:
								circular_linked_list.delete_tail()
								raise AssertionError  # This should not happen
				except IndexError:
								assert True  # This should happen

				try:
								circular_linked_list.delete_nth(-1       )
								raise AssertionError
				except IndexError:
								assert True

				try:
								circular_linked_list.delete_nth(0       )
								raise AssertionError
				except IndexError:
								assert True

				assert circular_linked_list.is_empty() is True
				for i in range(5       ):
								assert len(UpperCamelCase_       ) == i
								circular_linked_list.insert_nth(UpperCamelCase_      ,    i + 1       )
				assert str(UpperCamelCase_       ) == "->".join(str(UpperCamelCase_       ) for i in range(1      ,    6       )       )

				circular_linked_list.insert_tail(6       )
				assert str(UpperCamelCase_       ) == "->".join(str(UpperCamelCase_       ) for i in range(1      ,    7       )       )
				circular_linked_list.insert_head(0       )
				assert str(UpperCamelCase_       ) == "->".join(str(UpperCamelCase_       ) for i in range(0      ,    7       )       )

				assert circular_linked_list.delete_front() == 0
				assert circular_linked_list.delete_tail() == 6
				assert str(UpperCamelCase_       ) == "->".join(str(UpperCamelCase_       ) for i in range(1      ,    6       )       )
				assert circular_linked_list.delete_nth(2       ) == 3

				circular_linked_list.insert_nth(2      ,    3       )
				assert str(UpperCamelCase_       ) == "->".join(str(UpperCamelCase_       ) for i in range(1      ,    6       )       )

				assert circular_linked_list.is_empty() is False


if __name__ == "__main__":
	import doctest

	doctest.testmod()

