



'''simple docstring'''





import unittest

from parameterized import parameterized

from transformers import OpenLlamaConfig, is_torch_available, set_seed
from transformers.testing_utils import require_torch, torch_device

from ...generation.test_utils import GenerationTesterMixin
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 OpenLlamaForCausalLM, OpenLlamaForSequenceClassification, OpenLlamaModel






class __A			:



 '''simple docstring'''







 def __init__(self ,   A ,   A=13 ,   A=7 ,   A=True ,   A=True ,   A=False ,   A=True ,   A=99 ,   A=32 ,   A=5 ,   A=4 ,   A=37 ,   A="gelu" ,   A=0.1 ,   A=0.1 ,   A=512 ,   A=16 ,   A=2 ,   A=0.02 ,   A=3 ,   A=4 ,   A=None ,   )    ->     List[str]:


      """simple docstring"""



      _a      =  parent
      _a      =  batch_size
      _a      =  seq_length
      _a      =  is_training
      _a      =  use_input_mask
      _a      =  use_token_type_ids
      _a      =  use_labels
      _a      =  vocab_size
      _a      =  hidden_size
      _a      =  num_hidden_layers
      _a      =  num_attention_heads
      _a      =  intermediate_size
      _a      =  hidden_act
      _a      =  hidden_dropout_prob
      _a      =  attention_probs_dropout_prob
      _a      =  max_position_embeddings
      _a      =  type_vocab_size
      _a      =  type_sequence_label_size
      _a      =  initializer_range
      _a      =  num_labels
      _a      =  num_choices
      _a      =  scope



 def 					a__  (self       )    ->     str:


      """simple docstring"""



      _a      =  ids_tensor([self.batch_size, self.seq_length] ,   self.vocab_size       )

      _a      =  None
      if self.use_input_mask:
           _a      =  random_attention_mask([self.batch_size, self.seq_length]       )

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

      _a      =  None
      _a      =  None
      _a      =  None
      if self.use_labels:
           _a      =  ids_tensor([self.batch_size] ,   self.type_sequence_label_size       )
           _a      =  ids_tensor([self.batch_size, self.seq_length] ,   self.num_labels       )
           _a      =  ids_tensor([self.batch_size] ,   self.num_choices       )

      _a      =  self.get_config()

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



 def 					a__  (self       )    ->     Dict:


      """simple docstring"""



      return OpenLlamaConfig(
          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 ,   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=_snake_case ,   initializer_range=self.initializer_range ,   use_stable_embedding=_snake_case ,   )



 def 					a__  (self ,   A ,   A ,   A ,   A ,   A ,   A ,   A       )    ->     int:


      """simple docstring"""



      _a      =  OpenLlamaModel(config=_snake_case       )
      model.to(_snake_case       )
      model.eval()
      _a      =  model(_snake_case ,   attention_mask=_snake_case       )
      _a      =  model(_snake_case       )
      self.parent.assertEqual(result.last_hidden_state.shape ,   (self.batch_size, self.seq_length, self.hidden_size)       )



 def 					a__  (self ,   A ,   A ,   A ,   A ,   A ,   A ,   A ,   A ,   A ,   )    ->     Optional[int]:


      """simple docstring"""



      _a      =  True
      _a      =  OpenLlamaModel(_snake_case       )
      model.to(_snake_case       )
      model.eval()
      _a      =  model(
          _snake_case ,   attention_mask=_snake_case ,   encoder_hidden_states=_snake_case ,   encoder_attention_mask=_snake_case ,   )
      _a      =  model(
          _snake_case ,   attention_mask=_snake_case ,   encoder_hidden_states=_snake_case ,   )
      _a      =  model(_snake_case ,   attention_mask=_snake_case       )
      self.parent.assertEqual(result.last_hidden_state.shape ,   (self.batch_size, self.seq_length, self.hidden_size)       )



 def 					a__  (self ,   A ,   A ,   A ,   A ,   A ,   A ,   A ,   A ,   A ,   )    ->     Optional[Any]:


      """simple docstring"""



      _a      =  OpenLlamaForCausalLM(config=_snake_case       )
      model.to(_snake_case       )
      model.eval()
      _a      =  model(_snake_case ,   attention_mask=_snake_case ,   labels=_snake_case       )
      self.parent.assertEqual(result.logits.shape ,   (self.batch_size, self.seq_length, self.vocab_size)       )



 def 					a__  (self ,   A ,   A ,   A ,   A ,   A ,   A ,   A ,   A ,   A ,   )    ->     Any:


      """simple docstring"""



      _a      =  True
      _a      =  True
      _a      =  OpenLlamaForCausalLM(config=_snake_case       )
      model.to(_snake_case       )
      model.eval()

      # first forward pass
      _a      =  model(
          _snake_case ,   attention_mask=_snake_case ,   encoder_hidden_states=_snake_case ,   encoder_attention_mask=_snake_case ,   use_cache=_snake_case ,   )
      _a      =  outputs.past_key_values

      # create hypothetical multiple next token and extent to next_input_ids
      _a      =  ids_tensor((self.batch_size, 3) ,   config.vocab_size       )
      _a      =  ids_tensor((self.batch_size, 3) ,   vocab_size=2       )

      # append to next input_ids and
      _a      =  torch.cat([input_ids, next_tokens] ,   dim=-1       )
      _a      =  torch.cat([input_mask, next_mask] ,   dim=-1       )

      _a      =  model(
          _snake_case ,   attention_mask=_snake_case ,   encoder_hidden_states=_snake_case ,   encoder_attention_mask=_snake_case ,   output_hidden_states=_snake_case ,   )['''hidden_states'''][0]
      _a      =  model(
          _snake_case ,   attention_mask=_snake_case ,   encoder_hidden_states=_snake_case ,   encoder_attention_mask=_snake_case ,   past_key_values=_snake_case ,   output_hidden_states=_snake_case ,   )['''hidden_states'''][0]

      # select random slice
      _a      =  ids_tensor((1,) ,   output_from_past.shape[-1]       ).item()
      _a      =  output_from_no_past[:, -3:, random_slice_idx].detach()
      _a      =  output_from_past[:, :, random_slice_idx].detach()

      self.parent.assertTrue(output_from_past_slice.shape[1] == next_tokens.shape[1]       )

      # test that outputs are equal for slice
      self.parent.assertTrue(torch.allclose(_snake_case ,   _snake_case ,   atol=1E-3       )       )



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


      """simple docstring"""



      _a      =  self.prepare_config_and_inputs()
      (
          (
          _a       
      )  ,    (
          _a       
      )  ,    (
          _a       
      )  ,    (
          _a       
      )  ,    (
          _a       
      )  ,    (
          _a       
      )  ,    (
          _a       
      )  ,           
      )      =  config_and_inputs
      _a      =  {'''input_ids''': input_ids, '''attention_mask''': input_mask}
      return config, inputs_dict






