

from __future__ import annotations

import time

_lowerCAmelCase					:			Union[str, Any]  				=			list[tuple[int, int]]

_lowerCAmelCase					:			List[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					:			int  				=			[[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right






class 	__magic_name__    :





			def __init__(		self					,  __snake_case					,  __snake_case					,  __snake_case					,  __snake_case					,  __snake_case					)   -> int:




						'''simple docstring'''
						__a        =pos_x
						__a        =pos_y
						__a        =(pos_y, pos_x)
						__a        =goal_x
						__a        =goal_y
						__a        =parent






class 	__magic_name__    :





			def __init__(		self					,  __snake_case					,  __snake_case					)   -> Tuple:




						'''simple docstring'''
						__a        =Node(start[1]					,  start[0]					,  goal[1]					,  goal[0]					,  __snake_case					)
						__a        =Node(goal[1]					,  goal[0]					,  goal[1]					,  goal[0]					,  __snake_case					)

						__a        =[self.start]
						__a        =False





			def 		__magic_name__    (		self					)   -> Path | None:




						'''simple docstring'''
						while self.node_queue:
									__a        =self.node_queue.pop(0					)

									if current_node.pos == self.target.pos:
												__a        =True
												return self.retrace_path(__snake_case					)

									__a        =self.get_successors(__snake_case					)

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

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





			def 		__magic_name__    (		self					,  __snake_case					)   -> list[Node]:




						'''simple docstring'''
						__a        =[]
						for action in delta:
									__a        =parent.pos_x + action[1]
									__a        =parent.pos_y + action[0]
									if not (0 <= pos_x <= len(grid[0]					) - 1 and 0 <= pos_y <= len(__snake_case					) - 1):
												continue

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

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





			def 		__magic_name__    (		self					,  __snake_case					)   -> Path:




						'''simple docstring'''
						__a        =node
						__a        =[]
						while current_node is not None:
									path.append((current_node.pos_y, current_node.pos_x)					)
									__a        =current_node.parent
						path.reverse()
						return path






class 	__magic_name__    :





			def __init__(		self					,  __snake_case					,  __snake_case					)   -> Tuple:




						'''simple docstring'''
						__a        =BreadthFirstSearch(__snake_case					,  __snake_case					)
						__a        =BreadthFirstSearch(__snake_case					,  __snake_case					)
						__a        =False





			def 		__magic_name__    (		self					)   -> Path | None:




						'''simple docstring'''
						while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
									__a        =self.fwd_bfs.node_queue.pop(0					)
									__a        =self.bwd_bfs.node_queue.pop(0					)

									if current_bwd_node.pos == current_fwd_node.pos:
												__a        =True
												return self.retrace_bidirectional_path(
												    __snake_case					,  __snake_case					)

									__a        =current_bwd_node
									__a        =current_fwd_node

									__a        ={
									    self.fwd_bfs: self.fwd_bfs.get_successors(__snake_case					),
									    self.bwd_bfs: self.bwd_bfs.get_successors(__snake_case					),
									}

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

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





			def 		__magic_name__    (		self					,  __snake_case					,  __snake_case					)   -> Path:




						'''simple docstring'''
						__a        =self.fwd_bfs.retrace_path(__snake_case					)
						__a        =self.bwd_bfs.retrace_path(__snake_case					)
						bwd_path.pop()
						bwd_path.reverse()
						__a        =fwd_path + bwd_path
						return path


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

						doctest.testmod()
						_lowerCAmelCase					:			Optional[int]  				=			(0, 0)
						_lowerCAmelCase					:			int  				=			(len(grid) - 1, len(grid[0]) - 1)
						for elem in grid:
												print(elem)

						_lowerCAmelCase					:			Tuple  				=			time.time()
						_lowerCAmelCase					:			Tuple  				=			BreadthFirstSearch(init, goal)
						_lowerCAmelCase					:			List[Any]  				=			bfs.search()
						_lowerCAmelCase					:			Any  				=			time.time() - start_bfs_time

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

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

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









from __future__ import annotations






def        UpperCamelCase_(							_snake_case   :  int	):




			"""simple docstring"""






			__a        =str(_snake_case	)
			return len(_snake_case	) == 9 and set(_snake_case	) == set('123456789'	)






def        UpperCamelCase_(							):




			"""simple docstring"""






			for base_num in range(9999       ,     4999       ,     -1	):
						__a        =100002 * base_num
						if is_9_pandigital(_snake_case	):
									return candidate

			for base_num in range(333       ,     99       ,     -1	):
						__a        =1002003 * base_num
						if is_9_pandigital(_snake_case	):
									return candidate

			return None


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






