


import argparse
import copy

def 						_UpperCAmelCase    (      SCREAMING_SNAKE_CASE__      : Optional[Any]    ):
					__UpperCamelCase   							={}

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

					return dict_of_neighbours

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

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

					__UpperCamelCase   							=[]

					__UpperCamelCase   							=start_node

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

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

					first_solution.append(SCREAMING_SNAKE_CASE__    )

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

					__UpperCamelCase   							=(
					    distance_of_first_solution
					    + int(dict_of_neighbours[first_solution[-2]][position][1]    )
					    - 1_00_00
					)
					return first_solution, distance_of_first_solution

def 						_UpperCAmelCase    (      SCREAMING_SNAKE_CASE__      : Any      ,					SCREAMING_SNAKE_CASE__      : Dict    ):
					__UpperCamelCase   							=[]

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

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

															__UpperCamelCase   							=0

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

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

					__UpperCamelCase   							=len(neighborhood_of_solution[0]    ) - 1

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

def 						_UpperCAmelCase    (      SCREAMING_SNAKE_CASE__      : List[Any]      ,					SCREAMING_SNAKE_CASE__      : Tuple      ,					SCREAMING_SNAKE_CASE__      : Union[str, Any]      ,					SCREAMING_SNAKE_CASE__      : Union[str, Any]      ,					SCREAMING_SNAKE_CASE__      : int    ):
					__UpperCamelCase   							=1
					__UpperCamelCase   							=first_solution
					__UpperCamelCase   							=[]
					__UpperCamelCase   							=distance_of_first_solution
					__UpperCamelCase   							=solution

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

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

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

										__UpperCamelCase   							=count + 1

					return best_solution_ever, best_cost

def 						_UpperCAmelCase    (      SCREAMING_SNAKE_CASE__      : int=None    ):
					__UpperCamelCase   							=generate_neighbours(args.File    )

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

					__UpperCamelCase							,				__UpperCamelCase   							=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__":
			_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())









from __future__ import annotations

from typing import Any

def 						_UpperCAmelCase    (      SCREAMING_SNAKE_CASE__      : list[Any]    ):
     create_state_space_tree(SCREAMING_SNAKE_CASE__      ,					[]      ,					0    )

def 						_UpperCAmelCase    (      SCREAMING_SNAKE_CASE__      : list[Any]      ,					SCREAMING_SNAKE_CASE__      : list[Any]      ,					SCREAMING_SNAKE_CASE__      : int    ):

     if index == len(SCREAMING_SNAKE_CASE__    ):
          print(SCREAMING_SNAKE_CASE__    )
          return

     create_state_space_tree(SCREAMING_SNAKE_CASE__      ,					SCREAMING_SNAKE_CASE__      ,					index + 1    )
     current_subsequence.append(sequence[index]    )
     create_state_space_tree(SCREAMING_SNAKE_CASE__      ,					SCREAMING_SNAKE_CASE__      ,					index + 1    )
     current_subsequence.pop()


if __name__ == "__main__":
   _A			=						[3, 1, 2, 4]
   generate_all_subsequences(seq)

   seq.clear()
   seq.extend(['A', 'B', 'C'])
   generate_all_subsequences(seq)





