



'''simple docstring'''

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

import numpy as np


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

snake_case_			=     None






def       __lowercase  ():
				SCREAMING_SNAKE_CASE  :						Any      					= 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       __lowercase  (_SCREAMING_SNAKE_CASE      :Optional[int]       ):
				SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= {}
				for article in dataset:
								for p in article["paragraphs"]:
												for qa in p["qas"]:
																SCREAMING_SNAKE_CASE  :						List[str]      					= bool(qa['''answers''']['''text''']       )
				return qid_to_has_ans






def       __lowercase  (_SCREAMING_SNAKE_CASE      :str       ):

				def remove_articles(_SCREAMING_SNAKE_CASE      :Optional[Any]       ):
								return ARTICLES_REGEX.sub(''' '''    ,	_SCREAMING_SNAKE_CASE       )

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

				def remove_punc(_SCREAMING_SNAKE_CASE      :Tuple       ):
								SCREAMING_SNAKE_CASE  :						Dict      					= set(string.punctuation       )
								return "".join(ch for ch in text if ch not in exclude       )

				def lower(_SCREAMING_SNAKE_CASE      :Union[str, Any]       ):
								return text.lower()

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






def       __lowercase  (_SCREAMING_SNAKE_CASE      :List[Any]       ):
				if not s:
								return []
				return normalize_answer(_SCREAMING_SNAKE_CASE       ).split()






def       __lowercase  (_SCREAMING_SNAKE_CASE      :Optional[Any]    ,	_SCREAMING_SNAKE_CASE      :Union[str, Any]       ):
				return int(normalize_answer(_SCREAMING_SNAKE_CASE       ) == normalize_answer(_SCREAMING_SNAKE_CASE       )       )






def       __lowercase  (_SCREAMING_SNAKE_CASE      :Union[str, Any]    ,	_SCREAMING_SNAKE_CASE      :Optional[Any]       ):
				SCREAMING_SNAKE_CASE  :						Optional[int]      					= get_tokens(_SCREAMING_SNAKE_CASE       )
				SCREAMING_SNAKE_CASE  :						List[Any]      					= get_tokens(_SCREAMING_SNAKE_CASE       )
				SCREAMING_SNAKE_CASE  :						List[Any]      					= collections.Counter(_SCREAMING_SNAKE_CASE       ) & collections.Counter(_SCREAMING_SNAKE_CASE       )
				SCREAMING_SNAKE_CASE  :						Optional[int]      					= 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
				SCREAMING_SNAKE_CASE  :						Tuple      					= 1.0 * num_same / len(_SCREAMING_SNAKE_CASE       )
				SCREAMING_SNAKE_CASE  :						Dict      					= 1.0 * num_same / len(_SCREAMING_SNAKE_CASE       )
				SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= (2 * precision * recall) / (precision + recall)
				return fa






