

"""simple docstring"""






from __future__ import annotations

_lowerCAmelCase						=		list[tuple[int, int]]

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

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







class 	__UpperCamelCase    :

  def __init__(		self    ,_A    ,_A    ,_A    ,_A    ,_A    ,_A    ,):
      '''simple docstring'''

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

  def __lowerCamelCase		(		self      ):
      '''simple docstring'''

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







  def __lt__(		self    ,_A      ):
      '''simple docstring'''

      return self.f_cost < other.f_cost







class 	__UpperCamelCase    :

  def __init__(		self    ,_A    ,_A      ):
      '''simple docstring'''

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

      _lowerCAmelCase       :   List[str]  =    [self.start]
      _lowerCAmelCase       :   list[Node]  =    []

      _lowerCAmelCase       :   Union[str, Any]  =    False

  def __lowerCamelCase		(		self      ):
      '''simple docstring'''

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

          if current_node.pos == self.target.pos:
              _lowerCAmelCase       :   Any  =    True
              return self.retrace_path(_A      )

          self.closed_nodes.append(_A      )
          _lowerCAmelCase       :   Dict  =    self.get_successors(_A      )

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

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

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

  def __lowerCamelCase		(		self    ,_A      ):
      '''simple docstring'''

      _lowerCAmelCase       :   List[Any]  =    []
      for action in delta:
          _lowerCAmelCase       :   List[str]  =    parent.pos_x + action[1]
          _lowerCAmelCase       :   Union[str, Any]  =    parent.pos_y + action[0]

          if not (0 <= pos_x <= len(grid[0]      ) - 1 and 0 <= pos_y <= len(_A      ) - 1):
              continue

          if grid[pos_y][pos_x] != 0:
              continue

          successors.append(
              Node(
                  _A    ,_A    ,self.target.pos_y    ,self.target.pos_x    ,parent.g_cost + 1    ,_A    ,)      )
      return successors







  def __lowerCamelCase		(		self    ,_A      ):
      '''simple docstring'''

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


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

 print("""------""")

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

  for elem in grid:
   print(elem)








"""simple docstring"""






import json
from typing import List, Optional, Tuple

from tokenizers import normalizers

from ...tokenization_utils_fast import PreTrainedTokenizerFast
from ...utils import logging
from .tokenization_bert import BertTokenizer


_lowerCAmelCase						=		logging.get_logger(__name__)

_lowerCAmelCase						=		{"""vocab_file""": """vocab.txt""", """tokenizer_file""": """tokenizer.json"""}

