






import math
import os
import unittest

from transformers import MegatronBertConfig, is_torch_available
from transformers.models.auto import get_values
from transformers.testing_utils import require_sentencepiece, require_tokenizers, require_torch, slow, torch_device

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
							import torch

							from transformers import (
							    MODEL_FOR_PRETRAINING_MAPPING,
							    MegatronBertForCausalLM,
							    MegatronBertForMaskedLM,
							    MegatronBertForMultipleChoice,
							    MegatronBertForNextSentencePrediction,
							    MegatronBertForPreTraining,
							    MegatronBertForQuestionAnswering,
							    MegatronBertForSequenceClassification,
							    MegatronBertForTokenClassification,
							    MegatronBertModel,
							)




class 		UpperCAmelCase_						:


						'''simple docstring'''




						def __init__(	self		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE=13		,				_SCREAMING_SNAKE_CASE=7		,				_SCREAMING_SNAKE_CASE=True		,				_SCREAMING_SNAKE_CASE=True		,				_SCREAMING_SNAKE_CASE=True		,				_SCREAMING_SNAKE_CASE=True		,				_SCREAMING_SNAKE_CASE=99		,				_SCREAMING_SNAKE_CASE=64		,				_SCREAMING_SNAKE_CASE=32		,				_SCREAMING_SNAKE_CASE=5		,				_SCREAMING_SNAKE_CASE=4		,				_SCREAMING_SNAKE_CASE=37		,				_SCREAMING_SNAKE_CASE="gelu"		,				_SCREAMING_SNAKE_CASE=0.1		,				_SCREAMING_SNAKE_CASE=0.1		,				_SCREAMING_SNAKE_CASE=512		,				_SCREAMING_SNAKE_CASE=16		,				_SCREAMING_SNAKE_CASE=2		,				_SCREAMING_SNAKE_CASE=0.02		,				_SCREAMING_SNAKE_CASE=3		,				_SCREAMING_SNAKE_CASE=4		,				_SCREAMING_SNAKE_CASE=None		,				) ->				Optional[int]:
								snake_case_				:							Optional[int]						 =       parent
								snake_case_				:							List[str]						 =       batch_size
								snake_case_				:							Optional[int]						 =       seq_length
								snake_case_				:							Tuple						 =       is_training
								snake_case_				:							Optional[int]						 =       use_input_mask
								snake_case_				:							Optional[int]						 =       use_token_type_ids
								snake_case_				:							str						 =       use_labels
								snake_case_				:							Union[str, Any]						 =       vocab_size
								snake_case_				:							Tuple						 =       hidden_size
								snake_case_				:							Tuple						 =       embedding_size
								snake_case_				:							Tuple						 =       num_hidden_layers
								snake_case_				:							int						 =       num_attention_heads
								snake_case_				:							Optional[int]						 =       intermediate_size
								snake_case_				:							int						 =       hidden_act
								snake_case_				:							Optional[Any]						 =       hidden_dropout_prob
								snake_case_				:							str						 =       attention_probs_dropout_prob
								snake_case_				:							List[str]						 =       max_position_embeddings
								snake_case_				:							Union[str, Any]						 =       type_vocab_size
								snake_case_				:							Union[str, Any]						 =       type_sequence_label_size
								snake_case_				:							List[str]						 =       initializer_range
								snake_case_				:							List[Any]						 =       num_labels
								snake_case_				:							Optional[int]						 =       num_choices
								snake_case_				:							List[Any]						 =       scope






						def       _lowerCAmelCase       (	self				) ->				Optional[Any]:
								snake_case_				:							List[str]						 =       ids_tensor([self.batch_size, self.seq_length]		,				self.vocab_size				)

								snake_case_				:							Dict						 =       None
								if self.use_input_mask:
										snake_case_				:							Optional[Any]						 =       random_attention_mask([self.batch_size, self.seq_length]				)

								snake_case_				:							Any						 =       None
								if self.use_token_type_ids:
										snake_case_				:							Dict						 =       ids_tensor([self.batch_size, self.seq_length]		,				self.type_vocab_size				)

								snake_case_				:							Tuple						 =       None
								snake_case_				:							Any						 =       None
								snake_case_				:							Optional[Any]						 =       None
								if self.use_labels:
										snake_case_				:							Optional[int]						 =       ids_tensor([self.batch_size]		,				self.type_sequence_label_size				)
										snake_case_				:							List[str]						 =       ids_tensor([self.batch_size, self.seq_length]		,				self.num_labels				)
										snake_case_				:							Tuple						 =       ids_tensor([self.batch_size]		,				self.num_choices				)

								snake_case_				:							str						 =       self.get_config()

								return config, input_ids, token_type_ids, input_mask, sequence_labels, token_labels, choice_labels






						def       _lowerCAmelCase       (	self				) ->				List[str]:
								return MegatronBertConfig(
								    vocab_size=self.vocab_size		,				hidden_size=self.hidden_size		,				num_hidden_layers=self.num_hidden_layers		,				num_attention_heads=self.num_attention_heads		,				intermediate_size=self.intermediate_size		,				embedding_size=self.embedding_size		,				hidden_act=self.hidden_act		,				hidden_dropout_prob=self.hidden_dropout_prob		,				attention_probs_dropout_prob=self.attention_probs_dropout_prob		,				max_position_embeddings=self.max_position_embeddings		,				type_vocab_size=self.type_vocab_size		,				is_decoder=lowerCAmelCase_		,				initializer_range=self.initializer_range		,				)






						def       _lowerCAmelCase       (	self		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE				) ->				Dict:
								snake_case_				:							Any						 =       MegatronBertModel(config=lowerCAmelCase_				)
								model.to(lowerCAmelCase_				)
								model.eval()
								snake_case_				:							Optional[int]						 =       model(lowerCAmelCase_		,				attention_mask=lowerCAmelCase_		,				token_type_ids=lowerCAmelCase_				)
								snake_case_				:							Dict						 =       model(lowerCAmelCase_		,				token_type_ids=lowerCAmelCase_				)
								snake_case_				:							List[Any]						 =       model(lowerCAmelCase_				)

								self.parent.assertEqual(result.last_hidden_state.shape		,				(self.batch_size, self.seq_length, self.hidden_size)				)
								self.parent.assertEqual(result.pooler_output.shape		,				(self.batch_size, self.hidden_size)				)






						def       _lowerCAmelCase       (	self		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE				) ->				List[Any]:
								snake_case_				:							List[str]						 =       MegatronBertForMaskedLM(config=lowerCAmelCase_				)
								model.to(lowerCAmelCase_				)
								model.eval()
								snake_case_				:							str						 =       model(lowerCAmelCase_		,				attention_mask=lowerCAmelCase_		,				token_type_ids=lowerCAmelCase_		,				labels=lowerCAmelCase_				)
								self.parent.assertEqual(result.logits.shape		,				(self.batch_size, self.seq_length, self.vocab_size)				)






						def       _lowerCAmelCase       (	self		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE				) ->				Union[str, Any]:
								snake_case_				:							Any						 =       MegatronBertForCausalLM(config=lowerCAmelCase_				)
								model.to(lowerCAmelCase_				)
								model.eval()
								snake_case_				:							Dict						 =       model(lowerCAmelCase_		,				attention_mask=lowerCAmelCase_		,				token_type_ids=lowerCAmelCase_		,				labels=lowerCAmelCase_				)
								self.parent.assertEqual(result.logits.shape		,				(self.batch_size, self.seq_length, self.vocab_size)				)






						def       _lowerCAmelCase       (	self		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE				) ->				int:
								snake_case_				:							Optional[int]						 =       MegatronBertForNextSentencePrediction(config=lowerCAmelCase_				)
								model.to(lowerCAmelCase_				)
								model.eval()
								snake_case_				:							Union[str, Any]						 =       model(
								    lowerCAmelCase_		,				attention_mask=lowerCAmelCase_		,				token_type_ids=lowerCAmelCase_		,				labels=lowerCAmelCase_		,				)
								self.parent.assertEqual(result.logits.shape		,				(self.batch_size, 2)				)






						def       _lowerCAmelCase       (	self		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE				) ->				int:
								snake_case_				:							List[str]						 =       MegatronBertForPreTraining(config=lowerCAmelCase_				)
								model.to(lowerCAmelCase_				)
								model.eval()
								snake_case_				:							Tuple						 =       model(
								    lowerCAmelCase_		,				attention_mask=lowerCAmelCase_		,				token_type_ids=lowerCAmelCase_		,				labels=lowerCAmelCase_		,				next_sentence_label=lowerCAmelCase_		,				)
								self.parent.assertEqual(result.prediction_logits.shape		,				(self.batch_size, self.seq_length, self.vocab_size)				)
								self.parent.assertEqual(result.seq_relationship_logits.shape		,				(self.batch_size, 2)				)






						def       _lowerCAmelCase       (	self		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE				) ->				Optional[int]:
								snake_case_				:							Tuple						 =       MegatronBertForQuestionAnswering(config=lowerCAmelCase_				)
								model.to(lowerCAmelCase_				)
								model.eval()
								snake_case_				:							Optional[Any]						 =       model(
								    lowerCAmelCase_		,				attention_mask=lowerCAmelCase_		,				token_type_ids=lowerCAmelCase_		,				start_positions=lowerCAmelCase_		,				end_positions=lowerCAmelCase_		,				)
								self.parent.assertEqual(result.start_logits.shape		,				(self.batch_size, self.seq_length)				)
								self.parent.assertEqual(result.end_logits.shape		,				(self.batch_size, self.seq_length)				)






						def       _lowerCAmelCase       (	self		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE				) ->				str:
								snake_case_				:							Optional[int]						 =       self.num_labels
								snake_case_				:							int						 =       MegatronBertForSequenceClassification(lowerCAmelCase_				)
								model.to(lowerCAmelCase_				)
								model.eval()
								snake_case_				:							List[str]						 =       model(lowerCAmelCase_		,				attention_mask=lowerCAmelCase_		,				token_type_ids=lowerCAmelCase_		,				labels=lowerCAmelCase_				)
								self.parent.assertEqual(result.logits.shape		,				(self.batch_size, self.num_labels)				)






						def       _lowerCAmelCase       (	self		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE				) ->				Any:
								snake_case_				:							Optional[int]						 =       self.num_labels
								snake_case_				:							str						 =       MegatronBertForTokenClassification(config=lowerCAmelCase_				)
								model.to(lowerCAmelCase_				)
								model.eval()
								snake_case_				:							Union[str, Any]						 =       model(lowerCAmelCase_		,				attention_mask=lowerCAmelCase_		,				token_type_ids=lowerCAmelCase_		,				labels=lowerCAmelCase_				)
								self.parent.assertEqual(result.logits.shape		,				(self.batch_size, self.seq_length, self.num_labels)				)






						def       _lowerCAmelCase       (	self		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE				) ->				Tuple:
								snake_case_				:							Tuple						 =       self.num_choices
								snake_case_				:							List[Any]						 =       MegatronBertForMultipleChoice(config=lowerCAmelCase_				)
								model.to(lowerCAmelCase_				)
								model.eval()
								snake_case_				:							Dict						 =       input_ids.unsqueeze(1				).expand(-1		,				self.num_choices		,				-1				).contiguous()
								snake_case_				:							Optional[Any]						 =       token_type_ids.unsqueeze(1				).expand(-1		,				self.num_choices		,				-1				).contiguous()
								snake_case_				:							List[Any]						 =       input_mask.unsqueeze(1				).expand(-1		,				self.num_choices		,				-1				).contiguous()
								snake_case_				:							Union[str, Any]						 =       model(
								    lowerCAmelCase_		,				attention_mask=lowerCAmelCase_		,				token_type_ids=lowerCAmelCase_		,				labels=lowerCAmelCase_		,				)
								self.parent.assertEqual(result.logits.shape		,				(self.batch_size, self.num_choices)				)






						def       _lowerCAmelCase       (	self				) ->				List[str]:
								snake_case_				:							Any						 =       self.prepare_config_and_inputs()
								(
								    (
								    snake_case_						
								) ,       (
								    snake_case_						
								) ,       (
								    snake_case_						
								) ,       (
								    snake_case_						
								) ,       (
								    snake_case_						
								) ,       (
								    snake_case_						
								) ,       (
								    snake_case_						
								) ,       						
								)				:							Dict						 =       config_and_inputs
								snake_case_				:							Dict						 =       {"input_ids": input_ids, "token_type_ids": token_type_ids, "attention_mask": input_mask}
								return config, inputs_dict