def       __lowercase  (_SCREAMING_SNAKE_CASE      :Optional[int]    ,	_SCREAMING_SNAKE_CASE      :str       ):
				SCREAMING_SNAKE_CASE  :						List[Any]      					= {}
				SCREAMING_SNAKE_CASE  :						Optional[int]      					= {}
				for article in dataset:
								for p in article["paragraphs"]:
												for qa in p["qas"]:
																SCREAMING_SNAKE_CASE  :						str      					= qa['''id''']
																SCREAMING_SNAKE_CASE  :						Tuple      					= [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
																				SCREAMING_SNAKE_CASE  :						Dict      					= ['''''']
																if qid not in preds:
																				print(F'''Missing prediction for {qid}'''       )
																				continue
																SCREAMING_SNAKE_CASE  :						Tuple      					= preds[qid]
																# Take max over all gold answers
																SCREAMING_SNAKE_CASE  :						int      					= max(compute_exact(_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE       ) for a in gold_answers       )
																SCREAMING_SNAKE_CASE  :						Optional[Any]      					= max(compute_fa(_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE       ) for a in gold_answers       )
				return exact_scores, fa_scores






def       __lowercase  (_SCREAMING_SNAKE_CASE      :Dict    ,	_SCREAMING_SNAKE_CASE      :Dict    ,	_SCREAMING_SNAKE_CASE      :Any    ,	_SCREAMING_SNAKE_CASE      :Optional[int]       ):
				SCREAMING_SNAKE_CASE  :						Tuple      					= {}
				for qid, s in scores.items():
								SCREAMING_SNAKE_CASE  :						int      					= na_probs[qid] > na_prob_thresh
								if pred_na:
												SCREAMING_SNAKE_CASE  :						Dict      					= float(not qid_to_has_ans[qid]       )
								else:
												SCREAMING_SNAKE_CASE  :						Optional[int]      					= s
				return new_scores






def       __lowercase  (_SCREAMING_SNAKE_CASE      :List[Any]    ,	_SCREAMING_SNAKE_CASE      :str    ,	_SCREAMING_SNAKE_CASE      :int=None       ):
				if not qid_list:
								SCREAMING_SNAKE_CASE  :						Optional[int]      					= 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:
								SCREAMING_SNAKE_CASE  :						Any      					= 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       __lowercase  (_SCREAMING_SNAKE_CASE      :Dict    ,	_SCREAMING_SNAKE_CASE      :Dict    ,	_SCREAMING_SNAKE_CASE      :Optional[int]       ):
				for k in new_eval:
								SCREAMING_SNAKE_CASE  :						Tuple      					= new_eval[k]






def       __lowercase  (_SCREAMING_SNAKE_CASE      :Any    ,	_SCREAMING_SNAKE_CASE      :List[str]    ,	_SCREAMING_SNAKE_CASE      :List[str]    ,	_SCREAMING_SNAKE_CASE      :Dict       ):
				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       __lowercase  (_SCREAMING_SNAKE_CASE      :List[Any]    ,	_SCREAMING_SNAKE_CASE      :List[str]    ,	_SCREAMING_SNAKE_CASE      :Union[str, Any]    ,	_SCREAMING_SNAKE_CASE      :List[Any]    ,	_SCREAMING_SNAKE_CASE      :Union[str, Any]=None    ,	_SCREAMING_SNAKE_CASE      :int=None       ):
				SCREAMING_SNAKE_CASE  :						List[str]      					= sorted(_SCREAMING_SNAKE_CASE    ,	key=lambda _SCREAMING_SNAKE_CASE       : na_probs[k]       )
				SCREAMING_SNAKE_CASE  :						int      					= 0.0
				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= 1.0
				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= 0.0
				SCREAMING_SNAKE_CASE  :						Optional[int]      					= [1.0]
				SCREAMING_SNAKE_CASE  :						Optional[int]      					= [0.0]
				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= 0.0
				for i, qid in enumerate(_SCREAMING_SNAKE_CASE       ):
								if qid_to_has_ans[qid]:
												true_pos += scores[qid]
								SCREAMING_SNAKE_CASE  :						Dict      					= true_pos / float(i + 1       )
								SCREAMING_SNAKE_CASE  :						List[str]      					= 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       __lowercase  (_SCREAMING_SNAKE_CASE      :str    ,	_SCREAMING_SNAKE_CASE      :str    ,	_SCREAMING_SNAKE_CASE      :List[str]    ,	_SCREAMING_SNAKE_CASE      :str    ,	_SCREAMING_SNAKE_CASE      :int    ,	_SCREAMING_SNAKE_CASE      :str       ):
				if out_image_dir and not os.path.exists(_SCREAMING_SNAKE_CASE       ):
								os.makedirs(_SCREAMING_SNAKE_CASE       )
				SCREAMING_SNAKE_CASE  :						Tuple      					= sum(1 for v in qid_to_has_ans.values() if v       )
				if num_true_pos == 0:
								return
				SCREAMING_SNAKE_CASE  :						Tuple      					= 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'''    ,	)
				SCREAMING_SNAKE_CASE  :						Tuple      					= 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'''    ,	)
				SCREAMING_SNAKE_CASE  :						str      					= {k: float(_SCREAMING_SNAKE_CASE       ) for k, v in qid_to_has_ans.items()}
				SCREAMING_SNAKE_CASE  :						Dict      					= 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       __lowercase  (_SCREAMING_SNAKE_CASE      :Tuple    ,	_SCREAMING_SNAKE_CASE      :Tuple    ,	_SCREAMING_SNAKE_CASE      :Tuple    ,	_SCREAMING_SNAKE_CASE      :Dict       ):
				if not qid_list:
								return
				SCREAMING_SNAKE_CASE  :						Dict      					= [na_probs[k] for k in qid_list]
				SCREAMING_SNAKE_CASE  :						List[Any]      					= 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       __lowercase  (_SCREAMING_SNAKE_CASE      :List[str]    ,	_SCREAMING_SNAKE_CASE      :Union[str, Any]    ,	_SCREAMING_SNAKE_CASE      :Any    ,	_SCREAMING_SNAKE_CASE      :Union[str, Any]       ):
				SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= sum(1 for k in qid_to_has_ans if not qid_to_has_ans[k]       )
				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= num_no_ans
				SCREAMING_SNAKE_CASE  :						str      					= cur_score
				SCREAMING_SNAKE_CASE  :						Optional[int]      					= 0.0
				SCREAMING_SNAKE_CASE  :						Optional[int]      					= 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]:
												SCREAMING_SNAKE_CASE  :						int      					= scores[qid]
								else:
												if preds[qid]:
																SCREAMING_SNAKE_CASE  :						List[Any]      					= -1
												else:
																SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= 0
								cur_score += diff
								if cur_score > best_score:
												SCREAMING_SNAKE_CASE  :						List[Any]      					= cur_score
												SCREAMING_SNAKE_CASE  :						Dict      					= na_probs[qid]
				return 100.0 * best_score / len(_SCREAMING_SNAKE_CASE       ), best_thresh






