


import argparse
import copy






def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE      )->						Optional[int]:




      """simple docstring"""

      snake_case_ =   {}

      with open(SCREAMING_SNAKE_CASE      ) as f:
            for line in f:
                  if line.split()[0] not in dict_of_neighbours:
                        snake_case_ =   []
                        _list.append([line.split()[1], line.split()[2]]      )
                        snake_case_ =   _list
                  else:
                        dict_of_neighbours[line.split()[0]].append(
                            [line.split()[1], line.split()[2]]      )
                  if line.split()[1] not in dict_of_neighbours:
                        snake_case_ =   []
                        _list.append([line.split()[0], line.split()[2]]      )
                        snake_case_ =   _list
                  else:
                        dict_of_neighbours[line.split()[1]].append(
                            [line.split()[0], line.split()[2]]      )

      return dict_of_neighbours






def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE      ,      SCREAMING_SNAKE_CASE      )->						Union[str, Any]:




      """simple docstring"""

      with open(SCREAMING_SNAKE_CASE      ) as f:
            snake_case_ =   f.read(1      )
      snake_case_ =   start_node

      snake_case_ =   []

      snake_case_ =   start_node

      snake_case_ =   0
      while visiting not in first_solution:
            snake_case_ =   1_0000
            for k in dict_of_neighbours[visiting]:
                  if int(k[1]      ) < int(SCREAMING_SNAKE_CASE      ) and k[0] not in first_solution:
                        snake_case_ =   k[1]
                        snake_case_ =   k[0]

            first_solution.append(SCREAMING_SNAKE_CASE      )
            snake_case_ =   distance_of_first_solution + int(SCREAMING_SNAKE_CASE      )
            snake_case_ =   best_node

      first_solution.append(SCREAMING_SNAKE_CASE      )

      snake_case_ =   0
      for k in dict_of_neighbours[first_solution[-2]]:
            if k[0] == start_node:
                  break
            position += 1

      snake_case_ =   (
          distance_of_first_solution
          + int(dict_of_neighbours[first_solution[-2]][position][1]      )
          - 1_0000
      )
      return first_solution, distance_of_first_solution






def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE      ,      SCREAMING_SNAKE_CASE      )->						List[Any]:




      """simple docstring"""

      snake_case_ =   []

      for n in solution[1:-1]:
            snake_case_ =   solution.index(SCREAMING_SNAKE_CASE      )
            for kn in solution[1:-1]:
                  snake_case_ =   solution.index(SCREAMING_SNAKE_CASE      )
                  if n == kn:
                        continue

                  snake_case_ =   copy.deepcopy(SCREAMING_SNAKE_CASE      )
                  snake_case_ =   kn
                  snake_case_ =   n

                  snake_case_ =   0

                  for k in _tmp[:-1]:
                        snake_case_ =   _tmp[_tmp.index(SCREAMING_SNAKE_CASE      ) + 1]
                        for i in dict_of_neighbours[k]:
                              if i[0] == next_node:
                                    snake_case_ =   distance + int(i[1]      )
                  _tmp.append(SCREAMING_SNAKE_CASE      )

                  if _tmp not in neighborhood_of_solution:
                        neighborhood_of_solution.append(_tmp      )

      snake_case_ =   len(neighborhood_of_solution[0]      ) - 1

      neighborhood_of_solution.sort(key=lambda SCREAMING_SNAKE_CASE      : x[index_of_last_item_in_the_list]      )
      return neighborhood_of_solution






def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE      ,      SCREAMING_SNAKE_CASE      ,      SCREAMING_SNAKE_CASE      ,      SCREAMING_SNAKE_CASE      ,      SCREAMING_SNAKE_CASE      )->						List[Any]:




      """simple docstring"""

      snake_case_ =   1
      snake_case_ =   first_solution
      snake_case_ =   []
      snake_case_ =   distance_of_first_solution
      snake_case_ =   solution

      while count <= iters:
            snake_case_ =   find_neighborhood(SCREAMING_SNAKE_CASE      ,      SCREAMING_SNAKE_CASE      )
            snake_case_ =   0
            snake_case_ =   neighborhood[index_of_best_solution]
            snake_case_ =   len(SCREAMING_SNAKE_CASE      ) - 1

            snake_case_ =   False
            while not found:
                  snake_case_ =   0
                  while i < len(SCREAMING_SNAKE_CASE      ):
                        if best_solution[i] != solution[i]:
                              snake_case_ =   best_solution[i]
                              snake_case_ =   solution[i]
                              break
                        snake_case_ =   i + 1

                  if [first_exchange_node, second_exchange_node] not in tabu_list and [
                      second_exchange_node,
                      first_exchange_node,
                  ] not in tabu_list:
                        tabu_list.append([first_exchange_node, second_exchange_node]      )
                        snake_case_ =   True
                        snake_case_ =   best_solution[:-1]
                        snake_case_ =   neighborhood[index_of_best_solution][best_cost_index]
                        if cost < best_cost:
                              snake_case_ =   cost
                              snake_case_ =   solution
                  else:
                        snake_case_ =   index_of_best_solution + 1
                        snake_case_ =   neighborhood[index_of_best_solution]

            if len(SCREAMING_SNAKE_CASE      ) >= size:
                  tabu_list.pop(0      )

            snake_case_ =   count + 1

      return best_solution_ever, best_cost






