




'''simple docstring'''





import heapq
import sys

import numpy as np

_SCREAMING_SNAKE_CASE							:   Optional[int]      		= tuple[int, int]




class  _snake_case		:




			def __init__(					self							)				->				List[Any]:

										'''simple docstring'''




										snake_case_						=      []
										snake_case_						=      set()




			def    lowerCAmelCase__				(					self							)				->				Optional[int]:

										'''simple docstring'''




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




			def    lowerCAmelCase__				(					self							)				->				List[str]:

										'''simple docstring'''




										return len(self.elements							) == 0




			def    lowerCAmelCase__				(					self				,							a__				,							a__							)				->				List[str]:

										'''simple docstring'''




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




			def    lowerCAmelCase__				(					self				,							a__							)				->				int:

										'''simple docstring'''




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




			def    lowerCAmelCase__				(					self							)				->				List[str]:

										'''simple docstring'''




										return self.elements[0][1]




			def    lowerCAmelCase__				(					self							)				->				Optional[int]:

										'''simple docstring'''




										((snake_case_)					,      (snake_case_))						=      heapq.heappop(self.elements							)
										self.set.remove(a__							)
										return (priority, item)


def      UpperCamelCase_(	snake_case							:       TPos							,				snake_case							:       TPos     ):

							'''simple docstring'''






							snake_case_						=      np.array(snake_case     )
							snake_case_						=      np.array(snake_case     )
							return np.linalg.norm(a - b     )


def      UpperCamelCase_(	snake_case							:       TPos							,				snake_case							:       TPos     ):

							'''simple docstring'''






							return consistent_heuristic(snake_case							,				snake_case     ) // t


def      UpperCamelCase_(	snake_case							:       TPos							,				snake_case							:       TPos     ):

							'''simple docstring'''






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


def      UpperCamelCase_(	snake_case							:       TPos							,				snake_case							:       int							,				snake_case							:       TPos							,				snake_case							:       dict[TPos, float]     ):

							'''simple docstring'''






							snake_case_						=      g_function[start] + Wa * heuristics[i](snake_case							,				snake_case     )
							return ans


def      UpperCamelCase_(	snake_case							:       List[Any]							,				snake_case							:       List[Any]							,				snake_case							:       int     ):

							'''simple docstring'''






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

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

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

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


