





"""simple docstring"""
from __future__ import annotations

import time

lowerCamelCase_								=		list[tuple[int, int]]

lowerCamelCase_								=		[
    [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],
]

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






class 					_SCREAMING_SNAKE_CASE:




       def __init__(						self		,SCREAMING_SNAKE_CASE__		,SCREAMING_SNAKE_CASE__		,SCREAMING_SNAKE_CASE__		,SCREAMING_SNAKE_CASE__		,SCREAMING_SNAKE_CASE__							)			->      Any:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :Dict						=  pos_x
             __SCREAMING_SNAKE_CASE   :int						=  pos_y
             __SCREAMING_SNAKE_CASE   :Optional[Any]						=  (pos_y, pos_x)
             __SCREAMING_SNAKE_CASE   :Any						=  goal_x
             __SCREAMING_SNAKE_CASE   :Tuple						=  goal_y
             __SCREAMING_SNAKE_CASE   :List[Any]						=  parent






class 					_SCREAMING_SNAKE_CASE:




       def __init__(						self		,SCREAMING_SNAKE_CASE__		,SCREAMING_SNAKE_CASE__							)			->      Any:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :Optional[Any]						=  Node(start[1]		,start[0]		,goal[1]		,goal[0]		,SCREAMING_SNAKE_CASE__							)
             __SCREAMING_SNAKE_CASE   :Union[str, Any]						=  Node(goal[1]		,goal[0]		,goal[1]		,goal[0]		,SCREAMING_SNAKE_CASE__							)

             __SCREAMING_SNAKE_CASE   :List[Any]						=  [self.start]
             __SCREAMING_SNAKE_CASE   :List[Any]						=  False




       def     _UpperCamelCase     (						self							)			->      Path | None:





             """simple docstring"""






             while self.node_queue:
                   __SCREAMING_SNAKE_CASE   :Dict						=  self.node_queue.pop(0							)

                   if current_node.pos == self.target.pos:
                         __SCREAMING_SNAKE_CASE   :Optional[Any]						=  True
                         return self.retrace_path(SCREAMING_SNAKE_CASE__							)

                   __SCREAMING_SNAKE_CASE   :Any						=  self.get_successors(SCREAMING_SNAKE_CASE__							)

                   for node in successors:
                         self.node_queue.append(SCREAMING_SNAKE_CASE__							)

             if not self.reached:
                   return [self.start.pos]
             return None




       def     _UpperCamelCase     (						self		,SCREAMING_SNAKE_CASE__							)			->      list[Node]:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :int						=  []
             for action in delta:
                   __SCREAMING_SNAKE_CASE   :str						=  parent.pos_x + action[1]
                   __SCREAMING_SNAKE_CASE   :Any						=  parent.pos_y + action[0]
                   if not (0 <= pos_x <= len(grid[0]							) - 1 and 0 <= pos_y <= len(SCREAMING_SNAKE_CASE__							) - 1):
                         continue

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

                   successors.append(
                       Node(SCREAMING_SNAKE_CASE__		,SCREAMING_SNAKE_CASE__		,self.target.pos_y		,self.target.pos_x		,SCREAMING_SNAKE_CASE__							)							)
             return successors




       def     _UpperCamelCase     (						self		,SCREAMING_SNAKE_CASE__							)			->      Path:





             """simple docstring"""






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






class 					_SCREAMING_SNAKE_CASE:




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





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :Optional[Any]						=  BreadthFirstSearch(SCREAMING_SNAKE_CASE__		,SCREAMING_SNAKE_CASE__							)
             __SCREAMING_SNAKE_CASE   :Dict						=  BreadthFirstSearch(SCREAMING_SNAKE_CASE__		,SCREAMING_SNAKE_CASE__							)
             __SCREAMING_SNAKE_CASE   :int						=  False




       def     _UpperCamelCase     (						self							)			->      Path | None:





             """simple docstring"""






             while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
                   __SCREAMING_SNAKE_CASE   :Union[str, Any]						=  self.fwd_bfs.node_queue.pop(0							)
                   __SCREAMING_SNAKE_CASE   :int						=  self.bwd_bfs.node_queue.pop(0							)

                   if current_bwd_node.pos == current_fwd_node.pos:
                         __SCREAMING_SNAKE_CASE   :List[str]						=  True
                         return self.retrace_bidirectional_path(
                             SCREAMING_SNAKE_CASE__		,SCREAMING_SNAKE_CASE__							)

                   __SCREAMING_SNAKE_CASE   :List[Any]						=  current_bwd_node
                   __SCREAMING_SNAKE_CASE   :Union[str, Any]						=  current_fwd_node

                   __SCREAMING_SNAKE_CASE   :List[Any]						=  {
                       self.fwd_bfs: self.fwd_bfs.get_successors(SCREAMING_SNAKE_CASE__							),
                       self.bwd_bfs: self.bwd_bfs.get_successors(SCREAMING_SNAKE_CASE__							),
                   }

                   for bfs in [self.fwd_bfs, self.bwd_bfs]:
                         for node in successors[bfs]:
                               bfs.node_queue.append(SCREAMING_SNAKE_CASE__							)

             if not self.reached:
                   return [self.fwd_bfs.start.pos]
             return None




       def     _UpperCamelCase     (						self		,SCREAMING_SNAKE_CASE__		,SCREAMING_SNAKE_CASE__							)			->      Path:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :Any						=  self.fwd_bfs.retrace_path(SCREAMING_SNAKE_CASE__							)
             __SCREAMING_SNAKE_CASE   :int						=  self.bwd_bfs.retrace_path(SCREAMING_SNAKE_CASE__							)
             bwd_path.pop()
             bwd_path.reverse()
             __SCREAMING_SNAKE_CASE   :Any						=  fwd_path + bwd_path
             return path


