



"""simple docstring"""

import argparse
import hashlib  # hashlib is only used inside the Test class
import struct







class    __lowercase     :







						"""simple docstring"""







						def __init__(self   ,		lowercase__       ):
											snake_case_					:		Union[str, Any] 					=					data
											snake_case_					:		List[str] 					=					[0X6_7_4_5_2_3_0_1, 0Xe_f_c_d_a_b_8_9, 0X9_8_b_a_d_c_f_e, 0X1_0_3_2_5_4_7_6, 0Xc_3_d_2_e_1_f_0]







						@staticmethod
						def 						__UpperCamelCase							(lowercase__   ,		lowercase__       ):
											return ((n << b) | (n >> (32 - b))) & 0Xf_f_f_f_f_f_f_f







						def 						__UpperCamelCase							(self       ):
											snake_case_					:		Any 					=					B"""\x80""" + B"""\x00""" * (63 - (len(self.data       ) + 8) % 64)
											snake_case_					:		Tuple 					=					self.data + padding + struct.pack(""">Q"""   ,		8 * len(self.data       )       )
											return padded_data







						def 						__UpperCamelCase							(self       ):
											return [
											    self.padded_data[i : i + 64] for i in range(0   ,		len(self.padded_data       )   ,		64       )
											]







						def 						__UpperCamelCase							(self   ,		lowercase__       ):
											snake_case_					:		int 					=					list(struct.unpack(""">16L"""   ,		lowercase__       )       ) + [0] * 64
											for i in range(16   ,		80       ):
																snake_case_					:		Dict 					=					self.rotate((w[i - 3] ^ w[i - 8] ^ w[i - 14] ^ w[i - 16])   ,		1       )
											return w







						def 						__UpperCamelCase							(self       ):
											snake_case_					:		List[Any] 					=					self.padding()
											snake_case_					:		Any 					=					self.split_blocks()
											for block in self.blocks:
																snake_case_					:		Any 					=					self.expand_block(lowercase__       )
																snake_case_					:		List[Any] 					=					self.h
																for i in range(0   ,		80       ):
																					if 0 <= i < 20:
																										snake_case_					:		Optional[Any] 					=					(b & c) | ((~b) & d)
																										snake_case_					:		List[str] 					=					0X5_a_8_2_7_9_9_9
																					elif 20 <= i < 40:
																										snake_case_					:		Union[str, Any] 					=					b ^ c ^ d
																										snake_case_					:		Tuple 					=					0X6_e_d_9_e_b_a_1
																					elif 40 <= i < 60:
																										snake_case_					:		str 					=					(b & c) | (b & d) | (c & d)
																										snake_case_					:		List[str] 					=					0X8_f_1_b_b_c_d_c
																					elif 60 <= i < 80:
																										snake_case_					:		Tuple 					=					b ^ c ^ d
																										snake_case_					:		str 					=					0Xc_a_6_2_c_1_d_6
																					snake_case_					:		Optional[Any] 					=					(
																					    self.rotate(lowercase__   ,		5       ) + f + e + k + expanded_block[i] & 0Xf_f_f_f_f_f_f_f,
																					    a,
																					    self.rotate(lowercase__   ,		30       ),
																					    c,
																					    d,
																					)
																snake_case_					:		Any 					=					(
																    self.h[0] + a & 0Xf_f_f_f_f_f_f_f,
																    self.h[1] + b & 0Xf_f_f_f_f_f_f_f,
																    self.h[2] + c & 0Xf_f_f_f_f_f_f_f,
																    self.h[3] + d & 0Xf_f_f_f_f_f_f_f,
																    self.h[4] + e & 0Xf_f_f_f_f_f_f_f,
																)
											return ("{:08x}" * 5).format(*self.h       )







def 							SCREAMING_SNAKE_CASE__      (		):



					"""simple docstring"""





					snake_case_					:		Union[str, Any] 					=					b"""Test String"""
					assert SHAaHash(SCREAMING_SNAKE_CASE__			).final_hash() == hashlib.shaa(SCREAMING_SNAKE_CASE__			).hexdigest()  # noqa: S324







def 							SCREAMING_SNAKE_CASE__      (		):



					"""simple docstring"""





					snake_case_					:		int 					=					argparse.ArgumentParser(description="""Process some strings or files"""			)
					parser.add_argument(
					    """--string"""				,    dest="""input_string"""				,    default="""Hello World!! Welcome to Cryptography"""				,    help="""Hash the string"""				,    )
					parser.add_argument("""--file"""				,    dest="""input_file"""				,    help="""Hash contents of a file"""			)
					snake_case_					:		Optional[int] 					=					parser.parse_args()
					snake_case_					:		Optional[int] 					=					args.input_string
					# In any case hash input should be a bytestring
					if args.input_file:
										with open(args.input_file				,    """rb"""			) as f:
															snake_case_					:		List[str] 					=					f.read()
					else:
										snake_case_					:		Dict 					=					bytes(SCREAMING_SNAKE_CASE__				,    """utf-8"""			)
					print(SHAaHash(SCREAMING_SNAKE_CASE__			).final_hash()			)


