



'''simple docstring'''

import argparse
import collections
import json
import os
import re
import string
import sys

import numpy as np


UpperCAmelCase     		=   re.compile(r'\b(a|an|the)\b', re.UNICODE)

UpperCAmelCase     		=   None






def 		_snake_case		( )      ->						int:







	"""simple docstring"""
	lowerCAmelCase   =     argparse.ArgumentParser("""Official evaluation script for SQuAD version 2.0."""							)
	parser.add_argument("""data_file"""							,		metavar="""data.json"""							,		help="""Input data JSON file."""							)
	parser.add_argument("""pred_file"""							,		metavar="""pred.json"""							,		help="""Model predictions."""							)
	parser.add_argument(
	    """--out-file"""							,		"""-o"""							,		metavar="""eval.json"""							,		help="""Write accuracy metrics to file (default is stdout)."""							)
	parser.add_argument(
	    """--na-prob-file"""							,		"""-n"""							,		metavar="""na_prob.json"""							,		help="""Model estimates of probability of no answer."""							)
	parser.add_argument(
	    """--na-prob-thresh"""							,		"""-t"""							,		type=_SCREAMING_SNAKE_CASE							,		default=1.0							,		help="""Predict \"\" if no-answer probability exceeds this (default = 1.0)."""							,		)
	parser.add_argument(
	    """--out-image-dir"""							,		"""-p"""							,		metavar="""out_images"""							,		default=_SCREAMING_SNAKE_CASE							,		help="""Save precision-recall curves to directory."""							)
	parser.add_argument("""--verbose"""							,		"""-v"""							,		action="""store_true"""							)
	if len(sys.argv							) == 1:
		parser.print_help()
		sys.exit(1							)
	return parser.parse_args()






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						Optional[Any]							)      ->						int:







	"""simple docstring"""
	lowerCAmelCase   =     {}
	for article in dataset:
		for p in article["paragraphs"]:
			for qa in p["qas"]:
				lowerCAmelCase   =     bool(qa["""answers"""]["""text"""]							)
	return qid_to_has_ans






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						Dict							)      ->						Dict:







	"""simple docstring"""

	def remove_articles(_SCREAMING_SNAKE_CASE					:						int							):
		return ARTICLES_REGEX.sub(""" """							,		_SCREAMING_SNAKE_CASE							)

	def white_space_fix(_SCREAMING_SNAKE_CASE					:						Any							):
		return " ".join(text.split()							)

	def remove_punc(_SCREAMING_SNAKE_CASE					:						Union[str, Any]							):
		lowerCAmelCase   =     set(string.punctuation							)
		return "".join(ch for ch in text if ch not in exclude							)

	def lower(_SCREAMING_SNAKE_CASE					:						Tuple							):
		return text.lower()

	return white_space_fix(remove_articles(remove_punc(lower(_SCREAMING_SNAKE_CASE							)							)							)							)






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						int							)      ->						List[Any]:







	"""simple docstring"""
	if not s:
		return []
	return normalize_answer(_SCREAMING_SNAKE_CASE							).split()






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						List[str]							,		_SCREAMING_SNAKE_CASE					:						Optional[Any]							)      ->						Optional[int]:







	"""simple docstring"""
	return int(normalize_answer(_SCREAMING_SNAKE_CASE							) == normalize_answer(_SCREAMING_SNAKE_CASE							)							)






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						Tuple							,		_SCREAMING_SNAKE_CASE					:						int							)      ->						Dict:







	"""simple docstring"""
	lowerCAmelCase   =     get_tokens(_SCREAMING_SNAKE_CASE							)
	lowerCAmelCase   =     get_tokens(_SCREAMING_SNAKE_CASE							)
	lowerCAmelCase   =     collections.Counter(_SCREAMING_SNAKE_CASE							) & collections.Counter(_SCREAMING_SNAKE_CASE							)
	lowerCAmelCase   =     sum(common.values()							)
	if len(_SCREAMING_SNAKE_CASE							) == 0 or len(_SCREAMING_SNAKE_CASE							) == 0:
		# If either is no-answer, then F1 is 1 if they agree, 0 otherwise
		return int(gold_toks == pred_toks							)
	if num_same == 0:
		return 0
	lowerCAmelCase   =     1.0 * num_same / len(_SCREAMING_SNAKE_CASE							)
	lowerCAmelCase   =     1.0 * num_same / len(_SCREAMING_SNAKE_CASE							)
	lowerCAmelCase   =     (2 * precision * recall) / (precision + recall)
	return fa






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						Union[str, Any]							,		_SCREAMING_SNAKE_CASE					:						Optional[Any]							)      ->						Dict:







	"""simple docstring"""
	lowerCAmelCase   =     {}
	lowerCAmelCase   =     {}
	for article in dataset:
		for p in article["paragraphs"]:
			for qa in p["qas"]:
				lowerCAmelCase   =     qa["""id"""]
				lowerCAmelCase   =     [t for t in qa["""answers"""]["""text"""] if normalize_answer(_SCREAMING_SNAKE_CASE							)]
				if not gold_answers:
					# For unanswerable questions, only correct answer is empty string
					lowerCAmelCase   =     [""""""]
				if qid not in preds:
					print(f'Missing prediction for {qid}'							)
					continue
				lowerCAmelCase   =     preds[qid]
				# Take max over all gold answers
				lowerCAmelCase   =     max(compute_exact(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							) for a in gold_answers							)
				lowerCAmelCase   =     max(compute_fa(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							) for a in gold_answers							)
	return exact_scores, fa_scores






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						Dict							,		_SCREAMING_SNAKE_CASE					:						str							,		_SCREAMING_SNAKE_CASE					:						Any							,		_SCREAMING_SNAKE_CASE					:						List[str]							)      ->						Tuple:







	"""simple docstring"""
	lowerCAmelCase   =     {}
	for qid, s in scores.items():
		lowerCAmelCase   =     na_probs[qid] > na_prob_thresh
		if pred_na:
			lowerCAmelCase   =     float(not qid_to_has_ans[qid]							)
		else:
			lowerCAmelCase   =     s
	return new_scores






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						Dict							,		_SCREAMING_SNAKE_CASE					:						List[Any]							,		_SCREAMING_SNAKE_CASE					:						Any=None							)      ->						List[Any]:







	"""simple docstring"""
	if not qid_list:
		lowerCAmelCase   =     len(_SCREAMING_SNAKE_CASE							)
		return collections.OrderedDict(
		    [
		        ("""exact""", 100.0 * sum(exact_scores.values()							) / total),
		        ("""f1""", 100.0 * sum(fa_scores.values()							) / total),
		        ("""total""", total),
		    ]							)
	else:
		lowerCAmelCase   =     len(_SCREAMING_SNAKE_CASE							)
		return collections.OrderedDict(
		    [
		        ("""exact""", 100.0 * sum(exact_scores[k] for k in qid_list							) / total),
		        ("""f1""", 100.0 * sum(fa_scores[k] for k in qid_list							) / total),
		        ("""total""", total),
		    ]							)






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						Dict							,		_SCREAMING_SNAKE_CASE					:						List[Any]							,		_SCREAMING_SNAKE_CASE					:						List[Any]							)      ->						Optional[Any]:







	"""simple docstring"""
	for k in new_eval:
		lowerCAmelCase   =     new_eval[k]






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						Tuple							,		_SCREAMING_SNAKE_CASE					:						Optional[Any]							,		_SCREAMING_SNAKE_CASE					:						List[Any]							,		_SCREAMING_SNAKE_CASE					:						Any							)      ->						Optional[int]:







	"""simple docstring"""
	plt.step(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		color="""b"""							,		alpha=0.2							,		where="""post"""							)
	plt.fill_between(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		step="""post"""							,		alpha=0.2							,		color="""b"""							)
	plt.xlabel("""Recall"""							)
	plt.ylabel("""Precision"""							)
	plt.xlim([0.0, 1.05]							)
	plt.ylim([0.0, 1.05]							)
	plt.title(_SCREAMING_SNAKE_CASE							)
	plt.savefig(_SCREAMING_SNAKE_CASE							)
	plt.clf()






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						Tuple							,		_SCREAMING_SNAKE_CASE					:						Optional[int]							,		_SCREAMING_SNAKE_CASE					:						Any							,		_SCREAMING_SNAKE_CASE					:						int							,		_SCREAMING_SNAKE_CASE					:						Tuple=None							,		_SCREAMING_SNAKE_CASE					:						List[Any]=None							)      ->						int:







	"""simple docstring"""
	lowerCAmelCase   =     sorted(_SCREAMING_SNAKE_CASE							,		key=lambda _SCREAMING_SNAKE_CASE							: na_probs[k]							)
	lowerCAmelCase   =     0.0
	lowerCAmelCase   =     1.0
	lowerCAmelCase   =     0.0
	lowerCAmelCase   =     [1.0]
	lowerCAmelCase   =     [0.0]
	lowerCAmelCase   =     0.0
	for i, qid in enumerate(_SCREAMING_SNAKE_CASE							):
		if qid_to_has_ans[qid]:
			true_pos += scores[qid]
		lowerCAmelCase   =     true_pos / float(i + 1							)
		lowerCAmelCase   =     true_pos / float(_SCREAMING_SNAKE_CASE							)
		if i == len(_SCREAMING_SNAKE_CASE							) - 1 or na_probs[qid] != na_probs[qid_list[i + 1]]:
			# i.e., if we can put a threshold after this point
			avg_prec += cur_p * (cur_r - recalls[-1])
			precisions.append(_SCREAMING_SNAKE_CASE							)
			recalls.append(_SCREAMING_SNAKE_CASE							)
	if out_image:
		plot_pr_curve(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							)
	return {"ap": 100.0 * avg_prec}






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						Any							,		_SCREAMING_SNAKE_CASE					:						List[str]							,		_SCREAMING_SNAKE_CASE					:						Union[str, Any]							,		_SCREAMING_SNAKE_CASE					:						Any							,		_SCREAMING_SNAKE_CASE					:						Union[str, Any]							,		_SCREAMING_SNAKE_CASE					:						List[str]							)      ->						Optional[Any]:







	"""simple docstring"""
	if out_image_dir and not os.path.exists(_SCREAMING_SNAKE_CASE							):
		os.makedirs(_SCREAMING_SNAKE_CASE							)
	lowerCAmelCase   =     sum(1 for v in qid_to_has_ans.values() if v							)
	if num_true_pos == 0:
		return
	lowerCAmelCase   =     make_precision_recall_eval(
	    _SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		out_image=os.path.join(_SCREAMING_SNAKE_CASE							,		"""pr_exact.png"""							)							,		title="""Precision-Recall curve for Exact Match score"""							,		)
	lowerCAmelCase   =     make_precision_recall_eval(
	    _SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		out_image=os.path.join(_SCREAMING_SNAKE_CASE							,		"""pr_f1.png"""							)							,		title="""Precision-Recall curve for F1 score"""							,		)
	lowerCAmelCase   =     {k: float(_SCREAMING_SNAKE_CASE							) for k, v in qid_to_has_ans.items()}
	lowerCAmelCase   =     make_precision_recall_eval(
	    _SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		out_image=os.path.join(_SCREAMING_SNAKE_CASE							,		"""pr_oracle.png"""							)							,		title="""Oracle Precision-Recall curve (binary task of HasAns vs. NoAns)"""							,		)
	merge_eval(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		"""pr_exact"""							)
	merge_eval(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		"""pr_f1"""							)
	merge_eval(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		"""pr_oracle"""							)






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						str							,		_SCREAMING_SNAKE_CASE					:						Optional[Any]							,		_SCREAMING_SNAKE_CASE					:						List[str]							,		_SCREAMING_SNAKE_CASE					:						List[str]							)      ->						str:







	"""simple docstring"""
	if not qid_list:
		return
	lowerCAmelCase   =     [na_probs[k] for k in qid_list]
	lowerCAmelCase   =     np.ones_like(_SCREAMING_SNAKE_CASE							) / float(len(_SCREAMING_SNAKE_CASE							)							)
	plt.hist(_SCREAMING_SNAKE_CASE							,		weights=_SCREAMING_SNAKE_CASE							,		bins=20							,		range=(0.0, 1.0)							)
	plt.xlabel("""Model probability of no-answer"""							)
	plt.ylabel("""Proportion of dataset"""							)
	plt.title(f'Histogram of no-answer probability: {name}'							)
	plt.savefig(os.path.join(_SCREAMING_SNAKE_CASE							,		f'na_prob_hist_{name}.png'							)							)
	plt.clf()






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						Optional[int]							,		_SCREAMING_SNAKE_CASE					:						Optional[int]							,		_SCREAMING_SNAKE_CASE					:						Optional[Any]							,		_SCREAMING_SNAKE_CASE					:						Union[str, Any]							)      ->						Optional[int]:







	"""simple docstring"""
	lowerCAmelCase   =     sum(1 for k in qid_to_has_ans if not qid_to_has_ans[k]							)
	lowerCAmelCase   =     num_no_ans
	lowerCAmelCase   =     cur_score
	lowerCAmelCase   =     0.0
	lowerCAmelCase   =     sorted(_SCREAMING_SNAKE_CASE							,		key=lambda _SCREAMING_SNAKE_CASE							: na_probs[k]							)
	for i, qid in enumerate(_SCREAMING_SNAKE_CASE							):
		if qid not in scores:
			continue
		if qid_to_has_ans[qid]:
			lowerCAmelCase   =     scores[qid]
		else:
			if preds[qid]:
				lowerCAmelCase   =     -1
			else:
				lowerCAmelCase   =     0
		cur_score += diff
		if cur_score > best_score:
			lowerCAmelCase   =     cur_score
			lowerCAmelCase   =     na_probs[qid]
	return 100.0 * best_score / len(_SCREAMING_SNAKE_CASE							), best_thresh






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						List[str]							,		_SCREAMING_SNAKE_CASE					:						Tuple							,		_SCREAMING_SNAKE_CASE					:						Union[str, Any]							,		_SCREAMING_SNAKE_CASE					:						Optional[Any]							,		_SCREAMING_SNAKE_CASE					:						str							,		_SCREAMING_SNAKE_CASE					:						Tuple							)      ->						List[Any]:







	"""simple docstring"""
	lowerCAmelCase,       lowerCAmelCase   =     find_best_thresh(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							)
	lowerCAmelCase,       lowerCAmelCase   =     find_best_thresh(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							)
	lowerCAmelCase   =     best_exact
	lowerCAmelCase   =     exact_thresh
	lowerCAmelCase   =     best_fa
	lowerCAmelCase   =     fa_thresh






