'''simple docstring'''


import collections
import json
import math
import os
import re
import time
from fnmatch import fnmatch
from typing import Dict

import requests
from slack_sdk import WebClient


__lowerCAmelCase	:       List[str]						       =	WebClient(token=os.environ["CI_SLACK_BOT_TOKEN"])





def       lowerCAmelCase					(		UpperCamelCase__				:   Tuple       ):


	"""simple docstring"""
	__UpperCAmelCase							=			test_results.split(''' '''       )

	__UpperCAmelCase							=			0
	__UpperCAmelCase							=			0

	# When the output is short enough, the output is surrounded by = signs: "== OUTPUT =="
	# When it is too long, those signs are not present.
	__UpperCAmelCase							=			expressions[-2] if '''=''' in expressions[-1] else expressions[-1]

	for i, expression in enumerate(UpperCamelCase__       ):
		if "failed" in expression:
			failed += int(expressions[i - 1]       )
		if "passed" in expression:
			success += int(expressions[i - 1]       )

	return failed, success, time_spent





def       lowerCAmelCase					(		UpperCamelCase__				:   str       ):


	"""simple docstring"""
	__UpperCAmelCase							=			{}
	__UpperCAmelCase							=			None
	__UpperCAmelCase							=			False
	for line in failures_short_lines.split('''\n'''       ):
		if re.search(R'''_ \[doctest\]'''    ,					UpperCamelCase__       ):
			__UpperCAmelCase							=			True
			__UpperCAmelCase							=			line.split(''' '''       )[2]
		elif in_error and not line.split(''' '''       )[0].isdigit():
			__UpperCAmelCase							=			line
			__UpperCAmelCase							=			False

	return failures






