






from collections.abc import Iterator, MutableMapping
from dataclasses import dataclass
from typing import Generic, TypeVar

__lowerCamelCase      :    str   		=   TypeVar("""KEY""")
__lowerCamelCase      :    int   		=   TypeVar("""VAL""")



@dataclass(frozen=UpperCamelCase_				,     slots=UpperCamelCase_		)
class 							SCREAMING_SNAKE_CASE__		(       Generic[KEY, VAL]		):





					"""simple docstring"""






					a_			=	42
					a_			=	42



class 							SCREAMING_SNAKE_CASE__		(       _Item		):





					"""simple docstring"""






					def __init__(      self  :						Tuple ):
						super().__init__(__A							,	__A )






					def __bool__(      self  :						Dict ):
						return False
__lowerCamelCase      :    List[str]   		=   _DeletedItem()



class 							SCREAMING_SNAKE_CASE__		(       MutableMapping[KEY, VAL]		):





					"""simple docstring"""






					def __init__(      self  :						Optional[Any]							,	__A  :						int = 8							,	__A  :						float = 0.7_5 ):
						snake_case__				:   Dict     =						initial_block_size
						snake_case__				:   list[_Item | None]     =						[None] * initial_block_size
						assert 0.0 < capacity_factor < 1.0
						snake_case__				:   Optional[Any]     =						capacity_factor
						snake_case__				:   str     =						0



					def  _lowercase  (      self  :						List[str]							,	__A  :						KEY ):
						return hash(__A ) % len(self._buckets )



					def  _lowercase  (      self  :						Union[str, Any]							,	__A  :						int ):
						return (ind + 1) % len(self._buckets )



					def  _lowercase  (      self  :						Optional[Any]							,	__A  :						int							,	__A  :						KEY							,	__A  :						VAL ):
						snake_case__				:   Tuple     =						self._buckets[ind]
						if not stored:
							snake_case__				:   List[Any]     =						_Item(__A							,	__A )
							self._len += 1
							return True
						elif stored.key == key:
							snake_case__				:   List[str]     =						_Item(__A							,	__A )
							return True
						else:
							return False



					def  _lowercase  (      self  :						Dict ):
						snake_case__				:   Optional[Any]     =						len(self._buckets ) * self._capacity_factor
						return len(self ) >= int(__A )



					def  _lowercase  (      self  :						Dict ):
						if len(self._buckets ) <= self._initial_block_size:
							return False
						snake_case__				:   Optional[Any]     =						len(self._buckets ) * self._capacity_factor / 2
						return len(self ) < limit



					def  _lowercase  (      self  :						Optional[int]							,	__A  :						int ):
						snake_case__				:   Optional[Any]     =						self._buckets
						snake_case__				:   Optional[int]     =						[None] * new_size
						snake_case__				:   Any     =						0
						for item in old_buckets:
							if item:
								self._add_item(item.key							,	item.val )



					def  _lowercase  (      self  :						int ):
						self._resize(len(self._buckets ) * 2 )



					def  _lowercase  (      self  :						Union[str, Any] ):
						self._resize(len(self._buckets ) // 2 )



					def  _lowercase  (      self  :						int							,	__A  :						KEY ):
						snake_case__				:   List[Any]     =						self._get_bucket_index(__A )
						for _ in range(len(self._buckets ) ):
							yield ind
							snake_case__				:   int     =						self._get_next_ind(__A )



					def  _lowercase  (      self  :						Tuple							,	__A  :						KEY							,	__A  :						VAL ):
						for ind in self._iterate_buckets(__A ):
							if self._try_set(__A							,	__A							,	__A ):
								break



					def __setitem__(      self  :						Union[str, Any]							,	__A  :						KEY							,	__A  :						VAL ):
						if self._is_full():
							self._size_up()

						self._add_item(__A							,	__A )



					def __delitem__(      self  :						List[str]							,	__A  :						KEY ):
						for ind in self._iterate_buckets(__A ):
							snake_case__				:   str     =						self._buckets[ind]
							if item is None:
								raise KeyError(__A )
							if item is _deleted:
								continue
							if item.key == key:
								snake_case__				:   str     =						_deleted
								self._len -= 1
								break
						if self._is_sparse():
							self._size_down()



					def __getitem__(      self  :						str							,	__A  :						KEY ):
						for ind in self._iterate_buckets(__A ):
							snake_case__				:   Dict     =						self._buckets[ind]
							if item is None:
								break
							if item is _deleted:
								continue
							if item.key == key:
								return item.val
						raise KeyError(__A )



					def __len__(      self  :						int ):
						return self._len



					def __iter__(      self  :						List[str] ):
						yield from (item.key for item in self._buckets if item)






					def __repr__(      self  :						str ):
						snake_case__				:   Union[str, Any]     =						" ,".join(
						    f'''{item.key}: {item.val}''' for item in self._buckets if item )
						return f'''HashMap({val_string})'''











from __future__ import annotations

import time

__lowerCamelCase      :    str   		=   list[tuple[int, int]]

__lowerCamelCase      :    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],
]

