
"""simple docstring"""







def 			__UpperCAmelCase		(		a_			:		List[Any]    ,  a_			:		List[Any]    ,  a_			:		Union[str, Any]    ,  a_			:		Any				)     ->       int:
   return len_board * len_board_column * row + column
def 			__UpperCAmelCase		(		a_			:		int    ,  a_			:		List[Any]    ,  a_			:		Optional[Any]    ,  a_			:		Dict    ,  a_			:		int    ,  a_			:		Dict    ,  )     ->       bool:







   if board[row][column] != word[word_index]:
      return False

   if word_index == len(a_				) - 1:
      return True

   _UpperCAmelCase   	=					[(0, 1), (0, -1), (-1, 0), (1, 0)]
   _UpperCAmelCase   	=					len(a_				)
   _UpperCAmelCase   	=					len(board[0]				)
   for direction in traverts_directions:
      _UpperCAmelCase   	=					row + direction[0]
      _UpperCAmelCase   	=					column + direction[1]
      if not (0 <= next_i < len_board and 0 <= next_j < len_board_column):
         continue

      _UpperCAmelCase   	=					get_point_key(a_    ,  a_    ,  a_    ,  a_				)
      if key in visited_points_set:
         continue

      visited_points_set.add(a_				)
      if exits_word(a_    ,  a_    ,  a_    ,  a_    ,  word_index + 1    ,  a_				):
         return True

      visited_points_set.remove(a_				)

   return False
def 			__UpperCAmelCase		(		a_			:		Tuple    ,  a_			:		Union[str, Any]				)     ->       bool:
   _UpperCAmelCase   	=					(
       "The board should be a non empty matrix of single chars strings."
   )

   _UpperCAmelCase   	=					len(a_				)
   if not isinstance(a_    ,  a_				) or len(a_				) == 0:
      raise ValueError(a_				)

   for row in board:
      if not isinstance(a_    ,  a_				) or len(a_				) == 0:
         raise ValueError(a_				)

      for item in row:
         if not isinstance(a_    ,  a_				) or len(a_				) != 1:
            raise ValueError(a_				)

    # Validate word
   if not isinstance(a_    ,  a_				) or len(a_				) == 0:
      raise ValueError(
          "The word parameter should be a string of length greater than 0."				)

   _UpperCAmelCase   	=					len(board[0]				)
   for i in range(a_				):
      for j in range(a_				):
         if exits_word(
             a_    ,  a_    ,  a_    ,  a_    ,  0    ,  {get_point_key(a_    ,  a_    ,  a_    ,  a_				)}				):
            return True

   return False


if __name__ == "__main__":
  import doctest

  doctest.testmod()



"""simple docstring"""







import collections
import inspect
import unittest

from transformers import NatConfig
from transformers.testing_utils import require_natten, require_torch, require_vision, slow, torch_device
from transformers.utils import cached_property, is_torch_available, is_vision_available

from ...test_backbone_common import BackboneTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, _config_zero_init, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
  import torch
  from torch import nn

  from transformers import NatBackbone, NatForImageClassification, NatModel
  from transformers.models.nat.modeling_nat import NAT_PRETRAINED_MODEL_ARCHIVE_LIST

if is_vision_available():
  from PIL import Image

  from transformers import AutoImageProcessor