def 		_snake_case		( )      ->						List[str]:







	"""simple docstring"""
	with open(OPTS.data_file							) as f:
		lowerCAmelCase   =     json.load(_SCREAMING_SNAKE_CASE							)
		lowerCAmelCase   =     dataset_json["""data"""]
	with open(OPTS.pred_file							) as f:
		lowerCAmelCase   =     json.load(_SCREAMING_SNAKE_CASE							)
	if OPTS.na_prob_file:
		with open(OPTS.na_prob_file							) as f:
			lowerCAmelCase   =     json.load(_SCREAMING_SNAKE_CASE							)
	else:
		lowerCAmelCase   =     {k: 0.0 for k in preds}
	lowerCAmelCase   =     make_qid_to_has_ans(_SCREAMING_SNAKE_CASE							)  # maps qid to True/False
	lowerCAmelCase   =     [k for k, v in qid_to_has_ans.items() if v]
	lowerCAmelCase   =     [k for k, v in qid_to_has_ans.items() if not v]
	lowerCAmelCase,       lowerCAmelCase   =     get_raw_scores(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							)
	lowerCAmelCase   =     apply_no_ans_threshold(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		OPTS.na_prob_thresh							)
	lowerCAmelCase   =     apply_no_ans_threshold(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		OPTS.na_prob_thresh							)
	lowerCAmelCase   =     make_eval_dict(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							)
	if has_ans_qids:
		lowerCAmelCase   =     make_eval_dict(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		qid_list=_SCREAMING_SNAKE_CASE							)
		merge_eval(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		"""HasAns"""							)
	if no_ans_qids:
		lowerCAmelCase   =     make_eval_dict(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		qid_list=_SCREAMING_SNAKE_CASE							)
		merge_eval(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		"""NoAns"""							)
	if OPTS.na_prob_file:
		find_all_best_thresh(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							)
	if OPTS.na_prob_file and OPTS.out_image_dir:
		run_precision_recall_analysis(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		OPTS.out_image_dir							)
		histogram_na_prob(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		OPTS.out_image_dir							,		"""hasAns"""							)
		histogram_na_prob(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							,		OPTS.out_image_dir							,		"""noAns"""							)
	if OPTS.out_file:
		with open(OPTS.out_file							,		"""w"""							) as f:
			json.dump(_SCREAMING_SNAKE_CASE							,		_SCREAMING_SNAKE_CASE							)
	else:
		print(json.dumps(_SCREAMING_SNAKE_CASE							,		indent=2							)							)