@require_torch
class 		UpperCAmelCase_						(	__a					,  __a					,  unittest.TestCase					):


						'''simple docstring'''




						A     :   int						=					(
						    (
						        MegatronBertModel,
						        MegatronBertForMaskedLM,
						        MegatronBertForCausalLM,
						        MegatronBertForMultipleChoice,
						        MegatronBertForNextSentencePrediction,
						        MegatronBertForPreTraining,
						        MegatronBertForQuestionAnswering,
						        MegatronBertForSequenceClassification,
						        MegatronBertForTokenClassification,
						    )
						    if is_torch_available()
						    else ()
						)
						A     :   Dict						=					(
						    {
						        "feature-extraction": MegatronBertModel,
						        "fill-mask": MegatronBertForMaskedLM,
						        "question-answering": MegatronBertForQuestionAnswering,
						        "text-classification": MegatronBertForSequenceClassification,
						        "text-generation": MegatronBertForCausalLM,
						        "token-classification": MegatronBertForTokenClassification,
						        "zero-shot": MegatronBertForSequenceClassification,
						    }
						    if is_torch_available()
						    else {}
						)
						A     :   Optional[int]						=					True
						# test_resize_embeddings = False
						A     :   str						=					False






						def       _lowerCAmelCase       (	self		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE		,				_SCREAMING_SNAKE_CASE=False				) ->				str:
								snake_case_				:							Dict						 =       super()._prepare_for_class(lowerCAmelCase_		,				lowerCAmelCase_		,				return_labels=lowerCAmelCase_				)

								if return_labels:
										if model_class in get_values(lowerCAmelCase_				):
												snake_case_				:							int						 =       torch.zeros(
												    (self.model_tester.batch_size, self.model_tester.seq_length)		,				dtype=torch.long		,				device=lowerCAmelCase_				)
												snake_case_				:							List[Any]						 =       torch.zeros(
												    self.model_tester.batch_size		,				dtype=torch.long		,				device=lowerCAmelCase_				)
								return inputs_dict






						def       _lowerCAmelCase       (	self				) ->				Tuple:
								snake_case_				:							List[Any]						 =       MegatronBertModelTester(self				)
								snake_case_				:							int						 =       ConfigTester(self		,				config_class=lowerCAmelCase_		,				hidden_size=37				)






						def       _lowerCAmelCase       (	self				) ->				List[str]:
								self.config_tester.run_common_tests()






						def       _lowerCAmelCase       (	self				) ->				Optional[int]:
								snake_case_				:							str						 =       self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_megatron_bert_model(*lowerCAmelCase_				)






						def       _lowerCAmelCase       (	self				) ->				int:
								snake_case_				:							Tuple						 =       self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_megatron_bert_for_masked_lm(*lowerCAmelCase_				)






						def       _lowerCAmelCase       (	self				) ->				int:
								snake_case_				:							Union[str, Any]						 =       self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_megatron_bert_for_multiple_choice(*lowerCAmelCase_				)






						def       _lowerCAmelCase       (	self				) ->				int:
								snake_case_				:							Any						 =       self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_megatron_bert_for_next_sequence_prediction(*lowerCAmelCase_				)






						def       _lowerCAmelCase       (	self				) ->				List[str]:
								snake_case_				:							Dict						 =       self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_megatron_bert_for_pretraining(*lowerCAmelCase_				)






						def       _lowerCAmelCase       (	self				) ->				Optional[Any]:
								snake_case_				:							List[Any]						 =       self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_megatron_bert_for_question_answering(*lowerCAmelCase_				)






						def       _lowerCAmelCase       (	self				) ->				str:
								snake_case_				:							Any						 =       self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_megatron_bert_for_sequence_classification(*lowerCAmelCase_				)






						def       _lowerCAmelCase       (	self				) ->				List[Any]:
								snake_case_				:							Union[str, Any]						 =       self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_megatron_bert_for_token_classification(*lowerCAmelCase_				)