class     __a			:







       def __init__(					self							,lowerCamelCase_							,lowerCamelCase_=13							,lowerCamelCase_=64							,lowerCamelCase_=4							,lowerCamelCase_=3							,lowerCamelCase_=16							,lowerCamelCase_=[1, 2, 1]							,lowerCamelCase_=[2, 4, 8]							,lowerCamelCase_=3							,lowerCamelCase_=2.0							,lowerCamelCase_=True							,lowerCamelCase_=0.0							,lowerCamelCase_=0.0							,lowerCamelCase_=0.1							,lowerCamelCase_="gelu"							,lowerCamelCase_=True							,lowerCamelCase_=0.0_2							,lowerCamelCase_=1e-5							,lowerCamelCase_=True							,lowerCamelCase_=None							,lowerCamelCase_=True							,lowerCamelCase_=10							,lowerCamelCase_=["stage1", "stage2"]							,lowerCamelCase_=[1, 2]							,):



          '''simple docstring'''

          _UpperCAmelCase   	=					parent
          _UpperCAmelCase   	=					batch_size
          _UpperCAmelCase   	=					image_size
          _UpperCAmelCase   	=					patch_size
          _UpperCAmelCase   	=					num_channels
          _UpperCAmelCase   	=					embed_dim
          _UpperCAmelCase   	=					depths
          _UpperCAmelCase   	=					num_heads
          _UpperCAmelCase   	=					kernel_size
          _UpperCAmelCase   	=					mlp_ratio
          _UpperCAmelCase   	=					qkv_bias
          _UpperCAmelCase   	=					hidden_dropout_prob
          _UpperCAmelCase   	=					attention_probs_dropout_prob
          _UpperCAmelCase   	=					drop_path_rate
          _UpperCAmelCase   	=					hidden_act
          _UpperCAmelCase   	=					patch_norm
          _UpperCAmelCase   	=					layer_norm_eps
          _UpperCAmelCase   	=					initializer_range
          _UpperCAmelCase   	=					is_training
          _UpperCAmelCase   	=					scope
          _UpperCAmelCase   	=					use_labels
          _UpperCAmelCase   	=					num_labels
          _UpperCAmelCase   	=					out_features
          _UpperCAmelCase   	=					out_indices







       def    _snake_case			(					self		):



          '''simple docstring'''

          _UpperCAmelCase   	=					floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]		)

          _UpperCAmelCase   	=					None
          if self.use_labels:
             _UpperCAmelCase   	=					ids_tensor([self.batch_size]							,self.num_labels		)

          _UpperCAmelCase   	=					self.get_config()

          return config, pixel_values, labels







       def    _snake_case			(					self		):



          '''simple docstring'''

          return NatConfig(
              num_labels=self.num_labels							,image_size=self.image_size							,patch_size=self.patch_size							,num_channels=self.num_channels							,embed_dim=self.embed_dim							,depths=self.depths							,num_heads=self.num_heads							,kernel_size=self.kernel_size							,mlp_ratio=self.mlp_ratio							,qkv_bias=self.qkv_bias							,hidden_dropout_prob=self.hidden_dropout_prob							,attention_probs_dropout_prob=self.attention_probs_dropout_prob							,drop_path_rate=self.drop_path_rate							,hidden_act=self.hidden_act							,patch_norm=self.patch_norm							,layer_norm_eps=self.layer_norm_eps							,initializer_range=self.initializer_range							,out_features=self.out_features							,out_indices=self.out_indices							,)







       def    _snake_case			(					self							,lowerCamelCase_							,lowerCamelCase_							,lowerCamelCase_		):



          '''simple docstring'''

          _UpperCAmelCase   	=					NatModel(config=lowerCamelCase_		)
          model.to(lowerCamelCase_		)
          model.eval()
          _UpperCAmelCase   	=					model(lowerCamelCase_		)

          _UpperCAmelCase   	=					_UpperCAmelCase   	=					(config.image_size // config.patch_size) // (2 ** (len(config.depths		) - 1))
          _UpperCAmelCase   	=					int(config.embed_dim * 2 ** (len(config.depths		) - 1)		)

          self.parent.assertEqual(
              result.last_hidden_state.shape							,(self.batch_size, expected_height, expected_width, expected_dim)		)







       def    _snake_case			(					self							,lowerCamelCase_							,lowerCamelCase_							,lowerCamelCase_		):



          '''simple docstring'''

          _UpperCAmelCase   	=					NatForImageClassification(lowerCamelCase_		)
          model.to(lowerCamelCase_		)
          model.eval()
          _UpperCAmelCase   	=					model(lowerCamelCase_							,labels=lowerCamelCase_		)
          self.parent.assertEqual(result.logits.shape							,(self.batch_size, self.num_labels)		)

          # test greyscale images
          _UpperCAmelCase   	=					1
          _UpperCAmelCase   	=					NatForImageClassification(lowerCamelCase_		)
          model.to(lowerCamelCase_		)
          model.eval()

          _UpperCAmelCase   	=					floats_tensor([self.batch_size, 1, self.image_size, self.image_size]		)
          _UpperCAmelCase   	=					model(lowerCamelCase_		)
          self.parent.assertEqual(result.logits.shape							,(self.batch_size, self.num_labels)		)







       def    _snake_case			(					self							,lowerCamelCase_							,lowerCamelCase_							,lowerCamelCase_		):



          '''simple docstring'''

          _UpperCAmelCase   	=					NatBackbone(config=lowerCamelCase_		)
          model.to(lowerCamelCase_		)
          model.eval()
          _UpperCAmelCase   	=					model(lowerCamelCase_		)

          # verify hidden states
          self.parent.assertEqual(len(result.feature_maps		)							,len(config.out_features		)		)
          self.parent.assertListEqual(list(result.feature_maps[0].shape		)							,[self.batch_size, model.channels[0], 16, 16]		)

          # verify channels
          self.parent.assertEqual(len(model.channels		)							,len(config.out_features		)		)

          # verify backbone works with out_features=None
          _UpperCAmelCase   	=					None
          _UpperCAmelCase   	=					NatBackbone(config=lowerCamelCase_		)
          model.to(lowerCamelCase_		)
          model.eval()
          _UpperCAmelCase   	=					model(lowerCamelCase_		)

          # verify feature maps
          self.parent.assertEqual(len(result.feature_maps		)							,1		)
          self.parent.assertListEqual(list(result.feature_maps[0].shape		)							,[self.batch_size, model.channels[-1], 4, 4]		)

          # verify channels
          self.parent.assertEqual(len(model.channels		)							,1		)







       def    _snake_case			(					self		):



          '''simple docstring'''

          _UpperCAmelCase   	=					self.prepare_config_and_inputs()
          _UpperCAmelCase	,							_UpperCAmelCase	,							_UpperCAmelCase   	=					config_and_inputs
          _UpperCAmelCase   	=					{"pixel_values": pixel_values}
          return config, inputs_dict






@require_natten
@require_torch
class     __a			(					lowerCAmelCase_				,	lowerCAmelCase_				,	unittest.TestCase			):
       _lowerCamelCase							:							str       =			(
           (
               NatModel,
               NatForImageClassification,
               NatBackbone,
           )
           if is_torch_available()
           else ()
       )
       _lowerCamelCase							:							int       =			(
           {'feature-extraction': NatModel, 'image-classification': NatForImageClassification}
           if is_torch_available()
           else {}
       )
       _lowerCamelCase							:							Optional[Any]       =			False

       _lowerCamelCase							:							Optional[Any]       =			False
       _lowerCamelCase							:							Optional[int]       =			False
       _lowerCamelCase							:							List[str]       =			False
       _lowerCamelCase							:							str       =			False







       def    _snake_case			(					self		):



          '''simple docstring'''

          _UpperCAmelCase   	=					NatModelTester(self		)
          _UpperCAmelCase   	=					ConfigTester(self							,config_class=lowerCamelCase_							,embed_dim=37		)







       def    _snake_case			(					self		):



          '''simple docstring'''

          self.create_and_test_config_common_properties()
          self.config_tester.create_and_test_config_to_json_string()
          self.config_tester.create_and_test_config_to_json_file()
          self.config_tester.create_and_test_config_from_and_save_pretrained()
          self.config_tester.create_and_test_config_with_num_labels()
          self.config_tester.check_config_can_be_init_without_params()
          self.config_tester.check_config_arguments_init()







       def    _snake_case			(					self		):



          '''simple docstring'''

          return







       def    _snake_case			(					self		):



          '''simple docstring'''

          _UpperCAmelCase   	=					self.model_tester.prepare_config_and_inputs()
          self.model_tester.create_and_check_model(*lowerCamelCase_		)







       def    _snake_case			(					self		):



          '''simple docstring'''

          _UpperCAmelCase   	=					self.model_tester.prepare_config_and_inputs()
          self.model_tester.create_and_check_for_image_classification(*lowerCamelCase_		)







       def    _snake_case			(					self		):



          '''simple docstring'''

          _UpperCAmelCase   	=					self.model_tester.prepare_config_and_inputs()
          self.model_tester.create_and_check_backbone(*lowerCamelCase_		)







       @unittest.skip(reason="Nat does not use inputs_embeds"		)
       def    _snake_case			(					self		):



          '''simple docstring'''

          pass







       @unittest.skip(reason="Nat does not use feedforward chunking"		)
       def    _snake_case			(					self		):



          '''simple docstring'''

          pass







       def    _snake_case			(					self		):



          '''simple docstring'''

          _UpperCAmelCase	,							_UpperCAmelCase   	=					self.model_tester.prepare_config_and_inputs_for_common()

          for model_class in self.all_model_classes:
             _UpperCAmelCase   	=					model_class(lowerCamelCase_		)
             self.assertIsInstance(model.get_input_embeddings()							,(nn.Module)		)
             _UpperCAmelCase   	=					model.get_output_embeddings()
             self.assertTrue(x is None or isinstance(lowerCamelCase_							,nn.Linear		)		)







       def    _snake_case			(					self		):



          '''simple docstring'''

          _UpperCAmelCase	,							_UpperCAmelCase   	=					self.model_tester.prepare_config_and_inputs_for_common()

          for model_class in self.all_model_classes:
             _UpperCAmelCase   	=					model_class(lowerCamelCase_		)
             _UpperCAmelCase   	=					inspect.signature(model.forward		)
             # signature.parameters is an OrderedDict => so arg_names order is deterministic
             _UpperCAmelCase   	=					[*signature.parameters.keys()]

             _UpperCAmelCase   	=					["pixel_values"]
             self.assertListEqual(arg_names[:1]							,lowerCamelCase_		)







       def    _snake_case			(					self		):



          '''simple docstring'''

          self.skipTest("Nat's attention operation is handled entirely by NATTEN."		)







       def    _snake_case			(					self							,lowerCamelCase_							,lowerCamelCase_							,lowerCamelCase_							,lowerCamelCase_		):



          '''simple docstring'''

          _UpperCAmelCase   	=					model_class(lowerCamelCase_		)
          model.to(lowerCamelCase_		)
          model.eval()

          with torch.no_grad():
             _UpperCAmelCase   	=					model(**self._prepare_for_class(lowerCamelCase_							,lowerCamelCase_		)		)

          _UpperCAmelCase   	=					outputs.hidden_states

          _UpperCAmelCase   	=					getattr(
              self.model_tester							,"expected_num_hidden_layers"							,len(self.model_tester.depths		) + 1		)
          self.assertEqual(len(lowerCamelCase_		)							,lowerCamelCase_		)

          # Nat has a different seq_length
          _UpperCAmelCase   	=					(
              config.patch_size
              if isinstance(config.patch_size							,collections.abc.Iterable		)
              else (config.patch_size, config.patch_size)
          )

          _UpperCAmelCase   	=					image_size[0] // patch_size[0]
          _UpperCAmelCase   	=					image_size[1] // patch_size[1]

          self.assertListEqual(
              list(hidden_states[0].shape[-3:]		)							,[height, width, self.model_tester.embed_dim]							,)

          if model_class.__name__ != "NatBackbone":
             _UpperCAmelCase   	=					outputs.reshaped_hidden_states
             self.assertEqual(len(lowerCamelCase_		)							,lowerCamelCase_		)

             _UpperCAmelCase	,							_UpperCAmelCase	,							_UpperCAmelCase	,							_UpperCAmelCase   	=					reshaped_hidden_states[0].shape
             _UpperCAmelCase   	=					(
                 reshaped_hidden_states[0].view(lowerCamelCase_							,lowerCamelCase_							,lowerCamelCase_							,lowerCamelCase_		).permute(0							,2							,3							,1		)
             )
             self.assertListEqual(
                 list(reshaped_hidden_states.shape[-3:]		)							,[height, width, self.model_tester.embed_dim]							,)







       def    _snake_case			(					self		):



          '''simple docstring'''

          _UpperCAmelCase	,							_UpperCAmelCase   	=					self.model_tester.prepare_config_and_inputs_for_common()

          _UpperCAmelCase   	=					(
              self.model_tester.image_size
              if isinstance(self.model_tester.image_size							,collections.abc.Iterable		)
              else (self.model_tester.image_size, self.model_tester.image_size)
          )

          for model_class in self.all_model_classes:
             _UpperCAmelCase   	=					True
             self.check_hidden_states_output(lowerCamelCase_							,lowerCamelCase_							,lowerCamelCase_							,lowerCamelCase_		)

             # check that output_hidden_states also work using config
             del inputs_dict["output_hidden_states"]
             _UpperCAmelCase   	=					True

             self.check_hidden_states_output(lowerCamelCase_							,lowerCamelCase_							,lowerCamelCase_							,lowerCamelCase_		)







       @slow
       def    _snake_case			(					self		):



          '''simple docstring'''

          for model_name in NAT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
             _UpperCAmelCase   	=					NatModel.from_pretrained(lowerCamelCase_		)
             self.assertIsNotNone(lowerCamelCase_		)







       def    _snake_case			(					self		):



          '''simple docstring'''

          _UpperCAmelCase	,							_UpperCAmelCase   	=					self.model_tester.prepare_config_and_inputs_for_common()

          _UpperCAmelCase   	=					_config_zero_init(lowerCamelCase_		)
          for model_class in self.all_model_classes:
             _UpperCAmelCase   	=					model_class(config=lowerCamelCase_		)
             for name, param in model.named_parameters():
                if "embeddings" not in name and param.requires_grad:
                   self.assertIn(
                       ((param.data.mean() * 1e9).round() / 1e9).item()							,[0.0, 1.0]							,msg=f'''Parameter {name} of model {model_class} seems not properly initialized'''							,)






@require_natten
@require_vision
@require_torch
class     __a			(					unittest.TestCase			):







       @cached_property
       def    _snake_case			(					self		):



          '''simple docstring'''

          return AutoImageProcessor.from_pretrained("shi-labs/nat-mini-in1k-224"		) if is_vision_available() else None







       @slow
       def    _snake_case			(					self		):



          '''simple docstring'''

          _UpperCAmelCase   	=					NatForImageClassification.from_pretrained("shi-labs/nat-mini-in1k-224"		).to(lowerCamelCase_		)
          _UpperCAmelCase   	=					self.default_image_processor

          _UpperCAmelCase   	=					Image.open("./tests/fixtures/tests_samples/COCO/000000039769.png"		)
          _UpperCAmelCase   	=					image_processor(images=lowerCamelCase_							,return_tensors="pt"		).to(lowerCamelCase_		)

          # forward pass
          with torch.no_grad():
             _UpperCAmelCase   	=					model(**lowerCamelCase_		)

          # verify the logits
          _UpperCAmelCase   	=					torch.Size((1, 1000)		)
          self.assertEqual(outputs.logits.shape							,lowerCamelCase_		)
          _UpperCAmelCase   	=					torch.tensor([0.3_8_0_5, -0.8_6_7_6, -0.3_9_1_2]		).to(lowerCamelCase_		)
          self.assertTrue(torch.allclose(outputs.logits[0, :3]							,lowerCamelCase_							,atol=1e-4		)		)






@require_torch
@require_natten
class     __a			(					unittest.TestCase				,	lowerCAmelCase_			):
       _lowerCamelCase							:							Any       =			(NatBackbone,) if is_torch_available() else ()
       _lowerCamelCase							:							Dict       =			NatConfig







       def    _snake_case			(					self		):



          '''simple docstring'''

          _UpperCAmelCase   	=					NatModelTester(self		)

