"""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     UpperCAmelCase						:



    """simple docstring"""

    def __init__(   self    ,			_UpperCAmelCase    ,			_UpperCAmelCase    ,			_UpperCAmelCase    ,			_UpperCAmelCase    ,			_UpperCAmelCase							):
       lowercase__:   Union[str, Any]					=      pos_x
       lowercase__:   Any					=      pos_y
       lowercase__:   Union[str, Any]					=      (pos_y, pos_x)
       lowercase__:   int					=      goal_x
       lowercase__:   List[Any]					=      goal_y
       lowercase__:   Optional[Any]					=      parent



class     UpperCAmelCase						:



    """simple docstring"""

    def __init__(   self    ,			_UpperCAmelCase    ,			_UpperCAmelCase							):
       lowercase__:   Dict					=      Node(start[1]    ,			start[0]    ,			goal[1]    ,			goal[0]    ,			_UpperCAmelCase							)
       lowercase__:   Union[str, Any]					=      Node(goal[1]    ,			goal[0]    ,			goal[1]    ,			goal[0]    ,			_UpperCAmelCase							)

       lowercase__:   int					=      [self.start]
       lowercase__:   List[str]					=      False






    def _snake_case			(   self							):
       while self.node_queue:
          lowercase__:   str					=      self.node_queue.pop(0							)

          if current_node.pos == self.target.pos:
             lowercase__:   Tuple					=      True
             return self.retrace_path(_UpperCAmelCase							)

          lowercase__:   Optional[Any]					=      self.get_successors(_UpperCAmelCase							)

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

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






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



class     UpperCAmelCase						:



    """simple docstring"""

    def __init__(   self    ,			_UpperCAmelCase    ,			_UpperCAmelCase							):
       lowercase__:   Optional[Any]					=      BreadthFirstSearch(_UpperCAmelCase    ,			_UpperCAmelCase							)
       lowercase__:   Any					=      BreadthFirstSearch(_UpperCAmelCase    ,			_UpperCAmelCase							)
       lowercase__:   Optional[Any]					=      False






    def _snake_case			(   self							):
       while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
          lowercase__:   List[str]					=      self.fwd_bfs.node_queue.pop(0							)
          lowercase__:   int					=      self.bwd_bfs.node_queue.pop(0							)

          if current_bwd_node.pos == current_fwd_node.pos:
             lowercase__:   int					=      True
             return self.retrace_bidirectional_path(
                 _UpperCAmelCase    ,			_UpperCAmelCase							)

          lowercase__:   Optional[Any]					=      current_bwd_node
          lowercase__:   int					=      current_fwd_node

          lowercase__:   int					=      {
              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 _snake_case			(   self    ,			_UpperCAmelCase    ,			_UpperCAmelCase							):
       lowercase__:   Optional[int]					=      self.fwd_bfs.retrace_path(_UpperCAmelCase							)
       lowercase__:   Optional[Any]					=      self.bwd_bfs.retrace_path(_UpperCAmelCase							)
       bwd_path.pop()
       bwd_path.reverse()
       lowercase__:   Dict					=      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)

"""simple docstring"""






def SCREAMING_SNAKE_CASE__			(   __UpperCAmelCase       ,    __UpperCAmelCase )  ->  List[str]:
   lowercase__:   Optional[Any]					=      0
   lowercase__:   List[Any]					=      len(__UpperCAmelCase ) - 1

   while left <= right:
      # avoid divided by 0 during interpolation
      if sorted_collection[left] == sorted_collection[right]:
         if sorted_collection[left] == item:
            return left
         else:
            return None

      lowercase__:   Tuple					=      left + ((item - sorted_collection[left]) * (right - left)) // (
          sorted_collection[right] - sorted_collection[left]
      )

      # out of range check
      if point < 0 or point >= len(__UpperCAmelCase ):
         return None

      lowercase__:   Optional[int]					=      sorted_collection[point]
      if current_item == item:
         return point
      else:
         if point < left:
            lowercase__:   List[Any]					=      left
            lowercase__:   int					=      point
         elif point > right:
            lowercase__:   Dict					=      right
            lowercase__:   List[str]					=      point
         else:
            if item < current_item:
               lowercase__:   int					=      point - 1
            else:
               lowercase__:   int					=      point + 1
   return None



def SCREAMING_SNAKE_CASE__			(   __UpperCAmelCase       ,    __UpperCAmelCase       ,    __UpperCAmelCase       ,    __UpperCAmelCase )  ->  List[str]:

   # avoid divided by 0 during interpolation
   if sorted_collection[left] == sorted_collection[right]:
      if sorted_collection[left] == item:
         return left
      else:
         return None

   lowercase__:   Optional[int]					=      left + ((item - sorted_collection[left]) * (right - left)) // (
       sorted_collection[right] - sorted_collection[left]
   )

   # out of range check
   if point < 0 or point >= len(__UpperCAmelCase ):
      return None

   if sorted_collection[point] == item:
      return point
   elif point < left:
      return interpolation_search_by_recursion(__UpperCAmelCase       ,    __UpperCAmelCase       ,    __UpperCAmelCase       ,    __UpperCAmelCase )
   elif point > right:
      return interpolation_search_by_recursion(__UpperCAmelCase       ,    __UpperCAmelCase       ,    __UpperCAmelCase       ,    __UpperCAmelCase )
   else:
      if sorted_collection[point] > item:
         return interpolation_search_by_recursion(
             __UpperCAmelCase       ,    __UpperCAmelCase       ,    __UpperCAmelCase       ,    point - 1 )
      else:
         return interpolation_search_by_recursion(
             __UpperCAmelCase       ,    __UpperCAmelCase       ,    point + 1       ,    __UpperCAmelCase )



def SCREAMING_SNAKE_CASE__			(   __UpperCAmelCase )  ->  List[Any]:
   if collection != sorted(__UpperCAmelCase ):
      raise ValueError('''Collection must be ascending sorted''' )
   return True


if __name__ == "__main__":
       import sys
       __A			   = 0
       if debug == 1:
              __A			   = [1_0, 3_0, 4_0, 4_5, 5_0, 6_6, 7_7, 9_3]
              try:
                     __assert_sorted(collection)
              except ValueError:
                     sys.exit("Sequence must be ascending sorted to apply interpolation search")
              __A			   = 6_7

       __A			   = interpolation_search(collection, target)
       if result is not None:
              print(f'''{target} found at positions: {result}''')
       else:
              print("Not found")
