





from __future__ import annotations

import time

snake_case_     =	list[tuple[int, int]]

snake_case_     =	[
    [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_     =	[[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right


class   _lowercase						:


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







class   _lowercase						:


   def __init__( self    ,   _UpperCAmelCase    ,   _UpperCAmelCase					):
       A       :       Dict							=						Node(start[1]    ,   start[0]    ,   goal[1]    ,   goal[0]    ,   _UpperCAmelCase					)
       A       :       Optional[int]							=						Node(goal[1]    ,   goal[0]    ,   goal[1]    ,   goal[0]    ,   _UpperCAmelCase					)

       A       :       List[str]							=						[self.start]
       A       :       Dict							=						False


   def 					snake_case				( self					):
       while self.node_queue:
           A       :       List[Any]							=						self.node_queue.pop(0					)

           if current_node.pos == self.target.pos:
               A       :       int							=						True
               return self.retrace_path(_UpperCAmelCase					)

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







class   _lowercase						:


   def __init__( self    ,   _UpperCAmelCase    ,   _UpperCAmelCase					):
       A       :       Dict							=						BreadthFirstSearch(_UpperCAmelCase    ,   _UpperCAmelCase					)
       A       :       Optional[int]							=						BreadthFirstSearch(_UpperCAmelCase    ,   _UpperCAmelCase					)
       A       :       int							=						False


   def 					snake_case				( self					):
       while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
           A       :       Optional[Any]							=						self.fwd_bfs.node_queue.pop(0					)
           A       :       str							=						self.bwd_bfs.node_queue.pop(0					)

           if current_bwd_node.pos == current_fwd_node.pos:
               A       :       Tuple							=						True
               return self.retrace_bidirectional_path(
                   _UpperCAmelCase    ,   _UpperCAmelCase					)

           A       :       Dict							=						current_bwd_node
           A       :       List[Any]							=						current_fwd_node

           A       :       Union[str, Any]							=						{
               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					):
       A       :       Tuple							=						self.fwd_bfs.retrace_path(_UpperCAmelCase					)
       A       :       Optional[int]							=						self.bwd_bfs.retrace_path(_UpperCAmelCase					)
       bwd_path.pop()
       bwd_path.reverse()
       A       :       Optional[Any]							=						fwd_path + bwd_path
       return path


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

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

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

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

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

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







'''simple docstring'''






def 							_lowerCamelCase(  UpperCamelCase__    : Optional[int]    ,       UpperCamelCase__    : str		)		->  Optional[int]:
    A       :       Optional[int]							=						0
    A       :       str							=						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

        A       :       Any							=						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

        A       :       Union[str, Any]							=						sorted_collection[point]
        if current_item == item:
            return point
        else:
            if point < left:
                A       :       Tuple							=						left
                A       :       Tuple							=						point
            elif point > right:
                A       :       Optional[Any]							=						right
                A       :       str							=						point
            else:
                if item < current_item:
                    A       :       Tuple							=						point - 1
                else:
                    A       :       Optional[Any]							=						point + 1
    return None
def 							_lowerCamelCase(  UpperCamelCase__    : Dict    ,       UpperCamelCase__    : str    ,       UpperCamelCase__    : Dict    ,       UpperCamelCase__    : List[str]		)		->  List[Any]:

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

    A       :       Dict							=						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 							_lowerCamelCase(  UpperCamelCase__    : Optional[int]		)		->  List[Any]:
    if collection != sorted(UpperCamelCase__		):
        raise ValueError('''Collection must be ascending sorted'''		)
    return True


if __name__ == "__main__":
     import sys
     snake_case_     =	0
     if debug == 1:
          snake_case_     =	[10, 30, 40, 45, 50, 66, 77, 93]
          try:
               __assert_sorted(collection)
          except ValueError:
               sys.exit("""Sequence must be ascending sorted to apply interpolation search""")
          snake_case_     =	67

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