


from __future__ import annotations

import os
from collections.abc import Mapping

__UpperCamelCase     		=							tuple[int, int]







class 							lowerCamelCase__						:






			"""simple docstring"""






			def __init__(				self   ,    snake_case   ,    snake_case  ):

						'''simple docstring'''


						UpperCamelCase__       =							vertices
						UpperCamelCase__       =							{
						    (min(snake_case  ), max(snake_case  )): weight for edge, weight in edges.items()
						}




			def 					snake_case__					(				self   ,    snake_case   ,    snake_case  ):

						'''simple docstring'''


						self.vertices.add(edge[0]  )
						self.vertices.add(edge[1]  )
						UpperCamelCase__       =							weight







			def 					snake_case__					(				self  ):

						'''simple docstring'''


						UpperCamelCase__       =							Graph({min(self.vertices  )}   ,    {}  )
						UpperCamelCase__       =							42
						UpperCamelCase__       =							42
						UpperCamelCase__       =							42
						UpperCamelCase__       =							42

						while len(subgraph.vertices  ) < len(self.vertices  ):
									UpperCamelCase__       =							max(self.edges.values()  ) + 1
									for edge, weight in self.edges.items():
												if (edge[0] in subgraph.vertices) ^ (edge[1] in subgraph.vertices):
															if weight < min_weight:
																		UpperCamelCase__       =							edge
																		UpperCamelCase__       =							weight

									subgraph.add_edge(snake_case   ,    snake_case  )

						return subgraph



def 							UpperCamelCase_(					_A :str = "p107_network.txt"	)->		int:
			UpperCamelCase__       =							os.path.abspath(os.path.dirname(_A	)	)
			UpperCamelCase__       =							os.path.join(_A					,  _A	)
			UpperCamelCase__       =							{}
			UpperCamelCase__       =							42
			UpperCamelCase__       =							42
			UpperCamelCase__       =							42

			with open(_A	) as f:
						UpperCamelCase__       =							f.read().strip().split("\n"	)

			UpperCamelCase__       =							[line.split(","	) for line in data]

			for edgea in range(1					,  len(_A	)	):
						for edgea in range(_A	):
									if adjaceny_matrix[edgea][edgea] != "-":
												UpperCamelCase__       =							int(adjaceny_matrix[edgea][edgea]	)

			UpperCamelCase__       =							Graph(set(range(len(_A	)	)	)					,  _A	)

			UpperCamelCase__       =							graph.prims_algorithm()

			UpperCamelCase__       =							sum(graph.edges.values()	)
			UpperCamelCase__       =							sum(subgraph.edges.values()	)

			return initial_total - optimal_total


if __name__ == "__main__":
						print(f'''{solution() = }''')






import re
import string

import numpy as np

import datasets


__UpperCamelCase     		=							'\nReturns the rate at which the input predicted strings exactly match their references, ignoring any strings input as part of the regexes_to_ignore list.\n'

