


'''simple docstring'''

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






     def __init__(			self     ,							__UpperCamelCase     ,							__UpperCamelCase     ,							__UpperCamelCase     ,							__UpperCamelCase     ,							__UpperCamelCase		)       ->    Tuple:
          _a						=		pos_x
          _a						=		pos_y
          _a						=		(pos_y, pos_x)
          _a						=		goal_x
          _a						=		goal_y
          _a						=		parent







class 						__SCREAMING_SNAKE_CASE					:






     def __init__(			self     ,							__UpperCamelCase     ,							__UpperCamelCase		)       ->    Tuple:
          _a						=		Node(start[1]     ,							start[0]     ,							goal[1]     ,							goal[0]     ,							__UpperCamelCase		)
          _a						=		Node(goal[1]     ,							goal[0]     ,							goal[1]     ,							goal[0]     ,							__UpperCamelCase		)

          _a						=		[self.start]
          _a						=		False






     def  a_					(			self		)       ->    Path | None:
          while self.node_queue:
               _a						=		self.node_queue.pop(0		)

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

               _a						=		self.get_successors(__UpperCamelCase		)

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

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






     def  a_					(			self     ,							__UpperCamelCase		)       ->    list[Node]:
          _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(__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  a_					(			self     ,							__UpperCamelCase		)       ->    Path:
          _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 						__SCREAMING_SNAKE_CASE					:






     def __init__(			self     ,							__UpperCamelCase     ,							__UpperCamelCase		)       ->    List[Any]:
          _a						=		BreadthFirstSearch(__UpperCamelCase     ,							__UpperCamelCase		)
          _a						=		BreadthFirstSearch(__UpperCamelCase     ,							__UpperCamelCase		)
          _a						=		False






     def  a_					(			self		)       ->    Path | None:
          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(
                        __UpperCamelCase     ,							__UpperCamelCase		)

               _a						=		current_bwd_node
               _a						=		current_fwd_node

               _a						=		{
                   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  a_					(			self     ,							__UpperCamelCase     ,							__UpperCamelCase		)       ->    Path:
          _a						=		self.fwd_bfs.retrace_path(__UpperCamelCase		)
          _a						=		self.bwd_bfs.retrace_path(__UpperCamelCase		)
          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()
   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)





'''simple docstring'''

lowercase__				     =		65_521






def __UpperCamelCase   (			__lowerCamelCase		: str				)      ->     int:







     '''simple docstring'''






     _a						=		1
     _a						=		0
     for plain_chr in plain_text:
          _a						=		(a + ord(__lowerCamelCase				)) % MOD_ADLER
          _a						=		(b + a) % MOD_ADLER
     return (b << 16) | a

