

'''simple docstring'''





import collections
import importlib.util
import os
import re
from pathlib import Path


UpperCamelCase_							=					"""src/transformers"""


# Matches is_xxx_available()
UpperCamelCase_							=					re.compile(r"""is\_([a-z_]*)_available()""")
# Catches a one-line _import_struct = {xxx}
UpperCamelCase_							=					re.compile(r"""^_import_structure\s+=\s+\{([^\}]+)\}""")
# Catches a line with a key-values pattern: "bla": ["foo", "bar"]
UpperCamelCase_							=					re.compile(r"""\s+\"\S*\":\s+\[([^\]]*)\]""")
# Catches a line if not is_foo_available
UpperCamelCase_							=					re.compile(r"""^\s*if\s+not\s+is\_[a-z_]*\_available\(\)""")
# Catches a line _import_struct["bla"].append("foo")
UpperCamelCase_							=					re.compile(r"""^\s*_import_structure\[\"\S*\"\]\.append\(\"(\S*)\"\)""")
# Catches a line _import_struct["bla"].extend(["foo", "bar"]) or _import_struct["bla"] = ["foo", "bar"]
UpperCamelCase_							=					re.compile(r"""^\s*_import_structure\[\S*\](?:\.extend\(|\s*=\s+)\[([^\]]*)\]""")
# Catches a line with an object between quotes and a comma:     "MyModel",
UpperCamelCase_							=					re.compile("""^\s+\"([^\"]+)\",""")
# Catches a line with objects between brackets only:    ["foo", "bar"],
UpperCamelCase_							=					re.compile("""^\s+\[([^\]]+)\]""")
# Catches a line with from foo import bar, bla, boo
UpperCamelCase_							=					re.compile(r"""\s+from\s+\S*\s+import\s+([^\(\s].*)\n""")
# Catches a line with try:
UpperCamelCase_							=					re.compile(r"""^\s*try:""")
# Catches a line with else:
UpperCamelCase_							=					re.compile(r"""^\s*else:""")






def 							_lowerCAmelCase (      __magic_name__	:    int	)							->     str:
						if _re_test_backend.search(_snake_case	) is None:
												return None
						lowercase   :       List[Any]								=[b[0] for b in _re_backend.findall(_snake_case	)]
						backends.sort()
						return "_and_".join(_snake_case	)






