from __future__ import annotations

__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 			lowerCamelCase_  :






    '''simple docstring'''






    def __init__(			self				,				__lowercase				,				__lowercase				,				__lowercase				,				__lowercase				,				__lowercase				,				__lowercase				,				) ->			List[str]:
        __UpperCamelCase  :Optional[int]    						=	pos_x
        __UpperCamelCase  :int    						=	pos_y
        __UpperCamelCase  :List[Any]    						=	(pos_y, pos_x)
        __UpperCamelCase  :Union[str, Any]    						=	goal_x
        __UpperCamelCase  :List[str]    						=	goal_y
        __UpperCamelCase  :List[str]    						=	g_cost
        __UpperCamelCase  :Optional[Any]    						=	parent
        __UpperCamelCase  :List[Any]    						=	self.calculate_heuristic()







    def     UpperCamelCase__     (			self) ->			float:
        __UpperCamelCase  :str    						=	abs(self.pos_x - self.goal_x)
        __UpperCamelCase  :str    						=	abs(self.pos_y - self.goal_y)
        return dx + dy







    def __lt__(			self				,				__lowercase) ->			bool:
        return self.f_cost < other.f_cost


class 			lowerCamelCase_  :






    '''simple docstring'''






    def __init__(			self				,				__lowercase				,				__lowercase) ->			str:
        __UpperCamelCase  :List[Any]    						=	Node(start[1]				,				start[0]				,				goal[1]				,				goal[0]				,				0				,				__lowercase)
        __UpperCamelCase  :Optional[int]    						=	Node(goal[1]				,				goal[0]				,				goal[1]				,				goal[0]				,				99_999				,				__lowercase)

        __UpperCamelCase  :List[Any]    						=	[self.start]
        __UpperCamelCase  :list[Node]    						=	[]

        __UpperCamelCase  :List[Any]    						=	False







    def     UpperCamelCase__     (			self) ->			Path | None:
        while self.open_nodes:
            # Open Nodes are sorted using __lt__
            self.open_nodes.sort()
            __UpperCamelCase  :str    						=	self.open_nodes.pop(0)

            if current_node.pos == self.target.pos:
                __UpperCamelCase  :Union[str, Any]    						=	True
                return self.retrace_path(__lowercase)

            self.closed_nodes.append(__lowercase)
            __UpperCamelCase  :Optional[int]    						=	self.get_successors(__lowercase)

            for child_node in successors:
                if child_node in self.closed_nodes:
                    continue

                if child_node not in self.open_nodes:
                    self.open_nodes.append(__lowercase)
                else:
                    # retrieve the best current path
                    __UpperCamelCase  :Any    						=	self.open_nodes.pop(self.open_nodes.index(__lowercase))

                    if child_node.g_cost < better_node.g_cost:
                        self.open_nodes.append(__lowercase)
                    else:
                        self.open_nodes.append(__lowercase)

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







    def     UpperCamelCase__     (			self				,				__lowercase) ->			list[Node]:
        __UpperCamelCase  :str    						=	[]
        for action in delta:
            __UpperCamelCase  :int    						=	parent.pos_x + action[1]
            __UpperCamelCase  :Optional[int]    						=	parent.pos_y + action[0]

            if not (0 <= pos_x <= len(grid[0]) - 1 and 0 <= pos_y <= len(__lowercase) - 1):
                continue

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

            successors.append(
                Node(
                    __lowercase				,				__lowercase				,				self.target.pos_y				,				self.target.pos_x				,				parent.g_cost + 1				,				__lowercase				,				))
        return successors







    def     UpperCamelCase__     (			self				,				__lowercase) ->			Path:
        __UpperCamelCase  :Any    						=	node
        __UpperCamelCase  :Dict    						=	[]
        while current_node is not None:
            path.append((current_node.pos_y, current_node.pos_x))
            __UpperCamelCase  :Tuple    						=	current_node.parent
        path.reverse()
        return path