def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE=None      )->						int:




      """simple docstring"""

      snake_case_ =   generate_neighbours(args.File      )

      snake_case_ ,					snake_case_ =   generate_first_solution(
          args.File      ,      SCREAMING_SNAKE_CASE      )

      snake_case_ ,					snake_case_ =   tabu_search(
          SCREAMING_SNAKE_CASE      ,      SCREAMING_SNAKE_CASE      ,      SCREAMING_SNAKE_CASE      ,      args.Iterations      ,      args.Size      ,      )

      print(f'''Best solution: {best_sol}, with total distance: {best_cost}.'''      )


if __name__ == "__main__":
   UpperCAmelCase    =					argparse.ArgumentParser(description="""Tabu Search""")
   parser.add_argument(
       """-f""",
       """--File""",
       type=str,
       help="""Path to the file containing the data""",
       required=True,
   )
   parser.add_argument(
       """-i""",
       """--Iterations""",
       type=int,
       help="""How many iterations the algorithm should perform""",
       required=True,
   )
   parser.add_argument(
       """-s""", """--Size""", type=int, help="""Size of the tabu list""", required=True
   )

   # Pass the arguments to main method
   main(parser.parse_args())



import numpy as np

import datasets


UpperCAmelCase    =					"""
Compute the Mahalanobis Distance

Mahalonobis distance is the distance between a point and a distribution.
And not between two distinct points. It is effectively a multivariate equivalent of the Euclidean distance.
It was introduced by Prof. P. C. Mahalanobis in 1936
and has been used in various statistical applications ever since
[source: https://www.machinelearningplus.com/statistics/mahalanobis-distance/]
"""

UpperCAmelCase    =					"""\
@article{de2000mahalanobis,
  title={The mahalanobis distance},
  author={De Maesschalck, Roy and Jouan-Rimbaud, Delphine and Massart, D{\'e}sir{\'e} L},
  journal={Chemometrics and intelligent laboratory systems},
  volume={50},
  number={1},
  pages={1--18},
  year={2000},
  publisher={Elsevier}
}
"""

UpperCAmelCase    =					"""
Args:
    X: List of datapoints to be compared with the `reference_distribution`.
    reference_distribution: List of datapoints from the reference distribution we want to compare to.
Returns:
    mahalanobis: The Mahalonobis distance for each datapoint in `X`.
Examples:

    >>> mahalanobis_metric = datasets.load_metric(\"mahalanobis\")
    >>> results = mahalanobis_metric.compute(reference_distribution=[[0, 1], [1, 0]], X=[[0, 1]])
    >>> print(results)
    {'mahalanobis': array([0.5])}
"""







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

 '''simple docstring'''

 def 		UpperCamelCase__  (			self      ):
       return datasets.MetricInfo(
           description=_DESCRIPTION	,   citation=_CITATION	,   inputs_description=_KWARGS_DESCRIPTION	,   features=datasets.Features(
               {
                   '''X''': datasets.Sequence(datasets.Value('''float'''	,   id='''sequence'''      )	,   id='''X'''      ),
               }      )	,   )





 def 		UpperCamelCase__  (			self	,   _UpperCAmelCase	,   _UpperCAmelCase      ):
       # convert to numpy arrays
       snake_case_ =   np.array(_UpperCAmelCase      )
       snake_case_ =   np.array(_UpperCAmelCase      )

       # Assert that arrays are 2D
       if len(X.shape      ) != 2:
             raise ValueError('''Expected `X` to be a 2D vector'''      )
       if len(reference_distribution.shape      ) != 2:
             raise ValueError('''Expected `reference_distribution` to be a 2D vector'''      )
       if reference_distribution.shape[0] < 2:
             raise ValueError(
                 '''Expected `reference_distribution` to be a 2D vector with more than one element in the first dimension'''      )

       # Get mahalanobis distance for each prediction
       snake_case_ =   X - np.mean(_UpperCAmelCase      )
       snake_case_ =   np.cov(reference_distribution.T      )
       try:
             snake_case_ =   np.linalg.inv(_UpperCAmelCase      )
       except np.linalg.LinAlgError:
             snake_case_ =   np.linalg.pinv(_UpperCAmelCase      )
       snake_case_ =   np.dot(_UpperCAmelCase	,   _UpperCAmelCase      )
       snake_case_ =   np.dot(_UpperCAmelCase	,   X_minus_mu.T      ).diagonal()

       return {"mahalanobis": mahal_dist}