def      lowerCAmelCase__	(    _a       :			Optional[int]    ):
		return torch.tensor(
		    lowercase__  ,      dtype=torch.long  ,      device=lowercase__  ,      )


lowercase  :							Dict			  =    1e-4




@require_torch
@require_sentencepiece
@require_tokenizers
class 		UpperCAmelCase_						(	unittest.TestCase					):


						'''simple docstring'''




						@slow
						@unittest.skip("Model is not available."				)
						def       _lowerCAmelCase       (	self				) ->				Tuple:
								snake_case_				:							List[Any]						 =       "nvidia/megatron-bert-uncased-345m"
								if "MYDIR" in os.environ:
										snake_case_				:							Tuple						 =       os.path.join(os.environ["MYDIR"]		,				lowerCAmelCase_				)
								snake_case_				:							Union[str, Any]						 =       MegatronBertModel.from_pretrained(lowerCAmelCase_				)
								model.to(lowerCAmelCase_				)
								model.half()
								snake_case_				:							Optional[Any]						 =       _long_tensor([[101, 7110, 1005, 1056, 2023, 1_1333, 1_7413, 1029, 102]]				)
								with torch.no_grad():
										snake_case_				:							int						 =       model(lowerCAmelCase_				)[0]
								snake_case_				:							Optional[Any]						 =       torch.Size((1, 9, 1024)				)
								self.assertEqual(output.shape		,				lowerCAmelCase_				)

								snake_case_				:							Union[str, Any]						 =       [-0.6040, -0.2517, -0.1025, 0.3420, -0.6758, -0.0017, -0.1089, -0.1990, 0.5728]
								for ii in range(3				):
										for jj in range(3				):
												snake_case_				:							List[Any]						 =       output[0, ii, jj]
												snake_case_				:							str						 =       expected[3 * ii + jj]
												snake_case_				:							Optional[Any]						 =       "ii={} jj={} a={} b={}".format(lowerCAmelCase_		,				lowerCAmelCase_		,				lowerCAmelCase_		,				lowerCAmelCase_				)
												self.assertTrue(math.isclose(lowerCAmelCase_		,				lowerCAmelCase_		,				rel_tol=lowerCAmelCase_		,				abs_tol=lowerCAmelCase_				)		,				msg=lowerCAmelCase_				)








