





import argparse
import copy






def 					SCREAMING_SNAKE_CASE__				(							UpperCamelCase__:				Union[str, Any]     ):
		SCREAMING_SNAKE_CASE__								=   {}

		with open(UpperCamelCase__     ) as f:
				for line in f:
						if line.split()[0] not in dict_of_neighbours:
								SCREAMING_SNAKE_CASE__								=   []
								_list.append([line.split()[1], line.split()[2]]     )
								SCREAMING_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:
								SCREAMING_SNAKE_CASE__								=   []
								_list.append([line.split()[0], line.split()[2]]     )
								SCREAMING_SNAKE_CASE__								=   _list
						else:
								dict_of_neighbours[line.split()[1]].append(
								    [line.split()[0], line.split()[2]]     )

		return dict_of_neighbours






def 					SCREAMING_SNAKE_CASE__				(							UpperCamelCase__:				Tuple       , UpperCamelCase__:				int     ):

		with open(UpperCamelCase__     ) as f:
				SCREAMING_SNAKE_CASE__								=   f.read(1     )
		SCREAMING_SNAKE_CASE__								=   start_node

		SCREAMING_SNAKE_CASE__								=   []

		SCREAMING_SNAKE_CASE__								=   start_node

		SCREAMING_SNAKE_CASE__								=   0
		while visiting not in first_solution:
				SCREAMING_SNAKE_CASE__								=   10_000
				for k in dict_of_neighbours[visiting]:
						if int(k[1]     ) < int(UpperCamelCase__     ) and k[0] not in first_solution:
								SCREAMING_SNAKE_CASE__								=   k[1]
								SCREAMING_SNAKE_CASE__								=   k[0]

				first_solution.append(UpperCamelCase__     )
				SCREAMING_SNAKE_CASE__								=   distance_of_first_solution + int(UpperCamelCase__     )
				SCREAMING_SNAKE_CASE__								=   best_node

		first_solution.append(UpperCamelCase__     )

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

		SCREAMING_SNAKE_CASE__								=   (
		    distance_of_first_solution
		    + int(dict_of_neighbours[first_solution[-2]][position][1]     )
		    - 10_000
		)
		return first_solution, distance_of_first_solution






def 					SCREAMING_SNAKE_CASE__				(							UpperCamelCase__:				Tuple       , UpperCamelCase__:				Optional[int]     ):
		SCREAMING_SNAKE_CASE__								=   []

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

						SCREAMING_SNAKE_CASE__								=   copy.deepcopy(UpperCamelCase__     )
						SCREAMING_SNAKE_CASE__								=   kn
						SCREAMING_SNAKE_CASE__								=   n

						SCREAMING_SNAKE_CASE__								=   0

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

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

		SCREAMING_SNAKE_CASE__								=   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 					SCREAMING_SNAKE_CASE__				(							UpperCamelCase__:				Union[str, Any]       , UpperCamelCase__:				int       , UpperCamelCase__:				List[Any]       , UpperCamelCase__:				List[Any]       , UpperCamelCase__:				Optional[Any]     ):
		SCREAMING_SNAKE_CASE__								=   1
		SCREAMING_SNAKE_CASE__								=   first_solution
		SCREAMING_SNAKE_CASE__								=   []
		SCREAMING_SNAKE_CASE__								=   distance_of_first_solution
		SCREAMING_SNAKE_CASE__								=   solution

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

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

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

				SCREAMING_SNAKE_CASE__								=   count + 1

		return best_solution_ever, best_cost






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

		SCREAMING_SNAKE_CASE__						,    SCREAMING_SNAKE_CASE__								=   generate_first_solution(
		    args.File       , UpperCamelCase__     )

		SCREAMING_SNAKE_CASE__						,    SCREAMING_SNAKE_CASE__								=   tabu_search(
		    UpperCamelCase__       , UpperCamelCase__       , UpperCamelCase__       , args.Iterations       , args.Size       , )

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


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






def 					SCREAMING_SNAKE_CASE__				(							UpperCamelCase__:				List[str]     ):
		SCREAMING_SNAKE_CASE__								=   len(UpperCamelCase__     )
		SCREAMING_SNAKE_CASE__								=   sum(UpperCamelCase__     )

		SCREAMING_SNAKE_CASE__								=   [[False for x in range(s + 1     )] for y in range(n + 1     )]

		for i in range(1       , n + 1     ):
				SCREAMING_SNAKE_CASE__								=   True

		for i in range(1       , s + 1     ):
				SCREAMING_SNAKE_CASE__								=   False

		for i in range(1       , n + 1     ):
				for j in range(1       , s + 1     ):
						SCREAMING_SNAKE_CASE__								=   dp[i][j - 1]

						if arr[i - 1] <= j:
								SCREAMING_SNAKE_CASE__								=   dp[i][j] or dp[i - 1][j - arr[i - 1]]

		for j in range(int(s / 2     )       , -1       , -1     ):
				if dp[n][j] is True:
						SCREAMING_SNAKE_CASE__								=   s - 2 * j
						break

		return diff