



'''simple docstring'''

import copy
import inspect
import unittest

import numpy as np
from huggingface_hub import hf_hub_download

from transformers import VideoMAEConfig
from transformers.models.auto import get_values
from transformers.testing_utils import require_torch, require_vision, slow, torch_device
from transformers.utils import cached_property, is_torch_available, is_vision_available

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


if is_torch_available():
	import torch
	from torch import nn

	from transformers import (
	    MODEL_FOR_VIDEO_CLASSIFICATION_MAPPING,
	    VideoMAEForPreTraining,
	    VideoMAEForVideoClassification,
	    VideoMAEModel,
	)
	from transformers.models.videomae.modeling_videomae import VIDEOMAE_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
	from transformers import VideoMAEImageProcessor


class 	a__     :


	def __init__(self : Optional[Any],					__UpperCAmelCase : Union[str, Any],					__UpperCAmelCase : str=13,					__UpperCAmelCase : List[Any]=10,					__UpperCAmelCase : Any=3,					__UpperCAmelCase : Dict=2,					__UpperCAmelCase : int=2,					__UpperCAmelCase : List[Any]=2,					__UpperCAmelCase : Optional[int]=True,					__UpperCAmelCase : Union[str, Any]=True,					__UpperCAmelCase : int=32,					__UpperCAmelCase : Union[str, Any]=5,					__UpperCAmelCase : int=4,					__UpperCAmelCase : Tuple=37,					__UpperCAmelCase : Any="gelu",					__UpperCAmelCase : Union[str, Any]=0.1,					__UpperCAmelCase : int=0.1,					__UpperCAmelCase : int=10,					__UpperCAmelCase : Optional[Any]=0.02,					__UpperCAmelCase : int=0.9,					__UpperCAmelCase : Any=None,					)     ->			Optional[int]:

					"""simple docstring"""

					SCREAMING_SNAKE_CASE  :						str      					= parent
					SCREAMING_SNAKE_CASE  :						str      					= batch_size
					SCREAMING_SNAKE_CASE  :						int      					= image_size
					SCREAMING_SNAKE_CASE  :						List[str]      					= num_channels
					SCREAMING_SNAKE_CASE  :						List[str]      					= patch_size
					SCREAMING_SNAKE_CASE  :						Tuple      					= tubelet_size
					SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= num_frames
					SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= is_training
					SCREAMING_SNAKE_CASE  :						Optional[int]      					= use_labels
					SCREAMING_SNAKE_CASE  :						Tuple      					= hidden_size
					SCREAMING_SNAKE_CASE  :						Tuple      					= num_hidden_layers
					SCREAMING_SNAKE_CASE  :						Tuple      					= num_attention_heads
					SCREAMING_SNAKE_CASE  :						List[str]      					= intermediate_size
					SCREAMING_SNAKE_CASE  :						Optional[int]      					= hidden_act
					SCREAMING_SNAKE_CASE  :						Tuple      					= hidden_dropout_prob
					SCREAMING_SNAKE_CASE  :						Dict      					= attention_probs_dropout_prob
					SCREAMING_SNAKE_CASE  :						Dict      					= type_sequence_label_size
					SCREAMING_SNAKE_CASE  :						int      					= initializer_range
					SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= mask_ratio
					SCREAMING_SNAKE_CASE  :						Any      					= scope

					# in VideoMAE, the number of tokens equals num_frames/tubelet_size * num_patches per frame
					SCREAMING_SNAKE_CASE  :						List[Any]      					= (image_size // patch_size) ** 2
					SCREAMING_SNAKE_CASE  :						List[str]      					= (num_frames // tubelet_size) * self.num_patches_per_frame

					# use this variable to define bool_masked_pos
					SCREAMING_SNAKE_CASE  :						Optional[int]      					= int(mask_ratio * self.seq_length      )


	def 				lowercase__  (self : int      )     ->			Tuple:

					"""simple docstring"""

					SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= floats_tensor(
					    [self.batch_size, self.num_frames, self.num_channels, self.image_size, self.image_size]      )

					SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= None
					if self.use_labels:
									SCREAMING_SNAKE_CASE  :						Any      					= ids_tensor([self.batch_size],					self.type_sequence_label_size      )

					SCREAMING_SNAKE_CASE  :						List[str]      					= self.get_config()

					return config, pixel_values, labels


	def 				lowercase__  (self : str      )     ->			str:

					"""simple docstring"""

					return VideoMAEConfig(
					    image_size=self.image_size,					patch_size=self.patch_size,					num_channels=self.num_channels,					num_frames=self.num_frames,					tubelet_size=self.tubelet_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,					hidden_act=self.hidden_act,					hidden_dropout_prob=self.hidden_dropout_prob,					attention_probs_dropout_prob=self.attention_probs_dropout_prob,					is_decoder=__UpperCAmelCase,					initializer_range=self.initializer_range,					)


	def 				lowercase__  (self : Dict,					__UpperCAmelCase : int,					__UpperCAmelCase : Tuple,					__UpperCAmelCase : int      )     ->			Any:

					"""simple docstring"""

					SCREAMING_SNAKE_CASE  :						List[Any]      					= VideoMAEModel(config=__UpperCAmelCase      )
					model.to(__UpperCAmelCase      )
					model.eval()
					SCREAMING_SNAKE_CASE  :						str      					= model(__UpperCAmelCase      )
					self.parent.assertEqual(result.last_hidden_state.shape,					(self.batch_size, self.seq_length, self.hidden_size)      )


	def 				lowercase__  (self : Union[str, Any],					__UpperCAmelCase : Optional[int],					__UpperCAmelCase : Optional[int],					__UpperCAmelCase : Any      )     ->			Optional[int]:

					"""simple docstring"""

					SCREAMING_SNAKE_CASE  :						List[str]      					= VideoMAEForPreTraining(__UpperCAmelCase      )
					model.to(__UpperCAmelCase      )
					model.eval()
					# important: each video needs to have the same number of masked patches
					# hence we define a single mask, which we then repeat for each example in the batch
					SCREAMING_SNAKE_CASE  :						Tuple      					= torch.ones((self.num_masks,)      )
					SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= torch.cat([mask, torch.zeros(self.seq_length - mask.size(0      )      )]      )
					SCREAMING_SNAKE_CASE  :						Tuple      					= mask.expand(self.batch_size,					-1      ).bool()

					SCREAMING_SNAKE_CASE  :						Dict      					= model(__UpperCAmelCase,					__UpperCAmelCase      )
					# model only returns predictions for masked patches
					SCREAMING_SNAKE_CASE  :						Optional[Any]      					= mask.sum().item()
					SCREAMING_SNAKE_CASE  :						List[Any]      					= 3 * self.tubelet_size * self.patch_size**2
					self.parent.assertEqual(result.logits.shape,					(self.batch_size, num_masked_patches, decoder_num_labels)      )






	def 				lowercase__  (self : int      )     ->			Tuple:

					"""simple docstring"""

					SCREAMING_SNAKE_CASE  :						Dict      					= self.prepare_config_and_inputs()
					SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE  :						List[str]      					= config_and_inputs
					SCREAMING_SNAKE_CASE  :						str      					= {'''pixel_values''': pixel_values}
					return config, inputs_dict



@require_torch
class 	a__     (				_lowercase,			_lowercase,			unittest.TestCase	):
	__magic_name__		:    List[Any]	    =     (
	    (VideoMAEModel, VideoMAEForPreTraining, VideoMAEForVideoClassification) if is_torch_available() else ()
	)
	__magic_name__		:    Optional[int]	    =     (
	    {"feature-extraction": VideoMAEModel, "video-classification": VideoMAEForVideoClassification}
	    if is_torch_available()
	    else {}
	)

	__magic_name__		:    Optional[int]	    =     False
	__magic_name__		:    int	    =     False
	__magic_name__		:    List[Any]	    =     False
	__magic_name__		:    int	    =     False


	def 				lowercase__  (self : List[Any]      )     ->			List[str]:

					"""simple docstring"""

					SCREAMING_SNAKE_CASE  :						Optional[Any]      					= VideoMAEModelTester(self      )
					SCREAMING_SNAKE_CASE  :						str      					= ConfigTester(self,					config_class=__UpperCAmelCase,					has_text_modality=__UpperCAmelCase,					hidden_size=37      )


	def 				lowercase__  (self : Tuple,					__UpperCAmelCase : Any,					__UpperCAmelCase : Union[str, Any],					__UpperCAmelCase : int=False      )     ->			int:

					"""simple docstring"""

					SCREAMING_SNAKE_CASE  :						Tuple      					= copy.deepcopy(__UpperCAmelCase      )

					if model_class == VideoMAEForPreTraining:
									# important: each video needs to have the same number of masked patches
									# hence we define a single mask, which we then repeat for each example in the batch
									SCREAMING_SNAKE_CASE  :						Optional[Any]      					= torch.ones((self.model_tester.num_masks,)      )
									SCREAMING_SNAKE_CASE  :						List[str]      					= torch.cat([mask, torch.zeros(self.model_tester.seq_length - mask.size(0      )      )]      )
									SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= mask.expand(self.model_tester.batch_size,					-1      ).bool()
									SCREAMING_SNAKE_CASE  :						int      					= bool_masked_pos.to(__UpperCAmelCase      )

					if return_labels:
									if model_class in [
									    *get_values(__UpperCAmelCase      ),
									]:
													SCREAMING_SNAKE_CASE  :						str      					= torch.zeros(
													    self.model_tester.batch_size,					dtype=torch.long,					device=__UpperCAmelCase      )

					return inputs_dict


	def 				lowercase__  (self : str      )     ->			str:

					"""simple docstring"""

					self.config_tester.run_common_tests()


	@unittest.skip(reason='''VideoMAE does not use inputs_embeds'''      )
	def 				lowercase__  (self : Union[str, Any]      )     ->			Dict:

					"""simple docstring"""

					pass


	def 				lowercase__  (self : Union[str, Any]      )     ->			List[str]:

					"""simple docstring"""

					SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE  :						Optional[Any]      					= self.model_tester.prepare_config_and_inputs_for_common()

					for model_class in self.all_model_classes:
									SCREAMING_SNAKE_CASE  :						List[Any]      					= model_class(__UpperCAmelCase      )
									self.assertIsInstance(model.get_input_embeddings(),					(nn.Module)      )
									SCREAMING_SNAKE_CASE  :						str      					= model.get_output_embeddings()
									self.assertTrue(x is None or isinstance(__UpperCAmelCase,					nn.Linear      )      )


	def 				lowercase__  (self : List[Any]      )     ->			str:

					"""simple docstring"""

					SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE  :						List[str]      					= self.model_tester.prepare_config_and_inputs_for_common()

					for model_class in self.all_model_classes:
									SCREAMING_SNAKE_CASE  :						List[str]      					= model_class(__UpperCAmelCase      )
									SCREAMING_SNAKE_CASE  :						List[str]      					= inspect.signature(model.forward      )
									# signature.parameters is an OrderedDict => so arg_names order is deterministic
									SCREAMING_SNAKE_CASE  :						str      					= [*signature.parameters.keys()]

									SCREAMING_SNAKE_CASE  :						List[Any]      					= ['''pixel_values''']
									self.assertListEqual(arg_names[:1],					__UpperCAmelCase      )


	def 				lowercase__  (self : Tuple      )     ->			Dict:

					"""simple docstring"""

					SCREAMING_SNAKE_CASE  :						Any      					= self.model_tester.prepare_config_and_inputs()
					self.model_tester.create_and_check_model(*__UpperCAmelCase      )


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

					"""simple docstring"""

					SCREAMING_SNAKE_CASE  :						Dict      					= self.model_tester.prepare_config_and_inputs()
					self.model_tester.create_and_check_for_pretraining(*__UpperCAmelCase      )


	@slow
	def 				lowercase__  (self : Union[str, Any]      )     ->			Any:

					"""simple docstring"""

					for model_name in VIDEOMAE_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
									SCREAMING_SNAKE_CASE  :						Optional[int]      					= VideoMAEModel.from_pretrained(__UpperCAmelCase      )
									self.assertIsNotNone(__UpperCAmelCase      )


	def 				lowercase__  (self : Dict      )     ->			Optional[int]:

					"""simple docstring"""

					if not self.has_attentions:
									pass

					else:
									SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE  :						Tuple      					= self.model_tester.prepare_config_and_inputs_for_common()
									SCREAMING_SNAKE_CASE  :						List[str]      					= True

									for model_class in self.all_model_classes:
													SCREAMING_SNAKE_CASE  :						Any      					= self.model_tester.seq_length - self.model_tester.num_masks
													SCREAMING_SNAKE_CASE  :						List[Any]      					= (
													    num_visible_patches if model_class == VideoMAEForPreTraining else self.model_tester.seq_length
													)

													SCREAMING_SNAKE_CASE  :						Dict      					= True
													SCREAMING_SNAKE_CASE  :						Any      					= False
													SCREAMING_SNAKE_CASE  :						Dict      					= True
													SCREAMING_SNAKE_CASE  :						Any      					= model_class(__UpperCAmelCase      )
													model.to(__UpperCAmelCase      )
													model.eval()
													with torch.no_grad():
																	SCREAMING_SNAKE_CASE  :						List[str]      					= model(**self._prepare_for_class(__UpperCAmelCase,					__UpperCAmelCase      )      )
													SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= outputs.attentions
													self.assertEqual(len(__UpperCAmelCase      ),					self.model_tester.num_hidden_layers      )

													# check that output_attentions also work using config
													del inputs_dict["output_attentions"]
													SCREAMING_SNAKE_CASE  :						str      					= True
													SCREAMING_SNAKE_CASE  :						List[Any]      					= model_class(__UpperCAmelCase      )
													model.to(__UpperCAmelCase      )
													model.eval()
													with torch.no_grad():
																	SCREAMING_SNAKE_CASE  :						Tuple      					= model(**self._prepare_for_class(__UpperCAmelCase,					__UpperCAmelCase      )      )
													SCREAMING_SNAKE_CASE  :						Optional[int]      					= outputs.attentions
													self.assertEqual(len(__UpperCAmelCase      ),					self.model_tester.num_hidden_layers      )

													self.assertListEqual(
													    list(attentions[0].shape[-3:]      ),					[self.model_tester.num_attention_heads, seq_len, seq_len],					)
													SCREAMING_SNAKE_CASE  :						Dict      					= len(__UpperCAmelCase      )

													# Check attention is always last and order is fine
													SCREAMING_SNAKE_CASE  :						Any      					= True
													SCREAMING_SNAKE_CASE  :						Optional[int]      					= True
													SCREAMING_SNAKE_CASE  :						List[Any]      					= model_class(__UpperCAmelCase      )
													model.to(__UpperCAmelCase      )
													model.eval()
													with torch.no_grad():
																	SCREAMING_SNAKE_CASE  :						Optional[Any]      					= model(**self._prepare_for_class(__UpperCAmelCase,					__UpperCAmelCase      )      )

													self.assertEqual(out_len + 1,					len(__UpperCAmelCase      )      )

													SCREAMING_SNAKE_CASE  :						Tuple      					= outputs.attentions

													self.assertEqual(len(__UpperCAmelCase      ),					self.model_tester.num_hidden_layers      )
													self.assertListEqual(
													    list(self_attentions[0].shape[-3:]      ),					[self.model_tester.num_attention_heads, seq_len, seq_len],					)


	def 				lowercase__  (self : Dict      )     ->			List[Any]:

					"""simple docstring"""

					def check_hidden_states_output(__UpperCAmelCase : Tuple,					__UpperCAmelCase : Optional[int],					__UpperCAmelCase : Dict      ):
									SCREAMING_SNAKE_CASE  :						List[Any]      					= model_class(__UpperCAmelCase      )
									model.to(__UpperCAmelCase      )
									model.eval()

									with torch.no_grad():
													SCREAMING_SNAKE_CASE  :						int      					= model(**self._prepare_for_class(__UpperCAmelCase,					__UpperCAmelCase      )      )

									SCREAMING_SNAKE_CASE  :						Tuple      					= outputs.hidden_states
									SCREAMING_SNAKE_CASE  :						Tuple      					= self.model_tester.num_hidden_layers + 1
									self.assertEqual(len(__UpperCAmelCase      ),					__UpperCAmelCase      )

									SCREAMING_SNAKE_CASE  :						Any      					= self.model_tester.seq_length - self.model_tester.num_masks
									SCREAMING_SNAKE_CASE  :						Any      					= num_visible_patches if model_class == VideoMAEForPreTraining else self.model_tester.seq_length

									self.assertListEqual(
									    list(hidden_states[0].shape[-2:]      ),					[seq_length, self.model_tester.hidden_size],					)

					SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= self.model_tester.prepare_config_and_inputs_for_common()

					for model_class in self.all_model_classes:
									SCREAMING_SNAKE_CASE  :						List[str]      					= True
									check_hidden_states_output(__UpperCAmelCase,					__UpperCAmelCase,					__UpperCAmelCase      )

									# check that output_hidden_states also work using config
									del inputs_dict["output_hidden_states"]
									SCREAMING_SNAKE_CASE  :						Any      					= True

									check_hidden_states_output(__UpperCAmelCase,					__UpperCAmelCase,					__UpperCAmelCase      )






	@unittest.skip('''Will be fixed soon by reducing the size of the model used for common tests.'''      )
	def 				lowercase__  (self : Union[str, Any]      )     ->			Tuple:

					"""simple docstring"""

					pass






def       __lowercase  ():
				SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= hf_hub_download(
				    repo_id='''hf-internal-testing/spaghetti-video'''    ,	filename='''eating_spaghetti.npy'''    ,	repo_type='''dataset'''       )
				SCREAMING_SNAKE_CASE  :						Any      					= np.load(_SCREAMING_SNAKE_CASE       )
				return list(_SCREAMING_SNAKE_CASE       )




@require_torch
@require_vision
class 	a__     (				unittest.TestCase	):


	@cached_property
	def 				lowercase__  (self : Tuple      )     ->			str:

					"""simple docstring"""

					return (
					    VideoMAEImageProcessor(image_mean=[0.5, 0.5, 0.5],					image_std=[0.5, 0.5, 0.5]      )
					    if is_vision_available()
					    else None
					)


	@slow
	def 				lowercase__  (self : Optional[Any]      )     ->			Optional[Any]:

					"""simple docstring"""

					SCREAMING_SNAKE_CASE  :						Optional[Any]      					= VideoMAEForVideoClassification.from_pretrained('''MCG-NJU/videomae-base-finetuned-kinetics'''      ).to(
					    __UpperCAmelCase      )

					SCREAMING_SNAKE_CASE  :						str      					= self.default_image_processor
					SCREAMING_SNAKE_CASE  :						List[Any]      					= prepare_video()
					SCREAMING_SNAKE_CASE  :						int      					= image_processor(__UpperCAmelCase,					return_tensors='''pt'''      ).to(__UpperCAmelCase      )

					# forward pass
					with torch.no_grad():
									SCREAMING_SNAKE_CASE  :						int      					= model(**__UpperCAmelCase      )

					# verify the logits
					SCREAMING_SNAKE_CASE  :						Tuple      					= torch.Size((1, 400)      )
					self.assertEqual(outputs.logits.shape,					__UpperCAmelCase      )

					SCREAMING_SNAKE_CASE  :						str      					= torch.tensor([0.3669, -0.0688, -0.2421]      ).to(__UpperCAmelCase      )

					self.assertTrue(torch.allclose(outputs.logits[0, :3],					__UpperCAmelCase,					atol=1e-4      )      )






	@slow
	def 				lowercase__  (self : Tuple      )     ->			Any:

					"""simple docstring"""

					SCREAMING_SNAKE_CASE  :						str      					= VideoMAEForPreTraining.from_pretrained('''MCG-NJU/videomae-base-short'''      ).to(__UpperCAmelCase      )

					SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= self.default_image_processor
					SCREAMING_SNAKE_CASE  :						List[Any]      					= prepare_video()
					SCREAMING_SNAKE_CASE  :						Tuple      					= image_processor(__UpperCAmelCase,					return_tensors='''pt'''      ).to(__UpperCAmelCase      )

					# add boolean mask, indicating which patches to mask
					SCREAMING_SNAKE_CASE  :						int      					= hf_hub_download(repo_id='''hf-internal-testing/bool-masked-pos''',					filename='''bool_masked_pos.pt'''      )
					SCREAMING_SNAKE_CASE  :						Optional[int]      					= torch.load(__UpperCAmelCase      )

					# forward pass
					with torch.no_grad():
									SCREAMING_SNAKE_CASE  :						List[Any]      					= model(**__UpperCAmelCase      )

					# verify the logits
					SCREAMING_SNAKE_CASE  :						List[Any]      					= torch.Size([1, 1408, 1536]      )
					SCREAMING_SNAKE_CASE  :						Any      					= torch.tensor(
					    [[0.7994, 0.9612, 0.8508], [0.7401, 0.8958, 0.8302], [0.5862, 0.7468, 0.7325]],					device=__UpperCAmelCase      )
					self.assertEqual(outputs.logits.shape,					__UpperCAmelCase      )
					self.assertTrue(torch.allclose(outputs.logits[0, :3, :3],					__UpperCAmelCase,					atol=1e-4      )      )

					# verify the loss (`config.norm_pix_loss` = `True`)
					SCREAMING_SNAKE_CASE  :						Any      					= torch.tensor([0.5142],					device=__UpperCAmelCase      )
					self.assertTrue(torch.allclose(outputs.loss,					__UpperCAmelCase,					atol=1e-4      )      )

					# verify the loss (`config.norm_pix_loss` = `False`)
					SCREAMING_SNAKE_CASE  :						Dict      					= VideoMAEForPreTraining.from_pretrained('''MCG-NJU/videomae-base-short''',					norm_pix_loss=__UpperCAmelCase      ).to(
					    __UpperCAmelCase      )

					with torch.no_grad():
									SCREAMING_SNAKE_CASE  :						List[str]      					= model(**__UpperCAmelCase      )

					SCREAMING_SNAKE_CASE  :						Tuple      					= torch.tensor(torch.tensor([0.6469]      ),					device=__UpperCAmelCase      )
					self.assertTrue(torch.allclose(outputs.loss,					__UpperCAmelCase,					atol=1e-4      )      )









'''simple docstring'''

from __future__ import annotations

snake_case_			=     [
    [-1, 0],  # left
    [0, -1],  # down
    [1, 0],  # right
    [0, 1],  # up
]






def       __lowercase  (_SCREAMING_SNAKE_CASE      :list[list[int]]    ,	_SCREAMING_SNAKE_CASE      :list[int]    ,	_SCREAMING_SNAKE_CASE      :list[int]    ,	_SCREAMING_SNAKE_CASE      :int    ,	_SCREAMING_SNAKE_CASE      :list[list[int]]    ,	):
				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= [
				    [0 for col in range(len(grid[0]       )       )] for row in range(len(_SCREAMING_SNAKE_CASE       )       )
				]  # the reference grid
				SCREAMING_SNAKE_CASE  :						Dict      					= 1
				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= [
				    [0 for col in range(len(grid[0]       )       )] for row in range(len(_SCREAMING_SNAKE_CASE       )       )
				]  # the action grid

				SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= init[0]
				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= init[1]
				SCREAMING_SNAKE_CASE  :						Any      					= 0
				SCREAMING_SNAKE_CASE  :						List[Any]      					= g + heuristic[x][y]  # cost from starting cell to destination cell
				SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= [[f, g, x, y]]

				SCREAMING_SNAKE_CASE  :						List[str]      					= False  # flag that is set when search is complete
				SCREAMING_SNAKE_CASE  :						Any      					= False  # flag set if we can't find expand

				while not found and not resign:
								if len(_SCREAMING_SNAKE_CASE       ) == 0:
												raise ValueError('''Algorithm is unable to find solution'''       )
								else:  # to choose the least costliest action so as to move closer to the goal
												cell.sort()
												cell.reverse()
												SCREAMING_SNAKE_CASE  :						List[str]      					= cell.pop()
												SCREAMING_SNAKE_CASE  :						List[str]      					= next_cell[2]
												SCREAMING_SNAKE_CASE  :						Dict      					= next_cell[3]
												SCREAMING_SNAKE_CASE  :						str      					= next_cell[1]

												if x == goal[0] and y == goal[1]:
																SCREAMING_SNAKE_CASE  :						Dict      					= True
												else:
																for i in range(len(_SCREAMING_SNAKE_CASE       )       ):  # to try out different valid actions
																				SCREAMING_SNAKE_CASE  :						Optional[Any]      					= x + DIRECTIONS[i][0]
																				SCREAMING_SNAKE_CASE  :						Tuple      					= y + DIRECTIONS[i][1]
																				if xa >= 0 and xa < len(_SCREAMING_SNAKE_CASE       ) and ya >= 0 and ya < len(grid[0]       ):
																								if closed[xa][ya] == 0 and grid[xa][ya] == 0:
																												SCREAMING_SNAKE_CASE  :						Optional[Any]      					= g + cost
																												SCREAMING_SNAKE_CASE  :						Any      					= ga + heuristic[xa][ya]
																												cell.append([fa, ga, xa, ya]       )
																												SCREAMING_SNAKE_CASE  :						List[Any]      					= 1
																												SCREAMING_SNAKE_CASE  :						Optional[int]      					= i
				SCREAMING_SNAKE_CASE  :						Dict      					= []
				SCREAMING_SNAKE_CASE  :						List[Any]      					= goal[0]
				SCREAMING_SNAKE_CASE  :						Optional[int]      					= goal[1]
				invpath.append([x, y]       )  # we get the reverse path from here
				while x != init[0] or y != init[1]:
								SCREAMING_SNAKE_CASE  :						str      					= x - DIRECTIONS[action[x][y]][0]
								SCREAMING_SNAKE_CASE  :						str      					= y - DIRECTIONS[action[x][y]][1]
								SCREAMING_SNAKE_CASE  :						Tuple      					= xa
								SCREAMING_SNAKE_CASE  :						Dict      					= ya
								invpath.append([x, y]       )

				SCREAMING_SNAKE_CASE  :						Union[str, Any]      					= []
				for i in range(len(_SCREAMING_SNAKE_CASE       )       ):
								path.append(invpath[len(_SCREAMING_SNAKE_CASE       ) - 1 - i]       )
				return path, action


if __name__ == "__main__":
	snake_case_			=     [
	    [0, 1, 0, 0, 0, 0],
	    [0, 1, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
	    [0, 1, 0, 0, 0, 0],
	    [0, 1, 0, 0, 1, 0],
	    [0, 0, 0, 0, 1, 0],
	]

	snake_case_			=     [0, 0]
	# all coordinates are given in format [y,x]
	snake_case_			=     [len(grid) - 1, len(grid[0]) - 1]
	snake_case_			=     1

	# the cost map which pushes the path closer to the goal
	snake_case_			=     [[0 for row in range(len(grid[0]))] for col in range(len(grid))]
	for i in range(len(grid)):
		for j in range(len(grid[0])):
			snake_case_			=     abs(i - goal[0]) + abs(j - goal[1])
			if grid[i][j] == 1:
				# added extra penalty in the heuristic map
				snake_case_			=     99

	snake_case_			,				snake_case_			=     search(grid, init, goal, cost, heuristic)

	print("""ACTION MAP""")
	for i in range(len(action)):
		print(action[i])

	for i in range(len(path)):
		print(path[i])




