



"""simple docstring"""







from __future__ import annotations

lowercase__		:				List[Any]          =	[
    [-1, 0],  # left
    [0, -1],  # down
    [1, 0],  # right
    [0, 1],  # up
]

def 				UpperCamelCase_    (    lowerCAmelCase__      :				list[list[int]]    ,   lowerCAmelCase__      :				list[int]    ,   lowerCAmelCase__      :				list[int]    ,   lowerCAmelCase__      :				int    ,   lowerCAmelCase__      :				list[list[int]]    ,   )						->   tuple[list[list[int]], list[list[int]]]:

  """simple docstring"""




  lowerCAmelCase_   :				List[Any]								= [
      [0 for col in range(len(grid[0]						)						)] for row in range(len(lowerCAmelCase__						)						)
  ]  # the reference grid
  lowerCAmelCase_   :				Any								= 1
  lowerCAmelCase_   :				Any								= [
      [0 for col in range(len(grid[0]						)						)] for row in range(len(lowerCAmelCase__						)						)
  ]  # the action grid

  lowerCAmelCase_   :				Tuple								= init[0]
  lowerCAmelCase_   :				Dict								= init[1]
  lowerCAmelCase_   :				str								= 0
  lowerCAmelCase_   :				List[Any]								= g + heuristic[x][y]  # cost from starting cell to destination cell
  lowerCAmelCase_   :				Any								= [[f, g, x, y]]

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

  while not found and not resign:
    if len(lowerCAmelCase__						) == 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()
      lowerCAmelCase_   :				Dict								= cell.pop()
      lowerCAmelCase_   :				str								= next_cell[2]
      lowerCAmelCase_   :				str								= next_cell[3]
      lowerCAmelCase_   :				Optional[Any]								= next_cell[1]

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

  lowerCAmelCase_   :				List[str]								= []
  for i in range(len(lowerCAmelCase__						)						):
    path.append(invpath[len(lowerCAmelCase__						) - 1 - i]						)
  return path, action


if __name__ == "__main__":
     lowercase__		:				Optional[int]          =	[
         [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],
     ]

     lowercase__		:				Union[str, Any]          =	[0, 0]
     # all coordinates are given in format [y,x]
     lowercase__		:				int          =	[len(grid) - 1, len(grid[0]) - 1]
     lowercase__		:				Optional[Any]          =	1

     # the cost map which pushes the path closer to the goal
     lowercase__		:				Union[str, Any]          =	[[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])):
               lowercase__		:				str          =	abs(i - goal[0]) + abs(j - goal[1])
               if grid[i][j] == 1:
                    # added extra penalty in the heuristic map
                    lowercase__		:				str          =	9_9

     lowercase__    ,     lowercase__		:				List[str]          =	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"""







from dataclasses import dataclass, field
from typing import ClassVar, Dict

from ..features import Features, Value
from .base import TaskTemplate







@dataclass(frozen=lowercase_  )
class       UpperCamelCase__   (	lowercase_  ):




      """simple docstring"""




      _SCREAMING_SNAKE_CASE  				=     field(default="""summarization""",					metadata={"""include_in_asdict_even_if_is_default""": True}  )
      _SCREAMING_SNAKE_CASE  				=     Features({"""text""": Value("""string"""  )}  )
      _SCREAMING_SNAKE_CASE  				=     Features({"""summary""": Value("""string"""  )}  )
      _SCREAMING_SNAKE_CASE  				=     "text"
      _SCREAMING_SNAKE_CASE  				=     "summary"



      @property
      def      SCREAMING_SNAKE_CASE__ (      self				:      Dict       ):
        return {self.text_column: "text", self.summary_column: "summary"}





