






import collections
from typing import List, Optional, Union

from ...tokenization_utils_base import BatchEncoding
from ...utils import TensorType, add_end_docstrings, add_start_docstrings, logging
from ..bert.tokenization_bert_fast import BertTokenizerFast
from .tokenization_dpr import DPRContextEncoderTokenizer, DPRQuestionEncoderTokenizer, DPRReaderTokenizer


__UpperCamelCase      :      str     						=						logging.get_logger(__name__)

__UpperCamelCase      :      List[Any]     						=						{"""vocab_file""": """vocab.txt""", """tokenizer_file""": """tokenizer.json"""}

__UpperCamelCase      :      Dict     						=						{
    """vocab_file""": {
        """facebook/dpr-ctx_encoder-single-nq-base""": (
            """https://huggingface.co/facebook/dpr-ctx_encoder-single-nq-base/resolve/main/vocab.txt"""
        ),
        """facebook/dpr-ctx_encoder-multiset-base""": (
            """https://huggingface.co/facebook/dpr-ctx_encoder-multiset-base/resolve/main/vocab.txt"""
        ),
    },
    """tokenizer_file""": {
        """facebook/dpr-ctx_encoder-single-nq-base""": (
            """https://huggingface.co/facebook/dpr-ctx_encoder-single-nq-base/resolve/main/tokenizer.json"""
        ),
        """facebook/dpr-ctx_encoder-multiset-base""": (
            """https://huggingface.co/facebook/dpr-ctx_encoder-multiset-base/resolve/main/tokenizer.json"""
        ),
    },
}
__UpperCamelCase      :      Dict     						=						{
    """vocab_file""": {
        """facebook/dpr-question_encoder-single-nq-base""": (
            """https://huggingface.co/facebook/dpr-question_encoder-single-nq-base/resolve/main/vocab.txt"""
        ),
        """facebook/dpr-question_encoder-multiset-base""": (
            """https://huggingface.co/facebook/dpr-question_encoder-multiset-base/resolve/main/vocab.txt"""
        ),
    },
    """tokenizer_file""": {
        """facebook/dpr-question_encoder-single-nq-base""": (
            """https://huggingface.co/facebook/dpr-question_encoder-single-nq-base/resolve/main/tokenizer.json"""
        ),
        """facebook/dpr-question_encoder-multiset-base""": (
            """https://huggingface.co/facebook/dpr-question_encoder-multiset-base/resolve/main/tokenizer.json"""
        ),
    },
}
__UpperCamelCase      :      int     						=						{
    """vocab_file""": {
        """facebook/dpr-reader-single-nq-base""": (
            """https://huggingface.co/facebook/dpr-reader-single-nq-base/resolve/main/vocab.txt"""
        ),
        """facebook/dpr-reader-multiset-base""": (
            """https://huggingface.co/facebook/dpr-reader-multiset-base/resolve/main/vocab.txt"""
        ),
    },
    """tokenizer_file""": {
        """facebook/dpr-reader-single-nq-base""": (
            """https://huggingface.co/facebook/dpr-reader-single-nq-base/resolve/main/tokenizer.json"""
        ),
        """facebook/dpr-reader-multiset-base""": (
            """https://huggingface.co/facebook/dpr-reader-multiset-base/resolve/main/tokenizer.json"""
        ),
    },
}

__UpperCamelCase      :      Dict     						=						{
    """facebook/dpr-ctx_encoder-single-nq-base""": 512,
    """facebook/dpr-ctx_encoder-multiset-base""": 512,
}
__UpperCamelCase      :      Optional[Any]     						=						{
    """facebook/dpr-question_encoder-single-nq-base""": 512,
    """facebook/dpr-question_encoder-multiset-base""": 512,
}
__UpperCamelCase      :      Tuple     						=						{
    """facebook/dpr-reader-single-nq-base""": 512,
    """facebook/dpr-reader-multiset-base""": 512,
}


