






'''simple docstring'''
from __future__ import annotations

import time

a_ 		=       list[tuple[int, int]]

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

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






class    __SCREAMING_SNAKE_CASE					:




 def __init__(					self		:							List[Any]    ,					__lowercase		:							int    ,					__lowercase		:							int    ,					__lowercase		:							int    ,					__lowercase		:							int    ,					__lowercase		:							Node | None					)		->  int:
       SCREAMING_SNAKE_CASE__   : Any													=pos_x
       SCREAMING_SNAKE_CASE__   : Any													=pos_y
       SCREAMING_SNAKE_CASE__   : Dict													=(pos_y, pos_x)
       SCREAMING_SNAKE_CASE__   : Union[str, Any]													=goal_x
       SCREAMING_SNAKE_CASE__   : Optional[Any]													=goal_y
       SCREAMING_SNAKE_CASE__   : Dict													=parent






class    __SCREAMING_SNAKE_CASE					:




 def __init__(					self		:							Any    ,					__lowercase		:							tuple[int, int]    ,					__lowercase		:							tuple[int, int]					)		->  Tuple:
       SCREAMING_SNAKE_CASE__   : Union[str, Any]													=Node(start[1]    ,					start[0]    ,					goal[1]    ,					goal[0]    ,					UpperCAmelCase_					)
       SCREAMING_SNAKE_CASE__   : str													=Node(goal[1]    ,					goal[0]    ,					goal[1]    ,					goal[0]    ,					UpperCAmelCase_					)

       SCREAMING_SNAKE_CASE__   : Union[str, Any]													=[self.start]
       SCREAMING_SNAKE_CASE__   : Dict													=False




 def    __magic_name__		(					self		:							Union[str, Any]					)		->  str:
       while self.node_queue:
             SCREAMING_SNAKE_CASE__   : str													=self.node_queue.pop(0					)

             if current_node.pos == self.target.pos:
                   SCREAMING_SNAKE_CASE__   : List[Any]													=True
                   return self.retrace_path(UpperCAmelCase_					)

             SCREAMING_SNAKE_CASE__   : Tuple													=self.get_successors(UpperCAmelCase_					)

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

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




 def    __magic_name__		(					self		:							Any    ,					__lowercase		:							Node					)		->  List[str]:
       SCREAMING_SNAKE_CASE__   : List[str]													=[]
       for action in delta:
             SCREAMING_SNAKE_CASE__   : Any													=parent.pos_x + action[1]
             SCREAMING_SNAKE_CASE__   : Union[str, Any]													=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    __magic_name__		(					self		:							Optional[int]    ,					__lowercase		:							Node | None					)		->  int:
       SCREAMING_SNAKE_CASE__   : Dict													=node
       SCREAMING_SNAKE_CASE__   : Tuple													=[]
       while current_node is not None:
             path.append((current_node.pos_y, current_node.pos_x)					)
             SCREAMING_SNAKE_CASE__   : Optional[int]													=current_node.parent
       path.reverse()
       return path






class    __SCREAMING_SNAKE_CASE					:




 def __init__(					self		:							Union[str, Any]    ,					__lowercase		:							Any    ,					__lowercase		:							Union[str, Any]					)		->  str:
       SCREAMING_SNAKE_CASE__   : Union[str, Any]													=BreadthFirstSearch(UpperCAmelCase_    ,					UpperCAmelCase_					)
       SCREAMING_SNAKE_CASE__   : List[str]													=BreadthFirstSearch(UpperCAmelCase_    ,					UpperCAmelCase_					)
       SCREAMING_SNAKE_CASE__   : Union[str, Any]													=False




 def    __magic_name__		(					self		:							Union[str, Any]					)		->  Union[str, Any]:
       while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
             SCREAMING_SNAKE_CASE__   : List[Any]													=self.fwd_bfs.node_queue.pop(0					)
             SCREAMING_SNAKE_CASE__   : List[Any]													=self.bwd_bfs.node_queue.pop(0					)

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

             SCREAMING_SNAKE_CASE__   : Union[str, Any]													=current_bwd_node
             SCREAMING_SNAKE_CASE__   : Union[str, Any]													=current_fwd_node

             SCREAMING_SNAKE_CASE__   : Dict													={
                 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    __magic_name__		(					self		:							Dict    ,					__lowercase		:							Node    ,					__lowercase		:							Node					)		->  List[Any]:
       SCREAMING_SNAKE_CASE__   : str													=self.fwd_bfs.retrace_path(UpperCAmelCase_					)
       SCREAMING_SNAKE_CASE__   : Dict													=self.bwd_bfs.retrace_path(UpperCAmelCase_					)
       bwd_path.pop()
       bwd_path.reverse()
       SCREAMING_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()
  a_ 		=       (0, 0)
  a_ 		=       (len(grid) - 1, len(grid[0]) - 1)
  for elem in grid:
    print(elem)

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

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

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

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

import os






def 							_lowercase							(     )		->		List[str]:
					'''simple docstring'''


					with open(os.path.dirname(UpperCamelCase_		) + '/p022_names.txt'		) as file:
										SCREAMING_SNAKE_CASE__													= str(file.readlines()[0]		)
										SCREAMING_SNAKE_CASE__													= names.replace('"'	,	''		).split(','		)

					names.sort()

					SCREAMING_SNAKE_CASE__													= 0
					SCREAMING_SNAKE_CASE__													= 0

					for i, name in enumerate(UpperCamelCase_		):
										for letter in name:
															name_score += ord(UpperCamelCase_		) - 64

										total_score += (i + 1) * name_score
										SCREAMING_SNAKE_CASE__													= 0
					return total_score


if __name__ == "__main__":
				print(solution())





