





'''simple docstring'''


import argparse
import copy







def    _lowerCamelCase  (__lowerCamelCase  :     Tuple     )   ->    Any:
			a__     = {}

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

			return dict_of_neighbours







def    _lowerCamelCase  (__lowerCamelCase  :     int					,  __lowerCamelCase  :     List[str]     )   ->    Dict:

			with open(__lowerCamelCase     ) as f:
						a__     = f.read(1     )
			a__     = start_node

			a__     = []

			a__     = start_node

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

						first_solution.append(__lowerCamelCase     )
						a__     = distance_of_first_solution + int(__lowerCamelCase     )
						a__     = best_node

			first_solution.append(__lowerCamelCase     )

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

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







def    _lowerCamelCase  (__lowerCamelCase  :     List[str]					,  __lowerCamelCase  :     str     )   ->    str:
			a__     = []

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

									a__     = copy.deepcopy(__lowerCamelCase     )
									a__     = kn
									a__     = n

									a__     = 0

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

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

			a__     = len(neighborhood_of_solution[0]     ) - 1

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







def    _lowerCamelCase  (__lowerCamelCase  :     List[str]					,  __lowerCamelCase  :     List[str]					,  __lowerCamelCase  :     Optional[int]					,  __lowerCamelCase  :     str					,  __lowerCamelCase  :     str     )   ->    Tuple:
			a__     = 1
			a__     = first_solution
			a__     = []
			a__     = distance_of_first_solution
			a__     = solution

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

						a__     = False
						while not found:
									a__     = 0
									while i < len(__lowerCamelCase     ):
												if best_solution[i] != solution[i]:
															a__     = best_solution[i]
															a__     = solution[i]
															break
												a__     = 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]     )
												a__     = True
												a__     = best_solution[:-1]
												a__     = neighborhood[index_of_best_solution][best_cost_index]
												if cost < best_cost:
															a__     = cost
															a__     = solution
									else:
												a__     = index_of_best_solution + 1
												a__     = neighborhood[index_of_best_solution]

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

						a__     = count + 1

			return best_solution_ever, best_cost







def    _lowerCamelCase  (__lowerCamelCase  :     List[Any]=None     )   ->    Union[str, Any]:
			a__     = generate_neighbours(args.File     )

			a__   ,				a__     = generate_first_solution(
			    args.File					,  __lowerCamelCase     )

			a__   ,				a__     = tabu_search(
			    __lowerCamelCase					,  __lowerCamelCase					,  __lowerCamelCase					,  args.Iterations					,  args.Size					,  )

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


if __name__ == "__main__":
		lowerCAmelCase_   :   Dict       =					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())










'''simple docstring'''


import importlib
import os
import sys


# This is required to make the module import works (when the python process is running from the root of the repo)
sys.path.append(".")







def    _lowerCamelCase  (__lowerCamelCase  :     List[str]     )   ->    List[str]:
			a__     = test_file.split(os.path.sep     )
			if components[0:2] != ["tests", "models"]:
						raise ValueError(
						    "`test_file` should start with `tests/models/` (with `/` being the OS specific path separator). Got "
						    f'''{test_file} instead.'''     )
			a__     = components[-1]
			if not test_fn.endswith("py"     ):
						raise ValueError(f'''`test_file` should be a python file. Got {test_fn} instead.'''     )
			if not test_fn.startswith("test_modeling_"     ):
						raise ValueError(
						    f'''`test_file` should point to a file name of the form `test_modeling_*.py`. Got {test_fn} instead.'''     )

			a__     = components[:-1] + [test_fn.replace(".py"					,  ""     )]
			a__     = ".".join(__lowerCamelCase     )

			return test_module_path







def    _lowerCamelCase  (__lowerCamelCase  :     Union[str, Any]     )   ->    Optional[Any]:
			a__     = get_module_path(__lowerCamelCase     )
			a__     = importlib.import_module(__lowerCamelCase     )

			return test_module







def    _lowerCamelCase  (__lowerCamelCase  :     Optional[int]     )   ->    Union[str, Any]:
			a__     = []
			a__     = get_test_module(__lowerCamelCase     )
			for attr in dir(__lowerCamelCase     ):
						if attr.endswith("ModelTester"     ):
									tester_classes.append(getattr(__lowerCamelCase					,  __lowerCamelCase     )     )

    # sort with class names
			return sorted(__lowerCamelCase					,  key=lambda __lowerCamelCase     : x.__name__     )







