






import numpy as np
from nltk.translate import meteor_score

import datasets
from datasets.config import importlib_metadata, version


__lowerCamelCase      :    Dict   		=   version.parse(importlib_metadata.version("""nltk"""))
if NLTK_VERSION >= version.Version("""3.6.4"""):
	from nltk import word_tokenize


__lowerCamelCase      :    Dict   		=   "\\n@inproceedings{banarjee2005,\n  title     = {{METEOR}: An Automatic Metric for {MT} Evaluation with Improved Correlation with Human Judgments},\n  author    = {Banerjee, Satanjeev  and Lavie, Alon},\n  booktitle = {Proceedings of the {ACL} Workshop on Intrinsic and Extrinsic Evaluation Measures for Machine Translation and/or Summarization},\n  month     = jun,\n  year      = {2005},\n  address   = {Ann Arbor, Michigan},\n  publisher = {Association for Computational Linguistics},\n  url       = {https://www.aclweb.org/anthology/W05-0909},\n  pages     = {65--72},\n}\n"

__lowerCamelCase      :    Optional[int]   		=   "\\nMETEOR, an automatic metric for machine translation evaluation\nthat is based on a generalized concept of unigram matching between the\nmachine-produced translation and human-produced reference translations.\nUnigrams can be matched based on their surface forms, stemmed forms,\nand meanings; furthermore, METEOR can be easily extended to include more\nadvanced matching strategies. Once all generalized unigram matches\nbetween the two strings have been found, METEOR computes a score for\nthis matching using a combination of unigram-precision, unigram-recall, and\na measure of fragmentation that is designed to directly capture how\nwell-ordered the matched words in the machine translation are in relation\nto the reference.\n\nMETEOR gets an R correlation value of 0.347 with human evaluation on the Arabic\ndata and 0.331 on the Chinese data. This is shown to be an improvement on\nusing simply unigram-precision, unigram-recall and their harmonic F1\ncombination.\n"

__lowerCamelCase      :    Tuple   		=   "\nComputes METEOR score of translated segments against one or more references.\nArgs:\n    predictions: list of predictions to score. Each prediction\n        should be a string with tokens separated by spaces.\n    references: list of reference for each prediction. Each\n        reference should be a string with tokens separated by spaces.\n    alpha: Parameter for controlling relative weights of precision and recall. default: 0.9\n    beta: Parameter for controlling shape of penalty as a function of fragmentation. default: 3\n    gamma: Relative weight assigned to fragmentation penalty. default: 0.5\nReturns:\n    'meteor': meteor score.\nExamples:\n\n    >>> meteor = datasets.load_metric('meteor')\n    >>> predictions = [\"It is a guide to action which ensures that the military always obeys the commands of the party\"]\n    >>> references = [\"It is a guide to action that ensures that the military will forever heed Party commands\"]\n    >>> results = meteor.compute(predictions=predictions, references=references)\n    >>> print(round(results[\"meteor\"], 4))\n    0.6944\n"

@datasets.utils.file_utils.add_start_docstrings(_DESCRIPTION				,     _KWARGS_DESCRIPTION		)
class 							SCREAMING_SNAKE_CASE__		(       datasets.Metric		):





					"""simple docstring"""






					def  _lowercase  (      self  :						List[str] ):
						return datasets.MetricInfo(
						    description=_DESCRIPTION							,	citation=_CITATION							,	inputs_description=_KWARGS_DESCRIPTION							,	features=datasets.Features(
						        {
						            "predictions": datasets.Value("string"							,	id="sequence" ),
						            "references": datasets.Value("string"							,	id="sequence" ),
						        } )							,	codebase_urls=["https://github.com/nltk/nltk/blob/develop/nltk/translate/meteor_score.py"]							,	reference_urls=[
						        "https://www.nltk.org/api/nltk.translate.html#module-nltk.translate.meteor_score",
						        "https://en.wikipedia.org/wiki/METEOR",
						    ]							,	)



					def  _lowercase  (      self  :						int							,	__A  :						Optional[Any] ):
						import nltk

						nltk.download("wordnet" )
						if NLTK_VERSION >= version.Version("3.6.5" ):
							nltk.download("punkt" )
						if NLTK_VERSION >= version.Version("3.6.6" ):
							nltk.download("omw-1.4" )






					def  _lowercase  (      self  :						str							,	__A  :						Any							,	__A  :						Optional[int]							,	__A  :						List[str]=0.9							,	__A  :						Optional[Any]=3							,	__A  :						str=0.5 ):




						if NLTK_VERSION >= version.Version("3.6.5" ):
							snake_case__				:   List[Any]     =						[
							    meteor_score.single_meteor_score(
							        word_tokenize(lowerCamelCase_ )							,	word_tokenize(lowerCamelCase_ )							,	alpha=lowerCamelCase_							,	beta=lowerCamelCase_							,	gamma=lowerCamelCase_ )
							    for ref, pred in zip(lowerCamelCase_							,	lowerCamelCase_ )
							]
						else:
							snake_case__				:   Dict     =						[
							    meteor_score.single_meteor_score(lowerCamelCase_							,	lowerCamelCase_							,	alpha=lowerCamelCase_							,	beta=lowerCamelCase_							,	gamma=lowerCamelCase_ )
							    for ref, pred in zip(lowerCamelCase_							,	lowerCamelCase_ )
							]

						return {"meteor": np.mean(lowerCamelCase_ )}











from __future__ import annotations

import time

__lowerCamelCase      :    str   		=   list[tuple[int, int]]

__lowerCamelCase      :    Optional[int]   		=   [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
]