__UpperCamelCase      :      Tuple     						=						{
    """facebook/dpr-ctx_encoder-single-nq-base""": {"""do_lower_case""": True},
    """facebook/dpr-ctx_encoder-multiset-base""": {"""do_lower_case""": True},
}
__UpperCamelCase      :      Union[str, Any]     						=						{
    """facebook/dpr-question_encoder-single-nq-base""": {"""do_lower_case""": True},
    """facebook/dpr-question_encoder-multiset-base""": {"""do_lower_case""": True},
}
__UpperCamelCase      :      Optional[Any]     						=						{
    """facebook/dpr-reader-single-nq-base""": {"""do_lower_case""": True},
    """facebook/dpr-reader-multiset-base""": {"""do_lower_case""": True},
}


class        __UpperCamelCase    (     _lowerCAmelCase   ):
	__snake_case	:Optional[Any]   =       VOCAB_FILES_NAMES
	__snake_case	:Optional[Any]   =       CONTEXT_ENCODER_PRETRAINED_VOCAB_FILES_MAP
	__snake_case	:Union[str, Any]   =       CONTEXT_ENCODER_PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
	__snake_case	:Any   =       CONTEXT_ENCODER_PRETRAINED_INIT_CONFIGURATION
	__snake_case	:Optional[int]   =       DPRContextEncoderTokenizer


class        __UpperCamelCase    (     _lowerCAmelCase   ):
	__snake_case	:Union[str, Any]   =       VOCAB_FILES_NAMES
	__snake_case	:Dict   =       QUESTION_ENCODER_PRETRAINED_VOCAB_FILES_MAP
	__snake_case	:Optional[int]   =       QUESTION_ENCODER_PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
	__snake_case	:Optional[int]   =       QUESTION_ENCODER_PRETRAINED_INIT_CONFIGURATION
	__snake_case	:Tuple   =       DPRQuestionEncoderTokenizer

__UpperCamelCase      :      int     						=						collections.namedtuple(
    """DPRSpanPrediction""", ["""span_score""", """relevance_score""", """doc_id""", """start_index""", """end_index""", """text"""]
)

__UpperCamelCase      :      Any     						=						collections.namedtuple("""DPRReaderOutput""", ["""start_logits""", """end_logits""", """relevance_logits"""])


__UpperCamelCase      :      str     						=						r"""
    Return a dictionary with the token ids of the input strings and other information to give to `.decode_best_spans`.
    It converts the strings of a question and different passages (title and text) in a sequence of IDs (integers),
    using the tokenizer and vocabulary. The resulting `input_ids` is a matrix of size `(n_passages, sequence_length)`
    with the format:

    [CLS] <question token ids> [SEP] <titles ids> [SEP] <texts ids>

    Args:
        questions (`str` or `List[str]`):
            The questions to be encoded. You can specify one question for many passages. In this case, the question
            will be duplicated like `[questions] * n_passages`. Otherwise you have to specify as many questions as in
            `titles` or `texts`.
        titles (`str` or `List[str]`):
            The passages titles to be encoded. This can be a string or a list of strings if there are several passages.
        texts (`str` or `List[str]`):
            The passages texts to be encoded. This can be a string or a list of strings if there are several passages.
        padding (`bool`, `str` or [`~utils.PaddingStrategy`], *optional*, defaults to `False`):
            Activates and controls padding. Accepts the following values:

            - `True` or `'longest'`: Pad to the longest sequence in the batch (or no padding if only a single sequence
              if provided).
            - `'max_length'`: Pad to a maximum length specified with the argument `max_length` or to the maximum
              acceptable input length for the model if that argument is not provided.
            - `False` or `'do_not_pad'` (default): No padding (i.e., can output a batch with sequences of different
              lengths).
        truncation (`bool`, `str` or [`~tokenization_utils_base.TruncationStrategy`], *optional*, defaults to `False`):
            Activates and controls truncation. Accepts the following values:

            - `True` or `'longest_first'`: Truncate to a maximum length specified with the argument `max_length` or to
              the maximum acceptable input length for the model if that argument is not provided. This will truncate
              token by token, removing a token from the longest sequence in the pair if a pair of sequences (or a batch
              of pairs) is provided.
            - `'only_first'`: Truncate to a maximum length specified with the argument `max_length` or to the maximum
              acceptable input length for the model if that argument is not provided. This will only truncate the first
              sequence of a pair if a pair of sequences (or a batch of pairs) is provided.
            - `'only_second'`: Truncate to a maximum length specified with the argument `max_length` or to the maximum
              acceptable input length for the model if that argument is not provided. This will only truncate the
              second sequence of a pair if a pair of sequences (or a batch of pairs) is provided.
            - `False` or `'do_not_truncate'` (default): No truncation (i.e., can output batch with sequence lengths
              greater than the model maximum admissible input size).
        max_length (`int`, *optional*):
                Controls the maximum length to use by one of the truncation/padding parameters.

                If left unset or set to `None`, this will use the predefined model maximum length if a maximum length
                is required by one of the truncation/padding parameters. If the model has no specific maximum input
                length (like XLNet) truncation/padding to a maximum length will be deactivated.
        return_tensors (`str` or [`~utils.TensorType`], *optional*):
                If set, will return tensors instead of list of python integers. Acceptable values are:

                - `'tf'`: Return TensorFlow `tf.constant` objects.
                - `'pt'`: Return PyTorch `torch.Tensor` objects.
                - `'np'`: Return Numpy `np.ndarray` objects.
        return_attention_mask (`bool`, *optional*):
            Whether or not to return the attention mask. If not set, will return the attention mask according to the
            specific tokenizer's default, defined by the `return_outputs` attribute.

            [What are attention masks?](../glossary#attention-mask)

    Return:
        `Dict[str, List[List[int]]]`: A dictionary with the following keys:

        - `input_ids`: List of token ids to be fed to a model.
        - `attention_mask`: List of indices specifying which tokens should be attended to by the model.
    """