def 							_lowerCAmelCase (      __magic_name__	:    Dict	)							->     Optional[int]:
						with open(_snake_case      ,   '''r'''      ,   encoding='''utf-8'''      ,   newline='''\n'''	) as f:
												lowercase   :       List[Any]								=f.readlines()

						lowercase   :       Optional[int]								=0
						while line_index < len(_snake_case	) and not lines[line_index].startswith('''_import_structure = {'''	):
												line_index += 1

						# If this is a traditional init, just return.
						if line_index >= len(_snake_case	):
												return None

						# First grab the objects without a specific backend in _import_structure
						lowercase   :       str								=[]
						while not lines[line_index].startswith('''if TYPE_CHECKING'''	) and find_backend(lines[line_index]	) is None:
												lowercase   :       int								=lines[line_index]
												# If we have everything on a single line, let's deal with it.
												if _re_one_line_import_struct.search(_snake_case	):
																		lowercase   :       Optional[Any]								=_re_one_line_import_struct.search(_snake_case	).groups()[0]
																		lowercase   :       Any								=re.findall('''\[([^\]]+)\]'''      ,   _snake_case	)
																		for imp in imports:
																								objects.extend([obj[1:-1] for obj in imp.split(''', '''	)]	)
																		line_index += 1
																		continue
												lowercase   :       List[str]								=_re_import_struct_key_value.search(_snake_case	)
												if single_line_import_search is not None:
																		lowercase   :       Union[str, Any]								=[obj[1:-1] for obj in single_line_import_search.groups()[0].split(''', '''	) if len(_snake_case	) > 0]
																		objects.extend(_snake_case	)
												elif line.startswith(''' ''' * 8 + '''"'''	):
																		objects.append(line[9:-3]	)
												line_index += 1

						lowercase   :       List[str]								={'''none''': objects}
						# Let's continue with backend-specific objects in _import_structure
						while not lines[line_index].startswith('''if TYPE_CHECKING'''	):
												# If the line is an if not is_backend_available, we grab all objects associated.
												lowercase   :       List[Any]								=find_backend(lines[line_index]	)
												# Check if the backend declaration is inside a try block:
												if _re_try.search(lines[line_index - 1]	) is None:
																		lowercase   :       Optional[int]								=None

												if backend is not None:
																		line_index += 1

																		# Scroll until we hit the else block of try-except-else
																		while _re_else.search(lines[line_index]	) is None:
																								line_index += 1

																		line_index += 1

																		lowercase   :       Optional[int]								=[]
																		# Until we unindent, add backend objects to the list
																		while len(lines[line_index]	) <= 1 or lines[line_index].startswith(''' ''' * 4	):
																								lowercase   :       List[Any]								=lines[line_index]
																								if _re_import_struct_add_one.search(_snake_case	) is not None:
																														objects.append(_re_import_struct_add_one.search(_snake_case	).groups()[0]	)
																								elif _re_import_struct_add_many.search(_snake_case	) is not None:
																														lowercase   :       str								=_re_import_struct_add_many.search(_snake_case	).groups()[0].split(''', '''	)
																														lowercase   :       Dict								=[obj[1:-1] for obj in imports if len(_snake_case	) > 0]
																														objects.extend(_snake_case	)
																								elif _re_between_brackets.search(_snake_case	) is not None:
																														lowercase   :       Union[str, Any]								=_re_between_brackets.search(_snake_case	).groups()[0].split(''', '''	)
																														lowercase   :       List[Any]								=[obj[1:-1] for obj in imports if len(_snake_case	) > 0]
																														objects.extend(_snake_case	)
																								elif _re_quote_object.search(_snake_case	) is not None:
																														objects.append(_re_quote_object.search(_snake_case	).groups()[0]	)
																								elif line.startswith(''' ''' * 8 + '''"'''	):
																														objects.append(line[9:-3]	)
																								elif line.startswith(''' ''' * 12 + '''"'''	):
																														objects.append(line[13:-3]	)
																								line_index += 1

																		lowercase   :       Tuple								=objects
												else:
																		line_index += 1

    # At this stage we are in the TYPE_CHECKING part, first grab the objects without a specific backend
						lowercase   :       str								=[]
						while (
						    line_index < len(_snake_case	)
						    and find_backend(lines[line_index]	) is None
						    and not lines[line_index].startswith('''else'''	)
						):
												lowercase   :       Any								=lines[line_index]
												lowercase   :       Optional[int]								=_re_import.search(_snake_case	)
												if single_line_import_search is not None:
																		objects.extend(single_line_import_search.groups()[0].split(''', '''	)	)
												elif line.startswith(''' ''' * 8	):
																		objects.append(line[8:-2]	)
												line_index += 1

						lowercase   :       Dict								={'''none''': objects}
						# Let's continue with backend-specific objects
						while line_index < len(_snake_case	):
												# If the line is an if is_backend_available, we grab all objects associated.
												lowercase   :       Union[str, Any]								=find_backend(lines[line_index]	)
												# Check if the backend declaration is inside a try block:
												if _re_try.search(lines[line_index - 1]	) is None:
																		lowercase   :       List[str]								=None

												if backend is not None:
																		line_index += 1

																		# Scroll until we hit the else block of try-except-else
																		while _re_else.search(lines[line_index]	) is None:
																								line_index += 1

																		line_index += 1

																		lowercase   :       Union[str, Any]								=[]
																		# Until we unindent, add backend objects to the list
																		while len(lines[line_index]	) <= 1 or lines[line_index].startswith(''' ''' * 8	):
																								lowercase   :       Optional[Any]								=lines[line_index]
																								lowercase   :       int								=_re_import.search(_snake_case	)
																								if single_line_import_search is not None:
																														objects.extend(single_line_import_search.groups()[0].split(''', '''	)	)
																								elif line.startswith(''' ''' * 12	):
																														objects.append(line[12:-2]	)
																								line_index += 1

																		lowercase   :       str								=objects
												else:
																		line_index += 1

						return import_dict_objects, type_hint_objects






