

'''simple docstring'''







import argparse
import copy
def       UpperCAmelCase__    (      UpperCAmelCase__				)			->			int:
       A_						=      {}

       with open(UpperCAmelCase__				) as f:
              for line in f:
                     if line.split()[0] not in dict_of_neighbours:
                            A_						=      []
                            _list.append([line.split()[1], line.split()[2]]				)
                            A_						=      _list
                     else:
                            dict_of_neighbours[line.split()[0]].append(
                                [line.split()[1], line.split()[2]]				)
                     if line.split()[1] not in dict_of_neighbours:
                            A_						=      []
                            _list.append([line.split()[0], line.split()[2]]				)
                            A_						=      _list
                     else:
                            dict_of_neighbours[line.split()[1]].append(
                                [line.split()[0], line.split()[2]]				)

       return dict_of_neighbours
def       UpperCAmelCase__    (      UpperCAmelCase__,       UpperCAmelCase__				)			->			Tuple:

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

       A_						=      []

       A_						=      start_node

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

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

       first_solution.append(UpperCAmelCase__				)

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

       A_						=      (
           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__    (      UpperCAmelCase__,       UpperCAmelCase__				)			->			Dict:
       A_						=      []

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

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

                     A_						=      0

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

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

       A_						=      len(neighborhood_of_solution[0]				) - 1

       neighborhood_of_solution.sort(key=lambda UpperCAmelCase__				: x[index_of_last_item_in_the_list]				)
       return neighborhood_of_solution
def       UpperCAmelCase__    (      UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__				)			->			Optional[Any]:
       A_						=      1
       A_						=      first_solution
       A_						=      []
       A_						=      distance_of_first_solution
       A_						=      solution

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

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

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

              A_						=      count + 1

       return best_solution_ever, best_cost
def       UpperCAmelCase__    (      UpperCAmelCase__=None				)			->			Dict:
       A_						=      generate_neighbours(args.File				)

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

       A_					,			A_						=      tabu_search(
           UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       args.Iterations,       args.Size,       )

       print(F'''Best solution: {best_sol}, with total distance: {best_cost}.'''				)


if __name__ == "__main__":
      __lowerCamelCase		       =    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'''







import os

__lowerCamelCase		       =    {'''I''': 1, '''V''': 5, '''X''': 10, '''L''': 50, '''C''': 100, '''D''': 500, '''M''': 1000}
def       UpperCAmelCase__    (      UpperCAmelCase__				)			->			int:
       A_						=      0

       A_						=      0
       while index < len(UpperCAmelCase__				) - 1:
              A_						=      SYMBOLS[numerals[index]]
              A_						=      SYMBOLS[numerals[index + 1]]
              if current_value < next_value:
                     total_value -= current_value
              else:
                     total_value += current_value
              index += 1
       total_value += SYMBOLS[numerals[index]]

       return total_value
def       UpperCAmelCase__    (      UpperCAmelCase__				)			->			str:
       A_						=      """"""

       A_						=      num // 10_00
       numerals += m_count * "M"
       num %= 10_00

       A_						=      num // 1_00
       if c_count == 9:
              numerals += "CM"
              c_count -= 9
       elif c_count == 4:
              numerals += "CD"
              c_count -= 4
       if c_count >= 5:
              numerals += "D"
              c_count -= 5
       numerals += c_count * "C"
       num %= 1_00

       A_						=      num // 10
       if x_count == 9:
              numerals += "XC"
              x_count -= 9
       elif x_count == 4:
              numerals += "XL"
              x_count -= 4
       if x_count >= 5:
              numerals += "L"
              x_count -= 5
       numerals += x_count * "X"
       num %= 10

       if num == 9:
              numerals += "IX"
              num -= 9
       elif num == 4:
              numerals += "IV"
              num -= 4
       if num >= 5:
              numerals += "V"
              num -= 5
       numerals += num * "I"

       return numerals
def       UpperCAmelCase__    (      UpperCAmelCase__ = "/p089_roman.txt"				)			->			int:
       A_						=      0

       with open(os.path.dirname(UpperCAmelCase__				) + roman_numerals_filename				) as filea:
              A_						=      filea.readlines()

       for line in lines:
              A_						=      line.strip()
              A_						=      parse_roman_numerals(UpperCAmelCase__				)
              A_						=      generate_roman_numerals(UpperCAmelCase__				)
              savings += len(UpperCAmelCase__				) - len(UpperCAmelCase__				)

       return savings


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