def       __lowercase  (_SCREAMING_SNAKE_CASE      :Optional[Any]    ,	_SCREAMING_SNAKE_CASE      :List[Any]    ,	_SCREAMING_SNAKE_CASE      :Optional[int]    ,	_SCREAMING_SNAKE_CASE      :Tuple    ,	_SCREAMING_SNAKE_CASE      :Tuple    ,	_SCREAMING_SNAKE_CASE      :List[Any]       ):
				SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE  :						List[Any]      					= find_best_thresh(_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE       )
				SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE  :						Any      					= find_best_thresh(_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE       )
				SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= best_exact
				SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= exact_thresh
				SCREAMING_SNAKE_CASE  :						str      					= best_fa
				SCREAMING_SNAKE_CASE  :						Any      					= fa_thresh






def       __lowercase  ():
				with open(OPTS.data_file       ) as f:
								SCREAMING_SNAKE_CASE  :						List[str]      					= json.load(_SCREAMING_SNAKE_CASE       )
								SCREAMING_SNAKE_CASE  :						str      					= dataset_json['''data''']
				with open(OPTS.pred_file       ) as f:
								SCREAMING_SNAKE_CASE  :						str      					= json.load(_SCREAMING_SNAKE_CASE       )
				if OPTS.na_prob_file:
								with open(OPTS.na_prob_file       ) as f:
												SCREAMING_SNAKE_CASE  :						Optional[Any]      					= json.load(_SCREAMING_SNAKE_CASE       )
				else:
								SCREAMING_SNAKE_CASE  :						int      					= {k: 0.0 for k in preds}
				SCREAMING_SNAKE_CASE  :						Tuple      					= make_qid_to_has_ans(_SCREAMING_SNAKE_CASE       )  # maps qid to True/False
				SCREAMING_SNAKE_CASE  :						List[str]      					= [k for k, v in qid_to_has_ans.items() if v]
				SCREAMING_SNAKE_CASE  :						Tuple      					= [k for k, v in qid_to_has_ans.items() if not v]
				SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE  :						int      					= get_raw_scores(_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE       )
				SCREAMING_SNAKE_CASE  :						Any      					= apply_no_ans_threshold(_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE    ,	OPTS.na_prob_thresh       )
				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= apply_no_ans_threshold(_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE    ,	OPTS.na_prob_thresh       )
				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= make_eval_dict(_SCREAMING_SNAKE_CASE    ,	_SCREAMING_SNAKE_CASE       )
				if has_ans_qids:
								SCREAMING_SNAKE_CASE  :						List[str]      					= 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:
								SCREAMING_SNAKE_CASE  :						Optional[Any]      					= 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__":
	snake_case_			=     parse_args()
	if OPTS.out_image_dir:
		import matplotlib

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









'''simple docstring'''

from __future__ import annotations

snake_case_			=     [
    [-1, 0],  # left
    [0, -1],  # down
    [1, 0],  # right
    [0, 1],  # up
]






