




from __future__ import annotations

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




def 					__SCREAMING_SNAKE_CASE   (  lowercase_					,     lowercase_					,     lowercase_					,     lowercase_					,     lowercase_					,     )       ->	tuple[list[list[int]], list[list[int]]]:

    """simple docstring"""


    __UpperCamelCase  		=						[
        [0 for col in range(len(grid[0]      )      )] for row in range(len(lowercase_      )      )
    ]  # the reference grid
    __UpperCamelCase  		=						1
    __UpperCamelCase  		=						[
        [0 for col in range(len(grid[0]      )      )] for row in range(len(lowercase_      )      )
    ]  # the action grid

    __UpperCamelCase  		=						init[0]
    __UpperCamelCase  		=						init[1]
    __UpperCamelCase  		=						0
    __UpperCamelCase  		=						g + heuristic[x][y]  # cost from starting cell to destination cell
    __UpperCamelCase  		=						[[f, g, x, y]]

    __UpperCamelCase  		=						False  # flag that is set when search is complete
    __UpperCamelCase  		=						False  # flag set if we can't find expand

    while not found and not resign:
        if len(lowercase_      ) == 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()
            __UpperCamelCase  		=						cell.pop()
            __UpperCamelCase  		=						next_cell[2]
            __UpperCamelCase  		=						next_cell[3]
            __UpperCamelCase  		=						next_cell[1]

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

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


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

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

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

 a_		,    a_   		=     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])












import gc
import unittest

from transformers import CTRLConfig, is_torch_available
from transformers.testing_utils import require_torch, slow, torch_device

from ...generation.test_utils import GenerationTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
 import torch

 from transformers import (
     CTRL_PRETRAINED_MODEL_ARCHIVE_LIST,
     CTRLForSequenceClassification,
     CTRLLMHeadModel,
     CTRLModel,
 )

