






'''simple docstring'''





from sklearn.metrics import matthews_corrcoef

import datasets


__UpperCamelCase      :      List[str]     						=						"\nCompute the Matthews correlation coefficient (MCC)\n\nThe Matthews correlation coefficient is used in machine learning as a\nmeasure of the quality of binary and multiclass classifications. It takes\ninto account true and false positives and negatives and is generally\nregarded as a balanced measure which can be used even if the classes are of\nvery different sizes. The MCC is in essence a correlation coefficient value\nbetween -1 and +1. A coefficient of +1 represents a perfect prediction, 0\nan average random prediction and -1 an inverse prediction.  The statistic\nis also known as the phi coefficient. [source: Wikipedia]\n"

__UpperCamelCase      :      List[Any]     						=						"\nArgs:\n    predictions (list of int): Predicted labels, as returned by a model.\n    references (list of int): Ground truth labels.\n    sample_weight (list of int, float, or bool): Sample weights. Defaults to `None`.\nReturns:\n    matthews_correlation (dict containing float): Matthews correlation.\nExamples:\n    Example 1, a basic example with only predictions and references as inputs:\n        >>> matthews_metric = datasets.load_metric(\"matthews_correlation\")\n        >>> results = matthews_metric.compute(references=[1, 3, 2, 0, 3, 2],\n        ...                                     predictions=[1, 2, 2, 0, 3, 3])\n        >>> print(round(results['matthews_correlation'], 2))\n        0.54\n\n    Example 2, the same example as above, but also including sample weights:\n        >>> matthews_metric = datasets.load_metric(\"matthews_correlation\")\n        >>> results = matthews_metric.compute(references=[1, 3, 2, 0, 3, 2],\n        ...                                     predictions=[1, 2, 2, 0, 3, 3],\n        ...                                     sample_weight=[0.5, 3, 1, 1, 1, 2])\n        >>> print(round(results['matthews_correlation'], 2))\n        0.1\n\n    Example 3, the same example as above, but with sample weights that cause a negative correlation:\n        >>> matthews_metric = datasets.load_metric(\"matthews_correlation\")\n        >>> results = matthews_metric.compute(references=[1, 3, 2, 0, 3, 2],\n        ...                                     predictions=[1, 2, 2, 0, 3, 3],\n        ...                                     sample_weight=[0.5, 1, 0, 0, 0, 1])\n        >>> print(round(results['matthews_correlation'], 2))\n        -0.25\n"

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


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







	def  _a   (  self      :							Any			)		-> Optional[Any]:
		"""simple docstring"""







		return datasets.MetricInfo(
		    description=_DESCRIPTION       ,				citation=_CITATION       ,				inputs_description=_KWARGS_DESCRIPTION       ,				features=datasets.Features(
		        {
		            """predictions""": datasets.Value("""int32"""			),
		            """references""": datasets.Value("""int32"""			),
		        }			)       ,				reference_urls=[
		        """https://scikit-learn.org/stable/modules/generated/sklearn.metrics.matthews_corrcoef.html"""
		    ]       ,				)







	def  _a   (  self      :							List[Any]       ,				_lowerCAmelCase      :							Any       ,				_lowerCAmelCase      :							str       ,				_lowerCAmelCase      :							Optional[Any]=None			)		-> List[str]:
		"""simple docstring"""







		return {
		    "matthews_correlation": float(matthews_corrcoef(A__       ,				A__       ,				sample_weight=A__			)			),
		}









import heapq
import sys

import numpy as np

__UpperCamelCase      :      List[str]     						=						tuple[int, int]


