





import jax
import jax.numpy as jnp
from bigbird_flax import FlaxBigBirdForNaturalQuestions
from datasets import load_from_disk

from transformers import BigBirdTokenizerFast


_lowerCamelCase       =	{0: 'null', 1: 'short', 2: 'long', 3: 'yes', 4: 'no'}
_lowerCamelCase       =	set(''.join(['‘', '’', '´', '`', '.', ',', '-', '"']))






def  SCREAMING_SNAKE_CASE__							(				UpperCamelCase__:							Any    ,      UpperCamelCase__:							int=0    ,      UpperCamelCase__:							Optional[Any]=None			):
		return [" ".join(x.split(""" """			)[begin:end]			) for x in answers if len(x.split(""" """			)			) > 1]






def  SCREAMING_SNAKE_CASE__							(				UpperCamelCase__:							Union[str, Any]    ,      UpperCamelCase__:							Union[str, Any]=False			):
		if make_sub_answers:
				# if answers are longer than one word, make sure a predictions is correct if it coresponds to the complete 1: or :-1 sub word
				# *e.g.* if the correct answer contains a prefix such as "the", or "a"
				SCREAMING_SNAKE_CASE__								=					(
				    given_answers + get_sub_answers(UpperCamelCase__    ,      begin=1			) + get_sub_answers(UpperCamelCase__    ,      end=-1			)
				)
		SCREAMING_SNAKE_CASE__								=					[]
		for answer in given_answers:
				SCREAMING_SNAKE_CASE__								=					answer.replace("""_"""    ,      """ """			).lower()
				SCREAMING_SNAKE_CASE__								=					"""""".join(c if c not in PUNCTUATION_SET_TO_EXCLUDE else """ """ for c in alias			)
				answers.append(""" """.join(alias.split()			).strip()			)
		return set(UpperCamelCase__			)