def 							_lowerCAmelCase (      __magic_name__	:    str      ,   __magic_name__	:    str	)							->     List[str]:

						def find_duplicates(__magic_name__	:    Optional[Any]	):
												return [k for k, v in collections.Counter(_snake_case	).items() if v > 1]

						if list(import_dict_objects.keys()	) != list(type_hint_objects.keys()	):
												return ["Both sides of the init do not have the same backends!"]

						lowercase   :       List[Any]								=[]
						for key in import_dict_objects.keys():
												lowercase   :       int								=find_duplicates(import_dict_objects[key]	)
												if duplicate_imports:
																		errors.append(f'''Duplicate _import_structure definitions for: {duplicate_imports}'''	)
												lowercase   :       str								=find_duplicates(type_hint_objects[key]	)
												if duplicate_type_hints:
																		errors.append(f'''Duplicate TYPE_CHECKING objects for: {duplicate_type_hints}'''	)

												if sorted(set(import_dict_objects[key]	)	) != sorted(set(type_hint_objects[key]	)	):
																		lowercase   :       List[str]								='''base imports''' if key == '''none''' else f'''{key} backend'''
																		errors.append(f'''Differences for {name}:'''	)
																		for a in type_hint_objects[key]:
																								if a not in import_dict_objects[key]:
																														errors.append(f'''  {a} in TYPE_HINT but not in _import_structure.'''	)
																		for a in import_dict_objects[key]:
																								if a not in type_hint_objects[key]:
																														errors.append(f'''  {a} in _import_structure but not in TYPE_HINT.'''	)
						return errors






def 							_lowerCAmelCase (      )							->     List[str]:
						lowercase   :       int								=[]
						for root, _, files in os.walk(_snake_case	):
												if "__init__.py" in files:
																		lowercase   :       List[Any]								=os.path.join(_snake_case      ,   '''__init__.py'''	)
																		lowercase   :       Any								=parse_init(_snake_case	)
																		if objects is not None:
																								lowercase   :       Dict								=analyze_results(*_snake_case	)
																								if len(_snake_case	) > 0:
																														lowercase   :       Any								=f'''Problem in {fname}, both halves do not define the same objects.\n{errors[0]}'''
																														failures.append('''\n'''.join(_snake_case	)	)
						if len(_snake_case	) > 0:
												raise ValueError('''\n\n'''.join(_snake_case	)	)






def 							_lowerCAmelCase (      )							->     Any:
						lowercase   :       str								=[]
						for path, directories, files in os.walk(_snake_case	):
												for folder in directories:
																		# Ignore private modules
																		if folder.startswith('''_'''	):
																								directories.remove(_snake_case	)
																								continue
																		# Ignore leftovers from branches (empty folders apart from pycache)
																		if len(list((Path(_snake_case	) / folder).glob('''*.py'''	)	)	) == 0:
																								continue
																		lowercase   :       Optional[int]								=str((Path(_snake_case	) / folder).relative_to(_snake_case	)	)
																		lowercase   :       str								=short_path.replace(os.path.sep      ,   '''.'''	)
																		submodules.append(_snake_case	)
												for fname in files:
																		if fname == "__init__.py":
																								continue
																		lowercase   :       Any								=str((Path(_snake_case	) / fname).relative_to(_snake_case	)	)
																		lowercase   :       Optional[int]								=short_path.replace('''.py'''      ,   ''''''	).replace(os.path.sep      ,   '''.'''	)
																		if len(submodule.split('''.'''	)	) == 1:
																								submodules.append(_snake_case	)
						return submodules


UpperCamelCase_							=					[
    """convert_pytorch_checkpoint_to_tf2""",
    """modeling_flax_pytorch_utils""",
]






