




from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
_lowerCamelCase      :  Any      						=						0

_lowerCamelCase      :  str      						=						[
    [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],
]

_lowerCamelCase      :  str      						=						[[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

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



				def __init__(      self      :		str		,	_UpperCAmelCase      :		int		,	_UpperCAmelCase      :		int		,	_UpperCAmelCase      :		int		,	_UpperCAmelCase      :		int		,	_UpperCAmelCase      :		int		,	_UpperCAmelCase      :		Node | None		,	)  ->    None:





								'''simple docstring'''




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



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





								'''simple docstring'''




								_lowerCAmelCase    :    List[Any]										=      self.pos_x - self.goal_x
								_lowerCAmelCase    :    Optional[int]										=      self.pos_y - self.goal_y
								if HEURISTIC == 1:
												return abs(_UpperCAmelCase      ) + abs(_UpperCAmelCase      )
								else:
												return sqrt(dy**2 + dx**2      )



				def __lt__(      self      :		List[Any]		,	_UpperCAmelCase      :		Node      )  ->    bool:





								'''simple docstring'''




								return self.f_cost < other.f_cost






class        __snake_case  :



				def __init__(      self      :		Dict		,	_UpperCAmelCase      :		TPosition		,	_UpperCAmelCase      :		TPosition      )  ->    Optional[int]:





								'''simple docstring'''




								_lowerCAmelCase    :    Dict										=      Node(start[1]		,	start[0]		,	goal[1]		,	goal[0]		,	0		,	_UpperCAmelCase      )
								_lowerCAmelCase    :    Union[str, Any]										=      Node(goal[1]		,	goal[0]		,	goal[1]		,	goal[0]		,	9_9999		,	_UpperCAmelCase      )

								_lowerCAmelCase    :    Any										=      [self.start]
								_lowerCAmelCase    :    list[Node]										=      []

								_lowerCAmelCase    :    int										=      False



				def       SCREAMING_SNAKE_CASE       (      self      :		str      )  ->    list[TPosition]:





								'''simple docstring'''




								while self.open_nodes:
												# Open Nodes are sorted using __lt__
												self.open_nodes.sort()
												_lowerCAmelCase    :    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      )
												_lowerCAmelCase    :    List[Any]										=      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
																				_lowerCAmelCase    :    Optional[Any]										=      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       SCREAMING_SNAKE_CASE       (      self      :		Optional[Any]		,	_UpperCAmelCase      :		Node      )  ->    list[Node]:





								'''simple docstring'''




								_lowerCAmelCase    :    Any										=      []
								for action in delta:
												_lowerCAmelCase    :    List[str]										=      parent.pos_x + action[1]
												_lowerCAmelCase    :    str										=      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       SCREAMING_SNAKE_CASE       (      self      :		int		,	_UpperCAmelCase      :		Node | None      )  ->    list[TPosition]:





								'''simple docstring'''




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






class        __snake_case  :



				def __init__(      self      :		int		,	_UpperCAmelCase      :		TPosition		,	_UpperCAmelCase      :		TPosition      )  ->    None:





								'''simple docstring'''




								_lowerCAmelCase    :    Any										=      AStar(_UpperCAmelCase		,	_UpperCAmelCase      )
								_lowerCAmelCase    :    Dict										=      AStar(_UpperCAmelCase		,	_UpperCAmelCase      )
								_lowerCAmelCase    :    List[str]										=      False



				def       SCREAMING_SNAKE_CASE       (      self      :		str      )  ->    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()
												_lowerCAmelCase    :    Optional[Any]										=      self.fwd_astar.open_nodes.pop(0      )
												_lowerCAmelCase    :    Optional[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      )

												_lowerCAmelCase    :    int										=      current_bwd_node
												_lowerCAmelCase    :    List[Any]										=      current_fwd_node

												_lowerCAmelCase    :    List[str]										=      {
												    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
																								_lowerCAmelCase    :    Any										=      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       SCREAMING_SNAKE_CASE       (      self      :		Tuple		,	_UpperCAmelCase      :		Node		,	_UpperCAmelCase      :		Node      )  ->    list[TPosition]:





								'''simple docstring'''




								_lowerCAmelCase    :    int										=      self.fwd_astar.retrace_path(_UpperCAmelCase      )
								_lowerCAmelCase    :    Union[str, Any]										=      self.bwd_astar.retrace_path(_UpperCAmelCase      )
								bwd_path.pop()
								bwd_path.reverse()
								_lowerCAmelCase    :    Tuple										=      fwd_path + bwd_path
								return path


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

	_lowerCamelCase      :  Optional[int]      						=						time.time()
	_lowerCamelCase      :  Optional[int]      						=						AStar(init, goal)
	_lowerCamelCase      :  Dict      						=						a_star.search()
	_lowerCamelCase      :  Dict      						=						time.time() - start_time
	print(F'''AStar execution time = {end_time:f} seconds''')

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







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()

