




import copy
import inspect
import unittest

import numpy as np
from huggingface_hub import hf_hub_download

from transformers import TimesformerConfig
from transformers.models.auto import get_values
from transformers.testing_utils import require_torch, require_vision, slow, torch_device
from transformers.utils import cached_property, is_torch_available, is_vision_available

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


if is_torch_available():
     import torch
     from torch import nn

     from transformers import (
         MODEL_FOR_VIDEO_CLASSIFICATION_MAPPING,
         TimesformerForVideoClassification,
         TimesformerModel,
     )
     from transformers.models.timesformer.modeling_timesformer import TIMESFORMER_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
     from transformers import VideoMAEImageProcessor





class 					__lowerCamelCase			:




    """simple docstring"""

    def __init__(			self	:	Dict  ,      SCREAMING_SNAKE_CASE__	:	Optional[int]  ,      SCREAMING_SNAKE_CASE__	:	Tuple=13  ,      SCREAMING_SNAKE_CASE__	:	Optional[Any]=10  ,      SCREAMING_SNAKE_CASE__	:	Optional[int]=3  ,      SCREAMING_SNAKE_CASE__	:	List[str]=2  ,      SCREAMING_SNAKE_CASE__	:	List[Any]=2  ,      SCREAMING_SNAKE_CASE__	:	str=True  ,      SCREAMING_SNAKE_CASE__	:	int=True  ,      SCREAMING_SNAKE_CASE__	:	Any=32  ,      SCREAMING_SNAKE_CASE__	:	Optional[int]=5  ,      SCREAMING_SNAKE_CASE__	:	List[Any]=4  ,      SCREAMING_SNAKE_CASE__	:	List[Any]=37  ,      SCREAMING_SNAKE_CASE__	:	int="gelu"  ,      SCREAMING_SNAKE_CASE__	:	Optional[Any]=0.1  ,      SCREAMING_SNAKE_CASE__	:	Dict=0.1  ,      SCREAMING_SNAKE_CASE__	:	Any=10  ,      SCREAMING_SNAKE_CASE__	:	int=0.02  ,      SCREAMING_SNAKE_CASE__	:	Tuple="divided_space_time"  ,      SCREAMING_SNAKE_CASE__	:	Optional[int]=None  ,      ) ->			List[str]:
         lowerCAmelCase__            =					parent
         lowerCAmelCase__            =					batch_size
         lowerCAmelCase__            =					image_size
         lowerCAmelCase__            =					num_channels
         lowerCAmelCase__            =					patch_size
         lowerCAmelCase__            =					num_frames
         lowerCAmelCase__            =					is_training
         lowerCAmelCase__            =					use_labels
         lowerCAmelCase__            =					hidden_size
         lowerCAmelCase__            =					num_hidden_layers
         lowerCAmelCase__            =					num_attention_heads
         lowerCAmelCase__            =					intermediate_size
         lowerCAmelCase__            =					hidden_act
         lowerCAmelCase__            =					hidden_dropout_prob
         lowerCAmelCase__            =					attention_probs_dropout_prob
         lowerCAmelCase__            =					attention_type
         lowerCAmelCase__            =					initializer_range
         lowerCAmelCase__            =					scope
         lowerCAmelCase__            =					num_labels

         # in TimeSformer, the number of spatial tokens equals num_frames * num_patches per frame + 1 CLS token
         lowerCAmelCase__            =					(image_size // patch_size) ** 2
         lowerCAmelCase__            =					(num_frames) * self.num_patches_per_frame + 1


    def   a (			self	:	int  ) ->			Tuple:
         lowerCAmelCase__            =					floats_tensor(
             [self.batch_size, self.num_frames, self.num_channels, self.image_size, self.image_size]  )

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

         lowerCAmelCase__            =					self.get_config()

         return config, pixel_values, labels


    def   a (			self	:	List[Any]  ) ->			Any:
         lowerCAmelCase__            =					TimesformerConfig(
             image_size=self.image_size  ,      patch_size=self.patch_size  ,      num_channels=self.num_channels  ,      num_frames=self.num_frames  ,      hidden_size=self.hidden_size  ,      num_hidden_layers=self.num_hidden_layers  ,      num_attention_heads=self.num_attention_heads  ,      intermediate_size=self.intermediate_size  ,      hidden_act=self.hidden_act  ,      hidden_dropout_prob=self.hidden_dropout_prob  ,      attention_probs_dropout_prob=self.attention_probs_dropout_prob  ,      initializer_range=self.initializer_range  ,      attention_type=self.attention_type  ,      )
         lowerCAmelCase__            =					self.num_labels
         return config


    def   a (			self	:	str  ,      SCREAMING_SNAKE_CASE__	:	Optional[int]  ,      SCREAMING_SNAKE_CASE__	:	Dict  ,      SCREAMING_SNAKE_CASE__	:	Optional[int]  ) ->			Tuple:
         lowerCAmelCase__            =					TimesformerModel(config=SCREAMING_SNAKE_CASE__  )
         model.to(SCREAMING_SNAKE_CASE__  )
         model.eval()
         lowerCAmelCase__            =					model(SCREAMING_SNAKE_CASE__  )
         self.parent.assertEqual(result.last_hidden_state.shape  ,      (self.batch_size, self.seq_length, self.hidden_size)  )


    def   a (			self	:	Optional[int]  ,      SCREAMING_SNAKE_CASE__	:	List[str]  ,      SCREAMING_SNAKE_CASE__	:	Tuple  ,      SCREAMING_SNAKE_CASE__	:	Tuple  ) ->			Tuple:
         lowerCAmelCase__            =					TimesformerForVideoClassification(SCREAMING_SNAKE_CASE__  )
         model.to(SCREAMING_SNAKE_CASE__  )
         model.eval()

         lowerCAmelCase__            =					model(SCREAMING_SNAKE_CASE__  )

         # verify the logits shape
         lowerCAmelCase__            =					torch.Size((self.batch_size, self.num_labels)  )
         self.parent.assertEqual(result.logits.shape  ,      SCREAMING_SNAKE_CASE__  )


    def   a (			self	:	Tuple  ) ->			Dict:
         lowerCAmelCase__            =					self.prepare_config_and_inputs()
         lowerCAmelCase__      ,						lowerCAmelCase__      ,						lowerCAmelCase__            =					config_and_inputs
         lowerCAmelCase__            =					{"pixel_values": pixel_values}
         return config, inputs_dict






@require_torch
class 					__lowerCamelCase			(       UpperCamelCase__      ,							UpperCamelCase__      ,							unittest.TestCase       ):




    """simple docstring"""

    snake_case__   = (TimesformerModel, TimesformerForVideoClassification) if is_torch_available() else ()
    snake_case__   = (
        {"feature-extraction": TimesformerModel, "video-classification": TimesformerForVideoClassification}
        if is_torch_available()
        else {}
    )

    snake_case__   = False
    snake_case__   = False
    snake_case__   = False
    snake_case__   = False


    def   a (			self	:	List[str]  ) ->			List[Any]:
         lowerCAmelCase__            =					TimesformerModelTester(self  )
         lowerCAmelCase__            =					ConfigTester(
             self  ,      config_class=SCREAMING_SNAKE_CASE__  ,      has_text_modality=SCREAMING_SNAKE_CASE__  ,      hidden_size=37  )


    def   a (			self	:	Dict  ,      SCREAMING_SNAKE_CASE__	:	List[Any]  ,      SCREAMING_SNAKE_CASE__	:	Tuple  ,      SCREAMING_SNAKE_CASE__	:	Tuple=False  ) ->			str:
         lowerCAmelCase__            =					copy.deepcopy(SCREAMING_SNAKE_CASE__  )

         if return_labels:
              if model_class in get_values(SCREAMING_SNAKE_CASE__  ):
                   lowerCAmelCase__            =					torch.zeros(
                       self.model_tester.batch_size  ,      dtype=torch.long  ,      device=SCREAMING_SNAKE_CASE__  )

         return inputs_dict


    def   a (			self	:	Optional[Any]  ) ->			List[str]:
         self.config_tester.run_common_tests()


    @unittest.skip(reason="TimeSformer does not use inputs_embeds"  )
    def   a (			self	:	Union[str, Any]  ) ->			Tuple:
         pass


    def   a (			self	:	Dict  ) ->			List[str]:
         lowerCAmelCase__      ,						lowerCAmelCase__            =					self.model_tester.prepare_config_and_inputs_for_common()

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


    def   a (			self	:	int  ) ->			Optional[Any]:
         lowerCAmelCase__      ,						lowerCAmelCase__            =					self.model_tester.prepare_config_and_inputs_for_common()

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

              lowerCAmelCase__            =					["pixel_values"]
              self.assertListEqual(arg_names[:1]  ,      SCREAMING_SNAKE_CASE__  )


    def   a (			self	:	int  ) ->			Optional[Any]:
         lowerCAmelCase__            =					self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_model(*SCREAMING_SNAKE_CASE__  )


    def   a (			self	:	Optional[Any]  ) ->			Tuple:
         lowerCAmelCase__            =					self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_for_video_classification(*SCREAMING_SNAKE_CASE__  )


    @slow
    def   a (			self	:	str  ) ->			Tuple:
         for model_name in TIMESFORMER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
              lowerCAmelCase__            =					TimesformerModel.from_pretrained(SCREAMING_SNAKE_CASE__  )
              self.assertIsNotNone(SCREAMING_SNAKE_CASE__  )


    def   a (			self	:	int  ) ->			Dict:
         if not self.has_attentions:
              pass

         else:
              lowerCAmelCase__      ,						lowerCAmelCase__            =					self.model_tester.prepare_config_and_inputs_for_common()
              lowerCAmelCase__            =					True

              for model_class in self.all_model_classes:
                   lowerCAmelCase__            =					self.model_tester.seq_length
                   lowerCAmelCase__            =					self.model_tester.num_frames

                   lowerCAmelCase__            =					True
                   lowerCAmelCase__            =					False
                   lowerCAmelCase__            =					True
                   lowerCAmelCase__            =					model_class(SCREAMING_SNAKE_CASE__  )
                   model.to(SCREAMING_SNAKE_CASE__  )
                   model.eval()
                   with torch.no_grad():
                        lowerCAmelCase__            =					model(**self._prepare_for_class(SCREAMING_SNAKE_CASE__  ,      SCREAMING_SNAKE_CASE__  )  )
                   lowerCAmelCase__            =					outputs.attentions
                   self.assertEqual(len(SCREAMING_SNAKE_CASE__  )  ,      self.model_tester.num_hidden_layers  )

                   # check that output_attentions also work using config
                   del inputs_dict["output_attentions"]
                   lowerCAmelCase__            =					True
                   lowerCAmelCase__            =					model_class(SCREAMING_SNAKE_CASE__  )
                   model.to(SCREAMING_SNAKE_CASE__  )
                   model.eval()
                   with torch.no_grad():
                        lowerCAmelCase__            =					model(**self._prepare_for_class(SCREAMING_SNAKE_CASE__  ,      SCREAMING_SNAKE_CASE__  )  )
                   lowerCAmelCase__            =					outputs.attentions
                   self.assertEqual(len(SCREAMING_SNAKE_CASE__  )  ,      self.model_tester.num_hidden_layers  )

                   # attentions has shape (batch_size x num_frames) x num_heads x (num_patches per frame + 1) x (num_patches per frame + 1)
                   self.assertListEqual(
                       list(attentions[0].shape[-3:]  )  ,      [self.model_tester.num_attention_heads, seq_len // num_frames + 1, seq_len // num_frames + 1]  ,      )
                   lowerCAmelCase__            =					len(SCREAMING_SNAKE_CASE__  )

                   # Check attention is always last and order is fine
                   lowerCAmelCase__            =					True
                   lowerCAmelCase__            =					True
                   lowerCAmelCase__            =					model_class(SCREAMING_SNAKE_CASE__  )
                   model.to(SCREAMING_SNAKE_CASE__  )
                   model.eval()
                   with torch.no_grad():
                        lowerCAmelCase__            =					model(**self._prepare_for_class(SCREAMING_SNAKE_CASE__  ,      SCREAMING_SNAKE_CASE__  )  )

                   self.assertEqual(out_len + 1  ,      len(SCREAMING_SNAKE_CASE__  )  )

                   lowerCAmelCase__            =					outputs.attentions

                   self.assertEqual(len(SCREAMING_SNAKE_CASE__  )  ,      self.model_tester.num_hidden_layers  )

                   # attentions has shape (batch_size x num_frames) x num_heads x (num_patches per frame + 1) x (num_patches per frame + 1)
                   self.assertListEqual(
                       list(self_attentions[0].shape[-3:]  )  ,      [self.model_tester.num_attention_heads, seq_len // num_frames + 1, seq_len // num_frames + 1]  ,      )


    def   a (			self	:	List[str]  ) ->			Any:
         def check_hidden_states_output(SCREAMING_SNAKE_CASE__	:	str  ,      SCREAMING_SNAKE_CASE__	:	int  ,      SCREAMING_SNAKE_CASE__	:	Optional[int]  ):
              lowerCAmelCase__            =					model_class(SCREAMING_SNAKE_CASE__  )
              model.to(SCREAMING_SNAKE_CASE__  )
              model.eval()

              with torch.no_grad():
                   lowerCAmelCase__            =					model(**self._prepare_for_class(SCREAMING_SNAKE_CASE__  ,      SCREAMING_SNAKE_CASE__  )  )

              lowerCAmelCase__            =					outputs.hidden_states
              lowerCAmelCase__            =					self.model_tester.num_hidden_layers + 1
              self.assertEqual(len(SCREAMING_SNAKE_CASE__  )  ,      SCREAMING_SNAKE_CASE__  )

              lowerCAmelCase__            =					self.model_tester.seq_length

              self.assertListEqual(
                  list(hidden_states[0].shape[-2:]  )  ,      [seq_length, self.model_tester.hidden_size]  ,      )

         lowerCAmelCase__      ,						lowerCAmelCase__            =					self.model_tester.prepare_config_and_inputs_for_common()

         for model_class in self.all_model_classes:
              lowerCAmelCase__            =					True
              check_hidden_states_output(SCREAMING_SNAKE_CASE__  ,      SCREAMING_SNAKE_CASE__  ,      SCREAMING_SNAKE_CASE__  )

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

              check_hidden_states_output(SCREAMING_SNAKE_CASE__  ,      SCREAMING_SNAKE_CASE__  ,      SCREAMING_SNAKE_CASE__  )






def 				_A  (		):
     """simple docstring"""

     lowerCAmelCase__            =					hf_hub_download(
         repo_id="hf-internal-testing/spaghetti-video"  ,							filename="eating_spaghetti.npy"  ,							repo_type="dataset"     )
     lowerCAmelCase__            =					np.load(lowerCAmelCase_     )
     return list(lowerCAmelCase_     )






@require_torch
@require_vision
class 					__lowerCamelCase			(       unittest.TestCase       ):




    """simple docstring"""

    @cached_property
    def   a (			self	:	Optional[Any]  ) ->			Union[str, Any]:
         # logits were tested with a different mean and std, so we use the same here
         return (
             VideoMAEImageProcessor(image_mean=[0.5, 0.5, 0.5]  ,      image_std=[0.5, 0.5, 0.5]  )
             if is_vision_available()
             else None
         )


    @slow
    def   a (			self	:	Optional[Any]  ) ->			str:
         lowerCAmelCase__            =					TimesformerForVideoClassification.from_pretrained("facebook/timesformer-base-finetuned-k400"  ).to(
             SCREAMING_SNAKE_CASE__  )

         lowerCAmelCase__            =					self.default_image_processor
         lowerCAmelCase__            =					prepare_video()
         lowerCAmelCase__            =					image_processor(video[:8]  ,      return_tensors="pt"  ).to(SCREAMING_SNAKE_CASE__  )

         # forward pass
         with torch.no_grad():
              lowerCAmelCase__            =					model(**SCREAMING_SNAKE_CASE__  )

         # verify the logits
         lowerCAmelCase__            =					torch.Size((1, 400)  )
         self.assertEqual(outputs.logits.shape  ,      SCREAMING_SNAKE_CASE__  )

         lowerCAmelCase__            =					torch.tensor([-0.3_016, -0.7_713, -0.4_205]  ).to(SCREAMING_SNAKE_CASE__  )

         self.assertTrue(torch.allclose(outputs.logits[0, :3]  ,      SCREAMING_SNAKE_CASE__  ,      atol=1e-4  )  )


"""simple docstring"""


from __future__ import annotations






def    _snake_case					(		snake_case__ :  tuple[int, int]						,   snake_case__ :  int  ):
	A ,   A     = position
	A     = [
	    (y + 1, x + 2),
	    (y - 1, x + 2),
	    (y + 1, x - 2),
	    (y - 1, x - 2),
	    (y + 2, x + 1),
	    (y + 2, x - 1),
	    (y - 2, x + 1),
	    (y - 2, x - 1),
	]
	A     = []

	for position in positions:
		A ,   A     = position
		if 0 <= y_test < n and 0 <= x_test < n:
			permissible_positions.append(snake_case__  )

	return permissible_positions






def    _snake_case					(		snake_case__ :  list[list[int]]  ):
	return not any(elem == 0 for row in board for elem in row  )






def    _snake_case					(		snake_case__ :  list[list[int]]						,   snake_case__ :  tuple[int, int]						,   snake_case__ :  int  ):

	if is_complete(snake_case__  ):
		return True

	for position in get_valid_pos(snake_case__						,   len(snake_case__  )  ):
		A ,   A     = position

		if board[y][x] == 0:
			A     = curr + 1
			if open_knight_tour_helper(snake_case__						,   snake_case__						,   curr + 1  ):
				return True
			A     = 0

	return False






def    _snake_case					(		snake_case__ :  int  ):
	A     = [[0 for i in range(snake_case__  )] for j in range(snake_case__  )]

	for i in range(snake_case__  ):
		for j in range(snake_case__  ):
			A     = 1
			if open_knight_tour_helper(snake_case__						,   (i, j)						,   1  ):
				return board
			A     = 0

	A     = F'Open Kight Tour cannot be performed on a board of size {n}'
	raise ValueError(snake_case__  )


if __name__ == "__main__":
		import doctest

		doctest.testmod()