class 						A   :





							def __init__(      self				:							Union[str, Any]     ,		__a				:							str     ,		__a				:							Dict	)							->	str:
								__UpperCAmelCase							=			title

								__UpperCAmelCase							=			doc_test_results['''time_spent'''].split(''','''	)[0]
								__UpperCAmelCase							=			doc_test_results['''success''']
								__UpperCAmelCase							=			doc_test_results['''failures''']
								__UpperCAmelCase							=			self.n_success + self.n_failures

								# Failures and success of the modeling tests
								__UpperCAmelCase							=			doc_test_results





							@property
							def       snake_case__						(      self				:							Optional[int]	)							->	str:
								__UpperCAmelCase							=			[self._time_spent]
								__UpperCAmelCase							=			0

								for time in time_spent:
									__UpperCAmelCase							=			time.split(''':'''	)

									# Time can be formatted as xx:xx:xx, as .xx, or as x.xx if the time spent was less than a minute.
									if len(__a	) == 1:
										__UpperCAmelCase							=			[0, 0, time_parts[0]]

									__UpperCAmelCase				,			__UpperCAmelCase				,			__UpperCAmelCase							=			int(time_parts[0]	), int(time_parts[1]	), float(time_parts[2]	)
									total_secs += hours * 3_6_0_0 + minutes * 6_0 + seconds

								__UpperCAmelCase				,			__UpperCAmelCase				,			__UpperCAmelCase							=			total_secs // 3_6_0_0, (total_secs % 3_6_0_0) // 6_0, total_secs % 6_0
								return f"""{int(__a	)}h{int(__a	)}m{int(__a	)}s"""





							@property
							def       snake_case__						(      self				:							Optional[int]	)							->	Dict:
								return {"type": "header", "text": {"type": "plain_text", "text": self.title}}





							@property
							def       snake_case__						(      self				:							List[str]	)							->	Dict:
								return {
								    "type": "section",
								    "text": {
								        "type": "plain_text",
								        "text": f"""🌞 There were no failures: all {self.n_tests} tests passed. The suite ran in {self.time}.""",
								        "emoji": True,
								    },
								    "accessory": {
								        "type": "button",
								        "text": {"type": "plain_text", "text": "Check Action results", "emoji": True},
								        "url": f"""https://github.com/huggingface/transformers/actions/runs/{os.environ['GITHUB_RUN_ID']}""",
								    },
								}





							@property
							def       snake_case__						(      self				:							int	)							->	Dict:
								return {
								    "type": "section",
								    "text": {
								        "type": "plain_text",
								        "text": (
								            f"""There were {self.n_failures} failures, out of {self.n_tests} tests.\nThe suite ran in"""
								            f""" {self.time}."""
								        ),
								        "emoji": True,
								    },
								    "accessory": {
								        "type": "button",
								        "text": {"type": "plain_text", "text": "Check Action results", "emoji": True},
								        "url": f"""https://github.com/huggingface/transformers/actions/runs/{os.environ['GITHUB_RUN_ID']}""",
								    },
								}





							@property
							def       snake_case__						(      self				:							Optional[int]	)							->	Dict:
								__UpperCAmelCase							=			4_0
								__UpperCAmelCase							=			{k: v['''failed'''] for k, v in doc_test_results.items() if isinstance(__a     ,		__a	)}

								__UpperCAmelCase							=			''''''
								for category, failures in category_failures.items():
									if len(__a	) == 0:
										continue

									if report != "":
										report += "\n\n"

									report += f"""*{category} failures*:""".ljust(line_length // 2	).rjust(line_length // 2	) + "\n"
									report += "`"
									report += "`\n`".join(__a	)
									report += "`"

								return {
								    "type": "section",
								    "text": {
								        "type": "mrkdwn",
								        "text": f"""The following examples had failures:\n\n\n{report}\n""",
								    },
								}





							@property
							def       snake_case__						(      self				:							str	)							->	str:
								__UpperCAmelCase							=			[self.header]

								if self.n_failures > 0:
									blocks.append(self.failures	)

								if self.n_failures > 0:
									blocks.extend([self.category_failures]	)

								if self.n_failures == 0:
									blocks.append(self.no_failures	)

								return json.dumps(__a	)





							@staticmethod
							def       snake_case__						(      )							->	Dict:
								__UpperCAmelCase							=			[
								    {
								        '''type''': '''section''',
								        '''text''': {
								            '''type''': '''plain_text''',
								            '''text''': '''There was an issue running the tests.''',
								        },
								        '''accessory''': {
								            '''type''': '''button''',
								            '''text''': {'''type''': '''plain_text''', '''text''': '''Check Action results''', '''emoji''': True},
								            '''url''': f"""https://github.com/huggingface/transformers/actions/runs/{os.environ['GITHUB_RUN_ID']}""",
								        },
								    }
								]

								print('''Sending the following payload'''	)
								print(json.dumps({'''blocks''': json.loads(__a	)}	)	)

								client.chat_postMessage(
								    channel=os.environ['''CI_SLACK_CHANNEL_ID_DAILY''']     ,		text='''There was an issue running the tests.'''     ,		blocks=__a     ,		)





							def       snake_case__						(      self				:							int	)							->	Union[str, Any]:
								print('''Sending the following payload'''	)
								print(json.dumps({'''blocks''': json.loads(self.payload	)}	)	)

								__UpperCAmelCase							=			f"""{self.n_failures} failures out of {self.n_tests} tests,""" if self.n_failures else '''All tests passed.'''

								__UpperCAmelCase							=			client.chat_postMessage(
								    channel=os.environ['''CI_SLACK_CHANNEL_ID_DAILY''']     ,		blocks=self.payload     ,		text=__a     ,		)





							def       snake_case__						(      self				:							Tuple     ,		__a				:							Optional[Any]     ,		__a				:							Union[str, Any]     ,		__a				:							str     ,		__a				:							List[Any]	)							->	Tuple:
								__UpperCAmelCase							=			''''''
								for key, value in failures.items():
									__UpperCAmelCase							=			value[:2_0_0] + ''' [Truncated]''' if len(__a	) > 2_5_0 else value
									failures_text += f"""*{key}*\n_{value}_\n\n"""

								__UpperCAmelCase							=			job_name
								__UpperCAmelCase							=			{'''type''': '''section''', '''text''': {'''type''': '''mrkdwn''', '''text''': text}}

								if job_link is not None:
									__UpperCAmelCase							=			{
									    '''type''': '''button''',
									    '''text''': {'''type''': '''plain_text''', '''text''': '''GitHub Action job''', '''emoji''': True},
									    '''url''': job_link,
									}

								return [
								    {"type": "header", "text": {"type": "plain_text", "text": title.upper(), "emoji": True}},
								    content,
								    {"type": "section", "text": {"type": "mrkdwn", "text": failures_text}},
								]






							def       snake_case__						(      self				:							str	)							->	List[str]:
								if self.thread_ts is None:
									raise ValueError('''Can only post reply if a post has been made.'''	)

								__UpperCAmelCase							=			self.doc_test_results.pop('''job_link'''	)
								self.doc_test_results.pop('''failures'''	)
								self.doc_test_results.pop('''success'''	)
								self.doc_test_results.pop('''time_spent'''	)

								__UpperCAmelCase							=			sorted(self.doc_test_results.items()     ,		key=lambda __a	: t[0]	)
								for job, job_result in sorted_dict:
									if len(job_result['''failures''']	):
										__UpperCAmelCase							=			f"""*Num failures* :{len(job_result['failed']	)} \n"""
										__UpperCAmelCase							=			job_result['''failures''']
										__UpperCAmelCase							=			self.get_reply_blocks(__a     ,		__a     ,		__a     ,		text=__a	)

										print('''Sending the following reply'''	)
										print(json.dumps({'''blocks''': blocks}	)	)

										client.chat_postMessage(
										    channel=os.environ['''CI_SLACK_CHANNEL_ID_DAILY''']     ,		text=f"""Results for {job}"""     ,		blocks=__a     ,		thread_ts=self.thread_ts['''ts''']     ,		)

										time.sleep(1	)





def       lowerCAmelCase					(		):


	"""simple docstring"""
	__UpperCAmelCase							=			os.environ['''GITHUB_RUN_ID''']
	__UpperCAmelCase							=			f"""https://api.github.com/repos/huggingface/transformers/actions/runs/{run_id}/jobs?per_page=100"""
	__UpperCAmelCase							=			requests.get(UpperCamelCase__       ).json()
	__UpperCAmelCase							=			{}

	try:
		jobs.update({job['''name''']: job['''html_url'''] for job in result['''jobs''']}       )
		__UpperCAmelCase							=			math.ceil((result['''total_count'''] - 1_0_0) / 1_0_0       )

		for i in range(UpperCamelCase__       ):
			__UpperCAmelCase							=			requests.get(url + f"""&page={i + 2}"""       ).json()
			jobs.update({job['''name''']: job['''html_url'''] for job in result['''jobs''']}       )

		return jobs
	except Exception as e:
		print('''Unknown error, could not fetch links.'''    ,					UpperCamelCase__       )

	return {}





def       lowerCAmelCase					(		UpperCamelCase__				:   str       ):


	"""simple docstring"""
	__UpperCAmelCase							=			{}

	if os.path.exists(UpperCamelCase__       ):
		__UpperCAmelCase							=			os.listdir(UpperCamelCase__       )
		for file in files:
			try:
				with open(os.path.join(UpperCamelCase__    ,					UpperCamelCase__       )    ,					encoding='''utf-8'''       ) as f:
					__UpperCAmelCase							=			f.read()
			except UnicodeDecodeError as e:
				raise ValueError(f"""Could not open {os.path.join(UpperCamelCase__    ,					UpperCamelCase__       )}."""       ) from e

	return _artifact





def       lowerCAmelCase					(		):


	"""simple docstring"""






	class 						A   :





								def __init__(      self				:							Union[str, Any]     ,		__a				:							str	)							->	int:
									__UpperCAmelCase							=			name
									__UpperCAmelCase							=			[]





								def __str__(      self				:							str	)							->	List[str]:
									return self.name






								def       snake_case__						(      self				:							Optional[Any]     ,		__a				:							str	)							->	List[Any]:
									self.paths.append({'''name''': self.name, '''path''': path}	)

	__UpperCAmelCase							=			{}

	__UpperCAmelCase							=			filter(os.path.isdir    ,					os.listdir()       )
	for directory in directories:
		__UpperCAmelCase							=			directory
		if artifact_name not in _available_artifacts:
			__UpperCAmelCase							=			Artifact(UpperCamelCase__       )

			_available_artifacts[artifact_name].add_path(UpperCamelCase__       )

	return _available_artifacts


if __name__ == "__main__":
					__lowerCAmelCase	:       Optional[int]						       =	get_job_links()
					__lowerCAmelCase	:       Any						       =	retrieve_available_artifacts()

					__lowerCAmelCase	:       List[Any]						       =	collections.OrderedDict(
					    [
					        ("*.py", "API Examples"),
					        ("*.md", "MD Examples"),
					    ]
					)

					# This dict will contain all the information relative to each doc test category:
					# - failed: list of failed tests
					# - failures: dict in the format 'test': 'error_message'
					__lowerCAmelCase	:       Dict						       =	{
					    v: {
					        "failed": [],
					        "failures": {},
					    }
					    for v in docs.values()
					}

					# Link to the GitHub Action job
					__lowerCAmelCase	:       str						       =	github_actions_job_links.get("run_doctests")

					__lowerCAmelCase	:       Dict						       =	available_artifacts["doc_tests_gpu_test_reports"].paths[0]
					__lowerCAmelCase	:       Tuple						       =	retrieve_artifact(artifact_path["name"])
					if "stats" in artifact:
										__lowerCAmelCase	:       int						       =	handle_test_results(artifact["stats"])
										__lowerCAmelCase	:       Dict						       =	failed
										__lowerCAmelCase	:       str						       =	success
										__lowerCAmelCase	:       Optional[Any]						       =	time_spent[1:-1] + ", "

										__lowerCAmelCase	:       Dict						       =	extract_first_line_failure(artifact["failures_short"])
										for line in artifact["summary_short"].split("\n"):
															if re.search("FAILED", line):
																				__lowerCAmelCase	:       Any						       =	line.replace("FAILED ", "")
																				__lowerCAmelCase	:       Optional[Any]						       =	line.split()[0].replace("\n", "")

																				if "::" in line:
																									__lowerCAmelCase	:       Optional[int]						       =	line.split("::")
																				else:
																									__lowerCAmelCase	:       Any						       =	line, line

																				for file_regex in docs.keys():
																									if fnmatch(file_path, file_regex):
																														__lowerCAmelCase	:       Optional[Any]						       =	docs[file_regex]
																														doc_test_results[category]["failed"].append(test)

																														__lowerCAmelCase	:       Optional[int]						       =	all_failures[test] if test in all_failures else "N/A"
																														__lowerCAmelCase	:       Union[str, Any]						       =	failure
																														break

					__lowerCAmelCase	:       int						       =	Message("🤗 Results of the doc tests.", doc_test_results)
					message.post()
					message.post_reply()

'''simple docstring'''


import heapq
import sys

import numpy as np

__lowerCAmelCase	:       Any						       =	tuple[int, int]






class 						A   :





							def __init__(      self				:							Optional[int]	)							->	int:
								__UpperCAmelCase							=			[]
								__UpperCAmelCase							=			set()





							def       snake_case__						(      self				:							Optional[Any]	)							->	List[Any]:
								if not self.empty():
									return self.elements[0][0]
								else:
									return float('''inf'''	)





							def       snake_case__						(      self				:							Dict	)							->	Optional[int]:
								return len(self.elements	) == 0





							def       snake_case__						(      self				:							Optional[int]     ,		__a				:							Optional[Any]     ,		__a				:							Dict	)							->	Optional[Any]:
								if item not in self.set:
									heapq.heappush(self.elements     ,		(priority, item)	)
									self.set.add(__a	)
								else:
									# update
									# print("update", item)
									__UpperCAmelCase							=			[]
									((__UpperCAmelCase)				,			(__UpperCAmelCase))							=			heapq.heappop(self.elements	)
									while x != item:
										temp.append((pri, x)	)
										((__UpperCAmelCase)				,			(__UpperCAmelCase))							=			heapq.heappop(self.elements	)
									temp.append((priority, item)	)
									for pro, xxx in temp:
										heapq.heappush(self.elements     ,		(pro, xxx)	)





							def       snake_case__						(      self				:							int     ,		__a				:							Any	)							->	int:
								if item in self.set:
									self.set.remove(__a	)
									__UpperCAmelCase							=			[]
									((__UpperCAmelCase)				,			(__UpperCAmelCase))							=			heapq.heappop(self.elements	)
									while x != item:
										temp.append((pro, x)	)
										((__UpperCAmelCase)				,			(__UpperCAmelCase))							=			heapq.heappop(self.elements	)
									for prito, yyy in temp:
										heapq.heappush(self.elements     ,		(prito, yyy)	)





							def       snake_case__						(      self				:							List[str]	)							->	Dict:
								return self.elements[0][1]






							def       snake_case__						(      self				:							Any	)							->	List[str]:
								((__UpperCAmelCase)				,			(__UpperCAmelCase))							=			heapq.heappop(self.elements	)
								self.set.remove(__a	)
								return (priority, item)





def       lowerCAmelCase					(		UpperCamelCase__				:   TPos    ,					UpperCamelCase__				:   TPos       ):


	"""simple docstring"""
	# euclidean distance
	__UpperCAmelCase							=			np.array(UpperCamelCase__       )
	__UpperCAmelCase							=			np.array(UpperCamelCase__       )
	return np.linalg.norm(a - b       )





def       lowerCAmelCase					(		UpperCamelCase__				:   TPos    ,					UpperCamelCase__				:   TPos       ):


	"""simple docstring"""
	# integer division by time variable
	return consistent_heuristic(UpperCamelCase__    ,					UpperCamelCase__       ) // t





def       lowerCAmelCase					(		UpperCamelCase__				:   TPos    ,					UpperCamelCase__				:   TPos       ):


	"""simple docstring"""
	# manhattan distance
	return abs(p[0] - goal[0]       ) + abs(p[1] - goal[1]       )





def       lowerCAmelCase					(		UpperCamelCase__				:   TPos    ,					UpperCamelCase__				:   int    ,					UpperCamelCase__				:   TPos    ,					UpperCamelCase__				:   dict[TPos, float]       ):


	"""simple docstring"""
	__UpperCAmelCase							=			g_function[start] + Wa * heuristics[i](UpperCamelCase__    ,					UpperCamelCase__       )
	return ans





def       lowerCAmelCase					(		UpperCamelCase__				:   List[Any]    ,					UpperCamelCase__				:   int    ,					UpperCamelCase__				:   Optional[int]       ):


	"""simple docstring"""
	__UpperCAmelCase							=			np.chararray((n, n)       )
	for i in range(UpperCamelCase__       ):
		for j in range(UpperCamelCase__       ):
			__UpperCAmelCase							=			'''*'''

	for i in range(UpperCamelCase__       ):
		for j in range(UpperCamelCase__       ):
			if (j, (n - 1) - i) in blocks:
				__UpperCAmelCase							=			'''#'''

	__UpperCAmelCase							=			'''-'''
	__UpperCAmelCase							=			back_pointer[goal]
	while x != start:
		((__UpperCAmelCase)				,			(__UpperCAmelCase))							=			x
		# print(x)
		__UpperCAmelCase							=			'''-'''
		__UpperCAmelCase							=			back_pointer[x]
	__UpperCAmelCase							=			'''-'''

	for i in range(UpperCamelCase__       ):
		for j in range(UpperCamelCase__       ):
			if (i, j) == (0, n - 1):
				print(grid[i][j]    ,					end=''' '''       )
				print('''<-- End position'''    ,					end=''' '''       )
			else:
				print(grid[i][j]    ,					end=''' '''       )
		print()
	print('''^'''       )
	print('''Start position'''       )
	print()
	print('''# is an obstacle'''       )
	print('''- is the path taken by algorithm'''       )
	print('''PATH TAKEN BY THE ALGORITHM IS:-'''       )
	__UpperCAmelCase							=			back_pointer[goal]
	while x != start:
		print(UpperCamelCase__    ,					end=''' '''       )
		__UpperCAmelCase							=			back_pointer[x]
	print(UpperCamelCase__       )
	sys.exit()





def       lowerCAmelCase					(		UpperCamelCase__				:   TPos       ):


	"""simple docstring"""
	if p[0] < 0 or p[0] > n - 1:
		return False
	if p[1] < 0 or p[1] > n - 1:
		return False
	return True





def       lowerCAmelCase					(		UpperCamelCase__				:   Optional[Any]    ,					UpperCamelCase__				:   int    ,					UpperCamelCase__				:   List[Any]    ,					UpperCamelCase__				:   Dict    ,					UpperCamelCase__				:   Dict    ,					UpperCamelCase__				:   Dict    ,					UpperCamelCase__				:   List[Any]    ,					UpperCamelCase__				:   Tuple    ,					):


	"""simple docstring"""
	for itera in range(UpperCamelCase__       ):
		open_list[itera].remove_element(UpperCamelCase__       )
	# print("s", s)
	# print("j", j)
	((__UpperCAmelCase)				,			(__UpperCAmelCase))							=			s
	__UpperCAmelCase							=			(x - 1, y)
	__UpperCAmelCase							=			(x + 1, y)
	__UpperCAmelCase							=			(x, y + 1)
	__UpperCAmelCase							=			(x, y - 1)

	for neighbours in [left, right, up, down]:
		if neighbours not in blocks:
			if valid(UpperCamelCase__       ) and neighbours not in visited:
				# print("neighbour", neighbours)
				visited.add(UpperCamelCase__       )
				__UpperCAmelCase							=			-1
				__UpperCAmelCase							=			float('''inf'''       )

			if valid(UpperCamelCase__       ) and g_function[neighbours] > g_function[s] + 1:
				__UpperCAmelCase							=			g_function[s] + 1
				__UpperCAmelCase							=			s
				if neighbours not in close_list_anchor:
					open_list[0].put(UpperCamelCase__    ,					key(UpperCamelCase__    ,					0    ,					UpperCamelCase__    ,					UpperCamelCase__       )       )
					if neighbours not in close_list_inad:
						for var in range(1    ,					UpperCamelCase__       ):
							if key(UpperCamelCase__    ,					UpperCamelCase__    ,					UpperCamelCase__    ,					UpperCamelCase__       ) <= Wa * key(
							    UpperCamelCase__    ,					0    ,					UpperCamelCase__    ,					UpperCamelCase__       ):
								open_list[j].put(
								    UpperCamelCase__    ,					key(UpperCamelCase__    ,					UpperCamelCase__    ,					UpperCamelCase__    ,					UpperCamelCase__       )       )





def       lowerCAmelCase					(		):


	"""simple docstring"""
	__UpperCAmelCase							=			[]
	for x in range(1    ,					5       ):
		for y in range(1    ,					6       ):
			some_list.append((x, y)       )

	for x in range(1_5    ,					2_0       ):
		some_list.append((x, 1_7)       )

	for x in range(1_0    ,					1_9       ):
		for y in range(1    ,					1_5       ):
			some_list.append((x, y)       )

    # L block
	for x in range(1    ,					4       ):
		for y in range(1_2    ,					1_9       ):
			some_list.append((x, y)       )
	for x in range(3    ,					1_3       ):
		for y in range(1_6    ,					1_9       ):
			some_list.append((x, y)       )
	return some_list


__lowerCAmelCase	:       Optional[Any]						       =	{0: consistent_heuristic, 1: heuristic_a, 2: heuristic_a}

__lowerCAmelCase	:       List[Any]						       =	[
    (0, 1),
    (1, 1),
    (2, 1),
    (3, 1),
    (4, 1),
    (5, 1),
    (6, 1),
    (7, 1),
    (8, 1),
    (9, 1),
    (10, 1),
    (11, 1),
    (12, 1),
    (13, 1),
    (14, 1),
    (15, 1),
    (16, 1),
    (17, 1),
    (18, 1),
    (19, 1),
]
__lowerCAmelCase	:       Dict						       =	make_common_ground()


__lowerCAmelCase	:       int						       =	blocks_blk
# hyper parameters
__lowerCAmelCase	:       Dict						       =	1
__lowerCAmelCase	:       List[str]						       =	1
__lowerCAmelCase	:       Union[str, Any]						       =	20
__lowerCAmelCase	:       Any						       =	3  # one consistent and two other inconsistent

# start and end destination
__lowerCAmelCase	:       Optional[Any]						       =	(0, 0)
__lowerCAmelCase	:       Any						       =	(n - 1, n - 1)

__lowerCAmelCase	:       Optional[int]						       =	1





def       lowerCAmelCase					(		UpperCamelCase__				:   TPos    ,					UpperCamelCase__				:   TPos    ,					UpperCamelCase__				:   int       ):


	"""simple docstring"""
	__UpperCAmelCase							=			{start: 0, goal: float('''inf'''       )}
	__UpperCAmelCase							=			{start: -1, goal: -1}
	__UpperCAmelCase							=			[]
	__UpperCAmelCase							=			set()

	for i in range(UpperCamelCase__       ):
		open_list.append(PriorityQueue()       )
		open_list[i].put(UpperCamelCase__    ,					key(UpperCamelCase__    ,					UpperCamelCase__    ,					UpperCamelCase__    ,					UpperCamelCase__       )       )

	__UpperCAmelCase							=			[]
	__UpperCAmelCase							=			[]
	while open_list[0].minkey() < float('''inf'''       ):
		for i in range(1    ,					UpperCamelCase__       ):
			# print(open_list[0].minkey(), open_list[i].minkey())
			if open_list[i].minkey() <= Wa * open_list[0].minkey():
				global t
				t += 1
				if g_function[goal] <= open_list[i].minkey():
					if g_function[goal] < float('''inf'''       ):
						do_something(UpperCamelCase__    ,					UpperCamelCase__    ,					UpperCamelCase__       )
				else:
					__UpperCAmelCase				,			__UpperCAmelCase							=			open_list[i].top_show()
					visited.add(UpperCamelCase__       )
					expand_state(
					    UpperCamelCase__    ,					UpperCamelCase__    ,					UpperCamelCase__    ,					UpperCamelCase__    ,					UpperCamelCase__    ,					UpperCamelCase__    ,					UpperCamelCase__    ,					UpperCamelCase__    ,					)
					close_list_inad.append(UpperCamelCase__       )
			else:
				if g_function[goal] <= open_list[0].minkey():
					if g_function[goal] < float('''inf'''       ):
						do_something(UpperCamelCase__    ,					UpperCamelCase__    ,					UpperCamelCase__       )
				else:
					__UpperCAmelCase							=			open_list[0].top_show()
					visited.add(UpperCamelCase__       )
					expand_state(
					    UpperCamelCase__    ,					0    ,					UpperCamelCase__    ,					UpperCamelCase__    ,					UpperCamelCase__    ,					UpperCamelCase__    ,					UpperCamelCase__    ,					UpperCamelCase__    ,					)
					close_list_anchor.append(UpperCamelCase__       )
	print('''No path found to goal'''       )
	print()
	for i in range(n - 1    ,					-1    ,					-1       ):
		for j in range(UpperCamelCase__       ):
			if (j, i) in blocks:
				print('''#'''    ,					end=''' '''       )
			elif (j, i) in back_pointer:
				if (j, i) == (n - 1, n - 1):
					print('''*'''    ,					end=''' '''       )
				else:
					print('''-'''    ,					end=''' '''       )
			else:
				print('''*'''    ,					end=''' '''       )
			if (j, i) == (n - 1, n - 1):
				print('''<-- End position'''    ,					end=''' '''       )
		print()
	print('''^'''       )
	print('''Start position'''       )
	print()
	print('''# is an obstacle'''       )
	print('''- is the path taken by algorithm'''       )


if __name__ == "__main__":
					multi_a_star(start, goal, n_heuristic)
