





from sklearn.metrics import fa_score

import datasets


_lowerCamelCase :    Dict  							= '''
The F1 score is the harmonic mean of the precision and recall. It can be computed with the equation:
F1 = 2 * (precision * recall) / (precision + recall)
'''


_lowerCamelCase :    List[Any]  							= '''
Args:
    predictions (`list` of `int`): Predicted labels.
    references (`list` of `int`): Ground truth labels.
    labels (`list` of `int`): The set of labels to include when `average` is not set to `\'binary\'`, and the order of the labels if `average` is `None`. Labels present in the data can be excluded, for example to calculate a multiclass average ignoring a majority negative class. Labels not present in the data will result in 0 components in a macro average. For multilabel targets, labels are column indices. By default, all labels in `predictions` and `references` are used in sorted order. Defaults to None.
    pos_label (`int`): The class to be considered the positive class, in the case where `average` is set to `binary`. Defaults to 1.
    average (`string`): This parameter is required for multiclass/multilabel targets. If set to `None`, the scores for each class are returned. Otherwise, this determines the type of averaging performed on the data. Defaults to `\'binary\'`.

        - \'binary\': Only report results for the class specified by `pos_label`. This is applicable only if the classes found in `predictions` and `references` are binary.
        - \'micro\': Calculate metrics globally by counting the total true positives, false negatives and false positives.
        - \'macro\': Calculate metrics for each label, and find their unweighted mean. This does not take label imbalance into account.
        - \'weighted\': Calculate metrics for each label, and find their average weighted by support (the number of true instances for each label). This alters `\'macro\'` to account for label imbalance. This option can result in an F-score that is not between precision and recall.
        - \'samples\': Calculate metrics for each instance, and find their average (only meaningful for multilabel classification).
    sample_weight (`list` of `float`): Sample weights Defaults to None.

Returns:
    f1 (`float` or `array` of `float`): F1 score or list of f1 scores, depending on the value passed to `average`. Minimum possible value is 0. Maximum possible value is 1. Higher f1 scores are better.

Examples:

    Example 1-A simple binary example
        >>> f1_metric = datasets.load_metric(\"f1\")
        >>> results = f1_metric.compute(references=[0, 1, 0, 1, 0], predictions=[0, 0, 1, 1, 0])
        >>> print(results)
        {\'f1\': 0.5}

    Example 2-The same simple binary example as in Example 1, but with `pos_label` set to `0`.
        >>> f1_metric = datasets.load_metric(\"f1\")
        >>> results = f1_metric.compute(references=[0, 1, 0, 1, 0], predictions=[0, 0, 1, 1, 0], pos_label=0)
        >>> print(round(results[\'f1\'], 2))
        0.67

    Example 3-The same simple binary example as in Example 1, but with `sample_weight` included.
        >>> f1_metric = datasets.load_metric(\"f1\")
        >>> results = f1_metric.compute(references=[0, 1, 0, 1, 0], predictions=[0, 0, 1, 1, 0], sample_weight=[0.9, 0.5, 3.9, 1.2, 0.3])
        >>> print(round(results[\'f1\'], 2))
        0.35

    Example 4-A multiclass example, with different values for the `average` input.
        >>> predictions = [0, 2, 1, 0, 0, 1]
        >>> references = [0, 1, 2, 0, 1, 2]
        >>> results = f1_metric.compute(predictions=predictions, references=references, average=\"macro\")
        >>> print(round(results[\'f1\'], 2))
        0.27
        >>> results = f1_metric.compute(predictions=predictions, references=references, average=\"micro\")
        >>> print(round(results[\'f1\'], 2))
        0.33
        >>> results = f1_metric.compute(predictions=predictions, references=references, average=\"weighted\")
        >>> print(round(results[\'f1\'], 2))
        0.27
        >>> results = f1_metric.compute(predictions=predictions, references=references, average=None)
        >>> print(results)
        {\'f1\': array([0.8, 0. , 0. ])}
'''