@require_torch
class __A			(  A   ,   A   ,   A   ,   unittest.TestCase						):



 '''simple docstring'''







 __lowerCamelCase    :       Dict          =       (
     (OpenLlamaModel, OpenLlamaForCausalLM, OpenLlamaForSequenceClassification) if is_torch_available() else ()
 )
 __lowerCamelCase    :       int          =       (OpenLlamaForCausalLM,) if is_torch_available() else ()
 __lowerCamelCase    :       Union[str, Any]          =       (
     {
         '''feature-extraction''': OpenLlamaModel,
         '''text-classification''': OpenLlamaForSequenceClassification,
         '''text-generation''': OpenLlamaForCausalLM,
         '''zero-shot''': OpenLlamaForSequenceClassification,
     }
     if is_torch_available()
     else {}
 )
 __lowerCamelCase    :       Any          =       False
 __lowerCamelCase    :       Dict          =       False



 def 					a__  (self       )    ->     Any:


      """simple docstring"""



      _a      =  OpenLlamaModelTester(self       )
      _a      =  ConfigTester(self ,   config_class=_snake_case ,   hidden_size=37       )



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


      """simple docstring"""



      self.config_tester.run_common_tests()



 def 					a__  (self       )    ->     str:


      """simple docstring"""



      _a      =  self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_model(*_snake_case       )



 def 					a__  (self       )    ->     str:


      """simple docstring"""



      _a      =  self.model_tester.prepare_config_and_inputs()
      for type in ["absolute", "relative_key", "relative_key_query"]:
           _a      =  type
           self.model_tester.create_and_check_model(*_snake_case       )



 def 					a__  (self       )    ->     Any:


      """simple docstring"""



      _a  ,    _a      =  self.model_tester.prepare_config_and_inputs_for_common()
      _a      =  3
      _a      =  input_dict['''input_ids''']
      _a      =  input_ids.ne(1       ).to(_snake_case       )
      _a      =  ids_tensor([self.model_tester.batch_size] ,   self.model_tester.type_sequence_label_size       )
      _a      =  OpenLlamaForSequenceClassification(_snake_case       )
      model.to(_snake_case       )
      model.eval()
      _a      =  model(_snake_case ,   attention_mask=_snake_case ,   labels=_snake_case       )
      self.assertEqual(result.logits.shape ,   (self.model_tester.batch_size, self.model_tester.num_labels)       )



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


      """simple docstring"""



      _a  ,    _a      =  self.model_tester.prepare_config_and_inputs_for_common()
      _a      =  3
      _a      =  '''single_label_classification'''
      _a      =  input_dict['''input_ids''']
      _a      =  input_ids.ne(1       ).to(_snake_case       )
      _a      =  ids_tensor([self.model_tester.batch_size] ,   self.model_tester.type_sequence_label_size       )
      _a      =  OpenLlamaForSequenceClassification(_snake_case       )
      model.to(_snake_case       )
      model.eval()
      _a      =  model(_snake_case ,   attention_mask=_snake_case ,   labels=_snake_case       )
      self.assertEqual(result.logits.shape ,   (self.model_tester.batch_size, self.model_tester.num_labels)       )



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


      """simple docstring"""



      _a  ,    _a      =  self.model_tester.prepare_config_and_inputs_for_common()
      _a      =  3
      _a      =  '''multi_label_classification'''
      _a      =  input_dict['''input_ids''']
      _a      =  input_ids.ne(1       ).to(_snake_case       )
      _a      =  ids_tensor(
          [self.model_tester.batch_size, config.num_labels] ,   self.model_tester.type_sequence_label_size       ).to(torch.float       )
      _a      =  OpenLlamaForSequenceClassification(_snake_case       )
      model.to(_snake_case       )
      model.eval()
      _a      =  model(_snake_case ,   attention_mask=_snake_case ,   labels=_snake_case       )
      self.assertEqual(result.logits.shape ,   (self.model_tester.batch_size, self.model_tester.num_labels)       )



 @unittest.skip('''Open-Llama buffers include complex numbers, which breaks this test'''       )
 def 					a__  (self       )    ->     List[str]:


      """simple docstring"""



      pass



 @parameterized.expand([('''linear''',), ('''dynamic''',)]       )
 def 					a__  (self ,   A       )    ->     Tuple:


      """simple docstring"""



      _a  ,    _a      =  self.model_tester.prepare_config_and_inputs_for_common()
      _a      =  ids_tensor([1, 10] ,   config.vocab_size       )
      _a      =  ids_tensor([1, int(config.max_position_embeddings * 1.5       )] ,   config.vocab_size       )

      set_seed(42       )  # Fixed seed at init time so the two models get the same random weights
      _a      =  OpenLlamaModel(_snake_case       )
      original_model.to(_snake_case       )
      original_model.eval()
      _a      =  original_model(_snake_case       ).last_hidden_state
      _a      =  original_model(_snake_case       ).last_hidden_state

      set_seed(42       )  # Fixed seed at init time so the two models get the same random weights
      _a      =  {'''type''': scaling_type, '''factor''': 10.0}
      _a      =  OpenLlamaModel(_snake_case       )
      scaled_model.to(_snake_case       )
      scaled_model.eval()
      _a      =  scaled_model(_snake_case       ).last_hidden_state
      _a      =  scaled_model(_snake_case       ).last_hidden_state

      # Dynamic scaling does not change the RoPE embeddings until it receives an input longer than the original
      # maximum sequence length, so the outputs for the short input should match.
      if scaling_type == "dynamic":
           self.assertTrue(torch.allclose(_snake_case ,   _snake_case ,   atol=1E-5       )       )
      else:
           self.assertFalse(torch.allclose(_snake_case ,   _snake_case ,   atol=1E-5       )       )

      # The output should be different for long inputs
      self.assertFalse(torch.allclose(_snake_case ,   _snake_case ,   atol=1E-5       )       )









