'''simple docstring'''


from __future__ import annotations

import time

snake_case__					:      Dict				      =  list[tuple[int, int]]

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

snake_case__					:      List[str]				      =  [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right






class 					__SCREAMING_SNAKE_CASE						:







  '''simple docstring'''






  def __init__(			self				,		snake_case_				,		snake_case_				,		snake_case_				,		snake_case_				,		snake_case_						):




       '''simple docstring'''

       UpperCAmelCase_							:       Tuple       =				pos_x
       UpperCAmelCase_							:       int       =				pos_y
       UpperCAmelCase_							:       Optional[Any]       =				(pos_y, pos_x)
       UpperCAmelCase_							:       List[str]       =				goal_x
       UpperCAmelCase_							:       int       =				goal_y
       UpperCAmelCase_							:       int       =				parent







class 					__SCREAMING_SNAKE_CASE						:







  '''simple docstring'''






  def __init__(			self				,		snake_case_				,		snake_case_						):




       '''simple docstring'''

       UpperCAmelCase_							:       Optional[int]       =				Node(start[1]				,		start[0]				,		goal[1]				,		goal[0]				,		__A						)
       UpperCAmelCase_							:       Union[str, Any]       =				Node(goal[1]				,		goal[0]				,		goal[1]				,		goal[0]				,		__A						)

       UpperCAmelCase_							:       Optional[Any]       =				[self.start]
       UpperCAmelCase_							:       Optional[Any]       =				False


  def _UpperCamelCase					(			self						):




       '''simple docstring'''

       while self.node_queue:
            UpperCAmelCase_							:       List[Any]       =				self.node_queue.pop(0						)

            if current_node.pos == self.target.pos:
                 UpperCAmelCase_							:       str       =				True
                 return self.retrace_path(__A						)

            UpperCAmelCase_							:       Union[str, Any]       =				self.get_successors(__A						)

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

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


  def _UpperCamelCase					(			self				,		snake_case_						):




       '''simple docstring'''

       UpperCAmelCase_							:       int       =				[]
       for action in delta:
            UpperCAmelCase_							:       Optional[Any]       =				parent.pos_x + action[1]
            UpperCAmelCase_							:       str       =				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 _UpperCamelCase					(			self				,		snake_case_						):




       '''simple docstring'''

       UpperCAmelCase_							:       Dict       =				node
       UpperCAmelCase_							:       Union[str, Any]       =				[]
       while current_node is not None:
            path.append((current_node.pos_y, current_node.pos_x)						)
            UpperCAmelCase_							:       Optional[Any]       =				current_node.parent
       path.reverse()
       return path







class 					__SCREAMING_SNAKE_CASE						:







  '''simple docstring'''






  def __init__(			self				,		snake_case_				,		snake_case_						):




       '''simple docstring'''

       UpperCAmelCase_							:       List[Any]       =				BreadthFirstSearch(__A				,		__A						)
       UpperCAmelCase_							:       Any       =				BreadthFirstSearch(__A				,		__A						)
       UpperCAmelCase_							:       List[Any]       =				False


  def _UpperCamelCase					(			self						):




       '''simple docstring'''

       while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
            UpperCAmelCase_							:       Union[str, Any]       =				self.fwd_bfs.node_queue.pop(0						)
            UpperCAmelCase_							:       Any       =				self.bwd_bfs.node_queue.pop(0						)

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

            UpperCAmelCase_							:       Dict       =				current_bwd_node
            UpperCAmelCase_							:       Any       =				current_fwd_node

            UpperCAmelCase_							:       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 _UpperCamelCase					(			self				,		snake_case_				,		snake_case_						):




       '''simple docstring'''

       UpperCAmelCase_							:       Tuple       =				self.fwd_bfs.retrace_path(__A						)
       UpperCAmelCase_							:       Tuple       =				self.bwd_bfs.retrace_path(__A						)
       bwd_path.pop()
       bwd_path.reverse()
       UpperCAmelCase_							:       List[str]       =				fwd_path + bwd_path
       return path


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

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

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

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

 snake_case__					:      List[Any]				      =  time.time()
 snake_case__					:      Tuple				      =  BidirectionalBreadthFirstSearch(init, goal)
 snake_case__					:      Any				      =  bd_bfs.search()
 snake_case__					:      List[str]				      =  time.time() - start_bd_bfs_time

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







'''simple docstring'''


snake_case__					:      str				      =  '''Tobias Carryer'''

from time import time






class 					__SCREAMING_SNAKE_CASE						:







  '''simple docstring'''






  def __init__(			self				,		snake_case_				,		snake_case_				,		snake_case_				,		snake_case_=int(time()						)						):  # noqa: B008




       '''simple docstring'''

       UpperCAmelCase_							:       str       =				multiplier
       UpperCAmelCase_							:       Dict       =				increment
       UpperCAmelCase_							:       Tuple       =				modulo
       UpperCAmelCase_							:       Dict       =				seed






  def _UpperCamelCase					(			self						):




       '''simple docstring'''

       UpperCAmelCase_							:       Union[str, Any]       =				(self.multiplier * self.seed + self.increment) % self.modulo
       return self.seed


if __name__ == "__main__":
 # Show the LCG in action.
 snake_case__					:      Any				      =  LinearCongruentialGenerator(166_4525, 10_1390_4223, 2 << 31)
 while True:
  print(lcg.next_number())