@add_start_docstrings(_lowerCAmelCase   )
class        __UpperCamelCase    :







	def __call__(  self      :							Dict       ,				_lowerCAmelCase      :							Optional[Any]       ,				_lowerCAmelCase      :							Optional[str] = None       ,				_lowerCAmelCase      :							Optional[str] = None       ,				_lowerCAmelCase      :							Union[bool, str] = False       ,				_lowerCAmelCase      :							Union[bool, str] = False       ,				_lowerCAmelCase      :							Optional[int] = None       ,				_lowerCAmelCase      :							Optional[Union[str, TensorType]] = None       ,				_lowerCAmelCase      :							Optional[bool] = None       ,				**_lowerCAmelCase      :							Optional[Any]       ,				)		-> BatchEncoding:
		"""simple docstring"""







		if titles is None and texts is None:
			return super().__call__(
			    _lowerCAmelCase       ,				padding=_lowerCAmelCase       ,				truncation=_lowerCAmelCase       ,				max_length=_lowerCAmelCase       ,				return_tensors=_lowerCAmelCase       ,				return_attention_mask=_lowerCAmelCase       ,				**_lowerCAmelCase       ,				)
		elif titles is None or texts is None:
			__lowercase             =  titles if texts is None else texts
			return super().__call__(
			    _lowerCAmelCase       ,				_lowerCAmelCase       ,				padding=_lowerCAmelCase       ,				truncation=_lowerCAmelCase       ,				max_length=_lowerCAmelCase       ,				return_tensors=_lowerCAmelCase       ,				return_attention_mask=_lowerCAmelCase       ,				**_lowerCAmelCase       ,				)
		__lowercase             =  titles if not isinstance(_lowerCAmelCase       ,				_lowerCAmelCase			) else [titles]
		__lowercase             =  texts if not isinstance(_lowerCAmelCase       ,				_lowerCAmelCase			) else [texts]
		__lowercase             =  len(_lowerCAmelCase			)
		__lowercase             =  questions if not isinstance(_lowerCAmelCase       ,				_lowerCAmelCase			) else [questions] * n_passages
		assert len(_lowerCAmelCase			) == len(
		    _lowerCAmelCase			), F'There should be as many titles than texts but got {len(_lowerCAmelCase			)} titles and {len(_lowerCAmelCase			)} texts.'
		__lowercase             =  super().__call__(_lowerCAmelCase       ,				_lowerCAmelCase       ,				padding=_lowerCAmelCase       ,				truncation=_lowerCAmelCase			)["""input_ids"""]
		__lowercase             =  super().__call__(_lowerCAmelCase       ,				add_special_tokens=_lowerCAmelCase       ,				padding=_lowerCAmelCase       ,				truncation=_lowerCAmelCase			)["""input_ids"""]
		__lowercase             =  {
		    """input_ids""": [
		        (encoded_question_and_title + encoded_text)[:max_length]
		        if max_length is not None and truncation
		        else encoded_question_and_title + encoded_text
		        for encoded_question_and_title, encoded_text in zip(_lowerCAmelCase       ,				_lowerCAmelCase			)
		    ]
		}
		if return_attention_mask is not False:
			__lowercase             =  []
			for input_ids in encoded_inputs["input_ids"]:
				attention_mask.append([int(input_id != self.pad_token_id			) for input_id in input_ids]			)
			__lowercase             =  attention_mask
		return self.pad(_lowerCAmelCase       ,				padding=_lowerCAmelCase       ,				max_length=_lowerCAmelCase       ,				return_tensors=_lowerCAmelCase			)







	def  _a   (  self      :							Union[str, Any]       ,				_lowerCAmelCase      :							BatchEncoding       ,				_lowerCAmelCase      :							DPRReaderOutput       ,				_lowerCAmelCase      :							int = 16       ,				_lowerCAmelCase      :							int = 64       ,				_lowerCAmelCase      :							int = 4       ,				)		-> List[DPRSpanPrediction]:
		"""simple docstring"""







		__lowercase             =  reader_input["""input_ids"""]
		__lowercase       ,						__lowercase       ,						__lowercase             =  reader_output[:3]
		__lowercase             =  len(_lowerCAmelCase			)
		__lowercase             =  sorted(range(_lowerCAmelCase			)       ,				reverse=_lowerCAmelCase       ,				key=relevance_logits.__getitem__			)
		__lowercase             =  []
		for doc_id in sorted_docs:
			__lowercase             =  list(input_ids[doc_id]			)
			# assuming question & title information is at the beginning of the sequence
			__lowercase             =  sequence_ids.index(self.sep_token_id       ,				2			) + 1  # second sep id
			if sequence_ids[-1] == self.pad_token_id:
				__lowercase             =  sequence_ids.index(self.pad_token_id			)
			else:
				__lowercase             =  len(_lowerCAmelCase			)

			__lowercase             =  self._get_best_spans(
			    start_logits=start_logits[doc_id][passage_offset:sequence_len]       ,				end_logits=end_logits[doc_id][passage_offset:sequence_len]       ,				max_answer_length=_lowerCAmelCase       ,				top_spans=_lowerCAmelCase       ,				)
			for start_index, end_index in best_spans:
				start_index += passage_offset
				end_index += passage_offset
				nbest_spans_predictions.append(
				    DPRSpanPrediction(
				        span_score=start_logits[doc_id][start_index] + end_logits[doc_id][end_index]       ,				relevance_score=relevance_logits[doc_id]       ,				doc_id=_lowerCAmelCase       ,				start_index=_lowerCAmelCase       ,				end_index=_lowerCAmelCase       ,				text=self.decode(sequence_ids[start_index : end_index + 1]			)       ,				)			)
			if len(_lowerCAmelCase			) >= num_spans:
				break
		return nbest_spans_predictions[:num_spans]







	def  _a   (  self      :							List[Any]       ,				_lowerCAmelCase      :							List[int]       ,				_lowerCAmelCase      :							List[int]       ,				_lowerCAmelCase      :							int       ,				_lowerCAmelCase      :							int       ,				)		-> List[DPRSpanPrediction]:
		"""simple docstring"""







		__lowercase             =  []
		for start_index, start_score in enumerate(_lowerCAmelCase			):
			for answer_length, end_score in enumerate(end_logits[start_index : start_index + max_answer_length]			):
				scores.append(((start_index, start_index + answer_length), start_score + end_score)			)
		__lowercase             =  sorted(_lowerCAmelCase       ,				key=lambda _lowerCAmelCase			: x[1]       ,				reverse=_lowerCAmelCase			)
		__lowercase             =  []
		for (start_index, end_index), score in scores:
			assert start_index <= end_index, F'Wrong span indices: [{start_index}:{end_index}]'
			__lowercase             =  end_index - start_index + 1
			assert length <= max_answer_length, F'Span is too long: {length} > {max_answer_length}'
			if any(
			    start_index <= prev_start_index <= prev_end_index <= end_index
			    or prev_start_index <= start_index <= end_index <= prev_end_index
			    for (prev_start_index, prev_end_index) in chosen_span_intervals			):
				continue
			chosen_span_intervals.append((start_index, end_index)			)

			if len(_lowerCAmelCase			) == top_spans:
				break
		return chosen_span_intervals