_lowerCAmelCase						=		{
    """vocab_file""": {
        """bert-base-uncased""": """https://huggingface.co/bert-base-uncased/resolve/main/vocab.txt""",
        """bert-large-uncased""": """https://huggingface.co/bert-large-uncased/resolve/main/vocab.txt""",
        """bert-base-cased""": """https://huggingface.co/bert-base-cased/resolve/main/vocab.txt""",
        """bert-large-cased""": """https://huggingface.co/bert-large-cased/resolve/main/vocab.txt""",
        """bert-base-multilingual-uncased""": (
            """https://huggingface.co/bert-base-multilingual-uncased/resolve/main/vocab.txt"""
        ),
        """bert-base-multilingual-cased""": """https://huggingface.co/bert-base-multilingual-cased/resolve/main/vocab.txt""",
        """bert-base-chinese""": """https://huggingface.co/bert-base-chinese/resolve/main/vocab.txt""",
        """bert-base-german-cased""": """https://huggingface.co/bert-base-german-cased/resolve/main/vocab.txt""",
        """bert-large-uncased-whole-word-masking""": (
            """https://huggingface.co/bert-large-uncased-whole-word-masking/resolve/main/vocab.txt"""
        ),
        """bert-large-cased-whole-word-masking""": (
            """https://huggingface.co/bert-large-cased-whole-word-masking/resolve/main/vocab.txt"""
        ),
        """bert-large-uncased-whole-word-masking-finetuned-squad""": (
            """https://huggingface.co/bert-large-uncased-whole-word-masking-finetuned-squad/resolve/main/vocab.txt"""
        ),
        """bert-large-cased-whole-word-masking-finetuned-squad""": (
            """https://huggingface.co/bert-large-cased-whole-word-masking-finetuned-squad/resolve/main/vocab.txt"""
        ),
        """bert-base-cased-finetuned-mrpc""": (
            """https://huggingface.co/bert-base-cased-finetuned-mrpc/resolve/main/vocab.txt"""
        ),
        """bert-base-german-dbmdz-cased""": """https://huggingface.co/bert-base-german-dbmdz-cased/resolve/main/vocab.txt""",
        """bert-base-german-dbmdz-uncased""": (
            """https://huggingface.co/bert-base-german-dbmdz-uncased/resolve/main/vocab.txt"""
        ),
        """TurkuNLP/bert-base-finnish-cased-v1""": (
            """https://huggingface.co/TurkuNLP/bert-base-finnish-cased-v1/resolve/main/vocab.txt"""
        ),
        """TurkuNLP/bert-base-finnish-uncased-v1""": (
            """https://huggingface.co/TurkuNLP/bert-base-finnish-uncased-v1/resolve/main/vocab.txt"""
        ),
        """wietsedv/bert-base-dutch-cased""": (
            """https://huggingface.co/wietsedv/bert-base-dutch-cased/resolve/main/vocab.txt"""
        ),
    },
    """tokenizer_file""": {
        """bert-base-uncased""": """https://huggingface.co/bert-base-uncased/resolve/main/tokenizer.json""",
        """bert-large-uncased""": """https://huggingface.co/bert-large-uncased/resolve/main/tokenizer.json""",
        """bert-base-cased""": """https://huggingface.co/bert-base-cased/resolve/main/tokenizer.json""",
        """bert-large-cased""": """https://huggingface.co/bert-large-cased/resolve/main/tokenizer.json""",
        """bert-base-multilingual-uncased""": (
            """https://huggingface.co/bert-base-multilingual-uncased/resolve/main/tokenizer.json"""
        ),
        """bert-base-multilingual-cased""": (
            """https://huggingface.co/bert-base-multilingual-cased/resolve/main/tokenizer.json"""
        ),
        """bert-base-chinese""": """https://huggingface.co/bert-base-chinese/resolve/main/tokenizer.json""",
        """bert-base-german-cased""": """https://huggingface.co/bert-base-german-cased/resolve/main/tokenizer.json""",
        """bert-large-uncased-whole-word-masking""": (
            """https://huggingface.co/bert-large-uncased-whole-word-masking/resolve/main/tokenizer.json"""
        ),
        """bert-large-cased-whole-word-masking""": (
            """https://huggingface.co/bert-large-cased-whole-word-masking/resolve/main/tokenizer.json"""
        ),
        """bert-large-uncased-whole-word-masking-finetuned-squad""": (
            """https://huggingface.co/bert-large-uncased-whole-word-masking-finetuned-squad/resolve/main/tokenizer.json"""
        ),
        """bert-large-cased-whole-word-masking-finetuned-squad""": (
            """https://huggingface.co/bert-large-cased-whole-word-masking-finetuned-squad/resolve/main/tokenizer.json"""
        ),
        """bert-base-cased-finetuned-mrpc""": (
            """https://huggingface.co/bert-base-cased-finetuned-mrpc/resolve/main/tokenizer.json"""
        ),
        """bert-base-german-dbmdz-cased""": (
            """https://huggingface.co/bert-base-german-dbmdz-cased/resolve/main/tokenizer.json"""
        ),
        """bert-base-german-dbmdz-uncased""": (
            """https://huggingface.co/bert-base-german-dbmdz-uncased/resolve/main/tokenizer.json"""
        ),
        """TurkuNLP/bert-base-finnish-cased-v1""": (
            """https://huggingface.co/TurkuNLP/bert-base-finnish-cased-v1/resolve/main/tokenizer.json"""
        ),
        """TurkuNLP/bert-base-finnish-uncased-v1""": (
            """https://huggingface.co/TurkuNLP/bert-base-finnish-uncased-v1/resolve/main/tokenizer.json"""
        ),
        """wietsedv/bert-base-dutch-cased""": (
            """https://huggingface.co/wietsedv/bert-base-dutch-cased/resolve/main/tokenizer.json"""
        ),
    },
}

_lowerCAmelCase						=		{
    """bert-base-uncased""": 5_1_2,
    """bert-large-uncased""": 5_1_2,
    """bert-base-cased""": 5_1_2,
    """bert-large-cased""": 5_1_2,
    """bert-base-multilingual-uncased""": 5_1_2,
    """bert-base-multilingual-cased""": 5_1_2,
    """bert-base-chinese""": 5_1_2,
    """bert-base-german-cased""": 5_1_2,
    """bert-large-uncased-whole-word-masking""": 5_1_2,
    """bert-large-cased-whole-word-masking""": 5_1_2,
    """bert-large-uncased-whole-word-masking-finetuned-squad""": 5_1_2,
    """bert-large-cased-whole-word-masking-finetuned-squad""": 5_1_2,
    """bert-base-cased-finetuned-mrpc""": 5_1_2,
    """bert-base-german-dbmdz-cased""": 5_1_2,
    """bert-base-german-dbmdz-uncased""": 5_1_2,
    """TurkuNLP/bert-base-finnish-cased-v1""": 5_1_2,
    """TurkuNLP/bert-base-finnish-uncased-v1""": 5_1_2,
    """wietsedv/bert-base-dutch-cased""": 5_1_2,
}

