






'''simple docstring'''
import functools
from math import sqrt
from time import time




def 						__SCREAMING_SNAKE_CASE   (					_UpperCamelCase  ,						*_UpperCamelCase  ,						**_UpperCamelCase							):


   """simple docstring"""




   lowercase_		:      Tuple          =       time()
   lowercase_		:      str          =       func(*_UpperCamelCase  ,						**_UpperCamelCase							)
   lowercase_		:      List[Any]          =       time()
   if int(end - start							) > 0:
      print(F"""{func.__name__} runtime: {(end - start):0.4f} s"""							)
   else:
      print(F"""{func.__name__} runtime: {(end - start) * 1000:0.4f} ms"""							)
   return output




def 						__SCREAMING_SNAKE_CASE   (					_UpperCamelCase							):


   """simple docstring"""




   if n < 0:
      raise Exception("n is negative"							)
   if n == 0:
      return [0]
   lowercase_		:      Optional[int]          =       [0, 1]
   for _ in range(n - 1							):
      fib.append(fib[-1] + fib[-2]							)
   return fib




def 						__SCREAMING_SNAKE_CASE   (					_UpperCamelCase							):


   """simple docstring"""




   def fib_recursive_term(_UpperCamelCase							) -> int:
      if i < 0:
         raise Exception("n is negative"							)
      if i < 2:
         return i
      return fib_recursive_term(i - 1							) + fib_recursive_term(i - 2							)

   if n < 0:
      raise Exception("n is negative"							)
   return [fib_recursive_term(_UpperCamelCase							) for i in range(n + 1							)]




def 						__SCREAMING_SNAKE_CASE   (					_UpperCamelCase							):


   """simple docstring"""




   @functools.cache
   def fib_recursive_term(_UpperCamelCase							) -> int:
      if i < 0:
         raise Exception("n is negative"							)
      if i < 2:
         return i
      return fib_recursive_term(i - 1							) + fib_recursive_term(i - 2							)

   if n < 0:
      raise Exception("n is negative"							)
   return [fib_recursive_term(_UpperCamelCase							) for i in range(n + 1							)]




def 						__SCREAMING_SNAKE_CASE   (					_UpperCamelCase							):


   """simple docstring"""




   if n < 0:
      raise Exception("n is negative"							)
   # Cache must be outside recursuive function
   # other it will reset every time it calls itself.
   lowercase_		:      dict[int, int]          =       {0: 0, 1: 1, 2: 1}  # Prefilled cache

   def rec_fn_memoized(_UpperCamelCase							) -> int:
      if num in cache:
         return cache[num]

      lowercase_		:      List[str]          =       rec_fn_memoized(num - 1							) + rec_fn_memoized(num - 2							)
      lowercase_		:      int          =       value
      return value

   return [rec_fn_memoized(_UpperCamelCase							) for i in range(n + 1							)]




def 						__SCREAMING_SNAKE_CASE   (					_UpperCamelCase							):


   """simple docstring"""




   if n < 0:
      raise Exception("n is negative"							)
   if n >= 1475:
      raise Exception("n is too large"							)
   lowercase_		:      Union[str, Any]          =       sqrt(5							)
   lowercase_		:      List[Any]          =       (1 + sqrt_a) / 2
   return [round(phi**i / sqrt_a							) for i in range(n + 1							)]


if __name__ == "__main__":
 UpperCamelCase__	=     30
 time_func(fib_iterative, num)
 time_func(fib_recursive, num)  # Around 3s runtime
 time_func(fib_recursive_cached, num)  # Around 0ms runtime
 time_func(fib_memoization, num)
 time_func(fib_binet, num)












'''simple docstring'''
import os
import unittest

from transformers import RealmTokenizerFast
from transformers.models.bert.tokenization_bert import (
    VOCAB_FILES_NAMES,
    BasicTokenizer,
    WordpieceTokenizer,
    _is_control,
    _is_punctuation,
    _is_whitespace,
)
from transformers.models.realm.tokenization_realm import RealmTokenizer
from transformers.testing_utils import require_tokenizers, slow