@add_end_docstrings(_lowerCAmelCase   )
class        __UpperCamelCase    (     _lowerCAmelCase   ,			_lowerCAmelCase   ):
	__snake_case	:int   =       VOCAB_FILES_NAMES
	__snake_case	:Dict   =       READER_PRETRAINED_VOCAB_FILES_MAP
	__snake_case	:Optional[int]   =       READER_PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
	__snake_case	:Tuple   =       READER_PRETRAINED_INIT_CONFIGURATION
	__snake_case	:List[Any]   =       ['input_ids', 'attention_mask']
	__snake_case	:Any   =       DPRReaderTokenizer









import heapq
import sys

import numpy as np

__UpperCamelCase      :      List[str]     						=						tuple[int, int]


class        __UpperCamelCase    :







	def __init__(  self      :							Optional[int]			)		-> Dict:
		"""simple docstring"""







		__lowercase             =  []
		__lowercase             =  set()







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







		if not self.empty():
			return self.elements[0][0]
		else:
			return float("""inf"""			)







	def  _a   (  self      :							Dict			)		-> Optional[Any]:
		"""simple docstring"""







		return len(self.elements			) == 0







	def  _a   (  self      :							str       ,				_lowerCAmelCase      :							Union[str, Any]       ,				_lowerCAmelCase      :							Optional[Any]			)		-> Dict:
		"""simple docstring"""







		if item not in self.set:
			heapq.heappush(self.elements       ,				(priority, item)			)
			self.set.add(_lowerCAmelCase			)
		else:
			# update
			# print("update", item)
			__lowercase             =  []
			((__lowercase)       ,						(__lowercase))             =  heapq.heappop(self.elements			)
			while x != item:
				temp.append((pri, x)			)
				((__lowercase)       ,						(__lowercase))             =  heapq.heappop(self.elements			)
			temp.append((priority, item)			)
			for pro, xxx in temp:
				heapq.heappush(self.elements       ,				(pro, xxx)			)







	def  _a   (  self      :							List[str]       ,				_lowerCAmelCase      :							Optional[Any]			)		-> Dict:
		"""simple docstring"""







		if item in self.set:
			self.set.remove(_lowerCAmelCase			)
			__lowercase             =  []
			((__lowercase)       ,						(__lowercase))             =  heapq.heappop(self.elements			)
			while x != item:
				temp.append((pro, x)			)
				((__lowercase)       ,						(__lowercase))             =  heapq.heappop(self.elements			)
			for prito, yyy in temp:
				heapq.heappush(self.elements       ,				(prito, yyy)			)







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







		return self.elements[0][1]







	def  _a   (  self      :							Optional[int]			)		-> List[Any]:
		"""simple docstring"""







		((__lowercase)       ,						(__lowercase))             =  heapq.heappop(self.elements			)
		self.set.remove(_lowerCAmelCase			)
		return (priority, item)





