
from __future__ import annotations

import time

lowercase        =  list[tuple[int, int]]

lowercase        =  [
    [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],
]

lowercase        =  [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right





class       __A:

					def __init__(	self					:     Union[str, Any]   ,					__UpperCamelCase					:     int   ,					__UpperCamelCase					:     int   ,					__UpperCamelCase					:     int   ,					__UpperCamelCase					:     int   ,					__UpperCamelCase					:     Node | None   ):
												lowerCamelCase_							  =					pos_x
												lowerCamelCase_							  =					pos_y
												lowerCamelCase_							  =					(pos_y, pos_x)
												lowerCamelCase_							  =					goal_x
												lowerCamelCase_							  =					goal_y
												lowerCamelCase_							  =					parent





class       __A:

					def __init__(	self					:     int   ,					__UpperCamelCase					:     tuple[int, int]   ,					__UpperCamelCase					:     tuple[int, int]   ):
												lowerCamelCase_							  =					Node(start[1]   ,					start[0]   ,					goal[1]   ,					goal[0]   ,					__UpperCamelCase   )
												lowerCamelCase_							  =					Node(goal[1]   ,					goal[0]   ,					goal[1]   ,					goal[0]   ,					__UpperCamelCase   )

												lowerCamelCase_							  =					[self.start]
												lowerCamelCase_							  =					False

					def    lowercase__      (	self					:     Any   ):
												while self.node_queue:
																			lowerCamelCase_							  =					self.node_queue.pop(0   )

																			if current_node.pos == self.target.pos:
																										lowerCamelCase_							  =					True
																										return self.retrace_path(__UpperCamelCase   )

																			lowerCamelCase_							  =					self.get_successors(__UpperCamelCase   )

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

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

					def    lowercase__      (	self					:     Any   ,					__UpperCamelCase					:     Node   ):
												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(__UpperCamelCase   ) - 1):
																										continue

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

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



					def    lowercase__      (	self					:     Optional[Any]   ,					__UpperCamelCase					:     Node | None   ):
												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       __A:

					def __init__(	self					:     Optional[int]   ,					__UpperCamelCase					:     Union[str, Any]   ,					__UpperCamelCase					:     int   ):
												lowerCamelCase_							  =					BreadthFirstSearch(__UpperCamelCase   ,					__UpperCamelCase   )
												lowerCamelCase_							  =					BreadthFirstSearch(__UpperCamelCase   ,					__UpperCamelCase   )
												lowerCamelCase_							  =					False

					def    lowercase__      (	self					:     int   ):
												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(
																										    __UpperCamelCase   ,					__UpperCamelCase   )

																			lowerCamelCase_							  =					current_bwd_node
																			lowerCamelCase_							  =					current_fwd_node

																			lowerCamelCase_							  =					{
																			    self.fwd_bfs: self.fwd_bfs.get_successors(__UpperCamelCase   ),
																			    self.bwd_bfs: self.bwd_bfs.get_successors(__UpperCamelCase   ),
																			}

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

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



					def    lowercase__      (	self					:     Any   ,					__UpperCamelCase					:     Node   ,					__UpperCamelCase					:     Node   ):
												lowerCamelCase_							  =					self.fwd_bfs.retrace_path(__UpperCamelCase   )
												lowerCamelCase_							  =					self.bwd_bfs.retrace_path(__UpperCamelCase   )
												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()
		lowercase        =  (0, 0)
		lowercase        =  (len(grid) - 1, len(grid[0]) - 1)
		for elem in grid:
				print(elem)

		lowercase        =  time.time()
		lowercase        =  BreadthFirstSearch(init, goal)
		lowercase        =  bfs.search()
		lowercase        =  time.time() - start_bfs_time

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

		lowercase        =  time.time()
		lowercase        =  BidirectionalBreadthFirstSearch(init, goal)
		lowercase        =  bd_bfs.search()
		lowercase        =  time.time() - start_bd_bfs_time

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







def      __lowerCAmelCase						(							UpperCAmelCase__				:      int = 4_0_0_0_0_0_0       )  ->    int:
							lowerCamelCase_							  =					[]
							lowerCamelCase_  ,   lowerCamelCase_							  =					0, 1
							while b <= n:
														if b % 2 == 0:
																					even_fibs.append(UpperCAmelCase__       )
														lowerCamelCase_  ,   lowerCamelCase_							  =					b, a + b
							return sum(UpperCAmelCase__       )


if __name__ == "__main__":
		print(F"""{solution() = }""")





