


import argparse
import copy
def       UpperCAmelCase__						(UpperCamelCase_    ):



     """simple docstring"""






     snake_case					=    {}

     with open(UpperCamelCase_    ) 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       UpperCAmelCase__						(UpperCamelCase_							,UpperCamelCase_    ):



     """simple docstring"""






     with open(UpperCamelCase_    ) 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_00_00
          for k in dict_of_neighbours[visiting]:
               if int(k[1]    ) < int(UpperCamelCase_    ) and k[0] not in first_solution:
                    snake_case					=    k[1]
                    snake_case					=    k[0]

          first_solution.append(UpperCamelCase_    )
          snake_case					=    distance_of_first_solution + int(UpperCamelCase_    )
          snake_case					=    best_node

     first_solution.append(UpperCamelCase_    )

     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_00_00
     )
     return first_solution, distance_of_first_solution
def       UpperCAmelCase__						(UpperCamelCase_							,UpperCamelCase_    ):



     """simple docstring"""






     snake_case					=    []

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

               snake_case					=    copy.deepcopy(UpperCamelCase_    )
               snake_case					=    kn
               snake_case					=    n

               snake_case					=    0

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

               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 UpperCamelCase_    : x[index_of_last_item_in_the_list]    )
     return neighborhood_of_solution
def       UpperCAmelCase__						(UpperCamelCase_							,UpperCamelCase_							,UpperCamelCase_							,UpperCamelCase_							,UpperCamelCase_    ):



     """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(UpperCamelCase_							,UpperCamelCase_    )
          snake_case					=    0
          snake_case					=    neighborhood[index_of_best_solution]
          snake_case					=    len(UpperCamelCase_    ) - 1

          snake_case					=    False
          while not found:
               snake_case					=    0
               while i < len(UpperCamelCase_    ):
                    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(UpperCamelCase_    ) >= size:
               tabu_list.pop(0    )

          snake_case					=    count + 1

     return best_solution_ever, best_cost
def       UpperCAmelCase__						(UpperCamelCase_=None    ):



     """simple docstring"""






     snake_case					=    generate_neighbours(args.File    )

     snake_case					=    generate_first_solution(
         args.File							,UpperCamelCase_    )

     snake_case					=    tabu_search(
         UpperCamelCase_							,UpperCamelCase_							,UpperCamelCase_							,args.Iterations							,args.Size							,)

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


if __name__ == "__main__":
 _SCREAMING_SNAKE_CASE      :			Union[str, 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())








from __future__ import annotations

import time

_SCREAMING_SNAKE_CASE      :			List[Any]      				=   list[tuple[int, int]]

_SCREAMING_SNAKE_CASE      :			Any      				=   [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
]

_SCREAMING_SNAKE_CASE      :			Any      				=   [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

class   A__ :







    """simple docstring"""

    def __init__(	self      , __snake_case      , __snake_case      , __snake_case      , __snake_case      , __snake_case   ):
         snake_case					=    pos_x
         snake_case					=    pos_y
         snake_case					=    (pos_y, pos_x)
         snake_case					=    goal_x
         snake_case					=    goal_y
         snake_case					=    parent






class   A__ :







    """simple docstring"""

    def __init__(	self      , __snake_case      , __snake_case   ):
         snake_case					=    Node(start[1]      , start[0]      , goal[1]      , goal[0]      , __snake_case   )
         snake_case					=    Node(goal[1]      , goal[0]      , goal[1]      , goal[0]      , __snake_case   )

         snake_case					=    [self.start]
         snake_case					=    False
    def 		a_      (	self   ):
         while self.node_queue:
              snake_case					=    self.node_queue.pop(0   )

              if current_node.pos == self.target.pos:
                   snake_case					=    True
                   return self.retrace_path(__snake_case   )

              snake_case					=    self.get_successors(__snake_case   )

              for node in successors:
                   self.node_queue.append(__snake_case   )

         if not self.reached:
              return [self.start.pos]
         return None
    def 		a_      (	self      , __snake_case   ):
         snake_case					=    []
         for action in delta:
              snake_case					=    parent.pos_x + action[1]
              snake_case					=    parent.pos_y + action[0]
              if not (0 <= pos_x <= len(grid[0]   ) - 1 and 0 <= pos_y <= len(__snake_case   ) - 1):
                   continue

              if grid[pos_y][pos_x] != 0:
                   continue

              successors.append(
                  Node(__snake_case      , __snake_case      , self.target.pos_y      , self.target.pos_x      , __snake_case   )   )
         return successors




    def 		a_      (	self      , __snake_case   ):
         snake_case					=    node
         snake_case					=    []
         while current_node is not None:
              path.append((current_node.pos_y, current_node.pos_x)   )
              snake_case					=    current_node.parent
         path.reverse()
         return path






class   A__ :







    """simple docstring"""

    def __init__(	self      , __snake_case      , __snake_case   ):
         snake_case					=    BreadthFirstSearch(__snake_case      , __snake_case   )
         snake_case					=    BreadthFirstSearch(__snake_case      , __snake_case   )
         snake_case					=    False
    def 		a_      (	self   ):
         while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
              snake_case					=    self.fwd_bfs.node_queue.pop(0   )
              snake_case					=    self.bwd_bfs.node_queue.pop(0   )

              if current_bwd_node.pos == current_fwd_node.pos:
                   snake_case					=    True
                   return self.retrace_bidirectional_path(
                       __snake_case      , __snake_case   )

              snake_case					=    current_bwd_node
              snake_case					=    current_fwd_node

              snake_case					=    {
                  self.fwd_bfs: self.fwd_bfs.get_successors(__snake_case   ),
                  self.bwd_bfs: self.bwd_bfs.get_successors(__snake_case   ),
              }

              for bfs in [self.fwd_bfs, self.bwd_bfs]:
                   for node in successors[bfs]:
                        bfs.node_queue.append(__snake_case   )

         if not self.reached:
              return [self.fwd_bfs.start.pos]
         return None




    def 		a_      (	self      , __snake_case      , __snake_case   ):
         snake_case					=    self.fwd_bfs.retrace_path(__snake_case   )
         snake_case					=    self.bwd_bfs.retrace_path(__snake_case   )
         bwd_path.pop()
         bwd_path.reverse()
         snake_case					=    fwd_path + bwd_path
         return path


if __name__ == "__main__":
 # all coordinates are given in format [y,x]
 import doctest

 doctest.testmod()
 _SCREAMING_SNAKE_CASE      :			Optional[Any]      				=   (0, 0)
 _SCREAMING_SNAKE_CASE      :			List[Any]      				=   (len(grid) - 1, len(grid[0]) - 1)
 for elem in grid:
  print(elem)

 _SCREAMING_SNAKE_CASE      :			List[Any]      				=   time.time()
 _SCREAMING_SNAKE_CASE      :			List[Any]      				=   BreadthFirstSearch(init, goal)
 _SCREAMING_SNAKE_CASE      :			List[str]      				=   bfs.search()
 _SCREAMING_SNAKE_CASE      :			int      				=   time.time() - start_bfs_time

 print("Unidirectional BFS computation time : ", bfs_time)

 _SCREAMING_SNAKE_CASE      :			Any      				=   time.time()
 _SCREAMING_SNAKE_CASE      :			Union[str, Any]      				=   BidirectionalBreadthFirstSearch(init, goal)
 _SCREAMING_SNAKE_CASE      :			Union[str, Any]      				=   bd_bfs.search()
 _SCREAMING_SNAKE_CASE      :			Tuple      				=   time.time() - start_bd_bfs_time

 print("Bidirectional BFS computation time : ", bd_bfs_time)