from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
snake_case_ : str    		=       0

snake_case_ : Union[str, Any]    		=       [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
]

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

snake_case_ : List[Any]    		=       tuple[int, int]







class __snake_case			:







   def __init__(      self		:						Any					,						_snake_case		:						int					,						_snake_case		:						int					,						_snake_case		:						int					,						_snake_case		:						int					,						_snake_case		:						int					,						_snake_case		:						Node | None					,						):

        """simple docstring"""


        UpperCAmelCase_          =							pos_x
        UpperCAmelCase_          =							pos_y
        UpperCAmelCase_          =							(pos_y, pos_x)
        UpperCAmelCase_          =							goal_x
        UpperCAmelCase_          =							goal_y
        UpperCAmelCase_          =							g_cost
        UpperCAmelCase_          =							parent
        UpperCAmelCase_          =							self.calculate_heuristic()
        UpperCAmelCase_          =							self.g_cost + self.h_cost







   def lowerCamelCase						(      self		:						List[str]):

        """simple docstring"""


        UpperCAmelCase_          =							self.pos_x - self.goal_x
        UpperCAmelCase_          =							self.pos_y - self.goal_y
        if HEURISTIC == 1:
             return abs(_snake_case) + abs(_snake_case)
        else:
             return sqrt(dy**2 + dx**2)







   def __lt__(      self		:						Union[str, Any]					,						_snake_case		:						Node):

        """simple docstring"""


        return self.f_cost < other.f_cost