__UpperCamelCase     		=							'\nArgs:\n    predictions: List of predicted texts.\n    references: List of reference texts.\n    regexes_to_ignore: List, defaults to None. Regex expressions of characters to\n        ignore when calculating the exact matches. Note: these regexes are removed\n        from the input data before the changes based on the options below (e.g. ignore_case,\n        ignore_punctuation, ignore_numbers) are applied.\n    ignore_case: Boolean, defaults to False. If true, turns everything\n        to lowercase so that capitalization differences are ignored.\n    ignore_punctuation: Boolean, defaults to False. If true, removes all punctuation before\n        comparing predictions and references.\n    ignore_numbers: Boolean, defaults to False. If true, removes all punctuation before\n        comparing predictions and references.\nReturns:\n    exact_match: Dictionary containing exact_match rate. Possible values are between 0.0 and 100.0, inclusive.\nExamples:\n    >>> exact_match = datasets.load_metric("exact_match")\n    >>> refs = ["the cat", "theater", "YELLING", "agent007"]\n    >>> preds = ["cat?", "theater", "yelling", "agent"]\n    >>> results = exact_match.compute(references=refs, predictions=preds)\n    >>> print(round(results["exact_match"], 1))\n    25.0\n\n    >>> exact_match = datasets.load_metric("exact_match")\n    >>> refs = ["the cat", "theater", "YELLING", "agent007"]\n    >>> preds = ["cat?", "theater", "yelling", "agent"]\n    >>> results = exact_match.compute(references=refs, predictions=preds, regexes_to_ignore=["the ", "yell"], ignore_case=True, ignore_punctuation=True)\n    >>> print(round(results["exact_match"], 1))\n    50.0\n\n\n    >>> exact_match = datasets.load_metric("exact_match")\n    >>> refs = ["the cat", "theater", "YELLING", "agent007"]\n    >>> preds = ["cat?", "theater", "yelling", "agent"]\n    >>> results = exact_match.compute(references=refs, predictions=preds, regexes_to_ignore=["the ", "yell", "YELL"], ignore_case=True, ignore_punctuation=True)\n    >>> print(round(results["exact_match"], 1))\n    75.0\n\n    >>> exact_match = datasets.load_metric("exact_match")\n    >>> refs = ["the cat", "theater", "YELLING", "agent007"]\n    >>> preds = ["cat?", "theater", "yelling", "agent"]\n    >>> results = exact_match.compute(references=refs, predictions=preds, regexes_to_ignore=["the ", "yell", "YELL"], ignore_case=True, ignore_punctuation=True, ignore_numbers=True)\n    >>> print(round(results["exact_match"], 1))\n    100.0\n\n    >>> exact_match = datasets.load_metric("exact_match")\n    >>> refs = ["The cat sat on the mat.", "Theaters are great.", "It\'s like comparing oranges and apples."]\n    >>> preds = ["The cat sat on the mat?", "Theaters are great.", "It\'s like comparing apples and oranges."]\n    >>> results = exact_match.compute(references=refs, predictions=preds)\n    >>> print(round(results["exact_match"], 1))\n    33.3\n\n'

__UpperCamelCase     		=							'\n'







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






			"""simple docstring"""






			def 					snake_case__					(				self  ):

						'''simple docstring'''


						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"  ),
						        }  )   ,    reference_urls=[]   ,    )







			def 					snake_case__					(				self   ,    snake_case   ,    snake_case   ,    snake_case=None   ,    snake_case=False   ,    snake_case=False   ,    snake_case=False   ,    ):

						'''simple docstring'''


						if regexes_to_ignore is not None:
									for s in regexes_to_ignore:
												UpperCamelCase__       =							np.array([re.sub(snake_case   ,    ""   ,    snake_case  ) for x in predictions]  )
												UpperCamelCase__       =							np.array([re.sub(snake_case   ,    ""   ,    snake_case  ) for x in references]  )
						else:
									UpperCamelCase__       =							np.asarray(snake_case  )
									UpperCamelCase__       =							np.asarray(snake_case  )

						if ignore_case:
									UpperCamelCase__       =							np.char.lower(snake_case  )
									UpperCamelCase__       =							np.char.lower(snake_case  )

						if ignore_punctuation:
									UpperCamelCase__       =							string.punctuation.maketrans(""   ,    ""   ,    string.punctuation  )
									UpperCamelCase__       =							np.char.translate(snake_case   ,    table=snake_case  )
									UpperCamelCase__       =							np.char.translate(snake_case   ,    table=snake_case  )

						if ignore_numbers:
									UpperCamelCase__       =							string.digits.maketrans(""   ,    ""   ,    string.digits  )
									UpperCamelCase__       =							np.char.translate(snake_case   ,    table=snake_case  )
									UpperCamelCase__       =							np.char.translate(snake_case   ,    table=snake_case  )

						UpperCamelCase__       =							predictions == references

						return {"exact_match": np.mean(snake_case  ) * 100}