from ...test_tokenization_common import TokenizerTesterMixin, filter_non_english


@require_tokenizers
class     _UpperCAmelCase  (						snake_case			,   unittest.TestCase     ):
    __lowerCamelCase:				Optional[int]						    =      RealmTokenizer
    __lowerCamelCase:				Optional[Any]						    =      RealmTokenizerFast
    __lowerCamelCase:				Optional[int]						    =      True
    __lowerCamelCase:				str						    =      True
    __lowerCamelCase:				List[str]						    =      filter_non_english




    def 			lowerCAmelCase__			(     self					:    str     ):






       '''simple docstring'''






       super().setUp()

       lowercase_		:      Optional[int]          =       [
           "[UNK]",
           "[CLS]",
           "[SEP]",
           "[PAD]",
           "[MASK]",
           "want",
           "##want",
           "##ed",
           "wa",
           "un",
           "runn",
           "##ing",
           ",",
           "low",
           "lowest",
       ]
       lowercase_		:      List[str]          =       os.path.join(self.tmpdirname					,       VOCAB_FILES_NAMES["vocab_file"]     )
       with open(self.vocab_file					,       "w"					,       encoding="utf-8"     ) as vocab_writer:
          vocab_writer.write("".join([x + "\n" for x in vocab_tokens]     )     )




    def 			lowerCAmelCase__			(     self					:    int					,       a					:    str     ):






       '''simple docstring'''






       lowercase_		:      List[Any]          =       "UNwant\u00E9d,running"
       lowercase_		:      Dict          =       "unwanted, running"
       return input_text, output_text




    def 			lowerCAmelCase__			(     self					:    List[str]     ):






       '''simple docstring'''






       lowercase_		:      str          =       self.tokenizer_class(self.vocab_file     )

       lowercase_		:      Any          =       tokenizer.tokenize("UNwant\u00E9d,running"     )
       self.assertListEqual(a					,       ["un", "##want", "##ed", ",", "runn", "##ing"]     )
       self.assertListEqual(tokenizer.convert_tokens_to_ids(a     )					,       [9, 6, 7, 1_2, 1_0, 1_1]     )




    def 			lowerCAmelCase__			(     self					:    Union[str, Any]     ):






       '''simple docstring'''






       if not self.test_rust_tokenizer:
          return

       lowercase_		:      Optional[Any]          =       self.get_tokenizer()
       lowercase_		:      Any          =       self.get_rust_tokenizer()

       lowercase_		:      Tuple          =       "UNwant\u00E9d,running"

       lowercase_		:      List[str]          =       tokenizer.tokenize(a     )
       lowercase_		:      Union[str, Any]          =       rust_tokenizer.tokenize(a     )
       self.assertListEqual(a					,       a     )

       lowercase_		:      Dict          =       tokenizer.encode(a					,       add_special_tokens=a     )
       lowercase_		:      Dict          =       rust_tokenizer.encode(a					,       add_special_tokens=a     )
       self.assertListEqual(a					,       a     )

       lowercase_		:      List[Any]          =       self.get_rust_tokenizer()
       lowercase_		:      Any          =       tokenizer.encode(a     )
       lowercase_		:      Optional[Any]          =       rust_tokenizer.encode(a     )
       self.assertListEqual(a					,       a     )

       # With lower casing
       lowercase_		:      Union[str, Any]          =       self.get_tokenizer(do_lower_case=a     )
       lowercase_		:      Optional[Any]          =       self.get_rust_tokenizer(do_lower_case=a     )

       lowercase_		:      int          =       "UNwant\u00E9d,running"

       lowercase_		:      List[str]          =       tokenizer.tokenize(a     )
       lowercase_		:      Dict          =       rust_tokenizer.tokenize(a     )
       self.assertListEqual(a					,       a     )

       lowercase_		:      Optional[Any]          =       tokenizer.encode(a					,       add_special_tokens=a     )
       lowercase_		:      Tuple          =       rust_tokenizer.encode(a					,       add_special_tokens=a     )
       self.assertListEqual(a					,       a     )

       lowercase_		:      Dict          =       self.get_rust_tokenizer()
       lowercase_		:      Tuple          =       tokenizer.encode(a     )
       lowercase_		:      int          =       rust_tokenizer.encode(a     )
       self.assertListEqual(a					,       a     )




    def 			lowerCAmelCase__			(     self					:    List[str]     ):






       '''simple docstring'''






       lowercase_		:      Any          =       BasicTokenizer()

       self.assertListEqual(tokenizer.tokenize("ah\u535A\u63A8zz"     )					,       ["ah", "\u535A", "\u63A8", "zz"]     )




    def 			lowerCAmelCase__			(     self					:    Dict     ):






       '''simple docstring'''






       lowercase_		:      str          =       BasicTokenizer(do_lower_case=a     )

       self.assertListEqual(
           tokenizer.tokenize(" \tHeLLo!how  \n Are yoU?  "     )					,       ["hello", "!", "how", "are", "you", "?"]     )
       self.assertListEqual(tokenizer.tokenize("H\u00E9llo"     )					,       ["hello"]     )




    def 			lowerCAmelCase__			(     self					:    Any     ):






       '''simple docstring'''






       lowercase_		:      Optional[int]          =       BasicTokenizer(do_lower_case=a					,       strip_accents=a     )

       self.assertListEqual(
           tokenizer.tokenize(" \tHäLLo!how  \n Are yoU?  "     )					,       ["hällo", "!", "how", "are", "you", "?"]     )
       self.assertListEqual(tokenizer.tokenize("H\u00E9llo"     )					,       ["h\u00E9llo"]     )




    def 			lowerCAmelCase__			(     self					:    Any     ):






       '''simple docstring'''






       lowercase_		:      List[Any]          =       BasicTokenizer(do_lower_case=a					,       strip_accents=a     )

       self.assertListEqual(
           tokenizer.tokenize(" \tHäLLo!how  \n Are yoU?  "     )					,       ["hallo", "!", "how", "are", "you", "?"]     )
       self.assertListEqual(tokenizer.tokenize("H\u00E9llo"     )					,       ["hello"]     )




    def 			lowerCAmelCase__			(     self					:    Union[str, Any]     ):






       '''simple docstring'''






       lowercase_		:      Dict          =       BasicTokenizer(do_lower_case=a     )

       self.assertListEqual(
           tokenizer.tokenize(" \tHäLLo!how  \n Are yoU?  "     )					,       ["hallo", "!", "how", "are", "you", "?"]     )
       self.assertListEqual(tokenizer.tokenize("H\u00E9llo"     )					,       ["hello"]     )




    def 			lowerCAmelCase__			(     self					:    Union[str, Any]     ):






       '''simple docstring'''






       lowercase_		:      Any          =       BasicTokenizer(do_lower_case=a     )

       self.assertListEqual(
           tokenizer.tokenize(" \tHeLLo!how  \n Are yoU?  "     )					,       ["HeLLo", "!", "how", "Are", "yoU", "?"]     )




    def 			lowerCAmelCase__			(     self					:    str     ):






       '''simple docstring'''






       lowercase_		:      Union[str, Any]          =       BasicTokenizer(do_lower_case=a					,       strip_accents=a     )

       self.assertListEqual(
           tokenizer.tokenize(" \tHäLLo!how  \n Are yoU?  "     )					,       ["HäLLo", "!", "how", "Are", "yoU", "?"]     )




    def 			lowerCAmelCase__			(     self					:    Tuple     ):






       '''simple docstring'''






       lowercase_		:      str          =       BasicTokenizer(do_lower_case=a					,       strip_accents=a     )

       self.assertListEqual(
           tokenizer.tokenize(" \tHäLLo!how  \n Are yoU?  "     )					,       ["HaLLo", "!", "how", "Are", "yoU", "?"]     )




    def 			lowerCAmelCase__			(     self					:    Optional[Any]     ):






       '''simple docstring'''






       lowercase_		:      List[Any]          =       BasicTokenizer(do_lower_case=a					,       never_split=["[UNK]"]     )

       self.assertListEqual(
           tokenizer.tokenize(" \tHeLLo!how  \n Are yoU? [UNK]"     )					,       ["HeLLo", "!", "how", "Are", "yoU", "?", "[UNK]"]     )




    def 			lowerCAmelCase__			(     self					:    Tuple     ):






       '''simple docstring'''






       lowercase_		:      int          =       ["[UNK]", "[CLS]", "[SEP]", "want", "##want", "##ed", "wa", "un", "runn", "##ing"]

       lowercase_		:      Tuple          =       {}
       for i, token in enumerate(a     ):
          lowercase_		:      Union[str, Any]          =       i
       lowercase_		:      List[str]          =       WordpieceTokenizer(vocab=a					,       unk_token="[UNK]"     )

       self.assertListEqual(tokenizer.tokenize(""     )					,       []     )

       self.assertListEqual(tokenizer.tokenize("unwanted running"     )					,       ["un", "##want", "##ed", "runn", "##ing"]     )

       self.assertListEqual(tokenizer.tokenize("unwantedX running"     )					,       ["[UNK]", "runn", "##ing"]     )




    def 			lowerCAmelCase__			(     self					:    str     ):






       '''simple docstring'''






       self.assertTrue(_is_whitespace(" "     )     )
       self.assertTrue(_is_whitespace("\t"     )     )
       self.assertTrue(_is_whitespace("\r"     )     )
       self.assertTrue(_is_whitespace("\n"     )     )
       self.assertTrue(_is_whitespace("\u00A0"     )     )

       self.assertFalse(_is_whitespace("A"     )     )
       self.assertFalse(_is_whitespace("-"     )     )




    def 			lowerCAmelCase__			(     self					:    Tuple     ):






       '''simple docstring'''






       self.assertTrue(_is_control("\u0005"     )     )

       self.assertFalse(_is_control("A"     )     )
       self.assertFalse(_is_control(" "     )     )
       self.assertFalse(_is_control("\t"     )     )
       self.assertFalse(_is_control("\r"     )     )




    def 			lowerCAmelCase__			(     self					:    List[str]     ):






       '''simple docstring'''






       self.assertTrue(_is_punctuation("-"     )     )
       self.assertTrue(_is_punctuation("$"     )     )
       self.assertTrue(_is_punctuation("`"     )     )
       self.assertTrue(_is_punctuation("."     )     )

       self.assertFalse(_is_punctuation("A"     )     )
       self.assertFalse(_is_punctuation(" "     )     )




    def 			lowerCAmelCase__			(     self					:    List[str]     ):






       '''simple docstring'''






       lowercase_		:      Dict          =       self.get_tokenizer()

       # Example taken from the issue https://github.com/huggingface/tokenizers/issues/340
       self.assertListEqual([tokenizer.tokenize(a     ) for t in ["Test", "\xad", "test"]]					,       [["[UNK]"], [], ["[UNK]"]]     )

       if self.test_rust_tokenizer:
          lowercase_		:      Dict          =       self.get_rust_tokenizer()
          self.assertListEqual(
              [rust_tokenizer.tokenize(a     ) for t in ["Test", "\xad", "test"]]					,       [["[UNK]"], [], ["[UNK]"]]     )




    @slow
    def 			lowerCAmelCase__			(     self					:    List[str]     ):






       '''simple docstring'''






       lowercase_		:      Dict          =       self.tokenizer_class.from_pretrained("bert-base-uncased"     )

       lowercase_		:      List[str]          =       tokenizer.encode("sequence builders"					,       add_special_tokens=a     )
       lowercase_		:      Optional[Any]          =       tokenizer.encode("multi-sequence build"					,       add_special_tokens=a     )

       lowercase_		:      Optional[Any]          =       tokenizer.build_inputs_with_special_tokens(a     )
       lowercase_		:      List[str]          =       tokenizer.build_inputs_with_special_tokens(a					,       a     )

       assert encoded_sentence == [1_0_1] + text + [1_0_2]
       assert encoded_pair == [1_0_1] + text + [1_0_2] + text_a + [1_0_2]




    def 			lowerCAmelCase__			(     self					:    List[str]     ):






       '''simple docstring'''






       for tokenizer, pretrained_name, kwargs in self.tokenizers_list:
          with self.subTest(f"""{tokenizer.__class__.__name__} ({pretrained_name})"""     ):
             lowercase_		:      Any          =       self.rust_tokenizer_class.from_pretrained(a					,       **a     )

             lowercase_		:      Dict          =       f"""A, naïve {tokenizer_r.mask_token} AllenNLP sentence."""
             lowercase_		:      Union[str, Any]          =       tokenizer_r.encode_plus(
                 a					,       return_attention_mask=a					,       return_token_type_ids=a					,       return_offsets_mapping=a					,       add_special_tokens=a					,       )

             lowercase_		:      Optional[Any]          =       tokenizer_r.do_lower_case if hasattr(a					,       "do_lower_case"     ) else False
             lowercase_		:      int          =       (
                 [
                     ((0, 0), tokenizer_r.cls_token),
                     ((0, 1), "A"),
                     ((1, 2), ","),
                     ((3, 5), "na"),
                     ((5, 6), "##ï"),
                     ((6, 8), "##ve"),
                     ((9, 1_5), tokenizer_r.mask_token),
                     ((1_6, 2_1), "Allen"),
                     ((2_1, 2_3), "##NL"),
                     ((2_3, 2_4), "##P"),
                     ((2_5, 3_3), "sentence"),
                     ((3_3, 3_4), "."),
                     ((0, 0), tokenizer_r.sep_token),
                 ]
                 if not do_lower_case
                 else [
                     ((0, 0), tokenizer_r.cls_token),
                     ((0, 1), "a"),
                     ((1, 2), ","),
                     ((3, 8), "naive"),
                     ((9, 1_5), tokenizer_r.mask_token),
                     ((1_6, 2_1), "allen"),
                     ((2_1, 2_3), "##nl"),
                     ((2_3, 2_4), "##p"),
                     ((2_5, 3_3), "sentence"),
                     ((3_3, 3_4), "."),
                     ((0, 0), tokenizer_r.sep_token),
                 ]
             )

             self.assertEqual(
                 [e[1] for e in expected_results]					,       tokenizer_r.convert_ids_to_tokens(tokens["input_ids"]     )     )
             self.assertEqual([e[0] for e in expected_results]					,       tokens["offset_mapping"]     )





    @slow
    def 			lowerCAmelCase__			(     self					:    str     ):






       '''simple docstring'''






       for tokenizer, pretrained_name, kwargs in self.tokenizers_list:
          with self.subTest(f"""{tokenizer.__class__.__name__} ({pretrained_name})"""     ):
             lowercase_		:      Optional[Any]          =       self.rust_tokenizer_class.from_pretrained(a					,       **a     )
             lowercase_		:      List[str]          =       self.tokenizer_class.from_pretrained(a					,       **a     )
             lowercase_		:      List[str]          =       [["Hello world!", "Nice to meet you!"], ["The cute cat.", "The adorable dog."]]

             lowercase_		:      int          =       tokenizer_r.batch_encode_candidates(a					,       max_length=1_0					,       return_tensors="np"     )
             lowercase_		:      List[str]          =       tokenizer_p.batch_encode_candidates(a					,       max_length=1_0					,       return_tensors="np"     )

             lowercase_		:      Any          =       (2, 2, 1_0)

             self.assertEqual(encoded_sentence_r["input_ids"].shape					,       a     )
             self.assertEqual(encoded_sentence_r["attention_mask"].shape					,       a     )
             self.assertEqual(encoded_sentence_r["token_type_ids"].shape					,       a     )

             self.assertEqual(encoded_sentence_p["input_ids"].shape					,       a     )
             self.assertEqual(encoded_sentence_p["attention_mask"].shape					,       a     )
             self.assertEqual(encoded_sentence_p["token_type_ids"].shape					,       a     )