if __name__ == "__main__":
			main()
			import doctest

			doctest.testmod()









"""simple docstring"""

import argparse
import copy







def 							SCREAMING_SNAKE_CASE__      (		SCREAMING_SNAKE_CASE__ :  Any			):



					"""simple docstring"""





					snake_case_					:		List[Any] 					=					{}

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

					return dict_of_neighbours







def 							SCREAMING_SNAKE_CASE__      (		SCREAMING_SNAKE_CASE__ :  List[Any]				,    SCREAMING_SNAKE_CASE__ :  str			):



					"""simple docstring"""





					with open(SCREAMING_SNAKE_CASE__			) as f:
										snake_case_					:		Optional[Any] 					=					f.read(1			)
					snake_case_					:		Union[str, Any] 					=					start_node

					snake_case_					:		Dict 					=					[]

					snake_case_					:		Union[str, Any] 					=					start_node

					snake_case_					:		Tuple 					=					0
					while visiting not in first_solution:
										snake_case_					:		int 					=					1_0_0_0_0
										for k in dict_of_neighbours[visiting]:
															if int(k[1]			) < int(SCREAMING_SNAKE_CASE__			) and k[0] not in first_solution:
																				snake_case_					:		Union[str, Any] 					=					k[1]
																				snake_case_					:		Any 					=					k[0]

										first_solution.append(SCREAMING_SNAKE_CASE__			)
										snake_case_					:		Tuple 					=					distance_of_first_solution + int(SCREAMING_SNAKE_CASE__			)
										snake_case_					:		List[str] 					=					best_node

					first_solution.append(SCREAMING_SNAKE_CASE__			)

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

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







def 							SCREAMING_SNAKE_CASE__      (		SCREAMING_SNAKE_CASE__ :  Union[str, Any]				,    SCREAMING_SNAKE_CASE__ :  Optional[int]			):



					"""simple docstring"""





					snake_case_					:		Union[str, Any] 					=					[]

					for n in solution[1:-1]:
										snake_case_					:		str 					=					solution.index(SCREAMING_SNAKE_CASE__			)
										for kn in solution[1:-1]:
															snake_case_					:		Tuple 					=					solution.index(SCREAMING_SNAKE_CASE__			)
															if n == kn:
																				continue

															snake_case_					:		Optional[Any] 					=					copy.deepcopy(SCREAMING_SNAKE_CASE__			)
															snake_case_					:		int 					=					kn
															snake_case_					:		Dict 					=					n

															snake_case_					:		Optional[int] 					=					0

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

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

					snake_case_					:		Optional[Any] 					=					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 							SCREAMING_SNAKE_CASE__      (		SCREAMING_SNAKE_CASE__ :  List[str]				,    SCREAMING_SNAKE_CASE__ :  Dict				,    SCREAMING_SNAKE_CASE__ :  List[Any]				,    SCREAMING_SNAKE_CASE__ :  str				,    SCREAMING_SNAKE_CASE__ :  List[Any]			):



					"""simple docstring"""





					snake_case_					:		Dict 					=					1
					snake_case_					:		List[Any] 					=					first_solution
					snake_case_					:		List[Any] 					=					[]
					snake_case_					:		Optional[Any] 					=					distance_of_first_solution
					snake_case_					:		Dict 					=					solution

					while count <= iters:
										snake_case_					:		List[str] 					=					find_neighborhood(SCREAMING_SNAKE_CASE__				,    SCREAMING_SNAKE_CASE__			)
										snake_case_					:		List[Any] 					=					0
										snake_case_					:		List[Any] 					=					neighborhood[index_of_best_solution]
										snake_case_					:		Union[str, Any] 					=					len(SCREAMING_SNAKE_CASE__			) - 1

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

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

										snake_case_					:		List[str] 					=					count + 1

					return best_solution_ever, best_cost







def 							SCREAMING_SNAKE_CASE__      (		SCREAMING_SNAKE_CASE__ :  Optional[Any]=None			):



					"""simple docstring"""





					snake_case_					:		Tuple 					=					generate_neighbours(args.File			)

					snake_case_					,			snake_case_					:		Optional[Any] 					=					generate_first_solution(
					    args.File				,    SCREAMING_SNAKE_CASE__			)

					snake_case_					,			snake_case_					:		Dict 					=					tabu_search(
					    SCREAMING_SNAKE_CASE__				,    SCREAMING_SNAKE_CASE__				,    SCREAMING_SNAKE_CASE__				,    args.Iterations				,    args.Size				,    )

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


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