if __name__ == "__main__":
  # all coordinates are given in format [y,x]
  import doctest

  doctest.testmod()
  lowerCamelCase_								=		(0, 0)
  lowerCamelCase_								=		(len(grid) - 1, len(grid[0]) - 1)
  for elem in grid:
    print(elem)

  lowerCamelCase_								=		time.time()
  lowerCamelCase_								=		BreadthFirstSearch(init, goal)
  lowerCamelCase_								=		bfs.search()
  lowerCamelCase_								=		time.time() - start_bfs_time

  print("Unidirectional BFS computation time : ", bfs_time)

  lowerCamelCase_								=		time.time()
  lowerCamelCase_								=		BidirectionalBreadthFirstSearch(init, goal)
  lowerCamelCase_								=		bd_bfs.search()
  lowerCamelCase_								=		time.time() - start_bd_bfs_time

  print("Bidirectional BFS computation time : ", bd_bfs_time)






"""simple docstring"""
from ...configuration_utils import PretrainedConfig
from ...utils import logging


lowerCamelCase_								=		logging.get_logger(__name__)

lowerCamelCase_								=		{}






class 					_SCREAMING_SNAKE_CASE(   A  ):
       SCREAMING_SNAKE_CASE_   :      List[Any]							=  '''llama'''
       SCREAMING_SNAKE_CASE_   :      Optional[int]							=  ['''past_key_values''']




       def __init__(						self		,SCREAMING_SNAKE_CASE__=3_20_00		,SCREAMING_SNAKE_CASE__=40_96		,SCREAMING_SNAKE_CASE__=1_10_08		,SCREAMING_SNAKE_CASE__=32		,SCREAMING_SNAKE_CASE__=32		,SCREAMING_SNAKE_CASE__=None		,SCREAMING_SNAKE_CASE__="silu"		,SCREAMING_SNAKE_CASE__=20_48		,SCREAMING_SNAKE_CASE__=0.0_2		,SCREAMING_SNAKE_CASE__=1E-6		,SCREAMING_SNAKE_CASE__=True		,SCREAMING_SNAKE_CASE__=0		,SCREAMING_SNAKE_CASE__=1		,SCREAMING_SNAKE_CASE__=2		,SCREAMING_SNAKE_CASE__=1		,SCREAMING_SNAKE_CASE__=False		,SCREAMING_SNAKE_CASE__=None		,**SCREAMING_SNAKE_CASE__		,)			->      Union[str, Any]:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :Optional[Any]						=  vocab_size
             __SCREAMING_SNAKE_CASE   :int						=  max_position_embeddings
             __SCREAMING_SNAKE_CASE   :List[str]						=  hidden_size
             __SCREAMING_SNAKE_CASE   :Tuple						=  intermediate_size
             __SCREAMING_SNAKE_CASE   :List[str]						=  num_hidden_layers
             __SCREAMING_SNAKE_CASE   :List[Any]						=  num_attention_heads

             # for backward compatibility
             if num_key_value_heads is None:
                   __SCREAMING_SNAKE_CASE   :Optional[int]						=  num_attention_heads

             __SCREAMING_SNAKE_CASE   :str						=  num_key_value_heads
             __SCREAMING_SNAKE_CASE   :Union[str, Any]						=  hidden_act
             __SCREAMING_SNAKE_CASE   :List[str]						=  initializer_range
             __SCREAMING_SNAKE_CASE   :Union[str, Any]						=  rms_norm_eps
             __SCREAMING_SNAKE_CASE   :Dict						=  pretraining_tp
             __SCREAMING_SNAKE_CASE   :Optional[Any]						=  use_cache
             __SCREAMING_SNAKE_CASE   :Optional[Any]						=  rope_scaling
             self._rope_scaling_validation()

             super().__init__(
                 pad_token_id=SCREAMING_SNAKE_CASE__		,bos_token_id=SCREAMING_SNAKE_CASE__		,eos_token_id=SCREAMING_SNAKE_CASE__		,tie_word_embeddings=SCREAMING_SNAKE_CASE__		,**SCREAMING_SNAKE_CASE__		,)




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





             """simple docstring"""






             if self.rope_scaling is None:
                   return

             if not isinstance(self.rope_scaling		,SCREAMING_SNAKE_CASE__							) or len(self.rope_scaling							) != 2:
                   raise ValueError(
                       '''`rope_scaling` must be a dictionary with with two fields, `name` and `factor`, '''
                       f'''got {self.rope_scaling}'''							)
             __SCREAMING_SNAKE_CASE   :Optional[Any]						=  self.rope_scaling.get('''type'''		,SCREAMING_SNAKE_CASE__							)
             __SCREAMING_SNAKE_CASE   :Optional[int]						=  self.rope_scaling.get('''factor'''		,SCREAMING_SNAKE_CASE__							)
             if rope_scaling_type is None or rope_scaling_type not in ["linear", "dynamic"]:
                   raise ValueError(
                       f'''`rope_scaling`\'s name field must be one of [\'linear\', \'dynamic\'], got {rope_scaling_type}'''							)
             if rope_scaling_factor is None or not isinstance(SCREAMING_SNAKE_CASE__		,SCREAMING_SNAKE_CASE__							) or rope_scaling_factor <= 1.0:
                   raise ValueError(f'''`rope_scaling`\'s factor field must be an float > 1, got {rope_scaling_factor}'''							)