


from __future__ import annotations

import random

# Maximum size of the population.  Bigger could be faster but is more memory expensive.
__UpperCamelCase       :       Tuple						       =				200
# Number of elements selected in every generation of evolution. The selection takes
# place from best to worst of that generation and must be smaller than N_POPULATION.
__UpperCamelCase       :       Dict						       =				50
# Probability that an element of a generation can mutate, changing one of its genes.
# This will guarantee that all genes will be used during evolution.
__UpperCamelCase       :       List[str]						       =				0.4
# Just a seed to improve randomness required by the algorithm.
random.seed(random.randint(0, 1000))

def 			_a  (				SCREAMING_SNAKE_CASE	:				str    , SCREAMING_SNAKE_CASE	:				str     ):







 """simple docstring"""



 UpperCamelCase__					:    Tuple          =   len([g for position, g in enumerate(SCREAMING_SNAKE_CASE     ) if g == main_target[position]]     )
 return (item, float(SCREAMING_SNAKE_CASE     ))

def 			_a  (				SCREAMING_SNAKE_CASE	:				str    , SCREAMING_SNAKE_CASE	:				str     ):







 """simple docstring"""



 UpperCamelCase__					:    int          =   random.randint(0    , len(SCREAMING_SNAKE_CASE     ) - 1     )
 UpperCamelCase__					:    str          =   parent_a[:random_slice] + parent_a[random_slice:]
 UpperCamelCase__					:    Optional[int]          =   parent_a[:random_slice] + parent_a[random_slice:]
 return (child_a, child_a)

def 			_a  (				SCREAMING_SNAKE_CASE	:				str    , SCREAMING_SNAKE_CASE	:				list[str]     ):







 """simple docstring"""



 UpperCamelCase__					:    List[str]          =   list(SCREAMING_SNAKE_CASE     )
 if random.uniform(0    , 1     ) < MUTATION_PROBABILITY:
  UpperCamelCase__					:    Optional[Any]          =   random.choice(SCREAMING_SNAKE_CASE     )
 return "".join(SCREAMING_SNAKE_CASE     )

def 			_a  (				SCREAMING_SNAKE_CASE	:				tuple[str, float]    , SCREAMING_SNAKE_CASE	:				list[tuple[str, float]]    , SCREAMING_SNAKE_CASE	:				list[str]    , ):







 """simple docstring"""



 UpperCamelCase__					:    Optional[Any]          =   []
 # Generate more children proportionally to the fitness score.
 UpperCamelCase__					:    List[Any]          =   int(parent_a[1] * 100     ) + 1
 UpperCamelCase__					:    Any          =   10 if child_n >= 10 else child_n
 for _ in range(SCREAMING_SNAKE_CASE     ):
  UpperCamelCase__					:    int          =   population_score[random.randint(0    , SCREAMING_SNAKE_CASE     )][0]

  UpperCamelCase__       ,				UpperCamelCase__					:    List[str]          =   crossover(parent_a[0]    , SCREAMING_SNAKE_CASE     )
  # Append new string to the population list.
  pop.append(mutate(SCREAMING_SNAKE_CASE    , SCREAMING_SNAKE_CASE     )     )
  pop.append(mutate(SCREAMING_SNAKE_CASE    , SCREAMING_SNAKE_CASE     )     )
 return pop