_lowerCamelCase :    int  							= '''
@article{scikit-learn,
    title={Scikit-learn: Machine Learning in {P}ython},
    author={Pedregosa, F. and Varoquaux, G. and Gramfort, A. and Michel, V.
           and Thirion, B. and Grisel, O. and Blondel, M. and Prettenhofer, P.
           and Weiss, R. and Dubourg, V. and Vanderplas, J. and Passos, A. and
           Cournapeau, D. and Brucher, M. and Perrot, M. and Duchesnay, E.},
    journal={Journal of Machine Learning Research},
    volume={12},
    pages={2825--2830},
    year={2011}
}
'''


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







							"""simple docstring"""




							def  A_     ( self     :					List[Any]						)				->			List[Any]:





														"""simple docstring"""
														return datasets.MetricInfo(
														    description=_DESCRIPTION,			citation=_CITATION,			inputs_description=_KWARGS_DESCRIPTION,			features=datasets.Features(
														        {
														            "predictions": datasets.Sequence(datasets.Value("int32"						)						),
														            "references": datasets.Sequence(datasets.Value("int32"						)						),
														        }
														        if self.config_name == "multilabel"
														        else {
														            "predictions": datasets.Value("int32"						),
														            "references": datasets.Value("int32"						),
														        }						),			reference_urls=["https://scikit-learn.org/stable/modules/generated/sklearn.metrics.f1_score.html"],			)






							def  A_     ( self     :					Optional[Any],			_UpperCAmelCase     :					Dict,			_UpperCAmelCase     :					Any,			_UpperCAmelCase     :					Any=None,			_UpperCAmelCase     :					Optional[int]=1,			_UpperCAmelCase     :					Any="binary",			_UpperCAmelCase     :					Tuple=None						)				->			Optional[int]:





														"""simple docstring"""
														SCREAMING_SNAKE_CASE__       :      List[str]     =						fa_score(
														    __a,			__a,			labels=__a,			pos_label=__a,			average=__a,			sample_weight=__a						)
														return {"f1": float(__a						) if score.size == 1 else score}













from __future__ import annotations

import time

_lowerCamelCase :    Tuple  							= list[tuple[int, int]]

