



"""simple docstring"""
import unittest

from transformers import BigBirdTokenizer, BigBirdTokenizerFast
from transformers.testing_utils import get_tests_dir, require_sentencepiece, require_tokenizers, require_torch, slow
from transformers.utils import cached_property

from ...test_tokenization_common import TokenizerTesterMixin


UpperCAmelCase  :						Tuple	=       """▁"""

UpperCAmelCase  :						Optional[int]	=       get_tests_dir("fixtures/test_sentencepiece.model")


@require_sentencepiece
@require_tokenizers
class       SCREAMING_SNAKE_CASE__       (							a__					,     unittest.TestCase      ):
    lowercase__          =      BigBirdTokenizer
    lowercase__          =      BigBirdTokenizerFast
    lowercase__          =      True
    lowercase__          =      True

    def     _UpperCAmelCase		( self	: Any):







      """simple docstring"""







      super().setUp()

      lowercase_	    =       self.tokenizer_class(__lowerCAmelCase       ,     keep_accents=__lowerCAmelCase)
      tokenizer.save_pretrained(self.tmpdirname)

    def     _UpperCAmelCase		( self	: Dict):







      """simple docstring"""







      lowercase_	    =       '''<s>'''
      lowercase_	    =       1

      self.assertEqual(self.get_tokenizer()._convert_token_to_id(__lowerCAmelCase)       ,     __lowerCAmelCase)
      self.assertEqual(self.get_tokenizer()._convert_id_to_token(__lowerCAmelCase)       ,     __lowerCAmelCase)

    def     _UpperCAmelCase		( self	: Dict):







      """simple docstring"""







      lowercase_	    =       list(self.get_tokenizer().get_vocab().keys())

      self.assertEqual(vocab_keys[0]       ,     """<unk>""")
      self.assertEqual(vocab_keys[1]       ,     """<s>""")
      self.assertEqual(vocab_keys[-1]       ,     """[MASK]""")
      self.assertEqual(len(__lowerCAmelCase)       ,     1_0_0_4)

    def     _UpperCAmelCase		( self	: Optional[Any]):







      """simple docstring"""







      self.assertEqual(self.get_tokenizer().vocab_size       ,     1_0_0_0)

    def     _UpperCAmelCase		( self	: Optional[int]):







      """simple docstring"""







      if not self.test_rust_tokenizer:
        return

      lowercase_	    =       self.get_tokenizer()
      lowercase_	    =       self.get_rust_tokenizer()

      lowercase_	    =       '''I was born in 92000, and this is falsé.'''

      lowercase_	    =       tokenizer.tokenize(__lowerCAmelCase)
      lowercase_	    =       rust_tokenizer.tokenize(__lowerCAmelCase)
      self.assertListEqual(__lowerCAmelCase       ,     __lowerCAmelCase)

      lowercase_	    =       tokenizer.encode(__lowerCAmelCase       ,     add_special_tokens=__lowerCAmelCase)
      lowercase_	    =       rust_tokenizer.encode(__lowerCAmelCase       ,     add_special_tokens=__lowerCAmelCase)
      self.assertListEqual(__lowerCAmelCase       ,     __lowerCAmelCase)

      lowercase_	    =       self.get_rust_tokenizer()
      lowercase_	    =       tokenizer.encode(__lowerCAmelCase)
      lowercase_	    =       rust_tokenizer.encode(__lowerCAmelCase)
      self.assertListEqual(__lowerCAmelCase       ,     __lowerCAmelCase)

    def     _UpperCAmelCase		( self	: Any):







      """simple docstring"""







      lowercase_	    =       BigBirdTokenizer(__lowerCAmelCase       ,     keep_accents=__lowerCAmelCase)

      lowercase_	    =       tokenizer.tokenize("""This is a test""")
      self.assertListEqual(__lowerCAmelCase       ,     ["""▁This""", """▁is""", """▁a""", """▁t""", """est"""])

      self.assertListEqual(
          tokenizer.convert_tokens_to_ids(__lowerCAmelCase)       ,     [2_8_5, 4_6, 1_0, 1_7_0, 3_8_2]       ,     )

      lowercase_	    =       tokenizer.tokenize("""I was born in 92000, and this is falsé.""")
      self.assertListEqual(
          __lowerCAmelCase       ,     [
              SPIECE_UNDERLINE + """I""",
              SPIECE_UNDERLINE + """was""",
              SPIECE_UNDERLINE + """b""",
              """or""",
              """n""",
              SPIECE_UNDERLINE + """in""",
              SPIECE_UNDERLINE + """""",
              """9""",
              """2""",
              """0""",
              """0""",
              """0""",
              """,""",
              SPIECE_UNDERLINE + """and""",
              SPIECE_UNDERLINE + """this""",
              SPIECE_UNDERLINE + """is""",
              SPIECE_UNDERLINE + """f""",
              """al""",
              """s""",
              """é""",
              """.""",
          ]       ,     )
      lowercase_	    =       tokenizer.convert_tokens_to_ids(__lowerCAmelCase)
      self.assertListEqual(
          __lowerCAmelCase       ,     [8, 2_1, 8_4, 5_5, 2_4, 1_9, 7, 0, 6_0_2, 3_4_7, 3_4_7, 3_4_7, 3, 1_2, 6_6, 4_6, 7_2, 8_0, 6, 0, 4]       ,     )

      lowercase_	    =       tokenizer.convert_ids_to_tokens(__lowerCAmelCase)
      self.assertListEqual(
          __lowerCAmelCase       ,     [
              SPIECE_UNDERLINE + """I""",
              SPIECE_UNDERLINE + """was""",
              SPIECE_UNDERLINE + """b""",
              """or""",
              """n""",
              SPIECE_UNDERLINE + """in""",
              SPIECE_UNDERLINE + """""",
              """<unk>""",
              """2""",
              """0""",
              """0""",
              """0""",
              """,""",
              SPIECE_UNDERLINE + """and""",
              SPIECE_UNDERLINE + """this""",
              SPIECE_UNDERLINE + """is""",
              SPIECE_UNDERLINE + """f""",
              """al""",
              """s""",
              """<unk>""",
              """.""",
          ]       ,     )

    @cached_property
    def     _UpperCAmelCase		( self	: Any):







      """simple docstring"""







      return BigBirdTokenizer.from_pretrained("""google/bigbird-roberta-base""")

    @slow
    def     _UpperCAmelCase		( self	: List[Any]):







      """simple docstring"""







      lowercase_	    =       '''Hello World!'''
      lowercase_	    =       [6_5, 1_8_5_3_6, 2_2_6_0, 1_0_1, 6_6]

      self.assertListEqual(__lowerCAmelCase       ,     self.big_tokenizer.encode(__lowerCAmelCase))

    @slow
    def     _UpperCAmelCase		( self	: Optional[int]):







      """simple docstring"""







      lowercase_	    =       (
          '''This is a very long text with a lot of weird characters, such as: . , ~ ? ( ) " [ ] ! : - . Also we will'''
          ''' add words that should not exsist and be tokenized to <unk>, such as saoneuhaoesuth'''
      )
      # fmt: off
      lowercase_	    =       [6_5, 8_7_1, 4_1_9, 3_5_8, 9_4_6, 9_9_1, 2_5_2_1, 4_5_2, 3_5_8, 1_3_5_7, 3_8_7, 7_7_5_1, 3_5_3_6, 1_1_2, 9_8_5, 4_5_6, 1_2_6, 8_6_5, 9_3_8, 5_4_0_0, 5_7_3_4, 4_5_8, 1_3_6_8, 4_6_7, 7_8_6, 2_4_6_2, 5_2_4_6, 1_1_5_9, 6_3_3, 8_6_5, 4_5_1_9, 4_5_7, 5_8_2, 8_5_2, 2_5_5_7, 4_2_7, 9_1_6, 5_0_8, 4_0_5, 3_4_3_2_4, 4_9_7, 3_9_1, 4_0_8, 1_1_3_4_2, 1_2_4_4, 3_8_5, 1_0_0, 9_3_8, 9_8_5, 4_5_6, 5_7_4, 3_6_2, 1_2_5_9_7, 3_2_0_0, 3_1_2_9, 1_1_7_2, 6_6]  # noqa: E231
      # fmt: on
      self.assertListEqual(__lowerCAmelCase       ,     self.big_tokenizer.encode(__lowerCAmelCase))

    @require_torch
    @slow
    def     _UpperCAmelCase		( self	: Dict):







      """simple docstring"""







      import torch

      from transformers import BigBirdConfig, BigBirdModel

      # Build sequence
      lowercase_	    =       list(self.big_tokenizer.get_vocab().keys())[:1_0]
      lowercase_	    =       ''' '''.join(__lowerCAmelCase)
      lowercase_	    =       self.big_tokenizer.encode_plus(__lowerCAmelCase       ,     return_tensors="""pt"""       ,     return_token_type_ids=__lowerCAmelCase)
      lowercase_	    =       self.big_tokenizer.batch_encode_plus(
          [sequence + """ """ + sequence]       ,     return_tensors="""pt"""       ,     return_token_type_ids=__lowerCAmelCase)

      lowercase_	    =       BigBirdConfig(attention_type="""original_full""")
      lowercase_	    =       BigBirdModel(__lowerCAmelCase)

      assert model.get_input_embeddings().weight.shape[0] >= self.big_tokenizer.vocab_size

      with torch.no_grad():
        model(**__lowerCAmelCase)
        model(**__lowerCAmelCase)

    @slow
    def     _UpperCAmelCase		( self	: Optional[int]):







      """simple docstring"""







      lowercase_	    =       BigBirdTokenizer.from_pretrained("""google/bigbird-roberta-base""")
      lowercase_	    =       tokenizer.decode(tokenizer("""Paris is the [MASK].""").input_ids)

      self.assertTrue(decoded_text == """[CLS] Paris is the[MASK].[SEP]""")




    @slow
    def     _UpperCAmelCase		( self	: Any):







      """simple docstring"""







      lowercase_	    =       {'''input_ids''': [[6_5, 3_9_2_8_6, 4_5_8, 3_6_3_3_5, 2_0_0_1, 4_5_6, 1_3_0_7_3, 1_3_2_6_6, 4_5_5, 1_1_3, 7_7_4_6, 1_7_4_1, 1_1_1_5_7, 3_9_1, 1_3_0_7_3, 1_3_2_6_6, 4_5_5, 1_1_3, 3_9_6_7, 3_5_4_1_2, 1_1_3, 4_9_3_6, 1_0_9, 3_8_7_0, 2_3_7_7, 1_1_3, 3_0_0_8_4, 4_5_7_2_0, 4_5_8, 1_3_4, 1_7_4_9_6, 1_1_2, 5_0_3, 1_1_6_7_2, 1_1_3, 1_1_8, 1_1_2, 5_6_6_5, 1_3_3_4_7, 3_8_6_8_7, 1_1_2, 1_4_9_6, 3_1_3_8_9, 1_1_2, 3_2_6_8, 4_7_2_6_4, 1_3_4, 9_6_2, 1_1_2, 1_6_3_7_7, 8_0_3_5, 2_3_1_3_0, 4_3_0, 1_2_1_6_9, 1_5_5_1_8, 2_8_5_9_2, 4_5_8, 1_4_6, 4_1_6_9_7, 1_0_9, 3_9_1, 1_2_1_6_9, 1_5_5_1_8, 1_6_6_8_9, 4_5_8, 1_4_6, 4_1_3_5_8, 1_0_9, 4_5_2, 7_2_6, 4_0_3_4, 1_1_1, 7_6_3, 3_5_4_1_2, 5_0_8_2, 3_8_8, 1_9_0_3, 1_1_1, 9_0_5_1, 3_9_1, 2_8_7_0, 4_8_9_1_8, 1_9_0_0, 1_1_2_3, 5_5_0, 9_9_8, 1_1_2, 9_5_8_6, 1_5_9_8_5, 4_5_5, 3_9_1, 4_1_0, 2_2_9_5_5, 3_7_6_3_6, 1_1_4, 6_6], [6_5, 4_4_8, 1_7_4_9_6, 4_1_9, 3_6_6_3, 3_8_5, 7_6_3, 1_1_3, 2_7_5_3_3, 2_8_7_0, 3_2_8_3, 1_3_0_4_3, 1_6_3_9, 2_4_7_1_3, 5_2_3, 6_5_6, 2_4_0_1_3, 1_8_5_5_0, 2_5_2_1, 5_1_7, 2_7_0_1_4, 2_1_2_4_4, 4_2_0, 1_2_1_2, 1_4_6_5, 3_9_1, 9_2_7, 4_8_3_3, 3_8_8, 5_7_8, 1_1_7_8_6, 1_1_4, 6_6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [6_5, 4_8_4, 2_1_6_9, 7_6_8_7, 2_1_9_3_2, 1_8_1_4_6, 7_2_6, 3_6_3, 1_7_0_3_2, 3_3_9_1, 1_1_4, 6_6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], '''attention_mask''': [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]}  # noqa: E501
      # fmt: on

      self.tokenizer_integration_test_util(
          expected_encoding=__lowerCAmelCase       ,     model_name="""google/bigbird-roberta-base"""       ,     revision="""215c99f1600e06f83acce68422f2035b2b5c3510"""       ,     )


'''simple docstring'''

from math import pow
def 			__UpperCamelCase       (   UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     UpperCAmelCase		,     ):
 if current_sum == needed_sum:
  # If the sum of the powers is equal to needed_sum, then we have a solution.
  solutions_count += 1
  return current_sum, solutions_count

 lowercase__				:    Optional[Any]  =					int(pow(UpperCAmelCase		,     UpperCAmelCase     )     )
 if current_sum + i_to_n <= needed_sum:
  # If the sum of the powers is less than needed_sum, then continue adding powers.
  current_sum += i_to_n
  lowercase__ ,							lowercase__				:    Dict  =					backtrack(
      UpperCAmelCase		,     UpperCAmelCase		,     current_number + 1		,     UpperCAmelCase		,     UpperCAmelCase     )
  current_sum -= i_to_n
 if i_to_n < needed_sum:
  # If the power of i is less than needed_sum, then try with the next power.
  lowercase__ ,							lowercase__				:    str  =					backtrack(
      UpperCAmelCase		,     UpperCAmelCase		,     current_number + 1		,     UpperCAmelCase		,     UpperCAmelCase     )
 return current_sum, solutions_count
def 			__UpperCamelCase       (   UpperCAmelCase		,     UpperCAmelCase     ):
 if not (1 <= needed_sum <= 1000 and 2 <= power <= 10):
  raise ValueError(
      '''Invalid input\n'''
      '''needed_sum must be between 1 and 1000, power between 2 and 10.'''     )

 return backtrack(UpperCAmelCase		,     UpperCAmelCase		,     1		,     0		,     0     )[1]  # Return the solutions_count


if __name__ == "__main__":
  import doctest

  doctest.testmod()