def 			_a  (				SCREAMING_SNAKE_CASE	:				str    , SCREAMING_SNAKE_CASE	:				list[str]    , SCREAMING_SNAKE_CASE	:				bool = True     ):







 """simple docstring"""



 if N_POPULATION < N_SELECTED:
  UpperCamelCase__					:    Tuple          =   F"{N_POPULATION} must be bigger than {N_SELECTED}"
  raise ValueError(SCREAMING_SNAKE_CASE     )
 # Verify that the target contains no genes besides the ones inside genes variable.
 UpperCamelCase__					:    Optional[int]          =   sorted({c for c in target if c not in genes}     )
 if not_in_genes_list:
  UpperCamelCase__					:    Any          =   F"{not_in_genes_list} is not in genes list, evolution cannot converge"
  raise ValueError(SCREAMING_SNAKE_CASE     )

 # Generate random starting population.
 UpperCamelCase__					:    Union[str, Any]          =   []
 for _ in range(SCREAMING_SNAKE_CASE     ):
  population.append(''''''.join([random.choice(SCREAMING_SNAKE_CASE     ) for i in range(len(SCREAMING_SNAKE_CASE     )     )]     )     )

 # Just some logs to know what the algorithms is doing.
 UpperCamelCase__       ,				UpperCamelCase__					:    Tuple          =   0, 0

 # This loop will end when we find a perfect match for our target.
 while True:
  generation += 1
  total_population += len(SCREAMING_SNAKE_CASE     )

  # Random population created. Now it's time to evaluate.

  # Adding a bit of concurrency can make everything faster,
  #
  # import concurrent.futures
  # population_score: list[tuple[str, float]] = []
  # with concurrent.futures.ThreadPoolExecutor(
  #                                   max_workers=NUM_WORKERS) as executor:
  #     futures = {executor.submit(evaluate, item) for item in population}
  #     concurrent.futures.wait(futures)
  #     population_score = [item.result() for item in futures]
  #
  # but with a simple algorithm like this, it will probably be slower.
  # We just need to call evaluate for every item inside the population.
  UpperCamelCase__					:    Optional[int]          =   [evaluate(SCREAMING_SNAKE_CASE    , SCREAMING_SNAKE_CASE     ) for item in population]

  # Check if there is a matching evolution.
  UpperCamelCase__					:    int          =   sorted(SCREAMING_SNAKE_CASE    , key=lambda SCREAMING_SNAKE_CASE     : x[1]    , reverse=SCREAMING_SNAKE_CASE     )
  if population_score[0][0] == target:
   return (generation, total_population, population_score[0][0])

  # Print the best result every 10 generation.
  # Just to know that the algorithm is working.
  if debug and generation % 10 == 0:
   print(
       F"\nGeneration: {generation}"
       F"\nTotal Population:{total_population}"
       F"\nBest score: {population_score[0][1]}"
       F"\nBest string: {population_score[0][0]}"     )

  # Flush the old population, keeping some of the best evolutions.
  # Keeping this avoid regression of evolution.
  UpperCamelCase__					:    Any          =   population[: int(N_POPULATION / 3     )]
  population.clear()
  population.extend(SCREAMING_SNAKE_CASE     )
  # Normalize population score to be between 0 and 1.
  UpperCamelCase__					:    List[str]          =   [
      (item, score / len(SCREAMING_SNAKE_CASE     )) for item, score in population_score
  ]

  # This is selection
  for i in range(SCREAMING_SNAKE_CASE     ):
   population.extend(select(population_score[int(SCREAMING_SNAKE_CASE     )]    , SCREAMING_SNAKE_CASE    , SCREAMING_SNAKE_CASE     )     )
   # Check if the population has already reached the maximum value and if so,
   # break the cycle.  If this check is disabled, the algorithm will take
   # forever to compute large strings, but will also calculate small strings in
   # a far fewer generations.
   if len(SCREAMING_SNAKE_CASE     ) > N_POPULATION:
    break


if __name__ == "__main__":
       __UpperCamelCase       :       Optional[Any]						       =				(
           "This is a genetic algorithm to evaluate, combine, evolve, and mutate a string!"
       )
       __UpperCamelCase       :       str						       =				list(
           " ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklm"
           "nopqrstuvwxyz.,;!?+-*#@^'èéòà€ù=)(&%$£/\\"
       )
       __UpperCamelCase       ,						__UpperCamelCase       ,						__UpperCamelCase       :       Dict						       =				basic(target_str, genes_list)
       print(
           f"\nGeneration: {generation}\nTotal Population: {population}\nTarget: {target}"
       )






import os
import sys
import tempfile
import unittest
import unittest.mock as mock
from pathlib import Path