def    _lowerCamelCase  (__lowerCamelCase  :     Tuple     )   ->    Tuple:
			a__     = []
			a__     = get_test_module(__lowerCamelCase     )
			for attr in dir(__lowerCamelCase     ):
						a__     = getattr(__lowerCamelCase					,  __lowerCamelCase     )
						# (TF/Flax)ModelTesterMixin is also an attribute in specific model test module. Let's exclude them by checking
						# `all_model_classes` is not empty (which also excludes other special classes).
						a__     = getattr(__lowerCamelCase					,  "all_model_classes"					,  []     )
						if len(__lowerCamelCase     ) > 0:
									test_classes.append(__lowerCamelCase     )

    # sort with class names
			return sorted(__lowerCamelCase					,  key=lambda __lowerCamelCase     : x.__name__     )







def    _lowerCamelCase  (__lowerCamelCase  :     List[Any]     )   ->    List[Any]:
			a__     = get_test_classes(__lowerCamelCase     )
			a__     = set()
			for test_class in test_classes:
						model_classes.update(test_class.all_model_classes     )

			# sort with class names
			return sorted(__lowerCamelCase					,  key=lambda __lowerCamelCase     : x.__name__     )







def    _lowerCamelCase  (__lowerCamelCase  :     str     )   ->    Dict:
			a__     = test_class()
			if hasattr(__lowerCamelCase					,  "setUp"     ):
						test.setUp()

			a__     = None
			if hasattr(__lowerCamelCase					,  "model_tester"     ):
						# `(TF/Flax)ModelTesterMixin` has this attribute default to `None`. Let's skip this case.
						if test.model_tester is not None:
									a__     = test.model_tester.__class__

			return model_tester







def    _lowerCamelCase  (__lowerCamelCase  :     Dict					,  __lowerCamelCase  :     Optional[int]     )   ->    List[Any]:
			a__     = get_test_classes(__lowerCamelCase     )

			a__     = []
			for test_class in test_classes:
						if model_class in test_class.all_model_classes:
									target_test_classes.append(__lowerCamelCase     )

    # sort with class names
			return sorted(__lowerCamelCase					,  key=lambda __lowerCamelCase     : x.__name__     )







def    _lowerCamelCase  (__lowerCamelCase  :     Any					,  __lowerCamelCase  :     Tuple     )   ->    Dict:
			a__     = get_test_classes_for_model(__lowerCamelCase					,  __lowerCamelCase     )

			a__     = []
			for test_class in test_classes:
						a__     = get_model_tester_from_test_class(__lowerCamelCase     )
						if tester_class is not None:
									tester_classes.append(__lowerCamelCase     )

    # sort with class names
			return sorted(__lowerCamelCase					,  key=lambda __lowerCamelCase     : x.__name__     )







def    _lowerCamelCase  (__lowerCamelCase  :     List[str]     )   ->    int:
			a__     = get_test_classes(__lowerCamelCase     )
			a__     = {test_class: get_model_tester_from_test_class(__lowerCamelCase     ) for test_class in test_classes}
			return test_tester_mapping







def    _lowerCamelCase  (__lowerCamelCase  :     Any     )   ->    List[Any]:
			a__     = get_model_classes(__lowerCamelCase     )
			a__     = {
			    model_class: get_test_classes_for_model(__lowerCamelCase					,  __lowerCamelCase     ) for model_class in model_classes
			}
			return model_test_mapping







def    _lowerCamelCase  (__lowerCamelCase  :     Tuple     )   ->    Tuple:
			a__     = get_model_classes(__lowerCamelCase     )
			a__     = {
			    model_class: get_tester_classes_for_model(__lowerCamelCase					,  __lowerCamelCase     ) for model_class in model_classes
			}
			return model_to_tester_mapping







def    _lowerCamelCase  (__lowerCamelCase  :     str     )   ->    Dict:
			if isinstance(__lowerCamelCase					,  __lowerCamelCase     ):
						return o
			elif isinstance(__lowerCamelCase					,  __lowerCamelCase     ):
						return o.__name__
			elif isinstance(__lowerCamelCase					,  (list, tuple)     ):
						return [to_json(__lowerCamelCase     ) for x in o]
			elif isinstance(__lowerCamelCase					,  __lowerCamelCase     ):
						return {to_json(__lowerCamelCase     ): to_json(__lowerCamelCase     ) for k, v in o.items()}
			else:
						return o