def       __lowercase  (_SCREAMING_SNAKE_CASE      :list[list[int]]    ,	_SCREAMING_SNAKE_CASE      :list[int]    ,	_SCREAMING_SNAKE_CASE      :list[int]    ,	_SCREAMING_SNAKE_CASE      :int    ,	_SCREAMING_SNAKE_CASE      :list[list[int]]    ,	):
				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= [
				    [0 for col in range(len(grid[0]       )       )] for row in range(len(_SCREAMING_SNAKE_CASE       )       )
				]  # the reference grid
				SCREAMING_SNAKE_CASE  :						Dict      					= 1
				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= [
				    [0 for col in range(len(grid[0]       )       )] for row in range(len(_SCREAMING_SNAKE_CASE       )       )
				]  # the action grid

				SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= init[0]
				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= init[1]
				SCREAMING_SNAKE_CASE  :						Any      					= 0
				SCREAMING_SNAKE_CASE  :						List[Any]      					= g + heuristic[x][y]  # cost from starting cell to destination cell
				SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= [[f, g, x, y]]

				SCREAMING_SNAKE_CASE  :						List[str]      					= False  # flag that is set when search is complete
				SCREAMING_SNAKE_CASE  :						Any      					= False  # flag set if we can't find expand

				while not found and not resign:
								if len(_SCREAMING_SNAKE_CASE       ) == 0:
												raise ValueError('''Algorithm is unable to find solution'''       )
								else:  # to choose the least costliest action so as to move closer to the goal
												cell.sort()
												cell.reverse()
												SCREAMING_SNAKE_CASE  :						List[str]      					= cell.pop()
												SCREAMING_SNAKE_CASE  :						List[str]      					= next_cell[2]
												SCREAMING_SNAKE_CASE  :						Dict      					= next_cell[3]
												SCREAMING_SNAKE_CASE  :						str      					= next_cell[1]

												if x == goal[0] and y == goal[1]:
																SCREAMING_SNAKE_CASE  :						Dict      					= True
												else:
																for i in range(len(_SCREAMING_SNAKE_CASE       )       ):  # to try out different valid actions
																				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= x + DIRECTIONS[i][0]
																				SCREAMING_SNAKE_CASE  :						Tuple      					= y + DIRECTIONS[i][1]
																				if xa >= 0 and xa < len(_SCREAMING_SNAKE_CASE       ) and ya >= 0 and ya < len(grid[0]       ):
																								if closed[xa][ya] == 0 and grid[xa][ya] == 0:
																												SCREAMING_SNAKE_CASE  :						Optional[Any]      					= g + cost
																												SCREAMING_SNAKE_CASE  :						Any      					= ga + heuristic[xa][ya]
																												cell.append([fa, ga, xa, ya]       )
																												SCREAMING_SNAKE_CASE  :						List[Any]      					= 1
																												SCREAMING_SNAKE_CASE  :						Optional[int]      					= i
				SCREAMING_SNAKE_CASE  :						Dict      					= []
				SCREAMING_SNAKE_CASE  :						List[Any]      					= goal[0]
				SCREAMING_SNAKE_CASE  :						Optional[int]      					= goal[1]
				invpath.append([x, y]       )  # we get the reverse path from here
				while x != init[0] or y != init[1]:
								SCREAMING_SNAKE_CASE  :						str      					= x - DIRECTIONS[action[x][y]][0]
								SCREAMING_SNAKE_CASE  :						str      					= y - DIRECTIONS[action[x][y]][1]
								SCREAMING_SNAKE_CASE  :						Tuple      					= xa
								SCREAMING_SNAKE_CASE  :						Dict      					= ya
								invpath.append([x, y]       )

				SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= []
				for i in range(len(_SCREAMING_SNAKE_CASE       )       ):
								path.append(invpath[len(_SCREAMING_SNAKE_CASE       ) - 1 - i]       )
				return path, action


if __name__ == "__main__":
	snake_case_			=     [
	    [0, 1, 0, 0, 0, 0],
	    [0, 1, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
	    [0, 1, 0, 0, 0, 0],
	    [0, 1, 0, 0, 1, 0],
	    [0, 0, 0, 0, 1, 0],
	]

	snake_case_			=     [0, 0]
	# all coordinates are given in format [y,x]
	snake_case_			=     [len(grid) - 1, len(grid[0]) - 1]
	snake_case_			=     1

	# the cost map which pushes the path closer to the goal
	snake_case_			=     [[0 for row in range(len(grid[0]))] for col in range(len(grid))]
	for i in range(len(grid)):
		for j in range(len(grid[0])):
			snake_case_			=     abs(i - goal[0]) + abs(j - goal[1])
			if grid[i][j] == 1:
				# added extra penalty in the heuristic map
				snake_case_			=     99

	snake_case_			,				snake_case_			=     search(grid, init, goal, cost, heuristic)

	print("""ACTION MAP""")
	for i in range(len(action)):
		print(action[i])

	for i in range(len(path)):
		print(path[i])