from huggingface_hub import HfFolder, delete_repo
from huggingface_hub.file_download import http_get
from requests.exceptions import HTTPError

from transformers import (
    AlbertTokenizer,
    AutoTokenizer,
    BertTokenizer,
    BertTokenizerFast,
    GPTaTokenizerFast,
    is_tokenizers_available,
)
from transformers.testing_utils import TOKEN, USER, is_staging_test, require_tokenizers
from transformers.tokenization_utils import Trie


sys.path.append(str(Path(__file__).parent.parent / "utils"))

from test_module.custom_tokenization import CustomTokenizer  # noqa E402


if is_tokenizers_available():
       from test_module.custom_tokenization_fast import CustomTokenizerFast

class       __magic_name__	(     unittest.TestCase):


     def      UpperCAmelCase__	(      self							:     Union[str, Any]			)  ->      int:





      '''simple docstring'''






      UpperCamelCase__					:    int          =   mock.Mock()
      UpperCamelCase__					:    Tuple          =   500
      UpperCamelCase__					:    Dict          =   {}
      UpperCamelCase__					:    Dict          =   HTTPError
      UpperCamelCase__					:    Optional[Any]          =   {}

      # Download this model to make sure it's in the cache.
      UpperCamelCase__					:    List[Any]          =   BertTokenizer.from_pretrained('''hf-internal-testing/tiny-random-bert'''			)

      # Under the mock environment we get a 500 error when trying to reach the tokenizer.
      with mock.patch('''requests.Session.request'''							,	return_value=lowerCamelCase__			) as mock_head:
       UpperCamelCase__					:    Any          =   BertTokenizer.from_pretrained('''hf-internal-testing/tiny-random-bert'''			)
       # This check we did call the fake head request
       mock_head.assert_called()


     @require_tokenizers
     def      UpperCAmelCase__	(      self							:     str			)  ->      Any:





      '''simple docstring'''






      UpperCamelCase__					:    Union[str, Any]          =   mock.Mock()
      UpperCamelCase__					:    Any          =   500
      UpperCamelCase__					:    str          =   {}
      UpperCamelCase__					:    Optional[Any]          =   HTTPError
      UpperCamelCase__					:    Tuple          =   {}

      # Download this model to make sure it's in the cache.
      UpperCamelCase__					:    Optional[Any]          =   GPTaTokenizerFast.from_pretrained('''gpt2'''			)

      # Under the mock environment we get a 500 error when trying to reach the tokenizer.
      with mock.patch('''requests.Session.request'''							,	return_value=lowerCamelCase__			) as mock_head:
       UpperCamelCase__					:    str          =   GPTaTokenizerFast.from_pretrained('''gpt2'''			)
       # This check we did call the fake head request
       mock_head.assert_called()


     def      UpperCAmelCase__	(      self							:     Any			)  ->      List[str]:





      '''simple docstring'''






      try:
       UpperCamelCase__					:    Dict          =   tempfile.mktemp()
       with open(lowerCamelCase__							,	'''wb'''			) as f:
        http_get('''https://huggingface.co/albert-base-v1/resolve/main/spiece.model'''							,	lowerCamelCase__			)

       UpperCamelCase__					:    Dict          =   AlbertTokenizer.from_pretrained(lowerCamelCase__			)
      finally:
       os.remove(lowerCamelCase__			)

      # Supporting this legacy load introduced a weird bug where the tokenizer would load local files if they are in
      # the current folder and have the right name.
      if os.path.isfile('''tokenizer.json'''			):
       # We skip the test if the user has a `tokenizer.json` in this folder to avoid deleting it.
       return
      try:
       with open('''tokenizer.json'''							,	'''wb'''			) as f:
        http_get('''https://huggingface.co/hf-internal-testing/tiny-random-bert/blob/main/tokenizer.json'''							,	lowerCamelCase__			)
       UpperCamelCase__					:    Union[str, Any]          =   AutoTokenizer.from_pretrained('''hf-internal-testing/tiny-random-gpt2'''			)
       # The tiny random BERT has a vocab size of 1024, tiny gpt2 as a vocab size of 1000
       self.assertEqual(tokenizer.vocab_size							,	1000			)
       # Tokenizer should depend on the remote checkpoint, not the local tokenizer.json file.

      finally:
       os.remove('''tokenizer.json'''			)


     def      UpperCAmelCase__	(      self							:     str			)  ->      int:





      '''simple docstring'''






      UpperCamelCase__					:    Any          =   AlbertTokenizer.from_pretrained('''https://huggingface.co/albert-base-v1/resolve/main/spiece.model'''			)



