"""simple docstring"""






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

import numpy as np


__lowerCAmelCase       :			Tuple   	=re.compile(R"""\b(a|an|the)\b""", re.UNICODE)

__lowerCAmelCase       :			List[str]   	=None


def      UpperCAmelCase__			(							)					->       Tuple:
      '''simple docstring'''


      lowercase								=      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=lowerCAmelCase__   ,						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=lowerCAmelCase__   ,						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      UpperCAmelCase__			(							lowerCAmelCase__	:Union[str, Any]						)					->       Dict:
      '''simple docstring'''


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


def      UpperCAmelCase__			(							lowerCAmelCase__	:Union[str, Any]						)					->       int:
      '''simple docstring'''


      def remove_articles(lowerCAmelCase__	:Dict						):
            return ARTICLES_REGEX.sub(""" """   ,						lowerCAmelCase__						)

      def white_space_fix(lowerCAmelCase__	:int						):
            return " ".join(text.split()						)

      def remove_punc(lowerCAmelCase__	:str						):
            lowercase								=      set(string.punctuation						)
            return "".join(ch for ch in text if ch not in exclude						)

      def lower(lowerCAmelCase__	:Optional[int]						):
            return text.lower()

      return white_space_fix(remove_articles(remove_punc(lower(lowerCAmelCase__						)						)						)						)


def      UpperCAmelCase__			(							lowerCAmelCase__	:Any						)					->       Tuple:
      '''simple docstring'''


      if not s:
            return []
      return normalize_answer(lowerCAmelCase__						).split()


def      UpperCAmelCase__			(							lowerCAmelCase__	:Optional[int]   ,						lowerCAmelCase__	:List[str]						)					->       List[Any]:
      '''simple docstring'''


      return int(normalize_answer(lowerCAmelCase__						) == normalize_answer(lowerCAmelCase__						)						)


def      UpperCAmelCase__			(							lowerCAmelCase__	:Tuple   ,						lowerCAmelCase__	:Optional[Any]						)					->       Any:
      '''simple docstring'''


      lowercase								=      get_tokens(lowerCAmelCase__						)
      lowercase								=      get_tokens(lowerCAmelCase__						)
      lowercase								=      collections.Counter(lowerCAmelCase__						) & collections.Counter(lowerCAmelCase__						)
      lowercase								=      sum(common.values()						)
      if len(lowerCAmelCase__						) == 0 or len(lowerCAmelCase__						) == 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
      lowercase								=      1.0 * num_same / len(lowerCAmelCase__						)
      lowercase								=      1.0 * num_same / len(lowerCAmelCase__						)
      lowercase								=      (2 * precision * recall) / (precision + recall)
      return fa


def      UpperCAmelCase__			(							lowerCAmelCase__	:List[str]   ,						lowerCAmelCase__	:List[Any]						)					->       Optional[Any]:
      '''simple docstring'''


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


def      UpperCAmelCase__			(							lowerCAmelCase__	:str   ,						lowerCAmelCase__	:Optional[int]   ,						lowerCAmelCase__	:int   ,						lowerCAmelCase__	:List[Any]						)					->       List[Any]:
      '''simple docstring'''


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


def      UpperCAmelCase__			(							lowerCAmelCase__	:Dict   ,						lowerCAmelCase__	:Any   ,						lowerCAmelCase__	:int=None						)					->       Dict:
      '''simple docstring'''


      if not qid_list:
            lowercase								=      len(lowerCAmelCase__						)
            return collections.OrderedDict(
                [
                    ("""exact""", 100.0 * sum(exact_scores.values()						) / total),
                    ("""f1""", 100.0 * sum(fa_scores.values()						) / total),
                    ("""total""", total),
                ]						)
      else:
            lowercase								=      len(lowerCAmelCase__						)
            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      UpperCAmelCase__			(							lowerCAmelCase__	:Optional[int]   ,						lowerCAmelCase__	:Optional[Any]   ,						lowerCAmelCase__	:Union[str, Any]						)					->       List[str]:
      '''simple docstring'''


      for k in new_eval:
            lowercase								=      new_eval[k]


