




'''simple docstring'''



from __future__ import annotations

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




def   lowercase__(			__UpperCamelCase:					list[list[int]]      ,__UpperCamelCase:					list[int]      ,__UpperCamelCase:					list[int]      ,__UpperCamelCase:					int      ,__UpperCamelCase:					list[list[int]]      ,):

      """simple docstring"""






      SCREAMING_SNAKE_CASE   :      Union[str, Any]    					=						[
          [0 for col in range(len(grid[0]    )    )] for row in range(len(__UpperCamelCase    )    )
      ]  # the reference grid
      SCREAMING_SNAKE_CASE   :      int    					=						1
      SCREAMING_SNAKE_CASE   :      Union[str, Any]    					=						[
          [0 for col in range(len(grid[0]    )    )] for row in range(len(__UpperCamelCase    )    )
      ]  # the action grid

      SCREAMING_SNAKE_CASE   :      Tuple    					=						init[0]
      SCREAMING_SNAKE_CASE   :      Optional[Any]    					=						init[1]
      SCREAMING_SNAKE_CASE   :      Union[str, Any]    					=						0
      SCREAMING_SNAKE_CASE   :      Optional[Any]    					=						g + heuristic[x][y]  # cost from starting cell to destination cell
      SCREAMING_SNAKE_CASE   :      int    					=						[[f, g, x, y]]

      SCREAMING_SNAKE_CASE   :      List[str]    					=						False  # flag that is set when search is complete
      SCREAMING_SNAKE_CASE   :      Dict    					=						False  # flag set if we can't find expand

      while not found and not resign:
            if len(__UpperCamelCase    ) == 0:
                  raise ValueError('Algorithm is unable to find solution'    )
            else:  # to choose the least costliest action so as to move closer to the goal
                  cell.sort()
                  cell.reverse()
                  SCREAMING_SNAKE_CASE   :      List[Any]    					=						cell.pop()
                  SCREAMING_SNAKE_CASE   :      List[str]    					=						next_cell[2]
                  SCREAMING_SNAKE_CASE   :      Dict    					=						next_cell[3]
                  SCREAMING_SNAKE_CASE   :      Optional[Any]    					=						next_cell[1]

                  if x == goal[0] and y == goal[1]:
                        SCREAMING_SNAKE_CASE   :      Union[str, Any]    					=						True
                  else:
                        for i in range(len(__UpperCamelCase    )    ):  # to try out different valid actions
                              SCREAMING_SNAKE_CASE   :      Tuple    					=						x + DIRECTIONS[i][0]
                              SCREAMING_SNAKE_CASE   :      Union[str, Any]    					=						y + DIRECTIONS[i][1]
                              if xa >= 0 and xa < len(__UpperCamelCase    ) and ya >= 0 and ya < len(grid[0]    ):
                                    if closed[xa][ya] == 0 and grid[xa][ya] == 0:
                                          SCREAMING_SNAKE_CASE   :      List[Any]    					=						g + cost
                                          SCREAMING_SNAKE_CASE   :      Union[str, Any]    					=						ga + heuristic[xa][ya]
                                          cell.append([fa, ga, xa, ya]    )
                                          SCREAMING_SNAKE_CASE   :      int    					=						1
                                          SCREAMING_SNAKE_CASE   :      Union[str, Any]    					=						i
      SCREAMING_SNAKE_CASE   :      List[str]    					=						[]
      SCREAMING_SNAKE_CASE   :      str    					=						goal[0]
      SCREAMING_SNAKE_CASE   :      List[Any]    					=						goal[1]
      invpath.append([x, y]    )  # we get the reverse path from here
      while x != init[0] or y != init[1]:
            SCREAMING_SNAKE_CASE   :      Union[str, Any]    					=						x - DIRECTIONS[action[x][y]][0]
            SCREAMING_SNAKE_CASE   :      Optional[Any]    					=						y - DIRECTIONS[action[x][y]][1]
            SCREAMING_SNAKE_CASE   :      Optional[Any]    					=						xa
            SCREAMING_SNAKE_CASE   :      Dict    					=						ya
            invpath.append([x, y]    )

      SCREAMING_SNAKE_CASE   :      int    					=						[]
      for i in range(len(__UpperCamelCase    )    ):
            path.append(invpath[len(__UpperCamelCase    ) - 1 - i]    )
      return path, action


if __name__ == "__main__":
      UpperCamelCase_    	=				[
          [0, 1, 0, 0, 0, 0],
          [0, 1, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
          [0, 1, 0, 0, 0, 0],
          [0, 1, 0, 0, 1, 0],
          [0, 0, 0, 0, 1, 0],
      ]

      UpperCamelCase_    	=				[0, 0]
      # all coordinates are given in format [y,x]
      UpperCamelCase_    	=				[len(grid) - 1, len(grid[0]) - 1]
      UpperCamelCase_    	=				1

      # the cost map which pushes the path closer to the goal
      UpperCamelCase_    	=				[[0 for row in range(len(grid[0]))] for col in range(len(grid))]
      for i in range(len(grid)):
            for j in range(len(grid[0])):
                  UpperCamelCase_    	=				abs(i - goal[0]) + abs(j - goal[1])
                  if grid[i][j] == 1:
                        # added extra penalty in the heuristic map
                        UpperCamelCase_    	=				9_9

      UpperCamelCase_	,    UpperCamelCase_    	=				search(grid, init, goal, cost, heuristic)

      print("ACTION MAP")
      for i in range(len(action)):
            print(action[i])

      for i in range(len(path)):
            print(path[i])








'''simple docstring'''



def   lowercase__(			__UpperCamelCase:					int    ):

      """simple docstring"""






      if not isinstance(__UpperCamelCase      ,__UpperCamelCase    ):
            raise TypeError('Input value must be an \'int\' type'    )

      SCREAMING_SNAKE_CASE   :      int    					=						0
      while number:
            position += 1
            number >>= 1

      return position


if __name__ == "__main__":
      import doctest

      doctest.testmod()