class  _lowerCamelCase						:

      """simple docstring"""

      def __init__(     self					: str ,       snake_case					: Any ,       snake_case					: str=14 ,       snake_case					: Dict=7 ,       snake_case					: Any=True ,       snake_case					: Any=True ,       snake_case					: str=True ,       snake_case					: List[str]=True ,       snake_case					: int=True ,       snake_case					: List[Any]=99 ,       snake_case					: Optional[int]=32 ,       snake_case					: str=5 ,       snake_case					: int=4 ,       snake_case					: str=37 ,       snake_case					: Union[str, Any]="gelu" ,       snake_case					: List[str]=0.1 ,       snake_case					: Optional[int]=0.1 ,       snake_case					: Tuple=512 ,       snake_case					: int=16 ,       snake_case					: Any=2 ,       snake_case					: List[str]=0.02 ,       snake_case					: List[Any]=3 ,       snake_case					: str=4 ,       snake_case					: Tuple=None ,       ):
          __UpperCamelCase  		=						parent
          __UpperCamelCase  		=						batch_size
          __UpperCamelCase  		=						seq_length
          __UpperCamelCase  		=						is_training
          __UpperCamelCase  		=						use_token_type_ids
          __UpperCamelCase  		=						use_input_mask
          __UpperCamelCase  		=						use_labels
          __UpperCamelCase  		=						use_mc_token_ids
          __UpperCamelCase  		=						vocab_size
          __UpperCamelCase  		=						hidden_size
          __UpperCamelCase  		=						num_hidden_layers
          __UpperCamelCase  		=						num_attention_heads
          __UpperCamelCase  		=						intermediate_size
          __UpperCamelCase  		=						hidden_act
          __UpperCamelCase  		=						hidden_dropout_prob
          __UpperCamelCase  		=						attention_probs_dropout_prob
          __UpperCamelCase  		=						max_position_embeddings
          __UpperCamelCase  		=						type_vocab_size
          __UpperCamelCase  		=						type_sequence_label_size
          __UpperCamelCase  		=						initializer_range
          __UpperCamelCase  		=						num_labels
          __UpperCamelCase  		=						num_choices
          __UpperCamelCase  		=						scope
          __UpperCamelCase  		=						self.vocab_size - 1







      def       snake_case	(     self					: Optional[Any]				):
          __UpperCamelCase  		=						ids_tensor([self.batch_size, self.seq_length] ,       self.vocab_size				)

          __UpperCamelCase  		=						None
          if self.use_input_mask:
              __UpperCamelCase  		=						random_attention_mask([self.batch_size, self.seq_length]				)

          __UpperCamelCase  		=						None
          if self.use_token_type_ids:
              __UpperCamelCase  		=						ids_tensor([self.batch_size, self.seq_length] ,       self.type_vocab_size				)

          __UpperCamelCase  		=						None
          if self.use_mc_token_ids:
              __UpperCamelCase  		=						ids_tensor([self.batch_size, self.num_choices] ,       self.seq_length				)

          __UpperCamelCase  		=						None
          __UpperCamelCase  		=						None
          __UpperCamelCase  		=						None
          if self.use_labels:
              __UpperCamelCase  		=						ids_tensor([self.batch_size] ,       self.type_sequence_label_size				)
              __UpperCamelCase  		=						ids_tensor([self.batch_size, self.seq_length] ,       self.num_labels				)
              __UpperCamelCase  		=						ids_tensor([self.batch_size] ,       self.num_choices				)

          __UpperCamelCase  		=						self.get_config()

          __UpperCamelCase  		=						ids_tensor([self.num_hidden_layers, self.num_attention_heads] ,       2				)

          return (
              config,
              input_ids,
              input_mask,
              head_mask,
              token_type_ids,
              mc_token_ids,
              sequence_labels,
              token_labels,
              choice_labels,
          )







      def       snake_case	(     self					: Optional[int]				):
          return CTRLConfig(
              vocab_size=self.vocab_size ,       n_embd=self.hidden_size ,       n_layer=self.num_hidden_layers ,       n_head=self.num_attention_heads ,       n_positions=self.max_position_embeddings ,       pad_token_id=self.pad_token_id ,       )







      def       snake_case	(     self					: Any ,       snake_case					: Optional[int] ,       snake_case					: Any ,       snake_case					: Union[str, Any] ,       snake_case					: Dict ,       snake_case					: List[Any] ,       *snake_case					: Union[str, Any]				):
          __UpperCamelCase  		=						CTRLModel(config=snake_case				)
          model.to(snake_case				)
          model.eval()

          model(snake_case ,       token_type_ids=snake_case ,       head_mask=snake_case				)
          model(snake_case ,       token_type_ids=snake_case				)
          __UpperCamelCase  		=						model(snake_case				)
          self.parent.assertEqual(result.last_hidden_state.shape ,       (self.batch_size, self.seq_length, self.hidden_size)				)
          self.parent.assertEqual(len(result.past_key_values				) ,       config.n_layer				)







      def       snake_case	(     self					: Any ,       snake_case					: Tuple ,       snake_case					: Tuple ,       snake_case					: Union[str, Any] ,       snake_case					: Dict ,       snake_case					: List[str] ,       *snake_case					: Union[str, Any]				):
          __UpperCamelCase  		=						CTRLLMHeadModel(snake_case				)
          model.to(snake_case				)
          model.eval()

          __UpperCamelCase  		=						model(snake_case ,       token_type_ids=snake_case ,       labels=snake_case				)
          self.parent.assertEqual(result.loss.shape ,       ()				)
          self.parent.assertEqual(result.logits.shape ,       (self.batch_size, self.seq_length, self.vocab_size)				)







      def       snake_case	(     self					: Any				):
          __UpperCamelCase  		=						self.prepare_config_and_inputs()

          (
              (
              __UpperCamelCase
          )		,      (
              __UpperCamelCase
          )		,      (
              __UpperCamelCase
          )		,      (
              __UpperCamelCase
          )		,      (
              __UpperCamelCase
          )		,      (
              __UpperCamelCase
          )		,      (
              __UpperCamelCase
          )		,      (
              __UpperCamelCase
          )		,      (
              __UpperCamelCase
          )		,      
          )  		=						config_and_inputs

          __UpperCamelCase  		=						{'''input_ids''': input_ids, '''token_type_ids''': token_type_ids, '''head_mask''': head_mask}

          return config, inputs_dict







      def       snake_case	(     self					: List[Any] ,       snake_case					: int ,       snake_case					: Dict ,       snake_case					: Optional[Any] ,       snake_case					: Any ,       *snake_case					: str				):
          __UpperCamelCase  		=						self.num_labels
          __UpperCamelCase  		=						CTRLForSequenceClassification(snake_case				)
          model.to(snake_case				)
          model.eval()
          __UpperCamelCase  		=						ids_tensor([self.batch_size] ,       self.type_sequence_label_size				)
          __UpperCamelCase  		=						model(snake_case ,       token_type_ids=snake_case ,       labels=snake_case				)
          self.parent.assertEqual(result.logits.shape ,       (self.batch_size, self.num_labels)				)