class        __UpperCamelCase    :







	def __init__(  self      :							Optional[int]			)		-> Dict:
		"""simple docstring"""







		__lowercase             =  []
		__lowercase             =  set()







	def  _a   (  self      :							int			)		-> List[Any]:
		"""simple docstring"""







		if not self.empty():
			return self.elements[0][0]
		else:
			return float("""inf"""			)







	def  _a   (  self      :							Dict			)		-> Optional[Any]:
		"""simple docstring"""







		return len(self.elements			) == 0







	def  _a   (  self      :							str       ,				_lowerCAmelCase      :							Union[str, Any]       ,				_lowerCAmelCase      :							Optional[Any]			)		-> Dict:
		"""simple docstring"""







		if item not in self.set:
			heapq.heappush(self.elements       ,				(priority, item)			)
			self.set.add(_lowerCAmelCase			)
		else:
			# update
			# print("update", item)
			__lowercase             =  []
			((__lowercase)       ,						(__lowercase))             =  heapq.heappop(self.elements			)
			while x != item:
				temp.append((pri, x)			)
				((__lowercase)       ,						(__lowercase))             =  heapq.heappop(self.elements			)
			temp.append((priority, item)			)
			for pro, xxx in temp:
				heapq.heappush(self.elements       ,				(pro, xxx)			)







	def  _a   (  self      :							List[str]       ,				_lowerCAmelCase      :							Optional[Any]			)		-> Dict:
		"""simple docstring"""







		if item in self.set:
			self.set.remove(_lowerCAmelCase			)
			__lowercase             =  []
			((__lowercase)       ,						(__lowercase))             =  heapq.heappop(self.elements			)
			while x != item:
				temp.append((pro, x)			)
				((__lowercase)       ,						(__lowercase))             =  heapq.heappop(self.elements			)
			for prito, yyy in temp:
				heapq.heappush(self.elements       ,				(prito, yyy)			)







	def  _a   (  self      :							Any			)		-> List[Any]:
		"""simple docstring"""







		return self.elements[0][1]







	def  _a   (  self      :							Optional[int]			)		-> List[Any]:
		"""simple docstring"""







		((__lowercase)       ,						(__lowercase))             =  heapq.heappop(self.elements			)
		self.set.remove(_lowerCAmelCase			)
		return (priority, item)





def 				snake_case  (     lowerCamelCase				,  lowerCamelCase					):




	'''simple docstring'''







	__lowercase             =  np.array(lowerCamelCase					)
	__lowercase             =  np.array(lowerCamelCase					)
	return np.linalg.norm(a - b					)





def 				snake_case  (     lowerCamelCase				,  lowerCamelCase					):




	'''simple docstring'''







	return consistent_heuristic(lowerCamelCase				,  lowerCamelCase					) // t





def 				snake_case  (     lowerCamelCase				,  lowerCamelCase					):




	'''simple docstring'''







	return abs(p[0] - goal[0]					) + abs(p[1] - goal[1]					)





def 				snake_case  (     lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase					):




	'''simple docstring'''







	__lowercase             =  g_function[start] + Wa * heuristics[i](lowerCamelCase				,  lowerCamelCase					)
	return ans





def 				snake_case  (     lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase					):




	'''simple docstring'''







	__lowercase             =  np.chararray((n, n)					)
	for i in range(lowerCamelCase					):
		for j in range(lowerCamelCase					):
			__lowercase             =  """*"""

	for i in range(lowerCamelCase					):
		for j in range(lowerCamelCase					):
			if (j, (n - 1) - i) in blocks:
				__lowercase             =  """#"""

	__lowercase             =  """-"""
	__lowercase             =  back_pointer[goal]
	while x != start:
		((__lowercase)       ,						(__lowercase))             =  x
		# print(x)
		__lowercase             =  """-"""
		__lowercase             =  back_pointer[x]
	__lowercase             =  """-"""

	for i in range(lowerCamelCase					):
		for j in range(lowerCamelCase					):
			if (i, j) == (0, n - 1):
				print(grid[i][j]				,  end=""" """					)
				print("""<-- End position"""				,  end=""" """					)
			else:
				print(grid[i][j]				,  end=""" """					)
		print()
	print("""^"""					)
	print("""Start position"""					)
	print()
	print("""# is an obstacle"""					)
	print("""- is the path taken by algorithm"""					)
	print("""PATH TAKEN BY THE ALGORITHM IS:-"""					)
	__lowercase             =  back_pointer[goal]
	while x != start:
		print(lowerCamelCase				,  end=""" """					)
		__lowercase             =  back_pointer[x]
	print(lowerCamelCase					)
	sys.exit()





def 				snake_case  (     lowerCamelCase					):




	'''simple docstring'''







	if p[0] < 0 or p[0] > n - 1:
		return False
	if p[1] < 0 or p[1] > n - 1:
		return False
	return True





def 				snake_case  (     lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  ):




	'''simple docstring'''







	for itera in range(lowerCamelCase					):
		open_list[itera].remove_element(lowerCamelCase					)
	# print("s", s)
	# print("j", j)
	((__lowercase)       ,						(__lowercase))             =  s
	__lowercase             =  (x - 1, y)
	__lowercase             =  (x + 1, y)
	__lowercase             =  (x, y + 1)
	__lowercase             =  (x, y - 1)

	for neighbours in [left, right, up, down]:
		if neighbours not in blocks:
			if valid(lowerCamelCase					) and neighbours not in visited:
				# print("neighbour", neighbours)
				visited.add(lowerCamelCase					)
				__lowercase             =  -1
				__lowercase             =  float("""inf"""					)

			if valid(lowerCamelCase					) and g_function[neighbours] > g_function[s] + 1:
				__lowercase             =  g_function[s] + 1
				__lowercase             =  s
				if neighbours not in close_list_anchor:
					open_list[0].put(lowerCamelCase				,  key(lowerCamelCase				,  0				,  lowerCamelCase				,  lowerCamelCase					)					)
					if neighbours not in close_list_inad:
						for var in range(1				,  lowerCamelCase					):
							if key(lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase					) <= Wa * key(
							    lowerCamelCase				,  0				,  lowerCamelCase				,  lowerCamelCase					):
								open_list[j].put(
								    lowerCamelCase				,  key(lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase					)					)





