


'''simple docstring'''

import argparse
import copy





def lowerCamelCase			(			lowerCAmelCase				:	Optional[int]		):





	"""simple docstring"""







	__magic_name__       :    List[str]     	=     {}

	with open(SCREAMING_SNAKE_CASE__		) as f:
		for line in f:
			if line.split()[0] not in dict_of_neighbours:
				__magic_name__       :    List[str]     	=     []
				_list.append([line.split()[1], line.split()[2]]		)
				__magic_name__       :    Union[str, Any]     	=     _list
			else:
				dict_of_neighbours[line.split()[0]].append(
				    [line.split()[1], line.split()[2]]		)
			if line.split()[1] not in dict_of_neighbours:
				__magic_name__       :    int     	=     []
				_list.append([line.split()[0], line.split()[2]]		)
				__magic_name__       :    Tuple     	=     _list
			else:
				dict_of_neighbours[line.split()[1]].append(
				    [line.split()[0], line.split()[2]]		)

	return dict_of_neighbours





def lowerCamelCase			(			lowerCAmelCase				:	Any		,		lowerCAmelCase				:	Dict		):





	"""simple docstring"""







	with open(SCREAMING_SNAKE_CASE__		) as f:
		__magic_name__       :    Any     	=     f.read(1		)
	__magic_name__       :    str     	=     start_node

	__magic_name__       :    Optional[Any]     	=     []

	__magic_name__       :    List[str]     	=     start_node

	__magic_name__       :    int     	=     0
	while visiting not in first_solution:
		__magic_name__       :    Optional[int]     	=     1_0000
		for k in dict_of_neighbours[visiting]:
			if int(k[1]		) < int(SCREAMING_SNAKE_CASE__		) and k[0] not in first_solution:
				__magic_name__       :    Dict     	=     k[1]
				__magic_name__       :    Tuple     	=     k[0]

		first_solution.append(SCREAMING_SNAKE_CASE__		)
		__magic_name__       :    List[Any]     	=     distance_of_first_solution + int(SCREAMING_SNAKE_CASE__		)
		__magic_name__       :    Union[str, Any]     	=     best_node

	first_solution.append(SCREAMING_SNAKE_CASE__		)

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

	__magic_name__       :    str     	=     (
	    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				:	Dict		,		lowerCAmelCase				:	int		):





	"""simple docstring"""







	__magic_name__       :    Any     	=     []

	for n in solution[1:-1]:
		__magic_name__       :    int     	=     solution.index(SCREAMING_SNAKE_CASE__		)
		for kn in solution[1:-1]:
			__magic_name__       :    str     	=     solution.index(SCREAMING_SNAKE_CASE__		)
			if n == kn:
				continue

			__magic_name__       :    Union[str, Any]     	=     copy.deepcopy(SCREAMING_SNAKE_CASE__		)
			__magic_name__       :    str     	=     kn
			__magic_name__       :    Optional[int]     	=     n

			__magic_name__       :    Union[str, Any]     	=     0

			for k in _tmp[:-1]:
				__magic_name__       :    Dict     	=     _tmp[_tmp.index(SCREAMING_SNAKE_CASE__		) + 1]
				for i in dict_of_neighbours[k]:
					if i[0] == next_node:
						__magic_name__       :    Optional[Any]     	=     distance + int(i[1]		)
			_tmp.append(SCREAMING_SNAKE_CASE__		)

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

	__magic_name__       :    Union[str, Any]     	=     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				:	Tuple		,		lowerCAmelCase				:	str		,		lowerCAmelCase				:	str		,		lowerCAmelCase				:	Tuple		,		lowerCAmelCase				:	int		):





	"""simple docstring"""







	__magic_name__       :    Union[str, Any]     	=     1
	__magic_name__       :    Optional[Any]     	=     first_solution
	__magic_name__       :    Tuple     	=     []
	__magic_name__       :    Optional[int]     	=     distance_of_first_solution
	__magic_name__       :    str     	=     solution

	while count <= iters:
		__magic_name__       :    List[Any]     	=     find_neighborhood(SCREAMING_SNAKE_CASE__		,		SCREAMING_SNAKE_CASE__		)
		__magic_name__       :    List[str]     	=     0
		__magic_name__       :    Union[str, Any]     	=     neighborhood[index_of_best_solution]
		__magic_name__       :    Union[str, Any]     	=     len(SCREAMING_SNAKE_CASE__		) - 1

		__magic_name__       :    List[str]     	=     False
		while not found:
			__magic_name__       :    str     	=     0
			while i < len(SCREAMING_SNAKE_CASE__		):
				if best_solution[i] != solution[i]:
					__magic_name__       :    List[str]     	=     best_solution[i]
					__magic_name__       :    int     	=     solution[i]
					break
				__magic_name__       :    Optional[int]     	=     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]		)
				__magic_name__       :    Tuple     	=     True
				__magic_name__       :    int     	=     best_solution[:-1]
				__magic_name__       :    List[Any]     	=     neighborhood[index_of_best_solution][best_cost_index]
				if cost < best_cost:
					__magic_name__       :    int     	=     cost
					__magic_name__       :    Tuple     	=     solution
			else:
				__magic_name__       :    List[str]     	=     index_of_best_solution + 1
				__magic_name__       :    Any     	=     neighborhood[index_of_best_solution]

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

		__magic_name__       :    Tuple     	=     count + 1

	return best_solution_ever, best_cost





