



from __future__ import annotations

from collections.abc import Callable
from typing import Generic, TypeVar

_snake_case		=  TypeVar("T")
_snake_case		=  TypeVar("U")



class   UpperCAmelCase_    (       Generic[T, U]):







							def __init__(   self,			__a,			__a):

														'''simple docstring'''

														_lowerCAmelCase     :							Union[str, Any]    =    key
														_lowerCAmelCase     :							Any    =    val
														_lowerCAmelCase     :							DoubleLinkedListNode[T, U] | None    =    None
														_lowerCAmelCase     :							DoubleLinkedListNode[T, U] | None    =    None







							def __repr__(   self):

														'''simple docstring'''

														return (
														    f"Node: key: {self.key}, val: {self.val}, "
														    f"has next: {bool(self.next)}, has prev: {bool(self.prev)}"
														)



class   UpperCAmelCase_    (       Generic[T, U]):







							def __init__(   self):

														'''simple docstring'''

														_lowerCAmelCase     :							DoubleLinkedListNode[T, U]    =    DoubleLinkedListNode(__a,			__a)
														_lowerCAmelCase     :							DoubleLinkedListNode[T, U]    =    DoubleLinkedListNode(__a,			__a)
														_lowerCAmelCase   ,    _lowerCAmelCase     :							Optional[int]    =    self.rear, self.head







							def __repr__(   self):

														'''simple docstring'''

														_lowerCAmelCase     :							Dict    =    ["DoubleLinkedList"]
														_lowerCAmelCase     :							str    =    self.head
														while node.next is not None:
																					rep.append(str(__a))
																					_lowerCAmelCase     :							Tuple    =    node.next
														rep.append(str(self.rear))
														return ",\n    ".join(__a)







							def    snake_case__      (   self,			__a):

														'''simple docstring'''

														_lowerCAmelCase     :							Union[str, Any]    =    self.rear.prev

														# All nodes other than self.head are guaranteed to have non-None previous
														assert previous is not None

														_lowerCAmelCase     :							Union[str, Any]    =    node
														_lowerCAmelCase     :							Union[str, Any]    =    previous
														_lowerCAmelCase     :							Tuple    =    node
														_lowerCAmelCase     :							Optional[Any]    =    self.rear







							def    snake_case__      (   self,			__a):

														'''simple docstring'''

														if node.prev is None or node.next is None:
																					return None

														_lowerCAmelCase     :							List[str]    =    node.next
														_lowerCAmelCase     :							Union[str, Any]    =    node.prev
														_lowerCAmelCase     :							Dict    =    None
														_lowerCAmelCase     :							Optional[Any]    =    None
														return node



class   UpperCAmelCase_    (       Generic[T, U]):
							lowerCamelCase__   			=		{}







							def __init__(   self,			__a):

														'''simple docstring'''

														_lowerCAmelCase     :							DoubleLinkedList[T, U]    =    DoubleLinkedList()
														_lowerCAmelCase     :							int    =    capacity
														_lowerCAmelCase     :							int    =    0
														_lowerCAmelCase     :							Optional[Any]    =    0
														_lowerCAmelCase     :							List[Any]    =    0
														_lowerCAmelCase     :							dict[T, DoubleLinkedListNode[T, U]]    =    {}







							def __repr__(   self):

														'''simple docstring'''

														return (
														    f"CacheInfo(hits={self.hits}, misses={self.miss}, "
														    f"capacity={self.capacity}, current size={self.num_keys})"
														)







							def __contains__(   self,			__a):

														'''simple docstring'''

														return key in self.cache







							def    snake_case__      (   self,			__a):

														'''simple docstring'''

														if key in self.cache:
																					self.hits += 1
																					_lowerCAmelCase     :							DoubleLinkedListNode[T, U]    =    self.cache[key]
																					_lowerCAmelCase     :							Optional[int]    =    self.list.remove(self.cache[key])
																					assert node == value_node

																					# node is guaranteed not None because it is in self.cache
																					assert node is not None
																					self.list.add(__a)
																					return node.val
														self.miss += 1
														return None







							def    snake_case__      (   self,			__a,			__a):

														'''simple docstring'''

														if key not in self.cache:
																					if self.num_keys >= self.capacity:
																												# delete first node (oldest) when over capacity
																												_lowerCAmelCase     :							str    =    self.list.head.next

																												# guaranteed to have a non-None first node when num_keys > 0
																												# explain to type checker via assertions
																												assert first_node is not None
																												assert first_node.key is not None
																												assert (
																												    self.list.remove(__a) is not None
																												)  # node guaranteed to be in list assert node.key is not None

																												del self.cache[first_node.key]
																												self.num_keys -= 1
																					_lowerCAmelCase     :							Union[str, Any]    =    DoubleLinkedListNode(__a,			__a)
																					self.list.add(self.cache[key])
																					self.num_keys += 1

														else:
																					# bump node to the end of the list, update value
																					_lowerCAmelCase     :							Optional[Any]    =    self.list.remove(self.cache[key])
																					assert node is not None  # node guaranteed to be in list
																					_lowerCAmelCase     :							List[str]    =    value
																					self.list.add(__a)







							@classmethod
							def    snake_case__      (   cls,			__a = 128):

														'''simple docstring'''

														def cache_decorator_inner(__a) -> Callable[..., U]:
																					def cache_decorator_wrapper(*__a) -> U:
																												if func not in cls.decorator_function_to_instance_map:
																																			_lowerCAmelCase     :							Tuple    =    LRUCache(__a)

																												_lowerCAmelCase     :							Dict    =    cls.decorator_function_to_instance_map[func].get(args[0])
																												if result is None:
																																			_lowerCAmelCase     :							Optional[int]    =    func(*__a)
																																			cls.decorator_function_to_instance_map[func].put(args[0],			__a)
																												return result

																					def cache_info() -> LRUCache[T, U]:
																												return cls.decorator_function_to_instance_map[func]

																					setattr(__a,			"cache_info",			__a)  # noqa: B010

																					return cache_decorator_wrapper

														return cache_decorator_inner


