






import argparse
import copy







def       lowercase__	(					A_:						Tuple		)	->				Dict:







       """simple docstring"""






       __UpperCAmelCase     				={}

       with open(A_		) 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       lowercase__	(					A_:						str  ,      A_:						List[str]		)	->				Optional[Any]:







       """simple docstring"""






       with open(A_		) as f:
              __UpperCAmelCase     				=f.read(1		)
       __UpperCAmelCase     				=start_node

       __UpperCAmelCase     				=[]

       __UpperCAmelCase     				=start_node

       __UpperCAmelCase     				=0
       while visiting not in first_solution:
              __UpperCAmelCase     				=10000
              for k in dict_of_neighbours[visiting]:
                     if int(k[1]		) < int(A_		) and k[0] not in first_solution:
                            __UpperCAmelCase     				=k[1]
                            __UpperCAmelCase     				=k[0]

              first_solution.append(A_		)
              __UpperCAmelCase     				=distance_of_first_solution + int(A_		)
              __UpperCAmelCase     				=best_node

       first_solution.append(A_		)

       __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]		)
           - 10000
       )
       return first_solution, distance_of_first_solution







def       lowercase__	(					A_:						Any  ,      A_:						Optional[Any]		)	->				str:







       """simple docstring"""






       __UpperCAmelCase     				=[]

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

                     __UpperCAmelCase     				=copy.deepcopy(A_		)
                     __UpperCAmelCase     				=kn
                     __UpperCAmelCase     				=n

                     __UpperCAmelCase     				=0

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

                     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 A_		: x[index_of_last_item_in_the_list]		)
       return neighborhood_of_solution







def       lowercase__	(					A_:						List[Any]  ,      A_:						List[str]  ,      A_:						Union[str, Any]  ,      A_:						Optional[Any]  ,      A_:						Optional[Any]		)	->				List[Any]:







       """simple docstring"""






       __UpperCAmelCase     				=1
       __UpperCAmelCase     				=first_solution
       __UpperCAmelCase     				=[]
       __UpperCAmelCase     				=distance_of_first_solution
       __UpperCAmelCase     				=solution

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

              __UpperCAmelCase     				=False
              while not found:
                     __UpperCAmelCase     				=0
                     while i < len(A_		):
                            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(A_		) >= size:
                     tabu_list.pop(0		)

              __UpperCAmelCase     				=count + 1

       return best_solution_ever, best_cost







def       lowercase__	(					A_:						Union[str, Any]=None		)	->				Tuple:







       """simple docstring"""






       __UpperCAmelCase     				=generate_neighbours(args.File		)

       __UpperCAmelCase				, __UpperCAmelCase     				=generate_first_solution(
           args.File  ,      A_		)

       __UpperCAmelCase				, __UpperCAmelCase     				=tabu_search(
           A_  ,      A_  ,      A_  ,      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())












def 	UpperCamelCase	(							snake_case__  : int	):




     '''simple docstring'''






     __snake_case      :List[Any] 							=    0
     while num > 0:
          digit_sum += num % 10
          num //= 10
     return digit_sum






def 	UpperCamelCase	(							snake_case__  : int = 100	):




     '''simple docstring'''






     __snake_case      :Tuple 							=    1
     __snake_case      :Dict 							=    2

     for i in range(2						,max_n + 1	):
          __snake_case      :Optional[int] 							=    pre_numerator
          __snake_case      :List[Any] 							=    2 * i // 3 if i % 3 == 0 else 1
          __snake_case      :Dict 							=    cur_numerator
          __snake_case      :Optional[Any] 							=    e_cont * pre_numerator + temp

     return sum_digits(snake_case__	)


if __name__ == "__main__":
     print(f'''{solution() = }''')