class __snake_case			:







   def __init__(      self		:						str					,						_snake_case		:						TPosition					,						_snake_case		:						TPosition):

        """simple docstring"""


        UpperCAmelCase_          =							Node(start[1]					,						start[0]					,						goal[1]					,						goal[0]					,						0					,						_snake_case)
        UpperCAmelCase_          =							Node(goal[1]					,						goal[0]					,						goal[1]					,						goal[0]					,						99999					,						_snake_case)

        UpperCAmelCase_          =							[self.start]
        UpperCAmelCase_          =							[]

        UpperCAmelCase_          =							False







   def lowerCamelCase						(      self		:						Optional[int]):

        """simple docstring"""


        while self.open_nodes:
             # Open Nodes are sorted using __lt__
             self.open_nodes.sort()
             UpperCAmelCase_          =							self.open_nodes.pop(0)

             if current_node.pos == self.target.pos:
                  return self.retrace_path(_snake_case)

             self.closed_nodes.append(_snake_case)
             UpperCAmelCase_          =							self.get_successors(_snake_case)

             for child_node in successors:
                  if child_node in self.closed_nodes:
                       continue

                  if child_node not in self.open_nodes:
                       self.open_nodes.append(_snake_case)
                  else:
                       # retrieve the best current path
                       UpperCAmelCase_          =							self.open_nodes.pop(self.open_nodes.index(_snake_case))

                       if child_node.g_cost < better_node.g_cost:
                            self.open_nodes.append(_snake_case)
                       else:
                            self.open_nodes.append(_snake_case)

        return [self.start.pos]







   def lowerCamelCase						(      self		:						Tuple					,						_snake_case		:						Node):

        """simple docstring"""


        UpperCAmelCase_          =							[]
        for action in delta:
             UpperCAmelCase_          =							parent.pos_x + action[1]
             UpperCAmelCase_          =							parent.pos_y + action[0]
             if not (0 <= pos_x <= len(grid[0]) - 1 and 0 <= pos_y <= len(_snake_case) - 1):
                  continue

             if grid[pos_y][pos_x] != 0:
                  continue

             successors.append(
                 Node(
                     _snake_case					,						_snake_case					,						self.target.pos_y					,						self.target.pos_x					,						parent.g_cost + 1					,						_snake_case					,						))
        return successors







   def lowerCamelCase						(      self		:						Any					,						_snake_case		:						Node | None):

        """simple docstring"""


        UpperCAmelCase_          =							node
        UpperCAmelCase_          =							[]
        while current_node is not None:
             path.append((current_node.pos_y, current_node.pos_x))
             UpperCAmelCase_          =							current_node.parent
        path.reverse()
        return path