import heapq
import sys

import numpy as np

lowercase  :							str			  =    tuple[int, int]




class 		UpperCAmelCase_						:


						'''simple docstring'''




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






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






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






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






						def       _lowerCAmelCase       (	self		,				_SCREAMING_SNAKE_CASE				) ->				Any:
								if item in self.set:
										self.set.remove(_SCREAMING_SNAKE_CASE				)
										snake_case_				:							Optional[Any]						 =       []
										((snake_case_) ,       (snake_case_))				:							Tuple						 =       heapq.heappop(self.elements				)
										while x != item:
												temp.append((pro, x)				)
												((snake_case_) ,       (snake_case_))				:							Dict						 =       heapq.heappop(self.elements				)
										for prito, yyy in temp:
												heapq.heappush(self.elements		,				(prito, yyy)				)






						def       _lowerCAmelCase       (	self				) ->				Optional[Any]:
								return self.elements[0][1]






						def       _lowerCAmelCase       (	self				) ->				Optional[int]:
								((snake_case_) ,       (snake_case_))				:							Any						 =       heapq.heappop(self.elements				)
								self.set.remove(_SCREAMING_SNAKE_CASE				)
								return (priority, item)




def      lowerCAmelCase__	(    _a       :			TPos  ,      _a       :			TPos    ):
		# euclidean distance
		snake_case_				:							Optional[Any]						 =       np.array(_a    )
		snake_case_				:							Dict						 =       np.array(_a    )
		return np.linalg.norm(a - b    )

