





'''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'''


class       UpperCamelCase__  :







	def __init__(				self			:   str , lowerCamelCase			:   int , lowerCamelCase			:   List[str]=None , lowerCamelCase			:   int=None		):




				'''simple docstring'''
				a__     = data
				a__     = previous
				a__     = next_node







	def __str__(				self			:   List[Any]		):




				'''simple docstring'''
				return F'''{self.data}'''







	def 						__a   (				self			:   List[Any]		):




				'''simple docstring'''
				return self.data







	def 						__a   (				self			:   Tuple		):




				'''simple docstring'''
				return self.next







	def 						__a   (				self			:   Union[str, Any]		):




				'''simple docstring'''
				return self.previous






class       UpperCamelCase__  :







	def __init__(				self			:   int , lowerCamelCase			:   Tuple		):




				'''simple docstring'''
				a__     = head







	def __iter__(				self			:   Any		):




				'''simple docstring'''
				return self







	def 						__a   (				self			:   List[Any]		):




				'''simple docstring'''
				if not self.current:
							raise StopIteration
				else:
							a__     = self.current.get_data()
							a__     = self.current.get_next()
							return value






class       UpperCamelCase__  :







	def __init__(				self			:   Tuple		):




				'''simple docstring'''
				a__     = None  # First node in list
				a__     = None  # Last node in list







	def __str__(				self			:   Any		):




				'''simple docstring'''
				a__     = self.head
				a__     = []
				while current is not None:
							nodes.append(current.get_data()		)
							a__     = current.get_next()
				return " ".join(str(lowerCamelCase		) for node in nodes		)







	def __contains__(				self			:   Optional[int] , lowerCamelCase			:   int		):




				'''simple docstring'''
				a__     = self.head
				while current:
							if current.get_data() == value:
										return True
							a__     = current.get_next()
				return False







	def __iter__(				self			:   int		):




				'''simple docstring'''
				return LinkedListIterator(self.head		)







	def 						__a   (				self			:   str		):




				'''simple docstring'''
				if self.head:
							return self.head.get_data()
				return None







	def 						__a   (				self			:   Union[str, Any]		):




				'''simple docstring'''
				if self.tail:
							return self.tail.get_data()
				return None







	def 						__a   (				self			:   List[Any] , lowerCamelCase			:   Node		):




				'''simple docstring'''
				if self.head is None:
							a__     = node
							a__     = node
				else:
							self.insert_before_node(self.head , lowerCamelCase		)







	def 						__a   (				self			:   List[str] , lowerCamelCase			:   Node		):




				'''simple docstring'''
				if self.head is None:
							self.set_head(lowerCamelCase		)
				else:
							self.insert_after_node(self.tail , lowerCamelCase		)







	def 						__a   (				self			:   List[str] , lowerCamelCase			:   int		):




				'''simple docstring'''
				a__     = Node(lowerCamelCase		)
				if self.head is None:
							self.set_head(lowerCamelCase		)
				else:
							self.set_tail(lowerCamelCase		)







	def 						__a   (				self			:   Any , lowerCamelCase			:   Node , lowerCamelCase			:   Node		):




				'''simple docstring'''
				a__     = node
				a__     = node.previous

				if node.get_previous() is None:
							a__     = node_to_insert
				else:
							a__     = node_to_insert

				a__     = node_to_insert







	def 						__a   (				self			:   Tuple , lowerCamelCase			:   Node , lowerCamelCase			:   Node		):




				'''simple docstring'''
				a__     = node
				a__     = node.next

				if node.get_next() is None:
							a__     = node_to_insert
				else:
							a__     = node_to_insert

				a__     = node_to_insert







	def 						__a   (				self			:   Union[str, Any] , lowerCamelCase			:   int , lowerCamelCase			:   int		):




				'''simple docstring'''
				a__     = 1
				a__     = Node(lowerCamelCase		)
				a__     = self.head
				while node:
							if current_position == position:
										self.insert_before_node(lowerCamelCase , lowerCamelCase		)
										return
							current_position += 1
							a__     = node.next
				self.insert_after_node(self.tail , lowerCamelCase		)







	def 						__a   (				self			:   List[Any] , lowerCamelCase			:   int		):




				'''simple docstring'''
				a__     = self.head
				while node:
							if node.get_data() == item:
										return node
							a__     = node.get_next()
				raise Exception("Node not found"		)







	def 						__a   (				self			:   List[Any] , lowerCamelCase			:   List[str]		):




				'''simple docstring'''
				if (node := self.get_node(lowerCamelCase		)) is not None:
							if node == self.head:
										a__     = self.head.get_next()

							if node == self.tail:
										a__     = self.tail.get_previous()

							self.remove_node_pointers(lowerCamelCase		)







	@staticmethod
	def 						__a   (				lowerCamelCase			:   Node		):




				'''simple docstring'''
				if node.get_next():
							a__     = node.previous

				if node.get_previous():
							a__     = node.next

				a__     = None
				a__     = None







	def 						__a   (				self			:   List[str]		):




				'''simple docstring'''
				return self.head is None







def    _lowerCamelCase  ()   ->    None:
			pass


if __name__ == "__main__":
		import doctest

		doctest.testmod()



