


'''simple docstring'''



import argparse
import copy







def       _UpperCamelCase (						UpperCamelCase__   ):
			UpperCAmelCase__					:   Dict       				=       {}

			with open(UpperCamelCase__   ) as f:
						for line in f:
									if line.split()[0] not in dict_of_neighbours:
												UpperCAmelCase__					:   str       				=       []
												_list.append([line.split()[1], line.split()[2]]   )
												UpperCAmelCase__					:   str       				=       _list
									else:
												dict_of_neighbours[line.split()[0]].append(
												    [line.split()[1], line.split()[2]]   )
									if line.split()[1] not in dict_of_neighbours:
												UpperCAmelCase__					:   Optional[Any]       				=       []
												_list.append([line.split()[0], line.split()[2]]   )
												UpperCAmelCase__					:   Union[str, Any]       				=       _list
									else:
												dict_of_neighbours[line.split()[1]].append(
												    [line.split()[0], line.split()[2]]   )

			return dict_of_neighbours







def       _UpperCamelCase (						UpperCamelCase__	, UpperCamelCase__   ):

			with open(UpperCamelCase__   ) as f:
						UpperCAmelCase__					:   Any       				=       f.read(1   )
			UpperCAmelCase__					:   Tuple       				=       start_node

			UpperCAmelCase__					:   List[Any]       				=       []

			UpperCAmelCase__					:   List[Any]       				=       start_node

			UpperCAmelCase__					:   Any       				=       0
			while visiting not in first_solution:
						UpperCAmelCase__					:   str       				=       1_0_0_0_0
						for k in dict_of_neighbours[visiting]:
									if int(k[1]   ) < int(UpperCamelCase__   ) and k[0] not in first_solution:
												UpperCAmelCase__					:   Optional[int]       				=       k[1]
												UpperCAmelCase__					:   Tuple       				=       k[0]

						first_solution.append(UpperCamelCase__   )
						UpperCAmelCase__					:   List[str]       				=       distance_of_first_solution + int(UpperCamelCase__   )
						UpperCAmelCase__					:   Dict       				=       best_node

			first_solution.append(UpperCamelCase__   )

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

			UpperCAmelCase__					:   List[str]       				=       (
			    distance_of_first_solution
			    + int(dict_of_neighbours[first_solution[-2]][position][1]   )
			    - 1_0_0_0_0
			)
			return first_solution, distance_of_first_solution







def       _UpperCamelCase (						UpperCamelCase__	, UpperCamelCase__   ):
			UpperCAmelCase__					:   List[str]       				=       []

			for n in solution[1:-1]:
						UpperCAmelCase__					:   int       				=       solution.index(UpperCamelCase__   )
						for kn in solution[1:-1]:
									UpperCAmelCase__					:   Dict       				=       solution.index(UpperCamelCase__   )
									if n == kn:
												continue

									UpperCAmelCase__					:   str       				=       copy.deepcopy(UpperCamelCase__   )
									UpperCAmelCase__					:   str       				=       kn
									UpperCAmelCase__					:   Any       				=       n

									UpperCAmelCase__					:   Tuple       				=       0

									for k in _tmp[:-1]:
												UpperCAmelCase__					:   Any       				=       _tmp[_tmp.index(UpperCamelCase__   ) + 1]
												for i in dict_of_neighbours[k]:
															if i[0] == next_node:
																		UpperCAmelCase__					:   str       				=       distance + int(i[1]   )
									_tmp.append(UpperCamelCase__   )

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

			UpperCAmelCase__					:   Tuple       				=       len(neighborhood_of_solution[0]   ) - 1

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







def       _UpperCamelCase (						UpperCamelCase__	, UpperCamelCase__	, UpperCamelCase__	, UpperCamelCase__	, UpperCamelCase__   ):
			UpperCAmelCase__					:   Union[str, Any]       				=       1
			UpperCAmelCase__					:   List[Any]       				=       first_solution
			UpperCAmelCase__					:   str       				=       []
			UpperCAmelCase__					:   Dict       				=       distance_of_first_solution
			UpperCAmelCase__					:   Union[str, Any]       				=       solution

			while count <= iters:
						UpperCAmelCase__					:   int       				=       find_neighborhood(UpperCamelCase__	, UpperCamelCase__   )
						UpperCAmelCase__					:   Union[str, Any]       				=       0
						UpperCAmelCase__					:   Dict       				=       neighborhood[index_of_best_solution]
						UpperCAmelCase__					:   Union[str, Any]       				=       len(UpperCamelCase__   ) - 1

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

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

						UpperCAmelCase__					:   Union[str, Any]       				=       count + 1

			return best_solution_ever, best_cost







def       _UpperCamelCase (						UpperCamelCase__=None   ):
			UpperCAmelCase__					:   Optional[int]       				=       generate_neighbours(args.File   )

			UpperCAmelCase__					:   Union[str, Any]       				=       generate_first_solution(
			    args.File	, UpperCamelCase__   )

			UpperCAmelCase__					:   Dict       				=       tabu_search(
			    UpperCamelCase__	, UpperCamelCase__	, UpperCamelCase__	, args.Iterations	, args.Size	, )

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


if __name__ == "__main__":
		__A		=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'''



from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_torch_available


__A		={
    'configuration_table_transformer': [
        'TABLE_TRANSFORMER_PRETRAINED_CONFIG_ARCHIVE_MAP',
        'TableTransformerConfig',
        'TableTransformerOnnxConfig',
    ]
}

try:
		if not is_torch_available():
				raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
		pass
else:
		__A		=[
		    'TABLE_TRANSFORMER_PRETRAINED_MODEL_ARCHIVE_LIST',
		    'TableTransformerForObjectDetection',
		    'TableTransformerModel',
		    'TableTransformerPreTrainedModel',
		]


if TYPE_CHECKING:
		from .configuration_table_transformer import (
		    TABLE_TRANSFORMER_PRETRAINED_CONFIG_ARCHIVE_MAP,
		    TableTransformerConfig,
		    TableTransformerOnnxConfig,
		)

		try:
				if not is_torch_available():
						raise OptionalDependencyNotAvailable()
		except OptionalDependencyNotAvailable:
				pass
		else:
				from .modeling_table_transformer import (
				    TABLE_TRANSFORMER_PRETRAINED_MODEL_ARCHIVE_LIST,
				    TableTransformerForObjectDetection,
				    TableTransformerModel,
				    TableTransformerPreTrainedModel,
				)

else:
		import sys

		__A		=_LazyModule(__name__, globals()['__file__'], _import_structure, module_spec=__spec__)