def      lowerCAmelCase__	(    _a       :			TPos  ,      _a       :			TPos    ):
		# integer division by time variable
		return consistent_heuristic(_a  ,      _a    ) // t

def      lowerCAmelCase__	(    _a       :			TPos  ,      _a       :			TPos    ):
		# manhattan distance
		return abs(p[0] - goal[0]    ) + abs(p[1] - goal[1]    )

def      lowerCAmelCase__	(    _a       :			TPos  ,      _a       :			int  ,      _a       :			TPos  ,      _a       :			dict[TPos, float]    ):
		snake_case_				:							List[Any]						 =       g_function[start] + Wa * heuristics[i](_a  ,      _a    )
		return ans

def      lowerCAmelCase__	(    _a       :			Tuple  ,      _a       :			Union[str, Any]  ,      _a       :			List[Any]    ):
		snake_case_				:							Dict						 =       np.chararray((n, n)    )
		for i in range(_a    ):
				for j in range(_a    ):
						snake_case_				:							List[str]						 =       "*"

		for i in range(_a    ):
				for j in range(_a    ):
						if (j, (n - 1) - i) in blocks:
								snake_case_				:							Optional[Any]						 =       "#"

		snake_case_				:							Optional[int]						 =       "-"
		snake_case_				:							Tuple						 =       back_pointer[goal]
		while x != start:
				((snake_case_) ,       (snake_case_))				:							Any						 =       x
				# print(x)
				snake_case_				:							List[str]						 =       "-"
				snake_case_				:							Dict						 =       back_pointer[x]
		snake_case_				:							str						 =       "-"

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