@require_torch
class  _lowerCamelCase						(			_SCREAMING_SNAKE_CASE							,			_SCREAMING_SNAKE_CASE							,			_SCREAMING_SNAKE_CASE							,			unittest.TestCase   ):

      """simple docstring"""

      lowerCAmelCase__			: int    =					(CTRLModel, CTRLLMHeadModel, CTRLForSequenceClassification) if is_torch_available() else ()
      lowerCAmelCase__			: List[str]    =					(CTRLLMHeadModel,) if is_torch_available() else ()
      lowerCAmelCase__			: str    =					(
          {
              "feature-extraction": CTRLModel,
              "text-classification": CTRLForSequenceClassification,
              "text-generation": CTRLLMHeadModel,
              "zero-shot": CTRLForSequenceClassification,
          }
          if is_torch_available()
          else {}
      )
      lowerCAmelCase__			: Dict    =					True
      lowerCAmelCase__			: List[Any]    =					False
      lowerCAmelCase__			: str    =					False







      def       snake_case	(     self					: str ,       snake_case					: Optional[int] ,       snake_case					: List[str] ,       snake_case					: Tuple ,       snake_case					: Dict ,       snake_case					: List[str]				):
          if pipeline_test_casse_name == "ZeroShotClassificationPipelineTests":
              # Get `tokenizer does not have a padding token` error for both fast/slow tokenizers.
              # `CTRLConfig` was never used in pipeline tests, either because of a missing checkpoint or because a tiny
              # config could not be created.
              return True

          return False







      def       snake_case	(     self					: Optional[int]				):
          __UpperCamelCase  		=						CTRLModelTester(self				)
          __UpperCamelCase  		=						ConfigTester(self ,       config_class=snake_case ,       n_embd=37				)







      def       snake_case	(     self					: Union[str, Any]				):
          super().tearDown()
          # clean-up as much as possible GPU memory occupied by PyTorch
          gc.collect()
          torch.cuda.empty_cache()







      def       snake_case	(     self					: Dict				):
          self.config_tester.run_common_tests()







      def       snake_case	(     self					: Optional[int]				):
          __UpperCamelCase  		=						self.model_tester.prepare_config_and_inputs()
          self.model_tester.create_and_check_ctrl_model(*snake_case				)







      def       snake_case	(     self					: Tuple				):
          __UpperCamelCase  		=						self.model_tester.prepare_config_and_inputs()
          self.model_tester.create_and_check_lm_head_model(*snake_case				)







      @unittest.skip('''Will be fixed soon by reducing the size of the model used for common tests.'''				)
      def       snake_case	(     self					: List[Any]				):
          pass







      @slow
      def       snake_case	(     self					: Optional[Any]				):
          for model_name in CTRL_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
              __UpperCamelCase  		=						CTRLModel.from_pretrained(snake_case				)
              self.assertIsNotNone(snake_case				)







      @unittest.skip('''The model doesn\'t support left padding'''				)  # and it's not used enough to be worth fixing :)
      def       snake_case	(     self					: List[Any]				):
          pass







@require_torch
class  _lowerCamelCase						(			unittest.TestCase   ):

      """simple docstring"""

      def       snake_case	(     self					: int				):
          super().tearDown()
          # clean-up as much as possible GPU memory occupied by PyTorch
          gc.collect()
          torch.cuda.empty_cache()







      @slow
      def       snake_case	(     self					: Optional[int]				):
          __UpperCamelCase  		=						CTRLLMHeadModel.from_pretrained('''ctrl'''				)
          model.to(snake_case				)
          __UpperCamelCase  		=						torch.tensor(
              [[11859, 0, 1611, 8]] ,       dtype=torch.long ,       device=snake_case				)  # Legal the president is
          __UpperCamelCase  		=						[
              11859,
              0,
              1611,
              8,
              5,
              150,
              26449,
              2,
              19,
              348,
              469,
              3,
              2595,
              48,
              20740,
              246533,
              246533,
              19,
              30,
              5,
          ]  # Legal the president is a good guy and I don't want to lose my job. \n \n I have a

          __UpperCamelCase  		=						model.generate(snake_case ,       do_sample=snake_case				)
          self.assertListEqual(output_ids[0].tolist() ,       snake_case				)