def lowerCamelCase			(			lowerCAmelCase				:	Optional[Any]=None		):





	"""simple docstring"""







	__magic_name__       :    Optional[Any]     	=     generate_neighbours(args.File		)

	__magic_name__       :    Union[str, Any]     	=     generate_first_solution(
	    args.File		,		SCREAMING_SNAKE_CASE__		)

	__magic_name__       :    str     	=     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__":
							lowerCAmelCase      :Any    	=			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 os
import sys
import unittest


lowerCamelCase											=       os.path.abspath(os.path.dirname(os.path.dirname(os.path.dirname(__file__))))
sys.path.append(os.path.join(git_repo_path, 'utils'))

import check_dummies  # noqa: E402
from check_dummies import create_dummy_files, create_dummy_object, find_backend, read_init  # noqa: E402


# Align TRANSFORMERS_PATH in check_dummies with the current path
lowerCamelCase											=       os.path.join(git_repo_path, 'src', 'transformers')

lowerCamelCase											=       '\n{0} = None\n'

lowerCamelCase											=       '\nclass {0}(metaclass=DummyObject):\n    _backends = {1}\n\n    def __init__(self, *args, **kwargs):\n        requires_backends(self, {1})\n'


lowerCamelCase											=       '\ndef {0}(*args, **kwargs):\n    requires_backends({0}, {1})\n'




class A  (   unittest.TestCase     ):






      def        lowerCamelCase       (					self						:     Tuple )					->						Union[str, Any]:
             """simple docstring"""




             _lowerCamelCase       :		int		=find_backend('    _import_structure["models.albert"].append("AlbertTokenizerFast")' )
             self.assertIsNone(lowercase_ )

             _lowerCamelCase       :		List[str]		=find_backend('    if not is_tokenizers_available():' )
             self.assertEqual(lowercase_			,   'tokenizers' )

             _lowerCamelCase       :		List[Any]		=find_backend('    if not is_tensorflow_text_available():' )
             self.assertEqual(lowercase_			,   'tensorflow_text' )

             _lowerCamelCase       :		int		=find_backend('    if not (is_sentencepiece_available() and is_tokenizers_available()):' )
             self.assertEqual(lowercase_			,   'sentencepiece_and_tokenizers' )

             _lowerCamelCase       :		Dict		=find_backend(
                 '    if not (is_sentencepiece_available() and is_tensorflow_text_available()):' )
             self.assertEqual(lowercase_			,   'sentencepiece_and_tensorflow_text' )

             _lowerCamelCase       :		List[Any]		=find_backend(
                 '    if not (is_sentencepiece_available() and is_tokenizers_available() and is_vision_available()):' )
             self.assertEqual(lowercase_			,   'sentencepiece_and_tokenizers_and_vision' )






      def        lowerCamelCase       (					self						:     Optional[Any] )					->						List[str]:
             """simple docstring"""




             _lowerCamelCase       :		Union[str, Any]		=read_init()
             # We don't assert on the exact list of keys to allow for smooth grow of backend-specific objects
             self.assertIn('torch'			,   lowercase_ )
             self.assertIn('tensorflow_text'			,   lowercase_ )
             self.assertIn('sentencepiece_and_tokenizers'			,   lowercase_ )

             # Likewise, we can't assert on the exact content of a key
             self.assertIn('BertModel'			,   objects['torch'] )
             self.assertIn('TFBertModel'			,   objects['tf'] )
             self.assertIn('FlaxBertModel'			,   objects['flax'] )
             self.assertIn('BertModel'			,   objects['torch'] )
             self.assertIn('TFBertTokenizer'			,   objects['tensorflow_text'] )
             self.assertIn('convert_slow_tokenizer'			,   objects['sentencepiece_and_tokenizers'] )






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




             _lowerCamelCase       :		Optional[Any]		=create_dummy_object('CONSTANT'			,   '\'torch\'' )
             self.assertEqual(lowercase_			,   '\nCONSTANT = None\n' )

             _lowerCamelCase       :		Dict		=create_dummy_object('function'			,   '\'torch\'' )
             self.assertEqual(
                 lowercase_			,   '\ndef function(*args, **kwargs):\n    requires_backends(function, \'torch\')\n' )

             _lowerCamelCase       :		Union[str, Any]		='\nclass FakeClass(metaclass=DummyObject):\n    _backends = \'torch\'\n\n    def __init__(self, *args, **kwargs):\n        requires_backends(self, \'torch\')\n'
             _lowerCamelCase       :		Tuple		=create_dummy_object('FakeClass'			,   '\'torch\'' )
             self.assertEqual(lowercase_			,   lowercase_ )






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




             _lowerCamelCase       :		Dict		='# This file is autogenerated by the command `make fix-copies`, do not edit.\nfrom ..utils import DummyObject, requires_backends\n\n\nCONSTANT = None\n\n\ndef function(*args, **kwargs):\n    requires_backends(function, ["torch"])\n\n\nclass FakeClass(metaclass=DummyObject):\n    _backends = ["torch"]\n\n    def __init__(self, *args, **kwargs):\n        requires_backends(self, ["torch"])\n'
             _lowerCamelCase       :		Optional[int]		=create_dummy_files({'torch': ['CONSTANT', 'function', 'FakeClass']} )
             self.assertEqual(dummy_files['torch']			,   lowercase_ )