@is_staging_test
class       __magic_name__	(     unittest.TestCase):
     A:		List[Any]			=      ["[UNK]", "[CLS]", "[SEP]", "[PAD]", "[MASK]", "bla", "blou"]


     @classmethod
     def      UpperCAmelCase__	(      cls							:     List[str]			)  ->      int:





      '''simple docstring'''






      UpperCamelCase__					:    List[str]          =   TOKEN
      HfFolder.save_token(lowerCamelCase__			)


     @classmethod
     def      UpperCAmelCase__	(      cls							:     Any			)  ->      Optional[Any]:





      '''simple docstring'''






      try:
       delete_repo(token=cls._token							,	repo_id='''test-tokenizer'''			)
      except HTTPError:
       pass

      try:
       delete_repo(token=cls._token							,	repo_id='''valid_org/test-tokenizer-org'''			)
      except HTTPError:
       pass

      try:
       delete_repo(token=cls._token							,	repo_id='''test-dynamic-tokenizer'''			)
      except HTTPError:
       pass


     def      UpperCAmelCase__	(      self							:     Union[str, Any]			)  ->      Optional[int]:





      '''simple docstring'''






      with tempfile.TemporaryDirectory() as tmp_dir:
       UpperCamelCase__					:    int          =   os.path.join(lowerCamelCase__							,	'''vocab.txt'''			)
       with open(lowerCamelCase__							,	'''w'''							,	encoding='''utf-8'''			) as vocab_writer:
        vocab_writer.write(''''''.join([x + '''\n''' for x in self.vocab_tokens]			)			)
       UpperCamelCase__					:    Tuple          =   BertTokenizer(lowerCamelCase__			)

      tokenizer.push_to_hub('''test-tokenizer'''							,	use_auth_token=self._token			)
      UpperCamelCase__					:    Union[str, Any]          =   BertTokenizer.from_pretrained(F"{USER}/test-tokenizer"			)
      self.assertDictEqual(new_tokenizer.vocab							,	tokenizer.vocab			)

      # Reset repo
      delete_repo(token=self._token							,	repo_id='''test-tokenizer'''			)

      # Push to hub via save_pretrained
      with tempfile.TemporaryDirectory() as tmp_dir:
       tokenizer.save_pretrained(lowerCamelCase__							,	repo_id='''test-tokenizer'''							,	push_to_hub=lowerCamelCase__							,	use_auth_token=self._token			)

      UpperCamelCase__					:    str          =   BertTokenizer.from_pretrained(F"{USER}/test-tokenizer"			)
      self.assertDictEqual(new_tokenizer.vocab							,	tokenizer.vocab			)


     def      UpperCAmelCase__	(      self							:     str			)  ->      Optional[int]:





      '''simple docstring'''






      with tempfile.TemporaryDirectory() as tmp_dir:
       UpperCamelCase__					:    Dict          =   os.path.join(lowerCamelCase__							,	'''vocab.txt'''			)
       with open(lowerCamelCase__							,	'''w'''							,	encoding='''utf-8'''			) as vocab_writer:
        vocab_writer.write(''''''.join([x + '''\n''' for x in self.vocab_tokens]			)			)
       UpperCamelCase__					:    List[str]          =   BertTokenizer(lowerCamelCase__			)

      tokenizer.push_to_hub('''valid_org/test-tokenizer-org'''							,	use_auth_token=self._token			)
      UpperCamelCase__					:    Optional[Any]          =   BertTokenizer.from_pretrained('''valid_org/test-tokenizer-org'''			)
      self.assertDictEqual(new_tokenizer.vocab							,	tokenizer.vocab			)

      # Reset repo
      delete_repo(token=self._token							,	repo_id='''valid_org/test-tokenizer-org'''			)

      # Push to hub via save_pretrained
      with tempfile.TemporaryDirectory() as tmp_dir:
       tokenizer.save_pretrained(
           lowerCamelCase__							,	repo_id='''valid_org/test-tokenizer-org'''							,	push_to_hub=lowerCamelCase__							,	use_auth_token=self._token			)

      UpperCamelCase__					:    Union[str, Any]          =   BertTokenizer.from_pretrained('''valid_org/test-tokenizer-org'''			)
      self.assertDictEqual(new_tokenizer.vocab							,	tokenizer.vocab			)


     @require_tokenizers
     def      UpperCAmelCase__	(      self							:     List[str]			)  ->      int:





      '''simple docstring'''






      CustomTokenizer.register_for_auto_class()
      with tempfile.TemporaryDirectory() as tmp_dir:
       UpperCamelCase__					:    List[Any]          =   os.path.join(lowerCamelCase__							,	'''vocab.txt'''			)
       with open(lowerCamelCase__							,	'''w'''							,	encoding='''utf-8'''			) as vocab_writer:
        vocab_writer.write(''''''.join([x + '''\n''' for x in self.vocab_tokens]			)			)
       UpperCamelCase__					:    Any          =   CustomTokenizer(lowerCamelCase__			)

      # No fast custom tokenizer
      tokenizer.push_to_hub('''test-dynamic-tokenizer'''							,	use_auth_token=self._token			)

      UpperCamelCase__					:    str          =   AutoTokenizer.from_pretrained(F"{USER}/test-dynamic-tokenizer"							,	trust_remote_code=lowerCamelCase__			)
      # Can't make an isinstance check because the new_model.config is from the CustomTokenizer class of a dynamic module
      self.assertEqual(tokenizer.__class__.__name__							,	'''CustomTokenizer'''			)

      # Fast and slow custom tokenizer
      CustomTokenizerFast.register_for_auto_class()
      with tempfile.TemporaryDirectory() as tmp_dir:
       UpperCamelCase__					:    List[Any]          =   os.path.join(lowerCamelCase__							,	'''vocab.txt'''			)
       with open(lowerCamelCase__							,	'''w'''							,	encoding='''utf-8'''			) as vocab_writer:
        vocab_writer.write(''''''.join([x + '''\n''' for x in self.vocab_tokens]			)			)

       UpperCamelCase__					:    List[Any]          =   BertTokenizerFast.from_pretrained(lowerCamelCase__			)
       bert_tokenizer.save_pretrained(lowerCamelCase__			)
       UpperCamelCase__					:    Optional[int]          =   CustomTokenizerFast.from_pretrained(lowerCamelCase__			)

      tokenizer.push_to_hub('''test-dynamic-tokenizer'''							,	use_auth_token=self._token			)

      UpperCamelCase__					:    str          =   AutoTokenizer.from_pretrained(F"{USER}/test-dynamic-tokenizer"							,	trust_remote_code=lowerCamelCase__			)
      # Can't make an isinstance check because the new_model.config is from the FakeConfig class of a dynamic module
      self.assertEqual(tokenizer.__class__.__name__							,	'''CustomTokenizerFast'''			)
      UpperCamelCase__					:    int          =   AutoTokenizer.from_pretrained(
          F"{USER}/test-dynamic-tokenizer"							,	use_fast=lowerCamelCase__							,	trust_remote_code=lowerCamelCase__			)
      # Can't make an isinstance check because the new_model.config is from the FakeConfig class of a dynamic module
      self.assertEqual(tokenizer.__class__.__name__							,	'''CustomTokenizer'''			)