_lowerCAmelCase						=		{
    """bert-base-uncased""": {"""do_lower_case""": True},
    """bert-large-uncased""": {"""do_lower_case""": True},
    """bert-base-cased""": {"""do_lower_case""": False},
    """bert-large-cased""": {"""do_lower_case""": False},
    """bert-base-multilingual-uncased""": {"""do_lower_case""": True},
    """bert-base-multilingual-cased""": {"""do_lower_case""": False},
    """bert-base-chinese""": {"""do_lower_case""": False},
    """bert-base-german-cased""": {"""do_lower_case""": False},
    """bert-large-uncased-whole-word-masking""": {"""do_lower_case""": True},
    """bert-large-cased-whole-word-masking""": {"""do_lower_case""": False},
    """bert-large-uncased-whole-word-masking-finetuned-squad""": {"""do_lower_case""": True},
    """bert-large-cased-whole-word-masking-finetuned-squad""": {"""do_lower_case""": False},
    """bert-base-cased-finetuned-mrpc""": {"""do_lower_case""": False},
    """bert-base-german-dbmdz-cased""": {"""do_lower_case""": False},
    """bert-base-german-dbmdz-uncased""": {"""do_lower_case""": True},
    """TurkuNLP/bert-base-finnish-cased-v1""": {"""do_lower_case""": False},
    """TurkuNLP/bert-base-finnish-uncased-v1""": {"""do_lower_case""": True},
    """wietsedv/bert-base-dutch-cased""": {"""do_lower_case""": False},
}







class 	__UpperCamelCase    (    a__						):
  _UpperCAmelCase          =		VOCAB_FILES_NAMES
  _UpperCAmelCase          =		PRETRAINED_VOCAB_FILES_MAP
  _UpperCAmelCase          =		PRETRAINED_INIT_CONFIGURATION
  _UpperCAmelCase          =		PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
  _UpperCAmelCase          =		BertTokenizer

  def __init__(		self    ,_A=None    ,_A=None    ,_A=True    ,_A="[UNK]"    ,_A="[SEP]"    ,_A="[PAD]"    ,_A="[CLS]"    ,_A="[MASK]"    ,_A=True    ,_A=None    ,**_A    ,):
      '''simple docstring'''

      super().__init__(
          _A    ,tokenizer_file=_A    ,do_lower_case=_A    ,unk_token=_A    ,sep_token=_A    ,pad_token=_A    ,cls_token=_A    ,mask_token=_A    ,tokenize_chinese_chars=_A    ,strip_accents=_A    ,**_A    ,)

      _lowerCAmelCase       :   Tuple  =    json.loads(self.backend_tokenizer.normalizer.__getstate__()      )
      if (
          normalizer_state.get('lowercase'    ,_A      ) != do_lower_case
          or normalizer_state.get('strip_accents'    ,_A      ) != strip_accents
          or normalizer_state.get('handle_chinese_chars'    ,_A      ) != tokenize_chinese_chars
      ):
          _lowerCAmelCase       :   Dict  =    getattr(_A    ,normalizer_state.pop('type'      )      )
          _lowerCAmelCase       :   Dict  =    do_lower_case
          _lowerCAmelCase       :   Optional[int]  =    strip_accents
          _lowerCAmelCase       :   Union[str, Any]  =    tokenize_chinese_chars
          _lowerCAmelCase       :   Dict  =    normalizer_class(**_A      )

      _lowerCAmelCase       :   Union[str, Any]  =    do_lower_case

  def __lowerCamelCase		(		self    ,_A    ,_A=None      ):
      '''simple docstring'''

      _lowerCAmelCase       :   Tuple  =    [self.cls_token_id] + token_ids_a + [self.sep_token_id]

      if token_ids_a:
          output += token_ids_a + [self.sep_token_id]

      return output

  def __lowerCamelCase		(		self    ,_A    ,_A = None      ):
      '''simple docstring'''

      _lowerCAmelCase       :   Union[str, Any]  =    [self.sep_token_id]
      _lowerCAmelCase       :   str  =    [self.cls_token_id]
      if token_ids_a is None:
          return len(cls + token_ids_a + sep      ) * [0]
      return len(cls + token_ids_a + sep      ) * [0] + len(token_ids_a + sep      ) * [1]







  def __lowerCamelCase		(		self    ,_A    ,_A = None      ):
      '''simple docstring'''

      _lowerCAmelCase       :   str  =    self._tokenizer.model.save(_A    ,name=_A      )
      return tuple(_A      )