if __name__ == "__main__":
						import doctest

						doctest.testmod()





import argparse
import copy






def 				A				(					_lowerCamelCase  ):





							'''simple docstring'''




							_lowerCAmelCase     :							int    =    {}

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

							return dict_of_neighbours






def 				A				(					_lowerCamelCase				, _lowerCamelCase  ):





							'''simple docstring'''




							with open(_lowerCamelCase  ) as f:
														_lowerCAmelCase     :							str    =    f.read(1  )
							_lowerCAmelCase     :							str    =    start_node

							_lowerCAmelCase     :							List[str]    =    []

							_lowerCAmelCase     :							Any    =    start_node

							_lowerCAmelCase     :							str    =    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     :							List[str]    =    k[1]
																												_lowerCAmelCase     :							List[Any]    =    k[0]

														first_solution.append(_lowerCamelCase  )
														_lowerCAmelCase     :							Optional[int]    =    distance_of_first_solution + int(_lowerCamelCase  )
														_lowerCAmelCase     :							str    =    best_node

							first_solution.append(_lowerCamelCase  )

							_lowerCAmelCase     :							Union[str, Any]    =    0
							for k in dict_of_neighbours[first_solution[-2]]:
														if k[0] == start_node:
																					break
														position += 1

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






def 				A				(					_lowerCamelCase				, _lowerCamelCase  ):





							'''simple docstring'''




							_lowerCAmelCase     :							Tuple    =    []

							for n in solution[1:-1]:
														_lowerCAmelCase     :							Dict    =    solution.index(_lowerCamelCase  )
														for kn in solution[1:-1]:
																					_lowerCAmelCase     :							Dict    =    solution.index(_lowerCamelCase  )
																					if n == kn:
																												continue

																					_lowerCAmelCase     :							Optional[int]    =    copy.deepcopy(_lowerCamelCase  )
																					_lowerCAmelCase     :							int    =    kn
																					_lowerCAmelCase     :							Dict    =    n

																					_lowerCAmelCase     :							Optional[int]    =    0

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

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

							_lowerCAmelCase     :							List[Any]    =    len(neighborhood_of_solution[0]  ) - 1

							neighborhood_of_solution.sort(key=lambda _lowerCamelCase  : x[index_of_last_item_in_the_list]  )
							return neighborhood_of_solution






def 				A				(					_lowerCamelCase				, _lowerCamelCase				, _lowerCamelCase				, _lowerCamelCase				, _lowerCamelCase  ):





							'''simple docstring'''




							_lowerCAmelCase     :							List[str]    =    1
							_lowerCAmelCase     :							int    =    first_solution
							_lowerCAmelCase     :							Tuple    =    []
							_lowerCAmelCase     :							Tuple    =    distance_of_first_solution
							_lowerCAmelCase     :							Optional[int]    =    solution

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

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

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

														_lowerCAmelCase     :							int    =    count + 1

							return best_solution_ever, best_cost






def 				A				(					_lowerCamelCase=None  ):





							'''simple docstring'''




							_lowerCAmelCase     :							int    =    generate_neighbours(args.File  )

							_lowerCAmelCase   ,    _lowerCAmelCase     :							List[str]    =    generate_first_solution(
							    args.File				, _lowerCamelCase  )

							_lowerCAmelCase   ,    _lowerCAmelCase     :							Any    =    tabu_search(
							    _lowerCamelCase				, _lowerCamelCase				, _lowerCamelCase				, args.Iterations				, args.Size				, )

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


if __name__ == "__main__":
						_snake_case		=  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())
