"""simple docstring"""


from __future__ import annotations

__UpperCamelCase									=			list[tuple[int, int]]

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

__UpperCamelCase									=			([-1, 0], [0, -1], [1, 0], [0, 1])  # up, left, down, right




class  UpperCamelCase					:







       def __init__( self,							lowerCAmelCase__,							lowerCAmelCase__,							lowerCAmelCase__,							lowerCAmelCase__,							lowerCAmelCase__,							lowerCAmelCase__,							)      ->      Optional[Any]:
            snake_case_					       =					pos_x
            snake_case_					       =					pos_y
            snake_case_					       =					(pos_y, pos_x)
            snake_case_					       =					goal_x
            snake_case_					       =					goal_y
            snake_case_					       =					g_cost
            snake_case_					       =					parent
            snake_case_					       =					self.calculate_heuristic()







       def 		a_						( self)      ->      float:
            snake_case_					       =					abs(self.pos_x - self.goal_x)
            snake_case_					       =					abs(self.pos_y - self.goal_y)
            return dx + dy







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




class  UpperCamelCase					:







       def __init__( self,							lowerCAmelCase__,							lowerCAmelCase__)      ->      Dict:
            snake_case_					       =					Node(start[1],							start[0],							goal[1],							goal[0],							0,							lowerCAmelCase__)
            snake_case_					       =					Node(goal[1],							goal[0],							goal[1],							goal[0],							9_9999,							lowerCAmelCase__)

            snake_case_					       =					[self.start]
            snake_case_					       =					[]

            snake_case_					       =					False







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

                 if current_node.pos == self.target.pos:
                      snake_case_					       =					True
                      return self.retrace_path(lowerCAmelCase__)

                 self.closed_nodes.append(lowerCAmelCase__)
                 snake_case_					       =					self.get_successors(lowerCAmelCase__)

                 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(lowerCAmelCase__)
                      else:
                           # retrieve the best current path
                           snake_case_					       =					self.open_nodes.pop(self.open_nodes.index(lowerCAmelCase__))

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

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







       def 		a_						( self,							lowerCAmelCase__)      ->      list[Node]:
            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,							parent.g_cost + 1,							lowerCAmelCase__,							))
            return successors







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


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

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

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

        for elem in grid:
            print(elem)








'''simple docstring'''


def 							UpperCAmelCase_  (						__lowerCamelCase					:					int	,__lowerCamelCase					:					int ):
   return int((input_a, input_a).count(0 ) == 0 )
def 							UpperCAmelCase_  (						):
   assert and_gate(0	,0 ) == 0
   assert and_gate(0	,1 ) == 0
   assert and_gate(1	,0 ) == 0
   assert and_gate(1	,1 ) == 1


if __name__ == "__main__":
 test_and_gate()
 print(and_gate(1, 0))
 print(and_gate(0, 0))
 print(and_gate(0, 1))
 print(and_gate(1, 1))


