
from __future__ import annotations

import time

__magic_name__  							=	list[tuple[int, int]]

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

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




class        _SCREAMING_SNAKE_CASE	:
      def __init__(      self		,						lowerCamelCase		,						lowerCamelCase		,						lowerCamelCase		,						lowerCamelCase		,						lowerCamelCase			):
          snake_case__    =					pos_x
          snake_case__    =					pos_y
          snake_case__    =					(pos_y, pos_x)
          snake_case__    =					goal_x
          snake_case__    =					goal_y
          snake_case__    =					parent





class        _SCREAMING_SNAKE_CASE	:
      def __init__(      self		,						lowerCamelCase		,						lowerCamelCase			):
          snake_case__    =					Node(start[1]		,						start[0]		,						goal[1]		,						goal[0]		,						lowerCamelCase			)
          snake_case__    =					Node(goal[1]		,						goal[0]		,						goal[1]		,						goal[0]		,						lowerCamelCase			)

          snake_case__    =					[self.start]
          snake_case__    =					False
      def A_      (      self			):
          while self.node_queue:
              snake_case__    =					self.node_queue.pop(0			)

              if current_node.pos == self.target.pos:
                  snake_case__    =					True
                  return self.retrace_path(lowerCamelCase			)

              snake_case__    =					self.get_successors(lowerCamelCase			)

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

          if not self.reached:
              return [self.start.pos]
          return None
      def A_      (      self		,						lowerCamelCase			):
          snake_case__    =					[]
          for action in delta:
              snake_case__    =					parent.pos_x + action[1]
              snake_case__    =					parent.pos_y + action[0]
              if not (0 <= pos_x <= len(grid[0]			) - 1 and 0 <= pos_y <= len(lowerCamelCase			) - 1):
                  continue

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

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



      def A_      (      self		,						lowerCamelCase			):
          snake_case__    =					node
          snake_case__    =					[]
          while current_node is not None:
              path.append((current_node.pos_y, current_node.pos_x)			)
              snake_case__    =					current_node.parent
          path.reverse()
          return path





class        _SCREAMING_SNAKE_CASE	:
      def __init__(      self		,						lowerCamelCase		,						lowerCamelCase			):
          snake_case__    =					BreadthFirstSearch(lowerCamelCase		,						lowerCamelCase			)
          snake_case__    =					BreadthFirstSearch(lowerCamelCase		,						lowerCamelCase			)
          snake_case__    =					False
      def A_      (      self			):
          while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
              snake_case__    =					self.fwd_bfs.node_queue.pop(0			)
              snake_case__    =					self.bwd_bfs.node_queue.pop(0			)

              if current_bwd_node.pos == current_fwd_node.pos:
                  snake_case__    =					True
                  return self.retrace_bidirectional_path(
                      lowerCamelCase		,						lowerCamelCase			)

              snake_case__    =					current_bwd_node
              snake_case__    =					current_fwd_node

              snake_case__    =					{
                  self.fwd_bfs: self.fwd_bfs.get_successors(lowerCamelCase			),
                  self.bwd_bfs: self.bwd_bfs.get_successors(lowerCamelCase			),
              }

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

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



      def A_      (      self		,						lowerCamelCase		,						lowerCamelCase			):
          snake_case__    =					self.fwd_bfs.retrace_path(lowerCamelCase			)
          snake_case__    =					self.bwd_bfs.retrace_path(lowerCamelCase			)
          bwd_path.pop()
          bwd_path.reverse()
          snake_case__    =					fwd_path + bwd_path
          return path


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

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

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

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

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

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





from math import loga





def 						SCREAMING_SNAKE_CASE__     (   __lowerCAmelCase				):
    if a < 0:
        raise ValueError("Input value must be a positive integer"				)
    elif isinstance(__lowerCAmelCase     ,		__lowerCAmelCase				):
        raise TypeError("Input value must be a 'int' type"				)
    return 0 if (a == 0) else int(loga(a & -a				)				)


if __name__ == "__main__":
     import doctest

     doctest.testmod()