if __name__ == "__main__":
				UpperCAmelCase     		=   parse_args()
				if OPTS.out_image_dir:
								import matplotlib

								matplotlib.use('Agg')
								import matplotlib.pyplot as plt
				main()




'''simple docstring'''

class __snake_case:


						'''simple docstring'''



						def __init__( self				)     ->     None:
							lowerCAmelCase   =     {}  # Mapping from char to TrieNode
							lowerCAmelCase   =     False


						def     __snake_case   ( self     ,	A_				)     ->     None:
							for word in words:
								self.insert(A_				)


						def     __snake_case   ( self     ,	A_				)     ->     None:
							lowerCAmelCase   =     self
							for char in word:
								if char not in curr.nodes:
									lowerCAmelCase   =     TrieNode()
								lowerCAmelCase   =     curr.nodes[char]
							lowerCAmelCase   =     True


						def     __snake_case   ( self     ,	A_				)     ->     bool:
							lowerCAmelCase   =     self
							for char in word:
								if char not in curr.nodes:
									return False
								lowerCAmelCase   =     curr.nodes[char]
							return curr.is_leaf




						def     __snake_case   ( self     ,	A_				)     ->     None:

							def _delete(A_     ,	A_     ,	A_				) -> bool:
								if index == len(A_				):
									# If word does not exist
									if not curr.is_leaf:
										return False
									lowerCAmelCase   =     False
									return len(curr.nodes				) == 0
								lowerCAmelCase   =     word[index]
								lowerCAmelCase   =     curr.nodes.get(A_				)
								# If char not in current trie node
								if not char_node:
									return False
								# Flag to check if node can be deleted
								lowerCAmelCase   =     _delete(A_     ,	A_     ,	index + 1				)
								if delete_curr:
									del curr.nodes[char]
									return len(curr.nodes				) == 0
								return delete_curr

							_delete(self     ,	A_     ,	0				)







