


import argparse
import copy





def   _UpperCAmelCase       (     UpperCAmelCase      :			Tuple      ):
      """simple docstring"""




      __lowerCamelCase     :      List[str]       						=						{}

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

      return dict_of_neighbours





def   _UpperCAmelCase       (     UpperCAmelCase      :			Optional[int]						,	UpperCAmelCase      :			Union[str, Any]      ):
      """simple docstring"""




      with open(lowerCamelCase_      ) as f:
            __lowerCamelCase     :      str       						=						f.read(1      )
      __lowerCamelCase     :      Dict       						=						start_node

      __lowerCamelCase     :      Optional[int]       						=						[]

      __lowerCamelCase     :      Tuple       						=						start_node

      __lowerCamelCase     :      Optional[Any]       						=						0
      while visiting not in first_solution:
            __lowerCamelCase     :      Dict       						=						10_000
            for k in dict_of_neighbours[visiting]:
                  if int(k[1]      ) < int(lowerCamelCase_      ) and k[0] not in first_solution:
                        __lowerCamelCase     :      Optional[int]       						=						k[1]
                        __lowerCamelCase     :      Optional[Any]       						=						k[0]

            first_solution.append(lowerCamelCase_      )
            __lowerCamelCase     :      Tuple       						=						distance_of_first_solution + int(lowerCamelCase_      )
            __lowerCamelCase     :      Tuple       						=						best_node

      first_solution.append(lowerCamelCase_      )

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

      __lowerCamelCase     :      int       						=						(
          distance_of_first_solution
          + int(dict_of_neighbours[first_solution[-2]][position][1]      )
          - 10_000
      )
      return first_solution, distance_of_first_solution





def   _UpperCAmelCase       (     UpperCAmelCase      :			Dict						,	UpperCAmelCase      :			List[str]      ):
      """simple docstring"""




      __lowerCamelCase     :      Optional[Any]       						=						[]

      for n in solution[1:-1]:
            __lowerCamelCase     :      int       						=						solution.index(lowerCamelCase_      )
            for kn in solution[1:-1]:
                  __lowerCamelCase     :      List[Any]       						=						solution.index(lowerCamelCase_      )
                  if n == kn:
                        continue

                  __lowerCamelCase     :      Optional[int]       						=						copy.deepcopy(lowerCamelCase_      )
                  __lowerCamelCase     :      Dict       						=						kn
                  __lowerCamelCase     :      Tuple       						=						n

                  __lowerCamelCase     :      int       						=						0

                  for k in _tmp[:-1]:
                        __lowerCamelCase     :      Union[str, Any]       						=						_tmp[_tmp.index(lowerCamelCase_      ) + 1]
                        for i in dict_of_neighbours[k]:
                              if i[0] == next_node:
                                    __lowerCamelCase     :      Optional[int]       						=						distance + int(i[1]      )
                  _tmp.append(lowerCamelCase_      )

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





def   _UpperCAmelCase       (     UpperCAmelCase      :			int						,	UpperCAmelCase      :			Optional[Any]						,	UpperCAmelCase      :			Optional[Any]						,	UpperCAmelCase      :			Any						,	UpperCAmelCase      :			str      ):
      """simple docstring"""




      __lowerCamelCase     :      Optional[Any]       						=						1
      __lowerCamelCase     :      Tuple       						=						first_solution
      __lowerCamelCase     :      Dict       						=						[]
      __lowerCamelCase     :      int       						=						distance_of_first_solution
      __lowerCamelCase     :      List[str]       						=						solution

      while count <= iters:
            __lowerCamelCase     :      List[str]       						=						find_neighborhood(lowerCamelCase_						,	lowerCamelCase_      )
            __lowerCamelCase     :      Tuple       						=						0
            __lowerCamelCase     :      Any       						=						neighborhood[index_of_best_solution]
            __lowerCamelCase     :      Any       						=						len(lowerCamelCase_      ) - 1

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

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

            __lowerCamelCase     :      List[str]       						=						count + 1

      return best_solution_ever, best_cost





def   _UpperCAmelCase       (     UpperCAmelCase      :			Optional[int]=None      ):
      """simple docstring"""




      __lowerCamelCase     :      List[str]       						=						generate_neighbours(args.File      )

      __lowerCamelCase     :      Optional[Any]       						=						generate_first_solution(
          args.File						,	lowerCamelCase_      )

      __lowerCamelCase     :      Union[str, Any]       						=						tabu_search(
          lowerCamelCase_						,	lowerCamelCase_						,	lowerCamelCase_						,	args.Iterations						,	args.Size						,	)

      print(f"""Best solution: {best_sol}, with total distance: {best_cost}."""      )


if __name__ == "__main__":
    __UpperCamelCase    :						List[Any]     =							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       (     UpperCAmelCase      :			list      ):
      """simple docstring"""




      __lowerCamelCase     :      Optional[int]       						=						len(UpperCAmelCase      )
      for _ in range(UpperCAmelCase      ):
            for i in range(_ % 2						,	arr_size - 1						,	2      ):
                  if arr[i + 1] < arr[i]:
                        __lowerCamelCase						, __lowerCamelCase     :      List[str]       						=						arr[i + 1], arr[i]

      return arr


if __name__ == "__main__":
    __UpperCamelCase    :						str     =							list(range(10, 0, -1))
    print(F'''Original: {arr}. Sorted: {odd_even_transposition(arr)}''')



