



"""simple docstring"""

import argparse
import copy
def  __snake_case							(	__A      :						List[Any]     )     ->       Tuple:






				'''simple docstring'''
				SCREAMING_SNAKE_CASE						:							Dict							=     {}

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

				return dict_of_neighbours
def  __snake_case							(	__A      :						Union[str, Any]							,		__A      :						Tuple     )     ->       Tuple:






				'''simple docstring'''

				with open(__A     ) as f:
								SCREAMING_SNAKE_CASE						:							Tuple							=     f.read(1     )
				SCREAMING_SNAKE_CASE						:							int							=     start_node

				SCREAMING_SNAKE_CASE						:							Union[str, Any]							=     []

				SCREAMING_SNAKE_CASE						:							Union[str, Any]							=     start_node

				SCREAMING_SNAKE_CASE						:							Dict							=     0
				while visiting not in first_solution:
								SCREAMING_SNAKE_CASE						:							List[Any]							=     10000
								for k in dict_of_neighbours[visiting]:
												if int(k[1]     ) < int(__A     ) and k[0] not in first_solution:
																SCREAMING_SNAKE_CASE						:							Optional[int]							=     k[1]
																SCREAMING_SNAKE_CASE						:							List[Any]							=     k[0]

								first_solution.append(__A     )
								SCREAMING_SNAKE_CASE						:							int							=     distance_of_first_solution + int(__A     )
								SCREAMING_SNAKE_CASE						:							Optional[int]							=     best_node

				first_solution.append(__A     )

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

				SCREAMING_SNAKE_CASE						:							int							=     (
				    distance_of_first_solution
				    + int(dict_of_neighbours[first_solution[-2]][position][1]     )
				    - 10000
				)
				return first_solution, distance_of_first_solution
def  __snake_case							(	__A      :						Any							,		__A      :						Dict     )     ->       Union[str, Any]:






				'''simple docstring'''
				SCREAMING_SNAKE_CASE						:							int							=     []

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

												SCREAMING_SNAKE_CASE						:							Union[str, Any]							=     copy.deepcopy(__A     )
												SCREAMING_SNAKE_CASE						:							str							=     kn
												SCREAMING_SNAKE_CASE						:							Optional[Any]							=     n

												SCREAMING_SNAKE_CASE						:							Optional[Any]							=     0

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

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

				SCREAMING_SNAKE_CASE						:							str							=     len(neighborhood_of_solution[0]     ) - 1

				neighborhood_of_solution.sort(key=lambda __A     : x[index_of_last_item_in_the_list]     )
				return neighborhood_of_solution
def  __snake_case							(	__A      :						str							,		__A      :						int							,		__A      :						List[str]							,		__A      :						Optional[Any]							,		__A      :						Optional[int]     )     ->       int:






				'''simple docstring'''
				SCREAMING_SNAKE_CASE						:							Tuple							=     1
				SCREAMING_SNAKE_CASE						:							int							=     first_solution
				SCREAMING_SNAKE_CASE						:							Union[str, Any]							=     []
				SCREAMING_SNAKE_CASE						:							int							=     distance_of_first_solution
				SCREAMING_SNAKE_CASE						:							Any							=     solution

				while count <= iters:
								SCREAMING_SNAKE_CASE						:							int							=     find_neighborhood(__A							,		__A     )
								SCREAMING_SNAKE_CASE						:							Tuple							=     0
								SCREAMING_SNAKE_CASE						:							List[str]							=     neighborhood[index_of_best_solution]
								SCREAMING_SNAKE_CASE						:							List[str]							=     len(__A     ) - 1

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

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

								SCREAMING_SNAKE_CASE						:							Any							=     count + 1

				return best_solution_ever, best_cost
def  __snake_case							(	__A      :						List[str]=None     )     ->       int:






				'''simple docstring'''
				SCREAMING_SNAKE_CASE						:							Optional[Any]							=     generate_neighbours(args.File     )

				SCREAMING_SNAKE_CASE				,						SCREAMING_SNAKE_CASE						:							Dict							=     generate_first_solution(
				    args.File							,		__A     )

				SCREAMING_SNAKE_CASE				,						SCREAMING_SNAKE_CASE						:							Any							=     tabu_search(
				    __A							,		__A							,		__A							,		args.Iterations							,		args.Size							,		)

				print(F"""Best solution: {best_sol}, with total distance: {best_cost}."""     )


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

def  __snake_case							(	__A      :						list							,		__A      :						int							,		__A      :						int = 0							,		__A      :						int = 0     )     ->       int:






				'''simple docstring'''
				SCREAMING_SNAKE_CASE						:							Any							=     right or len(__A     ) - 1
				if left > right:
								return -1
				elif list_data[left] == key:
								return left
				elif list_data[right] == key:
								return right
				else:
								return search(__A							,		__A							,		left + 1							,		right - 1     )


if __name__ == "__main__":
							import doctest

							doctest.testmod()





