



"""simple docstring"""
from __future__ import annotations

import time

__SCREAMING_SNAKE_CASE  :						Optional[Any]    							=      list[tuple[int, int]]

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

__SCREAMING_SNAKE_CASE  :						Optional[int]    							=      [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right


class 							lowerCamelCase_:





					'''simple docstring'''



					def __init__(    self				,       lowerCamelCase__				,       lowerCamelCase__				,       lowerCamelCase__				,       lowerCamelCase__				,       lowerCamelCase__   ):
									_lowerCamelCase        =				pos_x
									_lowerCamelCase        =				pos_y
									_lowerCamelCase        =				(pos_y, pos_x)
									_lowerCamelCase        =				goal_x
									_lowerCamelCase        =				goal_y
									_lowerCamelCase        =				parent


class 							lowerCamelCase_:





					'''simple docstring'''



					def __init__(    self				,       lowerCamelCase__				,       lowerCamelCase__   ):
									_lowerCamelCase        =				Node(start[1]				,       start[0]				,       goal[1]				,       goal[0]				,       lowerCamelCase__   )
									_lowerCamelCase        =				Node(goal[1]				,       goal[0]				,       goal[1]				,       goal[0]				,       lowerCamelCase__   )

									_lowerCamelCase        =				[self.start]
									_lowerCamelCase        =				False

					def 			snake_case__      (    self   ):
									while self.node_queue:
													_lowerCamelCase        =				self.node_queue.pop(0   )

													if current_node.pos == self.target.pos:
																	_lowerCamelCase        =				True
																	return self.retrace_path(lowerCamelCase__   )

													_lowerCamelCase        =				self.get_successors(lowerCamelCase__   )

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

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

					def 			snake_case__      (    self				,       lowerCamelCase__   ):
									_lowerCamelCase        =				[]
									for action in delta:
													_lowerCamelCase        =				parent.pos_x + action[1]
													_lowerCamelCase        =				parent.pos_y + action[0]
													if not (0 <= pos_x <= len(grid[0]   ) - 1 and 0 <= pos_y <= len(lowerCamelCase__   ) - 1):
																	continue

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

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





					def 			snake_case__      (    self				,       lowerCamelCase__   ):
									_lowerCamelCase        =				node
									_lowerCamelCase        =				[]
									while current_node is not None:
													path.append((current_node.pos_y, current_node.pos_x)   )
													_lowerCamelCase        =				current_node.parent
									path.reverse()
									return path


class 							lowerCamelCase_:





					'''simple docstring'''



					def __init__(    self				,       lowerCamelCase__				,       lowerCamelCase__   ):
									_lowerCamelCase        =				BreadthFirstSearch(lowerCamelCase__				,       lowerCamelCase__   )
									_lowerCamelCase        =				BreadthFirstSearch(lowerCamelCase__				,       lowerCamelCase__   )
									_lowerCamelCase        =				False

					def 			snake_case__      (    self   ):
									while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
													_lowerCamelCase        =				self.fwd_bfs.node_queue.pop(0   )
													_lowerCamelCase        =				self.bwd_bfs.node_queue.pop(0   )

													if current_bwd_node.pos == current_fwd_node.pos:
																	_lowerCamelCase        =				True
																	return self.retrace_bidirectional_path(
																	    lowerCamelCase__				,       lowerCamelCase__   )

													_lowerCamelCase        =				current_bwd_node
													_lowerCamelCase        =				current_fwd_node

													_lowerCamelCase        =				{
													    self.fwd_bfs: self.fwd_bfs.get_successors(lowerCamelCase__   ),
													    self.bwd_bfs: self.bwd_bfs.get_successors(lowerCamelCase__   ),
													}

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

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





					def 			snake_case__      (    self				,       lowerCamelCase__				,       lowerCamelCase__   ):
									_lowerCamelCase        =				self.fwd_bfs.retrace_path(lowerCamelCase__   )
									_lowerCamelCase        =				self.bwd_bfs.retrace_path(lowerCamelCase__   )
									bwd_path.pop()
									bwd_path.reverse()
									_lowerCamelCase        =				fwd_path + bwd_path
									return path


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

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

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

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

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

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





"""simple docstring"""
from typing import Any


class 							lowerCamelCase_:





					'''simple docstring'''



					def __init__(    self				,       lowerCamelCase__   ):
									_lowerCamelCase        =				data
									_lowerCamelCase        =				None


class 							lowerCamelCase_:





					'''simple docstring'''



					def __init__(    self   ):
									_lowerCamelCase        =				None

					def 			snake_case__      (    self   ):
									_lowerCamelCase        =				self.head
									while temp is not None:
													print(temp.data				,       end=''' '''   )
													_lowerCamelCase        =				temp.next
									print()

					def 			snake_case__      (    self				,       lowerCamelCase__   ):
									_lowerCamelCase        =				Node(lowerCamelCase__   )
									_lowerCamelCase        =				self.head
									_lowerCamelCase        =				new_node





					def 			snake_case__      (    self				,       lowerCamelCase__				,       lowerCamelCase__   ):
									if node_data_a == node_data_a:
													return
									else:
													_lowerCamelCase        =				self.head
													while node_a is not None and node_a.data != node_data_a:
																	_lowerCamelCase        =				node_a.next

													_lowerCamelCase        =				self.head
													while node_a is not None and node_a.data != node_data_a:
																	_lowerCamelCase        =				node_a.next

													if node_a is None or node_a is None:
																	return

													_lowerCamelCase  ,     _lowerCamelCase        =				node_a.data, node_a.data


if __name__ == "__main__":
			__SCREAMING_SNAKE_CASE  :						List[Any]    							=      LinkedList()
			for i in range(5, 0, -1):
						ll.push(i)

			ll.print_list()

			ll.swap_nodes(1, 4)
			print('''After swapping''')
			ll.print_list()