def      UpperCAmelCase__			(							lowerCAmelCase__	:Union[str, Any]   ,						lowerCAmelCase__	:Tuple   ,						lowerCAmelCase__	:str   ,						lowerCAmelCase__	:Optional[Any]						)					->       Any:
      '''simple docstring'''


      plt.step(lowerCAmelCase__   ,						lowerCAmelCase__   ,						color="""b"""   ,						alpha=0.2   ,						where="""post"""						)
      plt.fill_between(lowerCAmelCase__   ,						lowerCAmelCase__   ,						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(lowerCAmelCase__						)
      plt.savefig(lowerCAmelCase__						)
      plt.clf()


def      UpperCAmelCase__			(							lowerCAmelCase__	:Any   ,						lowerCAmelCase__	:int   ,						lowerCAmelCase__	:List[Any]   ,						lowerCAmelCase__	:List[str]   ,						lowerCAmelCase__	:List[str]=None   ,						lowerCAmelCase__	:List[Any]=None						)					->       List[Any]:
      '''simple docstring'''


      lowercase								=      sorted(lowerCAmelCase__   ,						key=lambda lowerCAmelCase__						: na_probs[k]						)
      lowercase								=      0.0
      lowercase								=      1.0
      lowercase								=      0.0
      lowercase								=      [1.0]
      lowercase								=      [0.0]
      lowercase								=      0.0
      for i, qid in enumerate(lowerCAmelCase__						):
            if qid_to_has_ans[qid]:
                  true_pos += scores[qid]
            lowercase								=      true_pos / float(i + 1						)
            lowercase								=      true_pos / float(lowerCAmelCase__						)
            if i == len(lowerCAmelCase__						) - 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(lowerCAmelCase__						)
                  recalls.append(lowerCAmelCase__						)
      if out_image:
            plot_pr_curve(lowerCAmelCase__   ,						lowerCAmelCase__   ,						lowerCAmelCase__   ,						lowerCAmelCase__						)
      return {"ap": 100.0 * avg_prec}


def      UpperCAmelCase__			(							lowerCAmelCase__	:Optional[int]   ,						lowerCAmelCase__	:Union[str, Any]   ,						lowerCAmelCase__	:Union[str, Any]   ,						lowerCAmelCase__	:Union[str, Any]   ,						lowerCAmelCase__	:str   ,						lowerCAmelCase__	:Optional[int]						)					->       Union[str, Any]:
      '''simple docstring'''


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


def      UpperCAmelCase__			(							lowerCAmelCase__	:Any   ,						lowerCAmelCase__	:Optional[int]   ,						lowerCAmelCase__	:int   ,						lowerCAmelCase__	:Union[str, Any]						)					->       Any:
      '''simple docstring'''


      if not qid_list:
            return
      lowercase								=      [na_probs[k] for k in qid_list]
      lowercase								=      np.ones_like(lowerCAmelCase__						) / float(len(lowerCAmelCase__						)						)
      plt.hist(lowerCAmelCase__   ,						weights=lowerCAmelCase__   ,						bins=2_0   ,						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(lowerCAmelCase__   ,						f'na_prob_hist_{name}.png'						)						)
      plt.clf()


def      UpperCAmelCase__			(							lowerCAmelCase__	:int   ,						lowerCAmelCase__	:int   ,						lowerCAmelCase__	:Union[str, Any]   ,						lowerCAmelCase__	:List[Any]						)					->       int:
      '''simple docstring'''


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


def      UpperCAmelCase__			(							lowerCAmelCase__	:Optional[int]   ,						lowerCAmelCase__	:Dict   ,						lowerCAmelCase__	:Optional[Any]   ,						lowerCAmelCase__	:int   ,						lowerCAmelCase__	:int   ,						lowerCAmelCase__	:int						)					->       str:
      '''simple docstring'''


      lowercase				,				lowercase								=      find_best_thresh(lowerCAmelCase__   ,						lowerCAmelCase__   ,						lowerCAmelCase__   ,						lowerCAmelCase__						)
      lowercase				,				lowercase								=      find_best_thresh(lowerCAmelCase__   ,						lowerCAmelCase__   ,						lowerCAmelCase__   ,						lowerCAmelCase__						)
      lowercase								=      best_exact
      lowercase								=      exact_thresh
      lowercase								=      best_fa
      lowercase								=      fa_thresh


def      UpperCAmelCase__			(							)					->       Dict:
      '''simple docstring'''


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


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

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




"""simple docstring"""






from __future__ import annotations


def      UpperCAmelCase__			(							lowerCAmelCase__	:dict   ,						lowerCAmelCase__	:str						)					->       set[str]:
      '''simple docstring'''


      lowercase				,				lowercase								=      set(lowerCAmelCase__						), [start]

      while stack:
            lowercase								=      stack.pop()
            explored.add(lowerCAmelCase__						)
            # Differences from BFS:
            # 1) pop last element instead of first one
            # 2) add adjacent elements to stack without exploring them
            for adj in reversed(graph[v]						):
                  if adj not in explored:
                        stack.append(lowerCAmelCase__						)
      return explored


__lowerCAmelCase       :			str   	={
    """A""": ["""B""", """C""", """D"""],
    """B""": ["""A""", """D""", """E"""],
    """C""": ["""A""", """F"""],
    """D""": ["""B""", """D"""],
    """E""": ["""B""", """F"""],
    """F""": ["""C""", """E""", """G"""],
    """G""": ["""F"""],
}

if __name__ == "__main__":
       import doctest

       doctest.testmod()
       print(depth_first_search(G, """A"""))