if __name__ == "__main__":
    __lowercase											=      (0, 0)
    __lowercase											=      (len(grid) - 1, len(grid[0]) - 1)
    for elem in grid:
        print(elem)

    print('''------''')

    __lowercase											=      GreedyBestFirst(init, goal)
    __lowercase											=      greedy_bf.search()
    if path:
        for pos_x, pos_y in path:
            __lowercase											=      2

        for elem in grid:
            print(elem)






from __future__ import annotations

import bisect



def lowerCamelCase						(     SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE = 0						,    SCREAMING_SNAKE_CASE = -1			):
    '''simple docstring'''







    if hi < 0:
        __UpperCamelCase  :str    						=	len(SCREAMING_SNAKE_CASE			)

    while lo < hi:
        __UpperCamelCase  :Optional[int]    						=	lo + (hi - lo) // 2
        if sorted_collection[mid] < item:
            __UpperCamelCase  :List[Any]    						=	mid + 1
        else:
            __UpperCamelCase  :Any    						=	mid

    return lo



def lowerCamelCase						(     SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE = 0						,    SCREAMING_SNAKE_CASE = -1			):
    '''simple docstring'''







    if hi < 0:
        __UpperCamelCase  :List[str]    						=	len(SCREAMING_SNAKE_CASE			)

    while lo < hi:
        __UpperCamelCase  :Optional[Any]    						=	lo + (hi - lo) // 2
        if sorted_collection[mid] <= item:
            __UpperCamelCase  :Dict    						=	mid + 1
        else:
            __UpperCamelCase  :Optional[Any]    						=	mid

    return lo



def lowerCamelCase						(     SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE = 0						,    SCREAMING_SNAKE_CASE = -1			):
    '''simple docstring'''







    sorted_collection.insert(bisect_left(SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE			)						,    SCREAMING_SNAKE_CASE			)



def lowerCamelCase						(     SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE = 0						,    SCREAMING_SNAKE_CASE = -1			):
    '''simple docstring'''







    sorted_collection.insert(bisect_right(SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE			)						,    SCREAMING_SNAKE_CASE			)



def lowerCamelCase						(     SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE			):
    '''simple docstring'''







    __UpperCamelCase  :Tuple    						=	0
    __UpperCamelCase  :List[str]    						=	len(SCREAMING_SNAKE_CASE			) - 1

    while left <= right:
        __UpperCamelCase  :Optional[int]    						=	left + (right - left) // 2
        __UpperCamelCase  :List[str]    						=	sorted_collection[midpoint]
        if current_item == item:
            return midpoint
        elif item < current_item:
            __UpperCamelCase  :Union[str, Any]    						=	midpoint - 1
        else:
            __UpperCamelCase  :Dict    						=	midpoint + 1
    return None



def lowerCamelCase						(     SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE			):
    '''simple docstring'''







    __UpperCamelCase  :Dict    						=	bisect.bisect_left(SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE			)
    if index != len(SCREAMING_SNAKE_CASE			) and sorted_collection[index] == item:
        return index
    return None



def lowerCamelCase						(     SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE			):
    '''simple docstring'''







    if right < left:
        return None

    __UpperCamelCase  :str    						=	left + (right - left) // 2

    if sorted_collection[midpoint] == item:
        return midpoint
    elif sorted_collection[midpoint] > item:
        return binary_search_by_recursion(SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE						,    midpoint - 1			)
    else:
        return binary_search_by_recursion(SCREAMING_SNAKE_CASE						,    SCREAMING_SNAKE_CASE						,    midpoint + 1						,    SCREAMING_SNAKE_CASE			)


if __name__ == "__main__":
    __lowercase											=      input('''Enter numbers separated by comma:\n''').strip()
    __lowercase											=      sorted(int(item) for item in user_input.split(''','''))
    __lowercase											=      int(input('''Enter a single number to be found in the list:\n'''))
    __lowercase											=      binary_search(collection, target)
    if result is None:
        print(F'{target} was not found in {collection}.')
    else:
        print(F'{target} was found at position {result} in {collection}.')