def 				snake_case  (     ):




	'''simple docstring'''







	__lowercase             =  []
	for x in range(1				,  5					):
		for y in range(1				,  6					):
			some_list.append((x, y)					)

	for x in range(15				,  20					):
		some_list.append((x, 17)					)

	for x in range(10				,  19					):
		for y in range(1				,  15					):
			some_list.append((x, y)					)

    # L block
	for x in range(1				,  4					):
		for y in range(12				,  19					):
			some_list.append((x, y)					)
	for x in range(3				,  13					):
		for y in range(16				,  19					):
			some_list.append((x, y)					)
	return some_list


__UpperCamelCase      :      Optional[int]     						=						{0: consistent_heuristic, 1: heuristic_a, 2: heuristic_a}

__UpperCamelCase      :      Optional[Any]     						=						[
    (0, 1),
    (1, 1),
    (2, 1),
    (3, 1),
    (4, 1),
    (5, 1),
    (6, 1),
    (7, 1),
    (8, 1),
    (9, 1),
    (10, 1),
    (11, 1),
    (12, 1),
    (13, 1),
    (14, 1),
    (15, 1),
    (16, 1),
    (17, 1),
    (18, 1),
    (19, 1),
]
__UpperCamelCase      :      Optional[Any]     						=						make_common_ground()


__UpperCamelCase      :      Dict     						=						blocks_blk
# hyper parameters
__UpperCamelCase      :      Union[str, Any]     						=						1
__UpperCamelCase      :      Union[str, Any]     						=						1
__UpperCamelCase      :      Optional[int]     						=						20
__UpperCamelCase      :      List[str]     						=						3  # one consistent and two other inconsistent

# start and end destination
__UpperCamelCase      :      str     						=						(0, 0)
__UpperCamelCase      :      str     						=						(n - 1, n - 1)

__UpperCamelCase      :      Optional[Any]     						=						1





def 				snake_case  (     lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase					):




	'''simple docstring'''







	__lowercase             =  {start: 0, goal: float("""inf"""					)}
	__lowercase             =  {start: -1, goal: -1}
	__lowercase             =  []
	__lowercase             =  set()

	for i in range(lowerCamelCase					):
		open_list.append(PriorityQueue()					)
		open_list[i].put(lowerCamelCase				,  key(lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase					)					)

	__lowercase             =  []
	__lowercase             =  []
	while open_list[0].minkey() < float("""inf"""					):
		for i in range(1				,  lowerCamelCase					):
			# print(open_list[0].minkey(), open_list[i].minkey())
			if open_list[i].minkey() <= Wa * open_list[0].minkey():
				global t
				t += 1
				if g_function[goal] <= open_list[i].minkey():
					if g_function[goal] < float("""inf"""					):
						do_something(lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase					)
				else:
					__lowercase       ,						__lowercase             =  open_list[i].top_show()
					visited.add(lowerCamelCase					)
					expand_state(
					    lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  )
					close_list_inad.append(lowerCamelCase					)
			else:
				if g_function[goal] <= open_list[0].minkey():
					if g_function[goal] < float("""inf"""					):
						do_something(lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase					)
				else:
					__lowercase             =  open_list[0].top_show()
					visited.add(lowerCamelCase					)
					expand_state(
					    lowerCamelCase				,  0				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  )
					close_list_anchor.append(lowerCamelCase					)
	print("""No path found to goal"""					)
	print()
	for i in range(n - 1				,  -1				,  -1					):
		for j in range(lowerCamelCase					):
			if (j, i) in blocks:
				print("""#"""				,  end=""" """					)
			elif (j, i) in back_pointer:
				if (j, i) == (n - 1, n - 1):
					print("""*"""				,  end=""" """					)
				else:
					print("""-"""				,  end=""" """					)
			else:
				print("""*"""				,  end=""" """					)
			if (j, i) == (n - 1, n - 1):
				print("""<-- End position"""				,  end=""" """					)
		print()
	print("""^"""					)
	print("""Start position"""					)
	print()
	print("""# is an obstacle"""					)
	print("""- is the path taken by algorithm"""					)


if __name__ == "__main__":
						multi_a_star(start, goal, n_heuristic)