def 				snake_case  (     lowerCamelCase				,  lowerCamelCase					):




	'''simple docstring'''







	__lowercase             =  np.array(lowerCamelCase					)
	__lowercase             =  np.array(lowerCamelCase					)
	return np.linalg.norm(a - b					)





def 				snake_case  (     lowerCamelCase				,  lowerCamelCase					):




	'''simple docstring'''







	return consistent_heuristic(lowerCamelCase				,  lowerCamelCase					) // t





def 				snake_case  (     lowerCamelCase				,  lowerCamelCase					):




	'''simple docstring'''







	return abs(p[0] - goal[0]					) + abs(p[1] - goal[1]					)





def 				snake_case  (     lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase					):




	'''simple docstring'''







	__lowercase             =  g_function[start] + Wa * heuristics[i](lowerCamelCase				,  lowerCamelCase					)
	return ans





def 				snake_case  (     lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase					):




	'''simple docstring'''







	__lowercase             =  np.chararray((n, n)					)
	for i in range(lowerCamelCase					):
		for j in range(lowerCamelCase					):
			__lowercase             =  """*"""

	for i in range(lowerCamelCase					):
		for j in range(lowerCamelCase					):
			if (j, (n - 1) - i) in blocks:
				__lowercase             =  """#"""

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

	for i in range(lowerCamelCase					):
		for j in range(lowerCamelCase					):
			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:-"""					)
	__lowercase             =  back_pointer[goal]
	while x != start:
		print(lowerCamelCase				,  end=""" """					)
		__lowercase             =  back_pointer[x]
	print(lowerCamelCase					)
	sys.exit()





def 				snake_case  (     lowerCamelCase					):




	'''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 				snake_case  (     lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  ):




	'''simple docstring'''







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

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

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





def 				snake_case  (     ):




	'''simple docstring'''







	__lowercase             =  []
	for x in range(1				,  5					):
		for y in range(1				,  6					):
			some_list.append((x, y)					)

	for x in range(15				,  20					):
		some_list.append((x, 17)					)

	for x in range(10				,  19					):
		for y in range(1				,  15					):
			some_list.append((x, y)					)

    # L block
	for x in range(1				,  4					):
		for y in range(12				,  19					):
			some_list.append((x, y)					)
	for x in range(3				,  13					):
		for y in range(16				,  19					):
			some_list.append((x, y)					)
	return some_list


__UpperCamelCase      :      Optional[int]     						=						{0: consistent_heuristic, 1: heuristic_a, 2: heuristic_a}

__UpperCamelCase      :      Optional[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),
]
__UpperCamelCase      :      Optional[Any]     						=						make_common_ground()


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

# start and end destination
__UpperCamelCase      :      str     						=						(0, 0)
__UpperCamelCase      :      str     						=						(n - 1, n - 1)

__UpperCamelCase      :      Optional[Any]     						=						1





def 				snake_case  (     lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase					):




	'''simple docstring'''







	__lowercase             =  {start: 0, goal: float("""inf"""					)}
	__lowercase             =  {start: -1, goal: -1}
	__lowercase             =  []
	__lowercase             =  set()

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

	__lowercase             =  []
	__lowercase             =  []
	while open_list[0].minkey() < float("""inf"""					):
		for i in range(1				,  lowerCamelCase					):
			# 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(lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase					)
				else:
					__lowercase       ,						__lowercase             =  open_list[i].top_show()
					visited.add(lowerCamelCase					)
					expand_state(
					    lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  )
					close_list_inad.append(lowerCamelCase					)
			else:
				if g_function[goal] <= open_list[0].minkey():
					if g_function[goal] < float("""inf"""					):
						do_something(lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase					)
				else:
					__lowercase             =  open_list[0].top_show()
					visited.add(lowerCamelCase					)
					expand_state(
					    lowerCamelCase				,  0				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  )
					close_list_anchor.append(lowerCamelCase					)
	print("""No path found to goal"""					)
	print()
	for i in range(n - 1				,  -1				,  -1					):
		for j in range(lowerCamelCase					):
			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)