class       __magic_name__	(     unittest.TestCase):


     def      UpperCAmelCase__	(      self							:     str			)  ->      Dict:





      '''simple docstring'''






      UpperCamelCase__					:    Any          =   Trie()
      trie.add('''Hello 友達'''			)
      self.assertEqual(trie.data							,	{'''H''': {'''e''': {'''l''': {'''l''': {'''o''': {''' ''': {'''友''': {'''達''': {'''''': 1}}}}}}}}}			)
      trie.add('''Hello'''			)
      trie.data
      self.assertEqual(trie.data							,	{'''H''': {'''e''': {'''l''': {'''l''': {'''o''': {'''''': 1, ''' ''': {'''友''': {'''達''': {'''''': 1}}}}}}}}}			)


     def      UpperCAmelCase__	(      self							:     str			)  ->      str:





      '''simple docstring'''






      UpperCamelCase__					:    Dict          =   Trie()
      self.assertEqual(trie.split('''[CLS] This is a extra_id_100'''			)							,	['''[CLS] This is a extra_id_100''']			)
      trie.add('''[CLS]'''			)
      trie.add('''extra_id_1'''			)
      trie.add('''extra_id_100'''			)
      self.assertEqual(trie.split('''[CLS] This is a extra_id_100'''			)							,	['''[CLS]''', ''' This is a ''', '''extra_id_100''']			)


     def      UpperCAmelCase__	(      self							:     int			)  ->      Optional[int]:





      '''simple docstring'''






      UpperCamelCase__					:    int          =   Trie()
      trie.add('''A'''			)
      self.assertEqual(trie.split('''ABC'''			)							,	['''A''', '''BC''']			)
      self.assertEqual(trie.split('''BCA'''			)							,	['''BC''', '''A''']			)


     def      UpperCAmelCase__	(      self							:     Dict			)  ->      Optional[int]:





      '''simple docstring'''






      UpperCamelCase__					:    Any          =   Trie()
      trie.add('''TOKEN]'''			)
      trie.add('''[SPECIAL_TOKEN]'''			)
      self.assertEqual(trie.split('''This is something [SPECIAL_TOKEN]'''			)							,	['''This is something ''', '''[SPECIAL_TOKEN]''']			)


     def      UpperCAmelCase__	(      self							:     List[str]			)  ->      Optional[Any]:





      '''simple docstring'''






      UpperCamelCase__					:    List[Any]          =   Trie()
      trie.add('''A'''			)
      trie.add('''P'''			)
      trie.add('''[SPECIAL_TOKEN]'''			)
      self.assertEqual(trie.split('''This is something [SPECIAL_TOKEN]'''			)							,	['''This is something ''', '''[SPECIAL_TOKEN]''']			)


     def      UpperCAmelCase__	(      self							:     Any			)  ->      List[str]:





      '''simple docstring'''






      UpperCamelCase__					:    List[Any]          =   Trie()
      trie.add('''AB'''			)
      trie.add('''B'''			)
      trie.add('''C'''			)
      self.assertEqual(trie.split('''ABC'''			)							,	['''AB''', '''C''']			)


     def      UpperCAmelCase__	(      self							:     Optional[int]			)  ->      int:





      '''simple docstring'''






      UpperCamelCase__					:    int          =   Trie()
      trie.add('''ABC'''			)
      trie.add('''B'''			)
      trie.add('''CD'''			)
      self.assertEqual(trie.split('''ABCD'''			)							,	['''ABC''', '''D''']			)


     def      UpperCAmelCase__	(      self							:     Optional[int]			)  ->      Union[str, Any]:





      '''simple docstring'''






      UpperCamelCase__					:    Dict          =   Trie()
      UpperCamelCase__					:    Optional[Any]          =   trie.cut_text('''ABC'''							,	[0, 0, 2, 1, 2, 3]			)
      self.assertEqual(lowerCamelCase__							,	['''AB''', '''C''']			)


