
'''simple docstring'''



import argparse
import copy
def    lowerCAmelCase_	(				SCREAMING_SNAKE_CASE_						)     ->     Tuple:




   """simple docstring"""
   _SCREAMING_SNAKE_CASE      =				{}

   with open(SCREAMING_SNAKE_CASE_						) 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    lowerCAmelCase_	(				SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_						)     ->     int:




   """simple docstring"""

   with open(SCREAMING_SNAKE_CASE_						) 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      =				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:
            _SCREAMING_SNAKE_CASE      =				k[1]
            _SCREAMING_SNAKE_CASE      =				k[0]

      first_solution.append(SCREAMING_SNAKE_CASE_						)
      _SCREAMING_SNAKE_CASE      =				distance_of_first_solution + int(SCREAMING_SNAKE_CASE_						)
      _SCREAMING_SNAKE_CASE      =				best_node

   first_solution.append(SCREAMING_SNAKE_CASE_						)

   _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]						)
       - 1_00_00
   )
   return first_solution, distance_of_first_solution
def    lowerCAmelCase_	(				SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_						)     ->     Any:




   """simple docstring"""
   _SCREAMING_SNAKE_CASE      =				[]

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

         _SCREAMING_SNAKE_CASE      =				copy.deepcopy(SCREAMING_SNAKE_CASE_						)
         _SCREAMING_SNAKE_CASE      =				kn
         _SCREAMING_SNAKE_CASE      =				n

         _SCREAMING_SNAKE_CASE      =				0

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

         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 SCREAMING_SNAKE_CASE_						: x[index_of_last_item_in_the_list]						)
   return neighborhood_of_solution
def    lowerCAmelCase_	(				SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_						)     ->     Union[str, Any]:




   """simple docstring"""
   _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(SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_						)
      _SCREAMING_SNAKE_CASE      =				0
      _SCREAMING_SNAKE_CASE      =				neighborhood[index_of_best_solution]
      _SCREAMING_SNAKE_CASE      =				len(SCREAMING_SNAKE_CASE_						) - 1

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

      _SCREAMING_SNAKE_CASE      =				count + 1

   return best_solution_ever, best_cost
def    lowerCAmelCase_	(				SCREAMING_SNAKE_CASE_=None						)     ->     List[Any]:




   """simple docstring"""
   _SCREAMING_SNAKE_CASE      =				generate_neighbours(args.File						)

   _SCREAMING_SNAKE_CASE ,							_SCREAMING_SNAKE_CASE      =				generate_first_solution(
       args.File    ,      SCREAMING_SNAKE_CASE_						)

   _SCREAMING_SNAKE_CASE ,							_SCREAMING_SNAKE_CASE      =				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__":
     UpperCamelCase__      :		Tuple       							=  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'''



def    lowerCAmelCase_	(				SCREAMING_SNAKE_CASE_						)     ->     int:




   """simple docstring"""

   if not isinstance(SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_						):
      raise ValueError("""multiplicative_persistence() only accepts integral values"""						)
   if num < 0:
      raise ValueError("""multiplicative_persistence() does not accept negative values"""						)

   _SCREAMING_SNAKE_CASE      =				0
   _SCREAMING_SNAKE_CASE      =				str(SCREAMING_SNAKE_CASE_						)

   while len(SCREAMING_SNAKE_CASE_						) != 1:
      _SCREAMING_SNAKE_CASE      =				[int(SCREAMING_SNAKE_CASE_						) for i in num_string]

      _SCREAMING_SNAKE_CASE      =				1
      for i in range(0    ,      len(SCREAMING_SNAKE_CASE_						)						):
         total *= numbers[i]

      _SCREAMING_SNAKE_CASE      =				str(SCREAMING_SNAKE_CASE_						)

      steps += 1
   return steps
def    lowerCAmelCase_	(				SCREAMING_SNAKE_CASE_						)     ->     int:




   """simple docstring"""

   if not isinstance(SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_						):
      raise ValueError("""additive_persistence() only accepts integral values"""						)
   if num < 0:
      raise ValueError("""additive_persistence() does not accept negative values"""						)

   _SCREAMING_SNAKE_CASE      =				0
   _SCREAMING_SNAKE_CASE      =				str(SCREAMING_SNAKE_CASE_						)

   while len(SCREAMING_SNAKE_CASE_						) != 1:
      _SCREAMING_SNAKE_CASE      =				[int(SCREAMING_SNAKE_CASE_						) for i in num_string]

      _SCREAMING_SNAKE_CASE      =				0
      for i in range(0    ,      len(SCREAMING_SNAKE_CASE_						)						):
         total += numbers[i]

      _SCREAMING_SNAKE_CASE      =				str(SCREAMING_SNAKE_CASE_						)

      steps += 1
   return steps


if __name__ == "__main__":
     import doctest

     doctest.testmod()






