




from __future__ import annotations

import time

import numpy as np

UpperCAmelCase__				     = [8, 5, 9, 7]
UpperCAmelCase__				     = [
    [2, 0, 1, 1],
    [0, 1, 2, 1],
    [4, 0, 0, 3],
    [0, 2, 1, 0],
    [1, 0, 3, 0],
]
UpperCAmelCase__				     = [
    [3, 2, 1, 4],
    [0, 2, 5, 2],
    [5, 1, 0, 5],
    [1, 5, 3, 0],
    [3, 0, 3, 3],
]







class a :
						"""simple docstring"""

						def __init__( self :     List[str]				,							lowerCamelCase__ :     list[int]				,							lowerCamelCase__ :     list[list[int]]				,							lowerCamelCase__ :     list[list[int]]				,							)    ->						None:
													"""simple docstring"""


													__lowercase      =    claim_vector
													__lowercase      =    allocated_resources_table
													__lowercase      =    maximum_claim_table






						def     UpperCAmelCase_      ( self :     Tuple				)    ->						list[int]:
													"""simple docstring"""


													return [
													    sum(p_item[i] for p_item in self.__allocated_resources_table				)
													    for i in range(len(self.__allocated_resources_table[0]				)				)
													]






						def     UpperCAmelCase_      ( self :     str				)    ->						list[int]:
													"""simple docstring"""


													return np.array(self.__claim_vector				) - np.array(
													    self.__processes_resource_summation()				)






						def     UpperCAmelCase_      ( self :     Any				)    ->						list[list[int]]:
													"""simple docstring"""


													return [
													    list(np.array(self.__maximum_claim_table[i]				) - np.array(lowerCamelCase__				)				)
													    for i, allocated_resource in enumerate(self.__allocated_resources_table				)
													]






						def     UpperCAmelCase_      ( self :     Tuple				)    ->						dict[int, list[int]]:
													"""simple docstring"""


													return {self.__need().index(lowerCamelCase__				): i for i in self.__need()}






						def     UpperCAmelCase_      ( self :     Optional[int]				,							**lowerCamelCase__ :     Any				)    ->						None:
													"""simple docstring"""


													__lowercase      =    self.__need()
													__lowercase      =    self.__allocated_resources_table
													__lowercase      =    self.__available_resources()
													__lowercase      =    self.__need_index_manager()
													for kw, val in kwargs.items():
																				if kw and val is True:
																											self.__pretty_data()
													print('''_''' * 50 + '''\n'''				)
													while need_list:
																				__lowercase      =    False
																				for each_need in need_list:
																											__lowercase      =    True
																											for index, need in enumerate(lowerCamelCase__				):
																																		if need > available_resources[index]:
																																									__lowercase      =    False
																																									break
																											if execution:
																																		__lowercase      =    True
																																		# get the original index of the process from ind_ctrl db
																																		for original_need_index, need_clone in need_index_manager.items():
																																									if each_need == need_clone:
																																																__lowercase      =    original_need_index
																																		print(f'Process {process_number + 1} is executing.'				)
																																		# remove the process run from stack
																																		need_list.remove(lowerCamelCase__				)
																																		# update available/freed resources stack
																																		__lowercase      =    np.array(lowerCamelCase__				) + np.array(
																																		    alloc_resources_table[process_number]				)
																																		print(
																																		    '''Updated available resource stack for processes: '''
																																		    + ''' '''.join([str(lowerCamelCase__				) for x in available_resources]				)				)
																																		break
																				if safe:
																											print('''The process is in a safe state.\n'''				)
																				else:
																											print('''System in unsafe state. Aborting...\n'''				)
																											break






						def     UpperCAmelCase_      ( self :     List[Any]				)    ->						Any:
													"""simple docstring"""


													print(''' ''' * 9 + '''Allocated Resource Table'''				)
													for item in self.__allocated_resources_table:
																				print(
																				    f'P{self.__allocated_resources_table.index(lowerCamelCase__				) + 1}'
																				    + ''' '''.join(f'{it:>8}' for it in item				)
																				    + '''\n'''				)
													print(''' ''' * 9 + '''System Resource Table'''				)
													for item in self.__maximum_claim_table:
																				print(
																				    f'P{self.__maximum_claim_table.index(lowerCamelCase__				) + 1}'
																				    + ''' '''.join(f'{it:>8}' for it in item				)
																				    + '''\n'''				)
													print(
													    '''Current Usage by Active Processes: '''
													    + ''' '''.join(str(lowerCamelCase__				) for x in self.__claim_vector				)				)
													print(
													    '''Initial Available Resources:       '''
													    + ''' '''.join(str(lowerCamelCase__				) for x in self.__available_resources()				)				)
													time.sleep(1				)


if __name__ == "__main__":
			import doctest

			doctest.testmod()












import argparse
import copy







def 		_A(       UpperCamelCase__							:			Union[str, Any]				)    -> Tuple:
							'''simple docstring'''


							__lowercase      =    {}

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

							return dict_of_neighbours







def 		_A(       UpperCamelCase__							:			Optional[int]				,       UpperCamelCase__							:			Optional[Any]				)    -> Dict:
							'''simple docstring'''


							with open(UpperCamelCase__				) as f:
														__lowercase      =    f.read(1				)
							__lowercase      =    start_node

							__lowercase      =    []

							__lowercase      =    start_node

							__lowercase      =    0
							while visiting not in first_solution:
														__lowercase      =    1_0000
														for k in dict_of_neighbours[visiting]:
																					if int(k[1]				) < int(UpperCamelCase__				) and k[0] not in first_solution:
																												__lowercase      =    k[1]
																												__lowercase      =    k[0]

														first_solution.append(UpperCamelCase__				)
														__lowercase      =    distance_of_first_solution + int(UpperCamelCase__				)
														__lowercase      =    best_node

							first_solution.append(UpperCamelCase__				)

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

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







def 		_A(       UpperCamelCase__							:			int				,       UpperCamelCase__							:			Optional[Any]				)    -> Optional[int]:
							'''simple docstring'''


							__lowercase      =    []

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

																					__lowercase      =    copy.deepcopy(UpperCamelCase__				)
																					__lowercase      =    kn
																					__lowercase      =    n

																					__lowercase      =    0

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

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

							__lowercase      =    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 		_A(       UpperCamelCase__							:			List[Any]				,       UpperCamelCase__							:			List[str]				,       UpperCamelCase__							:			Optional[int]				,       UpperCamelCase__							:			Optional[int]				,       UpperCamelCase__							:			Optional[int]				)    -> List[str]:
							'''simple docstring'''


							__lowercase      =    1
							__lowercase      =    first_solution
							__lowercase      =    []
							__lowercase      =    distance_of_first_solution
							__lowercase      =    solution

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

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

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

														__lowercase      =    count + 1

							return best_solution_ever, best_cost







def 		_A(       UpperCamelCase__							:			List[Any]=None				)    -> int:
							'''simple docstring'''


							__lowercase      =    generate_neighbours(args.File				)

							__lowercase     ,     __lowercase      =    generate_first_solution(
							    args.File				,       UpperCamelCase__				)

							__lowercase     ,     __lowercase      =    tabu_search(
							    UpperCamelCase__				,       UpperCamelCase__				,       UpperCamelCase__				,       args.Iterations				,       args.Size				,       )

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


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