def      lowerCAmelCase__	(    _a       :			TPos    ):
		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__	(    _a       :			int  ,      _a       :			str  ,      _a       :			Optional[int]  ,      _a       :			List[str]  ,      _a       :			Optional[Any]  ,      _a       :			Dict  ,      _a       :			Tuple  ,      _a       :			Any  ,      ):
		for itera in range(_a    ):
				open_list[itera].remove_element(_a    )
		# print("s", s)
		# print("j", j)
		((snake_case_) ,       (snake_case_))				:							Tuple						 =       s
		snake_case_				:							Dict						 =       (x - 1, y)
		snake_case_				:							Union[str, Any]						 =       (x + 1, y)
		snake_case_				:							List[str]						 =       (x, y + 1)
		snake_case_				:							int						 =       (x, y - 1)

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

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

def      lowerCAmelCase__	(    ):
		snake_case_				:							Union[str, Any]						 =       []
		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


lowercase  :							Union[str, Any]			  =    {0: consistent_heuristic, 1: heuristic_a, 2: heuristic_a}

lowercase  :							Union[str, 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),
]
lowercase  :							int			  =    make_common_ground()


lowercase  :							Optional[Any]			  =    blocks_blk
# hyper parameters
lowercase  :							Optional[Any]			  =    1
lowercase  :							str			  =    1
lowercase  :							Any			  =    20
lowercase  :							str			  =    3  # one consistent and two other inconsistent

# start and end destination
lowercase  :							Any			  =    (0, 0)
lowercase  :							int			  =    (n - 1, n - 1)

lowercase  :							str			  =    1

def      lowerCAmelCase__	(    _a       :			TPos  ,      _a       :			TPos  ,      _a       :			int    ):
		snake_case_				:							List[str]						 =       {start: 0, goal: float("inf"    )}
		snake_case_				:							List[Any]						 =       {start: -1, goal: -1}
		snake_case_				:							Optional[Any]						 =       []
		snake_case_				:							Dict						 =       set()

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

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