






from __future__ import annotations





def 	SCREAMING_SNAKE_CASE__    ( snake_case_,	snake_case_ = None	) ->	list[list[str]]:


	"""simple docstring"""



	a												=      word_bank or []
	# create a table
	a												=      len(lowerCAmelCase__	) + 1

	a												=      []
	for _ in range(lowerCAmelCase__	):
		table.append([]	)
	# seed value
	a												=      [[]]  # because empty string has empty combination

	# iterate through the indices
	for i in range(lowerCAmelCase__	):
		# condition
		if table[i] != []:
			for word in word_bank:
				# slice condition
				if target[i : i + len(lowerCAmelCase__	)] == word:
					a												=      [
					    [word, *way] for way in table[i]
					]
					# adds the word to every combination the current position holds
					# now,push that combination to the table[i+len(word)]
					table[i + len(lowerCAmelCase__	)] += new_combinations

    # combinations are in reverse order so reverse for better output
	for combination in table[len(lowerCAmelCase__	)]:
		combination.reverse()

	return table[len(lowerCAmelCase__	)]


if __name__ == "__main__":
				print(all_construct("""jwajalapa""", ["""jwa""", """j""", """w""", """a""", """la""", """lapa"""]))
				print(all_construct("""rajamati""", ["""s""", """raj""", """amat""", """raja""", """ma""", """i""", """t"""]))
				print(
				    all_construct(
				        """hexagonosaurus""",
				        ["""h""", """ex""", """hex""", """ag""", """ago""", """ru""", """auru""", """rus""", """go""", """no""", """o""", """s"""],
				    )
				)






"""simple docstring"""






import inspect
import unittest

from transformers import ConvNextConfig
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_backbone_common import BackboneTesterMixin
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 transformers import ConvNextBackbone, ConvNextForImageClassification, ConvNextModel
       from transformers.models.convnext.modeling_convnext import CONVNEXT_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=32						,			__lowerCAmelCase=3						,			__lowerCAmelCase=4						,			__lowerCAmelCase=[10, 20, 30, 40]						,			__lowerCAmelCase=[2, 2, 3, 2]						,			__lowerCAmelCase=True						,			__lowerCAmelCase=True						,			__lowerCAmelCase=37						,			__lowerCAmelCase="gelu"						,			__lowerCAmelCase=10						,			__lowerCAmelCase=0.0_2						,			__lowerCAmelCase=["stage2", "stage3", "stage4"]						,			__lowerCAmelCase=[2, 3, 4]						,			__lowerCAmelCase=None						,			):







            """simple docstring"""



            lowercase								=      parent
            lowercase								=      batch_size
            lowercase								=      image_size
            lowercase								=      num_channels
            lowercase								=      num_stages
            lowercase								=      hidden_sizes
            lowercase								=      depths
            lowercase								=      is_training
            lowercase								=      use_labels
            lowercase								=      intermediate_size
            lowercase								=      hidden_act
            lowercase								=      num_labels
            lowercase								=      initializer_range
            lowercase								=      out_features
            lowercase								=      out_indices
            lowercase								=      scope

      def 							A__			(		self		):







            """simple docstring"""



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

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

            lowercase								=      self.get_config()
            return config, pixel_values, labels

      def 							A__			(		self		):







            """simple docstring"""



            return ConvNextConfig(
                num_channels=self.num_channels						,			hidden_sizes=self.hidden_sizes						,			depths=self.depths						,			num_stages=self.num_stages						,			hidden_act=self.hidden_act						,			is_decoder=__lowerCAmelCase						,			initializer_range=self.initializer_range						,			out_features=self.out_features						,			out_indices=self.out_indices						,			num_labels=self.num_labels						,			)

      def 							A__			(		self						,			__lowerCAmelCase						,			__lowerCAmelCase						,			__lowerCAmelCase		):







            """simple docstring"""



            lowercase								=      ConvNextModel(config=__lowerCAmelCase		)
            model.to(__lowerCAmelCase		)
            model.eval()
            lowercase								=      model(__lowerCAmelCase		)
            # expected last hidden states: B, C, H // 32, W // 32
            self.parent.assertEqual(
                result.last_hidden_state.shape						,			(self.batch_size, self.hidden_sizes[-1], self.image_size // 32, self.image_size // 32)						,			)

      def 							A__			(		self						,			__lowerCAmelCase						,			__lowerCAmelCase						,			__lowerCAmelCase		):







            """simple docstring"""



            lowercase								=      ConvNextForImageClassification(__lowerCAmelCase		)
            model.to(__lowerCAmelCase		)
            model.eval()
            lowercase								=      model(__lowerCAmelCase						,			labels=__lowerCAmelCase		)
            self.parent.assertEqual(result.logits.shape						,			(self.batch_size, self.num_labels)		)

      def 							A__			(		self						,			__lowerCAmelCase						,			__lowerCAmelCase						,			__lowerCAmelCase		):







            """simple docstring"""



            lowercase								=      ConvNextBackbone(config=__lowerCAmelCase		)
            model.to(__lowerCAmelCase		)
            model.eval()
            lowercase								=      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, self.hidden_sizes[1], 4, 4]		)

            # verify channels
            self.parent.assertEqual(len(model.channels		)						,			len(config.out_features		)		)
            self.parent.assertListEqual(model.channels						,			config.hidden_sizes[1:]		)

            # verify backbone works with out_features=None
            lowercase								=      None
            lowercase								=      ConvNextBackbone(config=__lowerCAmelCase		)
            model.to(__lowerCAmelCase		)
            model.eval()
            lowercase								=      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, self.hidden_sizes[-1], 1, 1]		)

            # verify channels
            self.parent.assertEqual(len(model.channels		)						,			1		)
            self.parent.assertListEqual(model.channels						,			[config.hidden_sizes[-1]]		)







      def 							A__			(		self		):







            """simple docstring"""



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