_lowerCamelCase :    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 :    str  							= [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right


class 						lowerCamelCase       :







							"""simple docstring"""




							def __init__( self     :					Optional[int],			_UpperCAmelCase     :					int,			_UpperCAmelCase     :					int,			_UpperCAmelCase     :					int,			_UpperCAmelCase     :					int,			_UpperCAmelCase     :					Node | None						)				->			Tuple:





														"""simple docstring"""
														SCREAMING_SNAKE_CASE__       :      List[Any]     =						pos_x
														SCREAMING_SNAKE_CASE__       :      List[Any]     =						pos_y
														SCREAMING_SNAKE_CASE__       :      str     =						(pos_y, pos_x)
														SCREAMING_SNAKE_CASE__       :      Dict     =						goal_x
														SCREAMING_SNAKE_CASE__       :      List[Any]     =						goal_y
														SCREAMING_SNAKE_CASE__       :      str     =						parent


class 						lowerCamelCase       :







							"""simple docstring"""




							def __init__( self     :					Dict,			_UpperCAmelCase     :					tuple[int, int],			_UpperCAmelCase     :					tuple[int, int]						)				->			Any:





														"""simple docstring"""
														SCREAMING_SNAKE_CASE__       :      str     =						Node(start[1],			start[0],			goal[1],			goal[0],			_UpperCAmelCase						)
														SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						Node(goal[1],			goal[0],			goal[1],			goal[0],			_UpperCAmelCase						)

														SCREAMING_SNAKE_CASE__       :      Optional[int]     =						[self.start]
														SCREAMING_SNAKE_CASE__       :      str     =						False






							def  A_     ( self     :					Dict						)				->			Path | None:





														"""simple docstring"""
														while self.node_queue:
																					SCREAMING_SNAKE_CASE__       :      int     =						self.node_queue.pop(0						)

																					if current_node.pos == self.target.pos:
																												SCREAMING_SNAKE_CASE__       :      Dict     =						True
																												return self.retrace_path(_UpperCAmelCase						)

																					SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						self.get_successors(_UpperCAmelCase						)

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

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






							def  A_     ( self     :					Any,			_UpperCAmelCase     :					Node						)				->			list[Node]:





														"""simple docstring"""
														SCREAMING_SNAKE_CASE__       :      Dict     =						[]
														for action in delta:
																					SCREAMING_SNAKE_CASE__       :      str     =						parent.pos_x + action[1]
																					SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						parent.pos_y + action[0]
																					if not (0 <= pos_x <= len(grid[0]						) - 1 and 0 <= pos_y <= len(_UpperCAmelCase						) - 1):
																												continue

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

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






							def  A_     ( self     :					List[str],			_UpperCAmelCase     :					Node | None						)				->			Path:





														"""simple docstring"""
														SCREAMING_SNAKE_CASE__       :      Optional[Any]     =						node
														SCREAMING_SNAKE_CASE__       :      Tuple     =						[]
														while current_node is not None:
																					path.append((current_node.pos_y, current_node.pos_x)						)
																					SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						current_node.parent
														path.reverse()
														return path


class 						lowerCamelCase       :







							"""simple docstring"""




							def __init__( self     :					List[str],			_UpperCAmelCase     :					Union[str, Any],			_UpperCAmelCase     :					List[str]						)				->			List[str]:





														"""simple docstring"""
														SCREAMING_SNAKE_CASE__       :      Any     =						BreadthFirstSearch(_UpperCAmelCase,			_UpperCAmelCase						)
														SCREAMING_SNAKE_CASE__       :      Optional[Any]     =						BreadthFirstSearch(_UpperCAmelCase,			_UpperCAmelCase						)
														SCREAMING_SNAKE_CASE__       :      Dict     =						False






							def  A_     ( self     :					List[str]						)				->			Path | None:





														"""simple docstring"""
														while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
																					SCREAMING_SNAKE_CASE__       :      int     =						self.fwd_bfs.node_queue.pop(0						)
																					SCREAMING_SNAKE_CASE__       :      Optional[int]     =						self.bwd_bfs.node_queue.pop(0						)

																					if current_bwd_node.pos == current_fwd_node.pos:
																												SCREAMING_SNAKE_CASE__       :      List[Any]     =						True
																												return self.retrace_bidirectional_path(
																												    _UpperCAmelCase,			_UpperCAmelCase						)

																					SCREAMING_SNAKE_CASE__       :      Optional[Any]     =						current_bwd_node
																					SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						current_fwd_node

																					SCREAMING_SNAKE_CASE__       :      List[str]     =						{
																					    self.fwd_bfs: self.fwd_bfs.get_successors(_UpperCAmelCase						),
																					    self.bwd_bfs: self.bwd_bfs.get_successors(_UpperCAmelCase						),
																					}

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

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






							def  A_     ( self     :					int,			_UpperCAmelCase     :					Node,			_UpperCAmelCase     :					Node						)				->			Path:





														"""simple docstring"""
														SCREAMING_SNAKE_CASE__       :      str     =						self.fwd_bfs.retrace_path(_UpperCAmelCase						)
														SCREAMING_SNAKE_CASE__       :      Any     =						self.bwd_bfs.retrace_path(_UpperCAmelCase						)
														bwd_path.pop()
														bwd_path.reverse()
														SCREAMING_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 :    Optional[Any]  							= (0, 0)
		_lowerCamelCase :    Dict  							= (len(grid) - 1, len(grid[0]) - 1)
		for elem in grid:
				print(elem)

		_lowerCamelCase :    Dict  							= time.time()
		_lowerCamelCase :    List[Any]  							= BreadthFirstSearch(init, goal)
		_lowerCamelCase :    Optional[Any]  							= bfs.search()
		_lowerCamelCase :    Dict  							= time.time() - start_bfs_time

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

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

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






