





import argparse
import copy





def      lowerCAmelCase_ (       __a		)     ->		Dict:







  """simple docstring"""





  lowerCamelCase__:      Dict			  ={}

  with open(__a		) as f:
    for line in f:
      if line.split()[0] not in dict_of_neighbours:
        lowerCamelCase__:      str			  =[]
        _list.append([line.split()[1], line.split()[2]]		)
        lowerCamelCase__:      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:
        lowerCamelCase__:      int			  =[]
        _list.append([line.split()[0], line.split()[2]]		)
        lowerCamelCase__:      List[Any]			  =_list
      else:
        dict_of_neighbours[line.split()[1]].append(
            [line.split()[0], line.split()[2]]		)

  return dict_of_neighbours





def      lowerCAmelCase_ (       __a	,    __a		)     ->		Dict:







  """simple docstring"""





  with open(__a		) as f:
    lowerCamelCase__:      Dict			  =f.read(1		)
  lowerCamelCase__:      str			  =start_node

  lowerCamelCase__:      List[Any]			  =[]

  lowerCamelCase__:      Optional[int]			  =start_node

  lowerCamelCase__:      Dict			  =0
  while visiting not in first_solution:
    lowerCamelCase__:      int			  =10000
    for k in dict_of_neighbours[visiting]:
      if int(k[1]		) < int(__a		) and k[0] not in first_solution:
        lowerCamelCase__:      str			  =k[1]
        lowerCamelCase__:      List[str]			  =k[0]

    first_solution.append(__a		)
    lowerCamelCase__:      str			  =distance_of_first_solution + int(__a		)
    lowerCamelCase__:      List[str]			  =best_node

  first_solution.append(__a		)

  lowerCamelCase__:      Union[str, Any]			  =0
  for k in dict_of_neighbours[first_solution[-2]]:
    if k[0] == start_node:
      break
    position += 1

  lowerCamelCase__:      List[str]			  =(
      distance_of_first_solution
      + int(dict_of_neighbours[first_solution[-2]][position][1]		)
      - 10000
  )
  return first_solution, distance_of_first_solution





def      lowerCAmelCase_ (       __a	,    __a		)     ->		Any:







  """simple docstring"""





  lowerCamelCase__:      Optional[int]			  =[]

  for n in solution[1:-1]:
    lowerCamelCase__:      Any			  =solution.index(__a		)
    for kn in solution[1:-1]:
      lowerCamelCase__:      Tuple			  =solution.index(__a		)
      if n == kn:
        continue

      lowerCamelCase__:      Optional[int]			  =copy.deepcopy(__a		)
      lowerCamelCase__:      Tuple			  =kn
      lowerCamelCase__:      Dict			  =n

      lowerCamelCase__:      List[Any]			  =0

      for k in _tmp[:-1]:
        lowerCamelCase__:      Tuple			  =_tmp[_tmp.index(__a		) + 1]
        for i in dict_of_neighbours[k]:
          if i[0] == next_node:
            lowerCamelCase__:      Dict			  =distance + int(i[1]		)
      _tmp.append(__a		)

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

  lowerCamelCase__:      Dict			  =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      lowerCAmelCase_ (       __a	,    __a	,    __a	,    __a	,    __a		)     ->		List[Any]:







  """simple docstring"""





  lowerCamelCase__:      Tuple			  =1
  lowerCamelCase__:      Tuple			  =first_solution
  lowerCamelCase__:      List[str]			  =[]
  lowerCamelCase__:      Union[str, Any]			  =distance_of_first_solution
  lowerCamelCase__:      Optional[Any]			  =solution

  while count <= iters:
    lowerCamelCase__:      Union[str, Any]			  =find_neighborhood(__a	,    __a		)
    lowerCamelCase__:      List[str]			  =0
    lowerCamelCase__:      str			  =neighborhood[index_of_best_solution]
    lowerCamelCase__:      Union[str, Any]			  =len(__a		) - 1

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

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

    lowerCamelCase__:      Dict			  =count + 1

  return best_solution_ever, best_cost





def      lowerCAmelCase_ (       __a=None		)     ->		Union[str, Any]:







  """simple docstring"""





  lowerCamelCase__:      Tuple			  =generate_neighbours(args.File		)

  lowerCamelCase__  ,					lowerCamelCase__:      Tuple			  =generate_first_solution(
      args.File	,    __a		)

  lowerCamelCase__  ,					lowerCamelCase__:      Dict			  =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())








class    _SCREAMING_SNAKE_CASE						:







 '''simple docstring'''

 def __init__(self				:   Optional[Any]       , UpperCAmelCase_				:   int)       ->Optional[int]:



   '''simple docstring'''



   lowerCamelCase__:      Any			  =n
   lowerCamelCase__:      Tuple			  =[None] * self.n
   lowerCamelCase__:      str			  =0  # index of the first element
   lowerCamelCase__:      Tuple			  =0
   lowerCamelCase__:      Optional[Any]			  =0

 def __len__(self				:   str)       ->int:



   '''simple docstring'''



   return self.size

 def 							SCREAMING_SNAKE_CASE_					(self				:   int)       ->bool:



   '''simple docstring'''



   return self.size == 0

 def 							SCREAMING_SNAKE_CASE_					(self				:   List[str])       ->str:



   '''simple docstring'''



   return False if self.is_empty() else self.array[self.front]

 def 							SCREAMING_SNAKE_CASE_					(self				:   int       , UpperCAmelCase_				:   Optional[int])       ->str:



   '''simple docstring'''



   if self.size >= self.n:
     raise Exception("QUEUE IS FULL")

   lowerCamelCase__:      List[Any]			  =data
   lowerCamelCase__:      Dict			  =(self.rear + 1) % self.n
   self.size += 1
   return self







 def 							SCREAMING_SNAKE_CASE_					(self				:   Tuple)       ->Tuple:



   '''simple docstring'''



   if self.size == 0:
     raise Exception("UNDERFLOW")

   lowerCamelCase__:      Optional[Any]			  =self.array[self.front]
   lowerCamelCase__:      Optional[int]			  =None
   lowerCamelCase__:      Dict			  =(self.front + 1) % self.n
   self.size -= 1
   return temp