@require_torch
class 					_A		(			lowerCAmelCase    ,       lowerCAmelCase    ,       unittest.TestCase      ):
      snake_case__     :  List[str]				    =      (
          (
              ConvNextModel,
              ConvNextForImageClassification,
              ConvNextBackbone,
          )
          if is_torch_available()
          else ()
      )
      snake_case__     :  Optional[Any]				    =      (
          {'feature-extraction': ConvNextModel, 'image-classification': ConvNextForImageClassification}
          if is_torch_available()
          else {}
      )

      snake_case__     :  List[str]				    =      True
      snake_case__     :  Dict				    =      False
      snake_case__     :  Optional[int]				    =      False
      snake_case__     :  Tuple				    =      False
      snake_case__     :  List[str]				    =      False

      def 							A__			(		self		):







            """simple docstring"""



            lowercase								=      ConvNextModelTester(self		)
            lowercase								=      ConfigTester(self						,			config_class=__lowerCAmelCase						,			has_text_modality=__lowerCAmelCase						,			hidden_size=37		)

      def 							A__			(		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 							A__			(		self		):







            """simple docstring"""



            return

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







            """simple docstring"""



            pass

      @unittest.skip(reason="""ConvNext does not support input and output embeddings"""		)
      def 							A__			(		self		):







            """simple docstring"""



            pass

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







            """simple docstring"""



            pass

      def 							A__			(		self		):







            """simple docstring"""



            lowercase				,				lowercase								=      self.model_tester.prepare_config_and_inputs_for_common()

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

                  lowercase								=      ["""pixel_values"""]
                  self.assertListEqual(arg_names[:1]						,			__lowerCAmelCase		)

      def 							A__			(		self		):







            """simple docstring"""



            lowercase								=      self.model_tester.prepare_config_and_inputs()
            self.model_tester.create_and_check_model(*__lowerCAmelCase		)

      def 							A__			(		self		):







            """simple docstring"""



            lowercase								=      self.model_tester.prepare_config_and_inputs()
            self.model_tester.create_and_check_backbone(*__lowerCAmelCase		)

      def 							A__			(		self		):







            """simple docstring"""



            def check_hidden_states_output(__lowerCAmelCase						,			__lowerCAmelCase						,			__lowerCAmelCase		):
                  lowercase								=      model_class(__lowerCAmelCase		)
                  model.to(__lowerCAmelCase		)
                  model.eval()

                  with torch.no_grad():
                        lowercase								=      model(**self._prepare_for_class(__lowerCAmelCase						,			__lowerCAmelCase		)		)

                  lowercase								=      outputs.encoder_hidden_states if config.is_encoder_decoder else outputs.hidden_states

                  lowercase								=      self.model_tester.num_stages
                  self.assertEqual(len(__lowerCAmelCase		)						,			expected_num_stages + 1		)

                  # ConvNext's feature maps are of shape (batch_size, num_channels, height, width)
                  self.assertListEqual(
                      list(hidden_states[0].shape[-2:]		)						,			[self.model_tester.image_size // 4, self.model_tester.image_size // 4]						,			)

            lowercase				,				lowercase								=      self.model_tester.prepare_config_and_inputs_for_common()

            for model_class in self.all_model_classes:
                  lowercase								=      True
                  check_hidden_states_output(__lowerCAmelCase						,			__lowerCAmelCase						,			__lowerCAmelCase		)

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

                  check_hidden_states_output(__lowerCAmelCase						,			__lowerCAmelCase						,			__lowerCAmelCase		)

      def 							A__			(		self		):







            """simple docstring"""



            lowercase								=      self.model_tester.prepare_config_and_inputs()
            self.model_tester.create_and_check_for_image_classification(*__lowerCAmelCase		)







      @slow
      def 							A__			(		self		):







            """simple docstring"""



            for model_name in CONVNEXT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
                  lowercase								=      ConvNextModel.from_pretrained(__lowerCAmelCase		)
                  self.assertIsNotNone(__lowerCAmelCase		)






def      UpperCAmelCase__			(							)					->       List[str]:
      '''simple docstring'''


      lowercase								=      Image.open("""./tests/fixtures/tests_samples/COCO/000000039769.png"""						)
      return image





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

      @cached_property
      def 							A__			(		self		):







            """simple docstring"""



            return AutoImageProcessor.from_pretrained("""facebook/convnext-tiny-224"""		) if is_vision_available() else None







      @slow
      def 							A__			(		self		):







            """simple docstring"""



            lowercase								=      ConvNextForImageClassification.from_pretrained("""facebook/convnext-tiny-224"""		).to(__lowerCAmelCase		)

            lowercase								=      self.default_image_processor
            lowercase								=      prepare_img()
            lowercase								=      image_processor(images=__lowerCAmelCase						,			return_tensors="""pt"""		).to(__lowerCAmelCase		)

            # forward pass
            with torch.no_grad():
                  lowercase								=      model(**__lowerCAmelCase		)

            # verify the logits
            lowercase								=      torch.Size((1, 1000)		)
            self.assertEqual(outputs.logits.shape						,			__lowerCAmelCase		)

            lowercase								=      torch.tensor([-0.0_2_6_0, -0.4_7_3_9, 0.1_9_1_1]		).to(__lowerCAmelCase		)

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






@require_torch
class 					_A		(			unittest.TestCase    ,       lowerCAmelCase      ):
      snake_case__     :  int				    =      (ConvNextBackbone,) if is_torch_available() else ()
      snake_case__     :  Tuple				    =      ConvNextConfig

      snake_case__     :  Dict				    =      False

      def 							A__			(		self		):







            """simple docstring"""



            lowercase								=      ConvNextModelTester(self		)



