






'''simple docstring'''



from __future__ import annotations

SCREAMING_SNAKE_CASE							=						list[tuple[int, int]]

SCREAMING_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],
]

SCREAMING_SNAKE_CASE							=						([-1, 0], [0, -1], [1, 0], [0, 1])  # up, left, down, right
class UpperCAmelCase_       :




      """simple docstring"""




      def __init__(			self      :		Optional[Any]  ,   UpperCAmelCase      :		int  ,   UpperCAmelCase      :		int  ,   UpperCAmelCase      :		int  ,   UpperCAmelCase      :		int  ,   UpperCAmelCase      :		float  ,   UpperCAmelCase      :		Node | None  ,   )	->	List[str]:


       '''simple docstring'''

       lowercase       : Dict						=pos_x
       lowercase       : Any						=pos_y
       lowercase       : Optional[Any]						=(pos_y, pos_x)
       lowercase       : Tuple						=goal_x
       lowercase       : Union[str, Any]						=goal_y
       lowercase       : Union[str, Any]						=g_cost
       lowercase       : str						=parent
       lowercase       : List[Any]						=self.calculate_heuristic()






      def 					A__   (			self      :		int		)	->	float:


       '''simple docstring'''

       lowercase       : List[str]						=abs(self.pos_x - self.goal_x		)
       lowercase       : List[Any]						=abs(self.pos_y - self.goal_y		)
       return dx + dy






      def __lt__(			self      :		Tuple  ,   UpperCAmelCase      :		Tuple		)	->	bool:


       '''simple docstring'''

       return self.f_cost < other.f_cost





class UpperCAmelCase_       :




      """simple docstring"""




      def __init__(			self      :		Tuple  ,   UpperCAmelCase      :		tuple[int, int]  ,   UpperCAmelCase      :		tuple[int, int]		)	->	Optional[Any]:


       '''simple docstring'''

       lowercase       : Tuple						=Node(start[1]  ,   start[0]  ,   goal[1]  ,   goal[0]  ,   0  ,   UpperCAmelCase		)
       lowercase       : int						=Node(goal[1]  ,   goal[0]  ,   goal[1]  ,   goal[0]  ,   9_9999  ,   UpperCAmelCase		)

       lowercase       : str						=[self.start]
       lowercase       : list[Node]						=[]

       lowercase       : Tuple						=False






      def 					A__   (			self      :		Union[str, Any]		)	->	Path | None:


       '''simple docstring'''

       while self.open_nodes:
        # Open Nodes are sorted using __lt__
        self.open_nodes.sort()
        lowercase       : Union[str, Any]						=self.open_nodes.pop(0		)

        if current_node.pos == self.target.pos:
         lowercase       : List[str]						=True
         return self.retrace_path(UpperCAmelCase		)

        self.closed_nodes.append(UpperCAmelCase		)
        lowercase       : Dict						=self.get_successors(UpperCAmelCase		)

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

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

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






      def 					A__   (			self      :		Optional[int]  ,   UpperCAmelCase      :		Node		)	->	list[Node]:


       '''simple docstring'''

       lowercase       : int						=[]
       for action in delta:
        lowercase       : List[Any]						=parent.pos_x + action[1]
        lowercase       : Optional[Any]						=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  ,   parent.g_cost + 1  ,   UpperCAmelCase  ,   )		)
       return successors






      def 					A__   (			self      :		int  ,   UpperCAmelCase      :		Node | None		)	->	Path:


       '''simple docstring'''

       lowercase       : Optional[Any]						=node
       lowercase       : int						=[]
       while current_node is not None:
        path.append((current_node.pos_y, current_node.pos_x)		)
        lowercase       : Any						=current_node.parent
       path.reverse()
       return path


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

      print('------')

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

            for elem in grid:
                  print(elem)











'''simple docstring'''



from unittest import TestCase

from datasets import Sequence, Value
from datasets.arrow_dataset import Dataset
class UpperCAmelCase_       (     __A					):




      """simple docstring"""




      def 					A__   (			self      :		Optional[int]		)	->	List[str]:


       '''simple docstring'''

       return [
           {"col_1": 3, "col_2": "a"},
           {"col_1": 2, "col_2": "b"},
           {"col_1": 1, "col_2": "c"},
           {"col_1": 0, "col_2": "d"},
       ]






      def 					A__   (			self      :		Any		)	->	List[str]:


       '''simple docstring'''

       lowercase       : List[str]						={'''col_1''': [3, 2, 1, 0], '''col_2''': ['''a''', '''b''', '''c''', '''d''']}
       return Dataset.from_dict(UpperCAmelCase		)






      def 					A__   (			self      :		Any		)	->	Tuple:


       '''simple docstring'''

       lowercase       : Tuple						=self._create_example_records()
       lowercase       : Tuple						=Dataset.from_list(UpperCAmelCase		)
       self.assertListEqual(dset.column_names  ,   ['''col_1''', '''col_2''']		)
       for i, r in enumerate(UpperCAmelCase		):
        self.assertDictEqual(UpperCAmelCase  ,   example_records[i]		)






      def 					A__   (			self      :		Dict		)	->	List[str]:


       '''simple docstring'''

       lowercase       : Optional[Any]						=self._create_example_records()
       lowercase       : Union[str, Any]						=Dataset.from_list(UpperCAmelCase		)
       lowercase       : Tuple						=Dataset.from_dict({k: [r[k] for r in example_records] for k in example_records[0]}		)
       self.assertEqual(dset.info  ,   dset_from_dict.info		)






      def 					A__   (			self      :		str		)	->	List[Any]:  # checks what happens with missing columns


       '''simple docstring'''

       lowercase       : Tuple						=[{'''col_1''': 1}, {'''col_2''': '''x'''}]
       lowercase       : Optional[Any]						=Dataset.from_list(UpperCAmelCase		)
       self.assertDictEqual(dset[0]  ,   {'''col_1''': 1}		)
       self.assertDictEqual(dset[1]  ,   {'''col_1''': None}		)  # NB: first record is used for columns






      def 					A__   (			self      :		List[Any]		)	->	int:  # checks if the type can be inferred from the second record


       '''simple docstring'''

       lowercase       : List[Any]						=[{'''col_1''': []}, {'''col_1''': [1, 2]}]
       lowercase       : Union[str, Any]						=Dataset.from_list(UpperCAmelCase		)
       self.assertEqual(dset.info.features['''col_1''']  ,   Sequence(Value('''int64'''		)		)		)






      def 					A__   (			self      :		int		)	->	str:


       '''simple docstring'''

       lowercase       : List[str]						=Dataset.from_list([]		)
       self.assertEqual(len(UpperCAmelCase		)  ,   0		)
       self.assertListEqual(dset.column_names  ,   []		)