def 							_lowerCAmelCase (      )							->     str:
						# This is to make sure the transformers module imported is the one in the repo.
						lowercase   :       Union[str, Any]								=importlib.util.spec_from_file_location(
						    '''transformers'''      ,   os.path.join(_snake_case      ,   '''__init__.py'''	)      ,   submodule_search_locations=[PATH_TO_TRANSFORMERS]      ,   )
						lowercase   :       Any								=spec.loader.load_module()

						lowercase   :       List[str]								=[
						    module
						    for module in get_transformers_submodules()
						    if module not in IGNORE_SUBMODULES and module not in transformers._import_structure.keys()
						]
						if len(_snake_case	) > 0:
												lowercase   :       Tuple								='''\n'''.join(f'''- {module}''' for module in module_not_registered	)
												raise ValueError(
												    '''The following submodules are not properly registered in the main init of Transformers:\n'''
												    f'''{list_of_modules}\n'''
												    '''Make sure they appear somewhere in the keys of `_import_structure` with an empty list as value.'''	)


if __name__ == "__main__":
							check_all_inits()
							check_submodules()








'''simple docstring'''





import argparse
import copy






def 							_lowerCAmelCase (      __magic_name__	:    List[str]	)							->     Union[str, Any]:
						lowercase   :       int								={}

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

						return dict_of_neighbours






def 							_lowerCAmelCase (      __magic_name__	:    Optional[int]      ,   __magic_name__	:    List[Any]	)							->     str:

						with open(__magic_name__	) as f:
												lowercase   :       Optional[int]								=f.read(1	)
						lowercase   :       List[Any]								=start_node

						lowercase   :       List[Any]								=[]

						lowercase   :       str								=start_node

						lowercase   :       str								=0
						while visiting not in first_solution:
												lowercase   :       Optional[int]								=10000
												for k in dict_of_neighbours[visiting]:
																		if int(k[1]	) < int(__magic_name__	) and k[0] not in first_solution:
																								lowercase   :       List[Any]								=k[1]
																								lowercase   :       str								=k[0]

												first_solution.append(__magic_name__	)
												lowercase   :       Any								=distance_of_first_solution + int(__magic_name__	)
												lowercase   :       Optional[int]								=best_node

						first_solution.append(__magic_name__	)

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

						lowercase   :       str								=(
						    distance_of_first_solution
						    + int(dict_of_neighbours[first_solution[-2]][position][1]	)
						    - 10000
						)
						return first_solution, distance_of_first_solution






def 							_lowerCAmelCase (      __magic_name__	:    str      ,   __magic_name__	:    Any	)							->     Tuple:
						lowercase   :       Tuple								=[]

						for n in solution[1:-1]:
												lowercase   :       Dict								=solution.index(__magic_name__	)
												for kn in solution[1:-1]:
																		lowercase   :       Tuple								=solution.index(__magic_name__	)
																		if n == kn:
																								continue

																		lowercase   :       Union[str, Any]								=copy.deepcopy(__magic_name__	)
																		lowercase   :       Optional[int]								=kn
																		lowercase   :       List[Any]								=n

																		lowercase   :       List[Any]								=0

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

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

						lowercase   :       Union[str, Any]								=len(neighborhood_of_solution[0]	) - 1

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






def 							_lowerCAmelCase (      __magic_name__	:    Any      ,   __magic_name__	:    str      ,   __magic_name__	:    List[Any]      ,   __magic_name__	:    Tuple      ,   __magic_name__	:    Dict	)							->     Union[str, Any]:
						lowercase   :       str								=1
						lowercase   :       List[Any]								=first_solution
						lowercase   :       Any								=[]
						lowercase   :       str								=distance_of_first_solution
						lowercase   :       str								=solution

						while count <= iters:
												lowercase   :       Union[str, Any]								=find_neighborhood(__magic_name__      ,   __magic_name__	)
												lowercase   :       Dict								=0
												lowercase   :       int								=neighborhood[index_of_best_solution]
												lowercase   :       Optional[int]								=len(__magic_name__	) - 1

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

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

												lowercase   :       Optional[int]								=count + 1

						return best_solution_ever, best_cost






def 							_lowerCAmelCase (      __magic_name__	:    str=None	)							->     Tuple:
						lowercase   :       List[str]								=generate_neighbours(args.File	)

						lowercase		,  lowercase   :       Optional[Any]								=generate_first_solution(
						    args.File      ,   __magic_name__	)

						lowercase		,  lowercase   :       int								=tabu_search(
						    __magic_name__      ,   __magic_name__      ,   __magic_name__      ,   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())