def  SCREAMING_SNAKE_CASE__							(				UpperCamelCase__:							Tuple    ,      UpperCamelCase__:							List[Any]    ,      UpperCamelCase__:							Tuple=1    ,      UpperCamelCase__:							str=100			):
		SCREAMING_SNAKE_CASE__		,  SCREAMING_SNAKE_CASE__								=					jax.lax.top_k(UpperCamelCase__    ,      UpperCamelCase__			)
		SCREAMING_SNAKE_CASE__		,  SCREAMING_SNAKE_CASE__								=					jax.lax.top_k(UpperCamelCase__    ,      UpperCamelCase__			)

		SCREAMING_SNAKE_CASE__								=					best_end_idx[:, None] - best_start_idx[None, :]
		SCREAMING_SNAKE_CASE__								=					jnp.logical_or(widths < 0    ,      widths > max_size			)
		SCREAMING_SNAKE_CASE__								=					(best_end_scores[:, None] + best_start_scores[None, :]) - (1e8 * mask)
		SCREAMING_SNAKE_CASE__								=					jnp.argmax(UpperCamelCase__			).item()

		return best_start_idx[best_score % top_k], best_end_idx[best_score // top_k]






def  SCREAMING_SNAKE_CASE__							(				UpperCamelCase__:							int			):
		SCREAMING_SNAKE_CASE__								=					sample["""question"""]["""text"""]
		SCREAMING_SNAKE_CASE__								=					sample["""document"""]["""tokens"""]["""token"""]
		SCREAMING_SNAKE_CASE__								=					sample["""document"""]["""tokens"""]["""is_html"""]
		SCREAMING_SNAKE_CASE__								=					sample["""annotations"""]["""long_answer"""]
		SCREAMING_SNAKE_CASE__								=					sample["""annotations"""]["""short_answers"""]

		SCREAMING_SNAKE_CASE__								=					""" """.join([context[i] for i in range(len(UpperCamelCase__			)			) if not is_html[i]]			)

		# 0 - No ; 1 - Yes
		for answer in sample["annotations"]["yes_no_answer"]:
				if answer == 0 or answer == 1:
						return {
						    "question": question,
						    "context": context_string,
						    "short": [],
						    "long": [],
						    "category": "no" if answer == 0 else "yes",
						}

		SCREAMING_SNAKE_CASE__								=					[]
		for s in short_answers:
				short_targets.extend(s["""text"""]			)
		SCREAMING_SNAKE_CASE__								=					list(set(UpperCamelCase__			)			)

		SCREAMING_SNAKE_CASE__								=					[]
		for s in long_answers:
				if s["start_token"] == -1:
						continue
				SCREAMING_SNAKE_CASE__								=					context[s["""start_token"""] : s["""end_token"""]]
				SCREAMING_SNAKE_CASE__								=					is_html[s["""start_token"""] : s["""end_token"""]]
				SCREAMING_SNAKE_CASE__								=					""" """.join([answer[i] for i in range(len(UpperCamelCase__			)			) if not html[i]]			)
				if new_answer not in long_targets:
						long_targets.append(UpperCamelCase__			)

		SCREAMING_SNAKE_CASE__								=					"""long_short""" if len(short_targets + long_targets			) > 0 else """null"""

		return {
		    "question": question,
		    "context": context_string,
		    "short": short_targets,
		    "long": long_targets,
		    "category": category,
		}






def  SCREAMING_SNAKE_CASE__							(				):
		SCREAMING_SNAKE_CASE__								=					load_from_disk("""natural-questions-validation"""			)
		SCREAMING_SNAKE_CASE__								=					dataset.map(UpperCamelCase__			).remove_columns(["""annotations""", """document""", """id"""]			)
		print(UpperCamelCase__			)

		SCREAMING_SNAKE_CASE__								=					dataset.filter(lambda UpperCamelCase__			: (len(x["""question"""]			) + len(x["""context"""]			)) < 4 * 4_096			)
		SCREAMING_SNAKE_CASE__								=					short_validation_dataset.filter(lambda UpperCamelCase__			: x["category"] != "null"			)
		short_validation_dataset

		SCREAMING_SNAKE_CASE__								=					"""vasudevgupta/flax-bigbird-natural-questions"""
		SCREAMING_SNAKE_CASE__								=					FlaxBigBirdForNaturalQuestions.from_pretrained(UpperCamelCase__			)
		SCREAMING_SNAKE_CASE__								=					BigBirdTokenizerFast.from_pretrained(UpperCamelCase__			)

		@jax.jit
		def forward(*UpperCamelCase__:							str    ,      **UpperCamelCase__:							Dict			):
				SCREAMING_SNAKE_CASE__		,  SCREAMING_SNAKE_CASE__		,  SCREAMING_SNAKE_CASE__								=					model(*UpperCamelCase__    ,      **UpperCamelCase__			)
				return start_logits, end_logits, jnp.argmax(UpperCamelCase__    ,      axis=-1			)

		def evaluate(UpperCamelCase__:							str			):
				# encode question and context so that they are separated by a tokenizer.sep_token and cut at max_length
				SCREAMING_SNAKE_CASE__								=					tokenizer(
				    example["""question"""]    ,      example["""context"""]    ,      return_tensors="""np"""    ,      max_length=4_096    ,      padding="""max_length"""    ,      truncation=UpperCamelCase__    ,      )

				SCREAMING_SNAKE_CASE__		,  SCREAMING_SNAKE_CASE__		,  SCREAMING_SNAKE_CASE__								=					forward(**UpperCamelCase__			)

				SCREAMING_SNAKE_CASE__								=					CATEGORY_MAPPING[category.item()]

				SCREAMING_SNAKE_CASE__								=					example["""long"""] + example["""short"""]
				if example["category"] in ["yes", "no", "null"]:
						SCREAMING_SNAKE_CASE__								=					[example["""category"""]]
				SCREAMING_SNAKE_CASE__								=					example["""category"""] != """null"""
				# Now target can be: "yes", "no", "null", "list of long & short answers"

				if predicted_category in ["yes", "no", "null"]:
						SCREAMING_SNAKE_CASE__								=					[predicted_category]
						SCREAMING_SNAKE_CASE__								=					example["""output"""] == example["""targets"""]
						SCREAMING_SNAKE_CASE__								=					predicted_category != """null"""
						return example

				SCREAMING_SNAKE_CASE__								=					38 if predicted_category == """short""" else 1_024
				SCREAMING_SNAKE_CASE__		,  SCREAMING_SNAKE_CASE__								=					get_best_valid_start_end_idx(
				    start_scores[0]    ,      end_scores[0]    ,      top_k=8    ,      max_size=UpperCamelCase__			)

				SCREAMING_SNAKE_CASE__								=					inputs["""input_ids"""][0].tolist()
				SCREAMING_SNAKE_CASE__								=					[tokenizer.decode(input_ids[start_score : end_score + 1]			)]

				SCREAMING_SNAKE_CASE__								=					expand_to_aliases(example["""targets"""]    ,      make_sub_answers=UpperCamelCase__			)
				SCREAMING_SNAKE_CASE__								=					expand_to_aliases(example["""output"""]			)

				# some preprocessing to both prediction and answer
				SCREAMING_SNAKE_CASE__								=					{"""""".join(a.split()			) for a in answers}
				SCREAMING_SNAKE_CASE__								=					{"""""".join(p.split()			) for p in predictions}
				SCREAMING_SNAKE_CASE__								=					{s for s in predictions if s not in ["""``""", """''""", """`""", """'"""]}

				# if there is a common element, it's a exact match
				SCREAMING_SNAKE_CASE__								=					len(list(answers & predictions			)			) > 0
				SCREAMING_SNAKE_CASE__								=					predicted_category != """null""" and len(UpperCamelCase__			) > 0

				return example

		SCREAMING_SNAKE_CASE__								=					short_validation_dataset.map(UpperCamelCase__			)

		SCREAMING_SNAKE_CASE__								=					len(UpperCamelCase__			)
		SCREAMING_SNAKE_CASE__								=					len(short_validation_dataset.filter(lambda UpperCamelCase__			: x["match"] == 1			)			)
		print("""EM score:"""    ,      (matched / total) * 100    ,      """%"""			)


if __name__ == "__main__":
	main()






from __future__ import annotations

from collections import deque
from queue import Queue
from timeit import timeit

_lowerCamelCase       =	{
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
}






def  SCREAMING_SNAKE_CASE__							(				UpperCamelCase__:							dict    ,      UpperCamelCase__:							str			):
		SCREAMING_SNAKE_CASE__								=					{start}
		SCREAMING_SNAKE_CASE__								=					[start]
		SCREAMING_SNAKE_CASE__								=					Queue()
		queue.put(UpperCamelCase__			)
		while not queue.empty():
				SCREAMING_SNAKE_CASE__								=					queue.get()
				for w in graph[v]:
						if w not in explored:
								explored.add(UpperCamelCase__			)
								result.append(UpperCamelCase__			)
								queue.put(UpperCamelCase__			)
		return result






def  SCREAMING_SNAKE_CASE__							(				UpperCamelCase__:							dict    ,      UpperCamelCase__:							str			):
		SCREAMING_SNAKE_CASE__								=					{start}
		SCREAMING_SNAKE_CASE__								=					[start]
		SCREAMING_SNAKE_CASE__								=					deque([start]			)
		while queue:
				SCREAMING_SNAKE_CASE__								=					queue.popleft()
				for child in graph[v]:
						if child not in visited:
								visited.add(UpperCamelCase__			)
								result.append(UpperCamelCase__			)
								queue.append(UpperCamelCase__			)
		return result






def  SCREAMING_SNAKE_CASE__							(				UpperCamelCase__:							str			):
		SCREAMING_SNAKE_CASE__								=					f'''from __main__ import G, {name}'''
		SCREAMING_SNAKE_CASE__								=					10_000
		SCREAMING_SNAKE_CASE__								=					timeit(f'''{name}(G, \'A\')'''    ,      setup=UpperCamelCase__    ,      number=UpperCamelCase__			)
		print(f'''{name:<35} finished {number} runs in {res:.5f} seconds'''			)


if __name__ == "__main__":
	import doctest

	doctest.testmod()

	benchmark_function('breadth_first_search')
	benchmark_function('breadth_first_search_with_deque')
	# breadth_first_search                finished 10000 runs in 0.20999 seconds
	# breadth_first_search_with_deque     finished 10000 runs in 0.01421 seconds