
import argparse
import copy







def        A_     (						__SCREAMING_SNAKE_CASE						:  List[Any] )				->       Optional[Any]:





  """simple docstring"""

  __A		:     List[Any]												=		{}

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

  return dict_of_neighbours







def        A_     (						__SCREAMING_SNAKE_CASE						:  str			,     __SCREAMING_SNAKE_CASE						:  Dict )				->       Optional[int]:





  """simple docstring"""

  with open(__UpperCamelCase ) as f:
    __A		:     str												=		f.read(1 )
  __A		:     Any												=		start_node

  __A		:     Dict												=		[]

  __A		:     Union[str, Any]												=		start_node

  __A		:     List[Any]												=		0
  while visiting not in first_solution:
    __A		:     List[Any]												=		1_0000
    for k in dict_of_neighbours[visiting]:
      if int(k[1] ) < int(__UpperCamelCase ) and k[0] not in first_solution:
        __A		:     Dict												=		k[1]
        __A		:     Optional[int]												=		k[0]

    first_solution.append(__UpperCamelCase )
    __A		:     List[Any]												=		distance_of_first_solution + int(__UpperCamelCase )
    __A		:     Dict												=		best_node

  first_solution.append(__UpperCamelCase )

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

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







def        A_     (						__SCREAMING_SNAKE_CASE						:  int			,     __SCREAMING_SNAKE_CASE						:  str )				->       Dict:





  """simple docstring"""

  __A		:     List[Any]												=		[]

  for n in solution[1:-1]:
    __A		:     Optional[int]												=		solution.index(__UpperCamelCase )
    for kn in solution[1:-1]:
      __A		:     Tuple												=		solution.index(__UpperCamelCase )
      if n == kn:
        continue

      __A		:     List[Any]												=		copy.deepcopy(__UpperCamelCase )
      __A		:     Union[str, Any]												=		kn
      __A		:     Dict												=		n

      __A		:     List[str]												=		0

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

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

  __A		:     Optional[int]												=		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        A_     (						__SCREAMING_SNAKE_CASE						:  Tuple			,     __SCREAMING_SNAKE_CASE						:  int			,     __SCREAMING_SNAKE_CASE						:  List[Any]			,     __SCREAMING_SNAKE_CASE						:  List[str]			,     __SCREAMING_SNAKE_CASE						:  List[Any] )				->       List[Any]:





  """simple docstring"""

  __A		:     List[Any]												=		1
  __A		:     int												=		first_solution
  __A		:     Tuple												=		[]
  __A		:     Tuple												=		distance_of_first_solution
  __A		:     Dict												=		solution

  while count <= iters:
    __A		:     Dict												=		find_neighborhood(__UpperCamelCase			,     __UpperCamelCase )
    __A		:     Dict												=		0
    __A		:     int												=		neighborhood[index_of_best_solution]
    __A		:     int												=		len(__UpperCamelCase ) - 1

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

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

    __A		:     Optional[Any]												=		count + 1

  return best_solution_ever, best_cost







def        A_     (						__SCREAMING_SNAKE_CASE						:  List[str]=None )				->       Tuple:





  """simple docstring"""

  __A		:     str												=		generate_neighbours(args.File )

  __A		:     str												=		generate_first_solution(
      args.File			,     __UpperCamelCase )

  __A		:     Tuple												=		tabu_search(
      __UpperCamelCase			,     __UpperCamelCase			,     __UpperCamelCase			,     args.Iterations			,     args.Size			,     )

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


if __name__ == "__main__":
     A__   :		int 		=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        A_     (						__SCREAMING_SNAKE_CASE						:  Dict )				->       Optional[Any]:





  """simple docstring"""

  if not head:
    return True
  # split the list to two parts
  __A							,					__A		:     Any												=		head.next, head
  while fast and fast.next:
    __A		:     List[str]												=		fast.next.next
    __A		:     List[Any]												=		slow.next
  __A		:     int												=		slow.next
  __A		:     List[str]												=		None  # Don't forget here! But forget still works!
  # reverse the second part
  __A		:     Dict												=		None
  while second:
    __A		:     Dict												=		second.next
    __A		:     str												=		node
    __A		:     int												=		second
    __A		:     Optional[int]												=		nxt
  # compare two parts
  # second part has the same or one less node
  while node:
    if node.val != head.val:
      return False
    __A		:     List[Any]												=		node.next
    __A		:     Tuple												=		head.next
  return True







def        A_     (						__SCREAMING_SNAKE_CASE						:  Union[str, Any] )				->       Optional[int]:





  """simple docstring"""

  if not head or not head.next:
    return True

  # 1. Get the midpoint (slow)
  __A		:     int												=		head
  while fast and fast.next:
    __A							,					__A		:     Optional[int]												=		fast.next.next, slow.next

  # 2. Push the second half into the stack
  __A		:     Union[str, Any]												=		[slow.val]
  while slow.next:
    __A		:     List[str]												=		slow.next
    stack.append(slow.val )

  # 3. Comparison
  while stack:
    if stack.pop() != cur.val:
      return False
    __A		:     Tuple												=		cur.next

  return True







def        A_     (						__SCREAMING_SNAKE_CASE						:  Dict )				->       Any:





  """simple docstring"""

  if not head or not head.next:
    return True
  __A		:     List[Any]												=		{}
  __A		:     Optional[int]												=		0
  while head:
    if head.val in d:
      d[head.val].append(__SCREAMING_SNAKE_CASE )
    else:
      __A		:     Tuple												=		[pos]
    __A		:     List[Any]												=		head.next
    pos += 1
  __A		:     List[Any]												=		pos - 1
  __A		:     List[str]												=		0
  for v in d.values():
    if len(__SCREAMING_SNAKE_CASE ) % 2 != 0:
      middle += 1
    else:
      __A		:     List[Any]												=		0
      for i in range(0			,     len(__SCREAMING_SNAKE_CASE ) ):
        if v[i] + v[len(__SCREAMING_SNAKE_CASE ) - 1 - step] != checksum:
          return False
        step += 1
    if middle > 1:
      return False
  return True