class __snake_case			:







   def __init__(      self		:						Any					,						_snake_case		:						TPosition					,						_snake_case		:						TPosition):

        """simple docstring"""


        UpperCAmelCase_          =							AStar(_snake_case					,						_snake_case)
        UpperCAmelCase_          =							AStar(_snake_case					,						_snake_case)
        UpperCAmelCase_          =							False







   def lowerCamelCase						(      self		:						List[Any]):

        """simple docstring"""


        while self.fwd_astar.open_nodes or self.bwd_astar.open_nodes:
             self.fwd_astar.open_nodes.sort()
             self.bwd_astar.open_nodes.sort()
             UpperCAmelCase_          =							self.fwd_astar.open_nodes.pop(0)
             UpperCAmelCase_          =							self.bwd_astar.open_nodes.pop(0)

             if current_bwd_node.pos == current_fwd_node.pos:
                  return self.retrace_bidirectional_path(
                      _snake_case					,						_snake_case)

             self.fwd_astar.closed_nodes.append(_snake_case)
             self.bwd_astar.closed_nodes.append(_snake_case)

             UpperCAmelCase_          =							current_bwd_node
             UpperCAmelCase_          =							current_fwd_node

             UpperCAmelCase_          =							{
                 self.fwd_astar: self.fwd_astar.get_successors(_snake_case),
                 self.bwd_astar: self.bwd_astar.get_successors(_snake_case),
             }

             for astar in [self.fwd_astar, self.bwd_astar]:
                  for child_node in successors[astar]:
                       if child_node in astar.closed_nodes:
                            continue

                       if child_node not in astar.open_nodes:
                            astar.open_nodes.append(_snake_case)
                       else:
                            # retrieve the best current path
                            UpperCAmelCase_          =							astar.open_nodes.pop(
                                astar.open_nodes.index(_snake_case))

                            if child_node.g_cost < better_node.g_cost:
                                 astar.open_nodes.append(_snake_case)
                            else:
                                 astar.open_nodes.append(_snake_case)

        return [self.fwd_astar.start.pos]







   def lowerCamelCase						(      self		:						int					,						_snake_case		:						Node					,						_snake_case		:						Node):

        """simple docstring"""


        UpperCAmelCase_          =							self.fwd_astar.retrace_path(_snake_case)
        UpperCAmelCase_          =							self.bwd_astar.retrace_path(_snake_case)
        bwd_path.pop()
        bwd_path.reverse()
        UpperCAmelCase_          =							fwd_path + bwd_path
        return path


if __name__ == "__main__":
    # all coordinates are given in format [y,x]
    snake_case_ : Any    		=       (0, 0)
    snake_case_ : Union[str, Any]    		=       (len(grid) - 1, len(grid[0]) - 1)
    for elem in grid:
        print(elem)

    snake_case_ : str    		=       time.time()
    snake_case_ : List[str]    		=       AStar(init, goal)
    snake_case_ : Optional[int]    		=       a_star.search()
    snake_case_ : Optional[Any]    		=       time.time() - start_time
    print(f"AStar execution time = {end_time:f} seconds")

    snake_case_ : int    		=       time.time()
    snake_case_ : Dict    		=       BidirectionalAStar(init, goal)
    snake_case_ : str    		=       time.time() - bd_start_time
    print(f"BidirectionalAStar execution time = {bd_end_time:f} seconds")