def      UpperCamelCase_(	snake_case							:       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      UpperCamelCase_(	snake_case							:       List[Any]							,				snake_case							:       int							,				snake_case							:       Tuple							,				snake_case							:       int							,				snake_case							:       List[str]							,				snake_case							:       Tuple							,				snake_case							:       Dict							,				snake_case							:       Dict							,				):

							'''simple docstring'''






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

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

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


def      UpperCamelCase_(	):

							'''simple docstring'''






							snake_case_						=      []
							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


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

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


_SCREAMING_SNAKE_CASE							:   List[str]      		= blocks_blk
# hyper parameters
_SCREAMING_SNAKE_CASE							:   Tuple      		= 1
_SCREAMING_SNAKE_CASE							:   Optional[int]      		= 1
_SCREAMING_SNAKE_CASE							:   int      		= 20
_SCREAMING_SNAKE_CASE							:   Tuple      		= 3  # one consistent and two other inconsistent

# start and end destination
_SCREAMING_SNAKE_CASE							:   List[str]      		= (0, 0)
_SCREAMING_SNAKE_CASE							:   Optional[int]      		= (n - 1, n - 1)

_SCREAMING_SNAKE_CASE							:   Tuple      		= 1


def      UpperCamelCase_(	snake_case							:       TPos							,				snake_case							:       TPos							,				snake_case							:       int     ):

							'''simple docstring'''






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

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

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









"""simple docstring"""






from collections import OrderedDict
from typing import TYPE_CHECKING, Any, Mapping, Optional, Union

from ...configuration_utils import PretrainedConfig
from ...onnx import OnnxConfig, OnnxSeqaSeqConfigWithPast
from ...utils import logging


if TYPE_CHECKING:
	from ...feature_extraction_utils import FeatureExtractionMixin
	from ...tokenization_utils_base import PreTrainedTokenizerBase
	from ...utils import TensorType

__snake_case							:   Optional[Any]      =    logging.get_logger(__name__)

__snake_case							:   Optional[Any]      =    {
    'openai/whisper-base': 'https://huggingface.co/openai/whisper-base/resolve/main/config.json',
}

# fmt: off
__snake_case							:   Any      =    [
    1, 2, 7, 8, 9, 10, 14, 25,
    26, 27, 28, 29, 31, 58, 59, 60, 61, 62,
    63, 90, 91, 92, 93, 357, 366, 438, 532, 685,
    705, 796, 930, 1_058, 1_220, 1_267, 1_279, 1_303, 1_343, 1_377,
    1_391, 1_635, 1_782, 1_875, 2_162, 2_361, 2_488, 3_467, 4_008, 4_211,
    4_600, 4_808, 5_299, 5_855, 6_329, 7_203, 9_609, 9_959, 10_563, 10_786,
    11_420, 11_709, 11_907, 13_163, 13_697, 13_700, 14_808, 15_306, 16_410, 16_791,
    17_992, 19_203, 19_510, 20_724, 22_305, 22_935, 27_007, 30_109, 30_420, 33_409,
    34_949, 40_283, 40_493, 40_549, 47_282, 49_146, 50_257, 50_359, 50_360, 50_361
]
__snake_case							:   str      =    [
    1, 2, 7, 8, 9, 10, 14, 25,
    26, 27, 28, 29, 31, 58, 59, 60, 61, 62,
    63, 90, 91, 92, 93, 359, 503, 522, 542, 873,
    893, 902, 918, 922, 931, 1_350, 1_853, 1_982, 2_460, 2_627,
    3_246, 3_253, 3_268, 3_536, 3_846, 3_961, 4_183, 4_667, 6_585, 6_647,
    7_273, 9_061, 9_383, 10_428, 10_929, 11_938, 12_033, 12_331, 12_562, 13_793,
    14_157, 14_635, 15_265, 15_618, 16_553, 16_604, 18_362, 18_956, 20_075, 21_675,
    22_520, 26_130, 26_161, 26_435, 28_279, 29_464, 31_650, 32_302, 32_470, 36_865,
    42_863, 47_425, 49_870, 50_254, 50_258, 50_360, 50_361, 50_362
]



class 			A__   (  __SCREAMING_SNAKE_CASE							):




	'''simple docstring'''





	SCREAMING_SNAKE_CASE          =	'whisper'
	SCREAMING_SNAKE_CASE          =	['past_key_values']
	SCREAMING_SNAKE_CASE          =	{'num_attention_heads': 'encoder_attention_heads', 'hidden_size': 'd_model'}

	def __init__(     self:		Optional[int]       ,			_SCREAMING_SNAKE_CASE:		Any=5_1865       ,			_SCREAMING_SNAKE_CASE:		Optional[Any]=80       ,			_SCREAMING_SNAKE_CASE:		Optional[int]=6       ,			_SCREAMING_SNAKE_CASE:		Any=4       ,			_SCREAMING_SNAKE_CASE:		Dict=6       ,			_SCREAMING_SNAKE_CASE:		Dict=4       ,			_SCREAMING_SNAKE_CASE:		Optional[Any]=1536       ,			_SCREAMING_SNAKE_CASE:		List[str]=1536       ,			_SCREAMING_SNAKE_CASE:		Optional[Any]=0.0       ,			_SCREAMING_SNAKE_CASE:		str=0.0       ,			_SCREAMING_SNAKE_CASE:		List[str]=5_0257       ,			_SCREAMING_SNAKE_CASE:		Optional[Any]=True       ,			_SCREAMING_SNAKE_CASE:		List[str]=True       ,			_SCREAMING_SNAKE_CASE:		Optional[int]="gelu"       ,			_SCREAMING_SNAKE_CASE:		Tuple=256       ,			_SCREAMING_SNAKE_CASE:		str=0.0       ,			_SCREAMING_SNAKE_CASE:		Optional[Any]=0.0       ,			_SCREAMING_SNAKE_CASE:		Optional[Any]=0.0       ,			_SCREAMING_SNAKE_CASE:		List[Any]=0.02       ,			_SCREAMING_SNAKE_CASE:		Tuple=False       ,			_SCREAMING_SNAKE_CASE:		Union[str, Any]=1500       ,			_SCREAMING_SNAKE_CASE:		str=448       ,			_SCREAMING_SNAKE_CASE:		Any=5_0256       ,			_SCREAMING_SNAKE_CASE:		Any=5_0256       ,			_SCREAMING_SNAKE_CASE:		List[str]=5_0256       ,			_SCREAMING_SNAKE_CASE:		Dict=None       ,			_SCREAMING_SNAKE_CASE:		List[Any]=[220, 5_0256]       ,			_SCREAMING_SNAKE_CASE:		Dict=False       ,			_SCREAMING_SNAKE_CASE:		str=256       ,			_SCREAMING_SNAKE_CASE:		List[str]=False       ,			_SCREAMING_SNAKE_CASE:		Tuple=0.05       ,			_SCREAMING_SNAKE_CASE:		List[str]=10       ,			_SCREAMING_SNAKE_CASE:		str=2       ,			_SCREAMING_SNAKE_CASE:		Any=0.0       ,			_SCREAMING_SNAKE_CASE:		Optional[int]=10       ,			_SCREAMING_SNAKE_CASE:		int=0       ,			_SCREAMING_SNAKE_CASE:		Any=7       ,			**_SCREAMING_SNAKE_CASE:		List[str]       ,			)				->       List[Any]:

				"""simple docstring"""

				__lowerCAmelCase      :  Optional[int]												=       vocab_size
				__lowerCAmelCase      :  Optional[Any]												=       num_mel_bins
				__lowerCAmelCase      :  int												=       d_model
				__lowerCAmelCase      :  List[Any]												=       encoder_layers
				__lowerCAmelCase      :  List[Any]												=       encoder_attention_heads
				__lowerCAmelCase      :  List[str]												=       decoder_layers
				__lowerCAmelCase      :  Tuple												=       decoder_attention_heads
				__lowerCAmelCase      :  Any												=       decoder_ffn_dim
				__lowerCAmelCase      :  Tuple												=       encoder_ffn_dim
				__lowerCAmelCase      :  List[str]												=       dropout
				__lowerCAmelCase      :  Union[str, Any]												=       attention_dropout
				__lowerCAmelCase      :  Union[str, Any]												=       activation_dropout
				__lowerCAmelCase      :  Dict												=       activation_function
				__lowerCAmelCase      :  Tuple												=       init_std
				__lowerCAmelCase      :  str												=       encoder_layerdrop
				__lowerCAmelCase      :  int												=       decoder_layerdrop
				__lowerCAmelCase      :  Optional[int]												=       use_cache
				__lowerCAmelCase      :  Union[str, Any]												=       encoder_layers
				__lowerCAmelCase      :  List[str]												=       scale_embedding  # scale factor will be sqrt(d_model) if True
				__lowerCAmelCase      :  int												=       max_source_positions
				__lowerCAmelCase      :  Any												=       max_target_positions

				# Audio Classification-specific parameters. Feel free to ignore for other classes.
				__lowerCAmelCase      :  Dict												=       classifier_proj_size
				__lowerCAmelCase      :  Dict												=       use_weighted_layer_sum

				# fine-tuning config parameters for SpecAugment: https://arxiv.org/abs/1904.08779
				__lowerCAmelCase      :  int												=       apply_spec_augment
				__lowerCAmelCase      :  Union[str, Any]												=       mask_time_prob
				__lowerCAmelCase      :  str												=       mask_time_length
				__lowerCAmelCase      :  int												=       mask_time_min_masks
				__lowerCAmelCase      :  List[Any]												=       mask_feature_prob
				__lowerCAmelCase      :  Tuple												=       mask_feature_length
				__lowerCAmelCase      :  Any												=       mask_feature_min_masks

				__lowerCAmelCase      :  Union[str, Any]												=       median_filter_width

				super().__init__(
				    pad_token_id=_SCREAMING_SNAKE_CASE       ,			bos_token_id=_SCREAMING_SNAKE_CASE       ,			eos_token_id=_SCREAMING_SNAKE_CASE       ,			is_encoder_decoder=_SCREAMING_SNAKE_CASE       ,			decoder_start_token_id=_SCREAMING_SNAKE_CASE       ,			suppress_tokens=_SCREAMING_SNAKE_CASE       ,			begin_suppress_tokens=_SCREAMING_SNAKE_CASE       ,			**_SCREAMING_SNAKE_CASE       ,			)






class 			A__   (  __SCREAMING_SNAKE_CASE							):




	'''simple docstring'''





	@property
	def 							_SCREAMING_SNAKE_CASE   (     self:		List[Any])				->       Mapping[str, Mapping[int, str]]:

				"""simple docstring"""

				__lowerCAmelCase      :  List[str]												=       OrderedDict(
				    [
				        ("input_features", {0: "batch", 1: "feature_size", 2: "encoder_sequence"}),
				    ])
				if self.use_past:
							__lowerCAmelCase      :  Tuple												=       {0: "batch"}
				else:
							__lowerCAmelCase      :  Union[str, Any]												=       {0: "batch", 1: "decoder_sequence"}

				if self.use_past:
							self.fill_with_past_key_values_(_SCREAMING_SNAKE_CASE       ,			direction="inputs")

				return common_inputs

	def 							_SCREAMING_SNAKE_CASE   (     self:		Any       ,			_SCREAMING_SNAKE_CASE:		Union["PreTrainedTokenizerBase", "FeatureExtractionMixin"]       ,			_SCREAMING_SNAKE_CASE:		int = -1       ,			_SCREAMING_SNAKE_CASE:		int = -1       ,			_SCREAMING_SNAKE_CASE:		bool = False       ,			_SCREAMING_SNAKE_CASE:		Optional["TensorType"] = None       ,			_SCREAMING_SNAKE_CASE:		int = 2_2050       ,			_SCREAMING_SNAKE_CASE:		float = 5.0       ,			_SCREAMING_SNAKE_CASE:		int = 220       ,			)				->       Mapping[str, Any]:

				"""simple docstring"""

				__lowerCAmelCase      :  int												=       OrderedDict()
				__lowerCAmelCase      :  Optional[Any]												=       OnnxConfig.generate_dummy_inputs(
				    self       ,			preprocessor=preprocessor.feature_extractor       ,			batch_size=_SCREAMING_SNAKE_CASE       ,			framework=_SCREAMING_SNAKE_CASE       ,			sampling_rate=_SCREAMING_SNAKE_CASE       ,			time_duration=_SCREAMING_SNAKE_CASE       ,			frequency=_SCREAMING_SNAKE_CASE       ,			)
				__lowerCAmelCase      :  List[str]												=       encoder_inputs["input_features"].shape[2]
				__lowerCAmelCase      :  List[str]												=       encoder_sequence_length // 2 if self.use_past else seq_length

				__lowerCAmelCase      :  List[Any]												=       super().generate_dummy_inputs(
				    preprocessor.tokenizer       ,			_SCREAMING_SNAKE_CASE       ,			_SCREAMING_SNAKE_CASE       ,			_SCREAMING_SNAKE_CASE       ,			_SCREAMING_SNAKE_CASE)

				__lowerCAmelCase      :  List[str]												=       encoder_inputs.pop("input_features")
				__lowerCAmelCase      :  List[Any]												=       decoder_inputs.pop("decoder_input_ids")

				if "past_key_values" in decoder_inputs:
							__lowerCAmelCase      :  int												=       decoder_inputs.pop("past_key_values")

				return dummy_inputs







	@property
	def 							_SCREAMING_SNAKE_CASE   (     self:		Union[str, Any])				->       float:

				"""simple docstring"""

				return 1e-3