


import argparse
import copy






def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE      )->						Optional[int]:




      """simple docstring"""

      snake_case_ =   {}

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




      """simple docstring"""

      with open(SCREAMING_SNAKE_CASE      ) as f:
            snake_case_ =   f.read(1      )
      snake_case_ =   start_node

      snake_case_ =   []

      snake_case_ =   start_node

      snake_case_ =   0
      while visiting not in first_solution:
            snake_case_ =   1_0000
            for k in dict_of_neighbours[visiting]:
                  if int(k[1]      ) < int(SCREAMING_SNAKE_CASE      ) and k[0] not in first_solution:
                        snake_case_ =   k[1]
                        snake_case_ =   k[0]

            first_solution.append(SCREAMING_SNAKE_CASE      )
            snake_case_ =   distance_of_first_solution + int(SCREAMING_SNAKE_CASE      )
            snake_case_ =   best_node

      first_solution.append(SCREAMING_SNAKE_CASE      )

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

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






def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE      ,      SCREAMING_SNAKE_CASE      )->						List[Any]:




      """simple docstring"""

      snake_case_ =   []

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

                  snake_case_ =   copy.deepcopy(SCREAMING_SNAKE_CASE      )
                  snake_case_ =   kn
                  snake_case_ =   n

                  snake_case_ =   0

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

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

      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      )->						List[Any]:




      """simple docstring"""

      snake_case_ =   1
      snake_case_ =   first_solution
      snake_case_ =   []
      snake_case_ =   distance_of_first_solution
      snake_case_ =   solution

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

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

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

            snake_case_ =   count + 1

      return best_solution_ever, best_cost






def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE=None      )->						int:




      """simple docstring"""

      snake_case_ =   generate_neighbours(args.File      )

      snake_case_ ,					snake_case_ =   generate_first_solution(
          args.File      ,      SCREAMING_SNAKE_CASE      )

      snake_case_ ,					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    =					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())



import copy
import re







class lowerCAmelCase_		:

 '''simple docstring'''

 __snake_case				=						"hp"
 __snake_case				=						{}
 __snake_case				=						None



 @classmethod
 def 		UpperCamelCase__  (			cls	,   _UpperCAmelCase	,   _UpperCAmelCase      ):
       snake_case_ =   prefix
       snake_case_ =   defaults
       cls.build_naming_info()



 @staticmethod
 def 		UpperCamelCase__  (			_UpperCAmelCase	,   _UpperCAmelCase      ):
       if len(_UpperCAmelCase      ) == 0:
             return ""
       snake_case_ =   None
       if any(char.isdigit() for char in word      ):
             raise Exception(F'''Parameters should not contain numbers: \'{word}\' contains a number'''      )
       if word in info["short_word"]:
             return info["short_word"][word]
       for prefix_len in range(1	,   len(_UpperCAmelCase      ) + 1      ):
             snake_case_ =   word[:prefix_len]
             if prefix in info["reverse_short_word"]:
                   continue
             else:
                   snake_case_ =   prefix
                   break

       if short_word is None:
             # Paranoid fallback
             def int_to_alphabetic(_UpperCAmelCase      ):
                   snake_case_ =   ''''''
                   while integer != 0:
                         snake_case_ =   chr(ord('''A'''      ) + integer % 10      ) + s
                         integer //= 10
                   return s

             snake_case_ =   0
             while True:
                   snake_case_ =   word + '''#''' + int_to_alphabetic(_UpperCAmelCase      )
                   if sword in info["reverse_short_word"]:
                         continue
                   else:
                         snake_case_ =   sword
                         break

       snake_case_ =   short_word
       snake_case_ =   word
       return short_word



 @staticmethod
 def 		UpperCamelCase__  (			_UpperCAmelCase	,   _UpperCAmelCase      ):
       snake_case_ =   param_name.split('''_'''      )

       snake_case_ =   [TrialShortNamer.shortname_for_word(_UpperCAmelCase	,   _UpperCAmelCase      ) for word in words]

       # We try to create a separatorless short name, but if there is a collision we have to fallback
       # to a separated short name
       snake_case_ =   ['''''', '''_''']

       for separator in separators:
             snake_case_ =   separator.join(_UpperCAmelCase      )
             if shortname not in info["reverse_short_param"]:
                   snake_case_ =   shortname
                   snake_case_ =   param_name
                   return shortname

       return param_name



 @staticmethod
 def 		UpperCamelCase__  (			_UpperCAmelCase	,   _UpperCAmelCase      ):
       snake_case_ =   TrialShortNamer.shortname_for_key(_UpperCAmelCase	,   _UpperCAmelCase      )
       snake_case_ =   short_name
       snake_case_ =   param_name



 @classmethod
 def 		UpperCamelCase__  (			cls      ):
       if cls.NAMING_INFO is not None:
             return

       snake_case_ =   {
           '''short_word''': {},
           '''reverse_short_word''': {},
           '''short_param''': {},
           '''reverse_short_param''': {},
       }

       snake_case_ =   list(cls.DEFAULTS.keys()      )

       for k in field_keys:
             cls.add_new_param_name(_UpperCAmelCase	,   _UpperCAmelCase      )

       snake_case_ =   info



 @classmethod
 def 		UpperCamelCase__  (			cls	,   _UpperCAmelCase      ):
       cls.build_naming_info()
       assert cls.PREFIX is not None
       snake_case_ =   [copy.copy(cls.PREFIX      )]

       for k, v in params.items():
             if k not in cls.DEFAULTS:
                   raise Exception(F'''You should provide a default value for the param name {k} with value {v}'''      )
             if v == cls.DEFAULTS[k]:
                   # The default value is not added to the name
                   continue

             snake_case_ =   cls.NAMING_INFO['''short_param'''][k]

             if isinstance(_UpperCAmelCase	,   _UpperCAmelCase      ):
                   snake_case_ =   1 if v else 0

             snake_case_ =   '''''' if isinstance(_UpperCAmelCase	,   (int, float)      ) else '''-'''
             snake_case_ =   F'''{key}{sep}{v}'''
             name.append(_UpperCAmelCase      )

       return "_".join(_UpperCAmelCase      )





 @classmethod
 def 		UpperCamelCase__  (			cls	,   _UpperCAmelCase      ):
       snake_case_ =   repr[len(cls.PREFIX      ) + 1 :]
       if repr == "":
             snake_case_ =   []
       else:
             snake_case_ =   repr.split('''_'''      )

       snake_case_ =   {}

       for value in values:
             if "-" in value:
                   snake_case_ ,					snake_case_ =   value.split('''-'''      )
             else:
                   snake_case_ =   re.sub('''[0-9.]'''	,   ''''''	,   _UpperCAmelCase      )
                   snake_case_ =   float(re.sub('''[^0-9.]'''	,   ''''''	,   _UpperCAmelCase      )      )

             snake_case_ =   cls.NAMING_INFO['''reverse_short_param'''][p_k]

             snake_case_ =   p_v

       for k in cls.DEFAULTS:
             if k not in parameters:
                   snake_case_ =   cls.DEFAULTS[k]

       return parameters