def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						TrieNode							,		_SCREAMING_SNAKE_CASE					:						str							)      ->						None:







	"""simple docstring"""
	if node.is_leaf:
		print(_SCREAMING_SNAKE_CASE							,		end=""" """							)

	for key, value in node.nodes.items():
		print_words(_SCREAMING_SNAKE_CASE							,		word + key							)






def 		_snake_case		( )      ->						bool:







	"""simple docstring"""
	lowerCAmelCase   =     """banana bananas bandana band apple all beast""".split()
	lowerCAmelCase   =     TrieNode()
	root.insert_many(_SCREAMING_SNAKE_CASE							)
	# print_words(root, "")
	assert all(root.find(_SCREAMING_SNAKE_CASE							) for word in words							)
	assert root.find("""banana"""							)
	assert not root.find("""bandanas"""							)
	assert not root.find("""apps"""							)
	assert root.find("""apple"""							)
	assert root.find("""all"""							)
	root.delete("""all"""							)
	assert not root.find("""all"""							)
	root.delete("""banana"""							)
	assert not root.find("""banana"""							)
	assert root.find("""bananas"""							)
	return True






def 		_snake_case		( _SCREAMING_SNAKE_CASE					:						str							,		_SCREAMING_SNAKE_CASE					:						bool							)      ->						None:







	"""simple docstring"""
	print(str(_SCREAMING_SNAKE_CASE							)							,		"""works!""" if passes else """doesn't work :("""							)






def 		_snake_case		( )      ->						None:







	"""simple docstring"""
	assert test_trie()






def 		_snake_case		( )      ->						None:







	"""simple docstring"""
	print_results("""Testing trie functionality"""							,		test_trie()							)


if __name__ == "__main__":
				main()