__lowerCamelCase      :    Tuple   		=   [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right



class 							SCREAMING_SNAKE_CASE__		:





					"""simple docstring"""






					def __init__(      self  :						Union[str, Any]							,	__A  :						int							,	__A  :						int							,	__A  :						int							,	__A  :						int							,	__A  :						Node | None ):
						snake_case__				:   Optional[int]     =						pos_x
						snake_case__				:   Dict     =						pos_y
						snake_case__				:   int     =						(pos_y, pos_x)
						snake_case__				:   Optional[int]     =						goal_x
						snake_case__				:   Tuple     =						goal_y
						snake_case__				:   str     =						parent



class 							SCREAMING_SNAKE_CASE__		:





					"""simple docstring"""






					def __init__(      self  :						List[Any]							,	__A  :						tuple[int, int]							,	__A  :						tuple[int, int] ):
						snake_case__				:   Tuple     =						Node(start[1]							,	start[0]							,	goal[1]							,	goal[0]							,	__A )
						snake_case__				:   Tuple     =						Node(goal[1]							,	goal[0]							,	goal[1]							,	goal[0]							,	__A )

						snake_case__				:   int     =						[self.start]
						snake_case__				:   Union[str, Any]     =						False



					def  _lowercase  (      self  :						Dict ):
						while self.node_queue:
							snake_case__				:   Optional[Any]     =						self.node_queue.pop(0 )

							if current_node.pos == self.target.pos:
								snake_case__				:   Optional[Any]     =						True
								return self.retrace_path(__A )

							snake_case__				:   int     =						self.get_successors(__A )

							for node in successors:
								self.node_queue.append(__A )

						if not self.reached:
							return [self.start.pos]
						return None



					def  _lowercase  (      self  :						Union[str, Any]							,	__A  :						Node ):
						snake_case__				:   str     =						[]
						for action in delta:
							snake_case__				:   str     =						parent.pos_x + action[1]
							snake_case__				:   Union[str, Any]     =						parent.pos_y + action[0]
							if not (0 <= pos_x <= len(grid[0] ) - 1 and 0 <= pos_y <= len(__A ) - 1):
								continue

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

							successors.append(
							    Node(__A							,	__A							,	self.target.pos_y							,	self.target.pos_x							,	__A ) )
						return successors






					def  _lowercase  (      self  :						Optional[Any]							,	__A  :						Node | None ):
						snake_case__				:   Tuple     =						node
						snake_case__				:   Any     =						[]
						while current_node is not None:
							path.append((current_node.pos_y, current_node.pos_x) )
							snake_case__				:   Tuple     =						current_node.parent
						path.reverse()
						return path



class 							SCREAMING_SNAKE_CASE__		:





					"""simple docstring"""






					def __init__(      self  :						Dict							,	__A  :						str							,	__A  :						int ):
						snake_case__				:   str     =						BreadthFirstSearch(__A							,	__A )
						snake_case__				:   int     =						BreadthFirstSearch(__A							,	__A )
						snake_case__				:   Tuple     =						False



					def  _lowercase  (      self  :						Optional[Any] ):
						while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
							snake_case__				:   Any     =						self.fwd_bfs.node_queue.pop(0 )
							snake_case__				:   List[str]     =						self.bwd_bfs.node_queue.pop(0 )

							if current_bwd_node.pos == current_fwd_node.pos:
								snake_case__				:   List[str]     =						True
								return self.retrace_bidirectional_path(
								    __A							,	__A )

							snake_case__				:   Union[str, Any]     =						current_bwd_node
							snake_case__				:   Dict     =						current_fwd_node

							snake_case__				:   List[Any]     =						{
							    self.fwd_bfs: self.fwd_bfs.get_successors(__A ),
							    self.bwd_bfs: self.bwd_bfs.get_successors(__A ),
							}

							for bfs in [self.fwd_bfs, self.bwd_bfs]:
								for node in successors[bfs]:
									bfs.node_queue.append(__A )

						if not self.reached:
							return [self.fwd_bfs.start.pos]
						return None






					def  _lowercase  (      self  :						Any							,	__A  :						Node							,	__A  :						Node ):
						snake_case__				:   List[str]     =						self.fwd_bfs.retrace_path(__A )
						snake_case__				:   Optional[Any]     =						self.bwd_bfs.retrace_path(__A )
						bwd_path.pop()
						bwd_path.reverse()
						snake_case__				:   List[Any]     =						fwd_path + bwd_path
						return path


if __name__ == "__main__":
	# all coordinates are given in format [y,x]
	import doctest

	doctest.testmod()
	__lowerCamelCase      :    str   		=   (0, 0)
	__lowerCamelCase      :    List[str]   		=   (len(grid) - 1, len(grid[0]) - 1)
	for elem in grid:
		print(elem)

	__lowerCamelCase      :    Any   		=   time.time()
	__lowerCamelCase      :    Optional[Any]   		=   BreadthFirstSearch(init, goal)
	__lowerCamelCase      :    str   		=   bfs.search()
	__lowerCamelCase      :    Optional[Any]   		=   time.time() - start_bfs_time

	print("""Unidirectional BFS computation time : """, bfs_time)

	__lowerCamelCase      :    Optional[Any]   		=   time.time()
	__lowerCamelCase      :    Optional[int]   		=   BidirectionalBreadthFirstSearch(init, goal)
	__lowerCamelCase      :    str   		=   bd_bfs.search()
	__lowerCamelCase      :    Optional[Any]   		=   time.time() - start_bd_bfs_time

	print("""Bidirectional BFS computation time : """, bd_bfs_time)