__lowerCamelCase      :    Tuple   		=   [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right



class 							SCREAMING_SNAKE_CASE__		:





					"""simple docstring"""






					def __init__(      self  :						Union[str, Any]							,	__A  :						int							,	__A  :						int							,	__A  :						int							,	__A  :						int							,	__A  :						Node | None ):
						snake_case__				:   Optional[int]     =						pos_x
						snake_case__				:   Dict     =						pos_y
						snake_case__				:   int     =						(pos_y, pos_x)
						snake_case__				:   Optional[int]     =						goal_x
						snake_case__				:   Tuple     =						goal_y
						snake_case__				:   str     =						parent



class 							SCREAMING_SNAKE_CASE__		:





					"""simple docstring"""






					def __init__(      self  :						List[Any]							,	__A  :						tuple[int, int]							,	__A  :						tuple[int, int] ):
						snake_case__				:   Tuple     =						Node(start[1]							,	start[0]							,	goal[1]							,	goal[0]							,	__A )
						snake_case__				:   Tuple     =						Node(goal[1]							,	goal[0]							,	goal[1]							,	goal[0]							,	__A )

						snake_case__				:   int     =						[self.start]
						snake_case__				:   Union[str, Any]     =						False



					def  _lowercase  (      self  :						Dict ):
						while self.node_queue:
							snake_case__				:   Optional[Any]     =						self.node_queue.pop(0 )

							if current_node.pos == self.target.pos:
								snake_case__				:   Optional[Any]     =						True
								return self.retrace_path(__A )

							snake_case__				:   int     =						self.get_successors(__A )

							for node in successors:
								self.node_queue.append(__A )

						if not self.reached:
							return [self.start.pos]
						return None



					def  _lowercase  (      self  :						Union[str, Any]							,	__A  :						Node ):
						snake_case__				:   str     =						[]
						for action in delta:
							snake_case__				:   str     =						parent.pos_x + action[1]
							snake_case__				:   Union[str, Any]     =						parent.pos_y + action[0]
							if not (0 <= pos_x <= len(grid[0] ) - 1 and 0 <= pos_y <= len(__A ) - 1):
								continue

							if grid[pos_y][pos_x] != 0:
								continue

							successors.append(
							    Node(__A							,	__A							,	self.target.pos_y							,	self.target.pos_x							,	__A ) )
						return successors






					def  _lowercase  (      self  :						Optional[Any]							,	__A  :						Node | None ):
						snake_case__				:   Tuple     =						node
						snake_case__				:   Any     =						[]
						while current_node is not None:
							path.append((current_node.pos_y, current_node.pos_x) )
							snake_case__				:   Tuple     =						current_node.parent
						path.reverse()
						return path



class 							SCREAMING_SNAKE_CASE__		:





					"""simple docstring"""






					def __init__(      self  :						Dict							,	__A  :						str							,	__A  :						int ):
						snake_case__				:   str     =						BreadthFirstSearch(__A							,	__A )
						snake_case__				:   int     =						BreadthFirstSearch(__A							,	__A )
						snake_case__				:   Tuple     =						False



					def  _lowercase  (      self  :						Optional[Any] ):
						while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
							snake_case__				:   Any     =						self.fwd_bfs.node_queue.pop(0 )
							snake_case__				:   List[str]     =						self.bwd_bfs.node_queue.pop(0 )

							if current_bwd_node.pos == current_fwd_node.pos:
								snake_case__				:   List[str]     =						True
								return self.retrace_bidirectional_path(
								    __A							,	__A )

							snake_case__				:   Union[str, Any]     =						current_bwd_node
							snake_case__				:   Dict     =						current_fwd_node

							snake_case__				:   List[Any]     =						{
							    self.fwd_bfs: self.fwd_bfs.get_successors(__A ),
							    self.bwd_bfs: self.bwd_bfs.get_successors(__A ),
							}

							for bfs in [self.fwd_bfs, self.bwd_bfs]:
								for node in successors[bfs]:
									bfs.node_queue.append(__A )

						if not self.reached:
							return [self.fwd_bfs.start.pos]
						return None






					def  _lowercase  (      self  :						Any							,	__A  :						Node							,	__A  :						Node ):
						snake_case__				:   List[str]     =						self.fwd_bfs.retrace_path(__A )
						snake_case__				:   Optional[Any]     =						self.bwd_bfs.retrace_path(__A )
						bwd_path.pop()
						bwd_path.reverse()
						snake_case__				:   List[Any]     =						fwd_path + bwd_path
						return path


if __name__ == "__main__":
	# all coordinates are given in format [y,x]
	import doctest

	doctest.testmod()
	__lowerCamelCase      :    str   		=   (0, 0)
	__lowerCamelCase      :    List[str]   		=   (len(grid) - 1, len(grid[0]) - 1)
	for elem in grid:
		print(elem)

	__lowerCamelCase      :    Any   		=   time.time()
	__lowerCamelCase      :    Optional[Any]   		=   BreadthFirstSearch(init, goal)
	__lowerCamelCase      :    str   		=   bfs.search()
	__lowerCamelCase      :    Optional[Any]   		=   time.time() - start_bfs_time

	print("""Unidirectional BFS computation time : """, bfs_time)

	__lowerCamelCase      :    Optional[Any]   		=   time.time()
	__lowerCamelCase      :    Optional[int]   		=   BidirectionalBreadthFirstSearch(init, goal)
	__lowerCamelCase      :    str   		=   bd_bfs.search()
	__lowerCamelCase      :    Optional[Any]   		=   time.time() - start_bd_bfs_time

	print("""Bidirectional BFS computation time : """, bd_bfs_time)



