


from __future__ import annotations

__UpperCamelCase    :						Optional[Any]     =							list[tuple[int, int]]

__UpperCamelCase    :						Optional[Any]     =							[
    [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    :						Optional[Any]     =							([-1, 0], [0, -1], [1, 0], [0, 1])  # up, left, down, right



class 							_UpperCamelCase :

   '''simple docstring'''







   def __init__(  self  : Optional[Any]       ,  _lowerCamelCase  : int       ,  _lowerCamelCase  : int       ,  _lowerCamelCase  : int       ,  _lowerCamelCase  : int       ,  _lowerCamelCase  : float       ,  _lowerCamelCase  : Node | None       ,  ):






         '''simple docstring'''



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

   def   _snake_case    (  self  : Optional[int]							):






         '''simple docstring'''



         __lowerCamelCase     :      str       						=						abs(self.pos_x - self.goal_x							)
         __lowerCamelCase     :      Optional[int]       						=						abs(self.pos_y - self.goal_y							)
         return dx + dy


   def __lt__(  self  : Optional[int]       ,  _lowerCamelCase  : Tuple							):






         '''simple docstring'''



         return self.f_cost < other.f_cost



class 							_UpperCamelCase :

   '''simple docstring'''







   def __init__(  self  : Any       ,  _lowerCamelCase  : tuple[int, int]       ,  _lowerCamelCase  : tuple[int, int]							):






         '''simple docstring'''



         __lowerCamelCase     :      List[Any]       						=						Node(start[1]       ,  start[0]       ,  goal[1]       ,  goal[0]       ,  0       ,  _lowerCamelCase							)
         __lowerCamelCase     :      Optional[int]       						=						Node(goal[1]       ,  goal[0]       ,  goal[1]       ,  goal[0]       ,  9_9_9_9_9       ,  _lowerCamelCase							)

         __lowerCamelCase     :      int       						=						[self.start]
         __lowerCamelCase     :      list[Node]       						=						[]

         __lowerCamelCase     :      List[str]       						=						False

   def   _snake_case    (  self  : str							):






         '''simple docstring'''



         while self.open_nodes:
               # Open Nodes are sorted using __lt__
               self.open_nodes.sort()
               __lowerCamelCase     :      Optional[Any]       						=						self.open_nodes.pop(0							)

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

               self.closed_nodes.append(_lowerCamelCase							)
               __lowerCamelCase     :      Any       						=						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
                           __lowerCamelCase     :      int       						=						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   _snake_case    (  self  : str       ,  _lowerCamelCase  : Node							):






         '''simple docstring'''



         __lowerCamelCase     :      str       						=						[]
         for action in delta:
               __lowerCamelCase     :      List[str]       						=						parent.pos_x + action[1]
               __lowerCamelCase     :      Tuple       						=						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   _snake_case    (  self  : Dict       ,  _lowerCamelCase  : Node | None							):






         '''simple docstring'''



         __lowerCamelCase     :      Union[str, Any]       						=						node
         __lowerCamelCase     :      Dict       						=						[]
         while current_node is not None:
               path.append((current_node.pos_y, current_node.pos_x)							)
               __lowerCamelCase     :      Dict       						=						current_node.parent
         path.reverse()
         return path


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

    print('------')

    __UpperCamelCase    :						Optional[int]     =							GreedyBestFirst(init, goal)
    __UpperCamelCase    :						List[Any]     =							greedy_bf.search()
    if path:
        for pos_x, pos_y in path:
            __UpperCamelCase    :						Optional[Any]     =							2

        for elem in grid:
            print(elem)







import json
from typing import Iterator, List, Union

from tokenizers import AddedToken, Regex, Tokenizer, decoders, normalizers, pre_tokenizers, trainers
from tokenizers.implementations.base_tokenizer import BaseTokenizer
from tokenizers.models import Unigram
from tokenizers.processors import TemplateProcessing



class 							_UpperCamelCase (						A						):

   '''simple docstring'''







   def __init__(  self  : str       ,  _lowerCamelCase  : str = "▁"       ,  _lowerCamelCase  : bool = True       ,  _lowerCamelCase  : Union[str, AddedToken] = "<unk>"       ,  _lowerCamelCase  : Union[str, AddedToken] = "</s>"       ,  _lowerCamelCase  : Union[str, AddedToken] = "<pad>"       ,  ):






         '''simple docstring'''



         __lowerCamelCase     :      Tuple       						=						{
             """pad""": {"""id""": 0, """token""": pad_token},
             """eos""": {"""id""": 1, """token""": eos_token},
             """unk""": {"""id""": 2, """token""": unk_token},
         }

         __lowerCamelCase     :      Optional[Any]       						=						[None] * len(self.special_tokens							)
         for token_dict in self.special_tokens.values():
               __lowerCamelCase     :      Tuple       						=						token_dict["""token"""]

         __lowerCamelCase     :      Optional[int]       						=						Tokenizer(Unigram()							)

         __lowerCamelCase     :      str       						=						normalizers.Sequence(
             [
                 normalizers.Nmt(),
                 normalizers.NFKC(),
                 normalizers.Replace(Regex(""" {2,}"""							)       ,  """ """							),
                 normalizers.Lowercase(),
             ]							)
         __lowerCamelCase     :      int       						=						pre_tokenizers.Sequence(
             [
                 pre_tokenizers.Metaspace(replacement=_lowerCamelCase       ,  add_prefix_space=_lowerCamelCase							),
                 pre_tokenizers.Digits(individual_digits=_lowerCamelCase							),
                 pre_tokenizers.Punctuation(),
             ]							)
         __lowerCamelCase     :      Tuple       						=						decoders.Metaspace(replacement=_lowerCamelCase       ,  add_prefix_space=_lowerCamelCase							)

         __lowerCamelCase     :      Tuple       						=						TemplateProcessing(
             single=F"""$A {self.special_tokens["eos"]["token"]}"""       ,  special_tokens=[(self.special_tokens["""eos"""]["""token"""], self.special_tokens["""eos"""]["""id"""])]       ,  )

         __lowerCamelCase     :      Tuple       						=						{
             """model""": """SentencePieceUnigram""",
             """replacement""": replacement,
             """add_prefix_space""": add_prefix_space,
         }

         super().__init__(_lowerCamelCase       ,  _lowerCamelCase							)

   def   _snake_case    (  self  : Dict       ,  _lowerCamelCase  : Union[str, List[str]]       ,  _lowerCamelCase  : int = 8_0_0_0       ,  _lowerCamelCase  : bool = True       ,  ):






         '''simple docstring'''



         __lowerCamelCase     :      Optional[Any]       						=						trainers.UnigramTrainer(
             vocab_size=_lowerCamelCase       ,  special_tokens=self.special_tokens_list       ,  show_progress=_lowerCamelCase       ,  )

         if isinstance(_lowerCamelCase       ,  _lowerCamelCase							):
               __lowerCamelCase     :      Optional[int]       						=						[files]
         self._tokenizer.train(_lowerCamelCase       ,  trainer=_lowerCamelCase							)

         self.add_unk_id()

   def   _snake_case    (  self  : List[Any]       ,  _lowerCamelCase  : Union[Iterator[str], Iterator[Iterator[str]]]       ,  _lowerCamelCase  : int = 8_0_0_0       ,  _lowerCamelCase  : bool = True       ,  ):






         '''simple docstring'''



         __lowerCamelCase     :      Any       						=						trainers.UnigramTrainer(
             vocab_size=_lowerCamelCase       ,  special_tokens=self.special_tokens_list       ,  show_progress=_lowerCamelCase       ,  )

         self._tokenizer.train_from_iterator(_lowerCamelCase       ,  trainer=_lowerCamelCase							)

         self.add_unk_id()


   def   _snake_case    (  self  : List[str]							):






         '''simple docstring'''



         __lowerCamelCase     :      List[str]       						=						json.loads(self._tokenizer.to_str()							)

         __lowerCamelCase     :      Optional[int]       						=						self.special_tokens["""unk"""]["""id"""]

         __lowerCamelCase     :      List[str]       						=						Tokenizer.from_str(json.dumps(_lowerCamelCase							)							)



