
from __future__ import annotations

import time

lowerCamelCase__     :		List[str]        = list[tuple[int, int]]

lowerCamelCase__     :		str        = [
    [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__     :		List[Any]        = [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right



class    _snake_case :


 def __init__(       self       ,	SCREAMING_SNAKE_CASE_       ,	SCREAMING_SNAKE_CASE_       ,	SCREAMING_SNAKE_CASE_       ,	SCREAMING_SNAKE_CASE_       ,	SCREAMING_SNAKE_CASE_):


   '''simple docstring'''




   lowercase__	: Optional[int]     		=   pos_x
   lowercase__	: Optional[int]     		=   pos_y
   lowercase__	: List[Any]     		=   (pos_y, pos_x)
   lowercase__	: Optional[Any]     		=   goal_x
   lowercase__	: Union[str, Any]     		=   goal_y
   lowercase__	: Any     		=   parent



class    _snake_case :


 def __init__(       self       ,	SCREAMING_SNAKE_CASE_       ,	SCREAMING_SNAKE_CASE_):


   '''simple docstring'''




   lowercase__	: int     		=   Node(start[1]       ,	start[0]       ,	goal[1]       ,	goal[0]       ,	SCREAMING_SNAKE_CASE_)
   lowercase__	: int     		=   Node(goal[1]       ,	goal[0]       ,	goal[1]       ,	goal[0]       ,	SCREAMING_SNAKE_CASE_)

   lowercase__	: List[Any]     		=   [self.start]
   lowercase__	: int     		=   False


 def   lowercase__  (       self):


   '''simple docstring'''




   while self.node_queue:
     lowercase__	: List[Any]     		=   self.node_queue.pop(0)

     if current_node.pos == self.target.pos:
       lowercase__	: Union[str, Any]     		=   True
       return self.retrace_path(SCREAMING_SNAKE_CASE_)

     lowercase__	: str     		=   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   lowercase__  (       self       ,	SCREAMING_SNAKE_CASE_):


   '''simple docstring'''




   lowercase__	: Optional[int]     		=   []
   for action in delta:
     lowercase__	: Optional[Any]     		=   parent.pos_x + action[1]
     lowercase__	: Dict     		=   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   lowercase__  (       self       ,	SCREAMING_SNAKE_CASE_):


   '''simple docstring'''




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



class    _snake_case :


 def __init__(       self       ,	SCREAMING_SNAKE_CASE_       ,	SCREAMING_SNAKE_CASE_):


   '''simple docstring'''




   lowercase__	: Optional[int]     		=   BreadthFirstSearch(SCREAMING_SNAKE_CASE_       ,	SCREAMING_SNAKE_CASE_)
   lowercase__	: Dict     		=   BreadthFirstSearch(SCREAMING_SNAKE_CASE_       ,	SCREAMING_SNAKE_CASE_)
   lowercase__	: List[str]     		=   False


 def   lowercase__  (       self):


   '''simple docstring'''




   while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
     lowercase__	: Optional[int]     		=   self.fwd_bfs.node_queue.pop(0)
     lowercase__	: Optional[Any]     		=   self.bwd_bfs.node_queue.pop(0)

     if current_bwd_node.pos == current_fwd_node.pos:
       lowercase__	: Optional[Any]     		=   True
       return self.retrace_bidirectional_path(
           SCREAMING_SNAKE_CASE_       ,	SCREAMING_SNAKE_CASE_)

     lowercase__	: str     		=   current_bwd_node
     lowercase__	: str     		=   current_fwd_node

     lowercase__	: Tuple     		=   {
         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   lowercase__  (       self       ,	SCREAMING_SNAKE_CASE_       ,	SCREAMING_SNAKE_CASE_):


   '''simple docstring'''




   lowercase__	: List[Any]     		=   self.fwd_bfs.retrace_path(SCREAMING_SNAKE_CASE_)
   lowercase__	: List[str]     		=   self.bwd_bfs.retrace_path(SCREAMING_SNAKE_CASE_)
   bwd_path.pop()
   bwd_path.reverse()
   lowercase__	: Optional[Any]     		=   fwd_path + bwd_path
   return path


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

     doctest.testmod()
     lowerCamelCase__     :		Optional[Any]        = (0, 0)
     lowerCamelCase__     :		Tuple        = (len(grid) - 1, len(grid[0]) - 1)
     for elem in grid:
          print(elem)

     lowerCamelCase__     :		Tuple        = time.time()
     lowerCamelCase__     :		Union[str, Any]        = BreadthFirstSearch(init, goal)
     lowerCamelCase__     :		List[Any]        = bfs.search()
     lowerCamelCase__     :		str        = time.time() - start_bfs_time

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

     lowerCamelCase__     :		Tuple        = time.time()
     lowerCamelCase__     :		Union[str, Any]        = BidirectionalBreadthFirstSearch(init, goal)
     lowerCamelCase__     :		Union[str, Any]        = bd_bfs.search()
     lowerCamelCase__     :		Optional[Any]        = time.time() - start_bd_bfs_time

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








"""simple docstring"""


from typing import TYPE_CHECKING

from ...utils import (
    OptionalDependencyNotAvailable,
    _LazyModule,
    is_flax_available,
    is_tf_available,
    is_tokenizers_available,
    is_torch_available,
)


_lowercase				 =					{
    '''configuration_electra''': ['''ELECTRA_PRETRAINED_CONFIG_ARCHIVE_MAP''', '''ElectraConfig''', '''ElectraOnnxConfig'''],
    '''tokenization_electra''': ['''ElectraTokenizer'''],
}

try:
		if not is_tokenizers_available():
				raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
		pass
else:
		_lowercase				 =					['''ElectraTokenizerFast''']

try:
		if not is_torch_available():
				raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
		pass
else:
		_lowercase				 =					[
		    '''ELECTRA_PRETRAINED_MODEL_ARCHIVE_LIST''',
		    '''ElectraForCausalLM''',
		    '''ElectraForMaskedLM''',
		    '''ElectraForMultipleChoice''',
		    '''ElectraForPreTraining''',
		    '''ElectraForQuestionAnswering''',
		    '''ElectraForSequenceClassification''',
		    '''ElectraForTokenClassification''',
		    '''ElectraModel''',
		    '''ElectraPreTrainedModel''',
		    '''load_tf_weights_in_electra''',
		]

try:
		if not is_tf_available():
				raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
		pass
else:
		_lowercase				 =					[
		    '''TF_ELECTRA_PRETRAINED_MODEL_ARCHIVE_LIST''',
		    '''TFElectraForMaskedLM''',
		    '''TFElectraForMultipleChoice''',
		    '''TFElectraForPreTraining''',
		    '''TFElectraForQuestionAnswering''',
		    '''TFElectraForSequenceClassification''',
		    '''TFElectraForTokenClassification''',
		    '''TFElectraModel''',
		    '''TFElectraPreTrainedModel''',
		]

try:
		if not is_flax_available():
				raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
		pass
else:
		_lowercase				 =					[
		    '''FlaxElectraForCausalLM''',
		    '''FlaxElectraForMaskedLM''',
		    '''FlaxElectraForMultipleChoice''',
		    '''FlaxElectraForPreTraining''',
		    '''FlaxElectraForQuestionAnswering''',
		    '''FlaxElectraForSequenceClassification''',
		    '''FlaxElectraForTokenClassification''',
		    '''FlaxElectraModel''',
		    '''FlaxElectraPreTrainedModel''',
		]


if TYPE_CHECKING:
		from .configuration_electra import ELECTRA_PRETRAINED_CONFIG_ARCHIVE_MAP, ElectraConfig, ElectraOnnxConfig
		from .tokenization_electra import ElectraTokenizer

		try:
				if not is_tokenizers_available():
						raise OptionalDependencyNotAvailable()
		except OptionalDependencyNotAvailable:
				pass
		else:
				from .tokenization_electra_fast import ElectraTokenizerFast

		try:
				if not is_torch_available():
						raise OptionalDependencyNotAvailable()
		except OptionalDependencyNotAvailable:
				pass
		else:
				from .modeling_electra import (
				    ELECTRA_PRETRAINED_MODEL_ARCHIVE_LIST,
				    ElectraForCausalLM,
				    ElectraForMaskedLM,
				    ElectraForMultipleChoice,
				    ElectraForPreTraining,
				    ElectraForQuestionAnswering,
				    ElectraForSequenceClassification,
				    ElectraForTokenClassification,
				    ElectraModel,
				    ElectraPreTrainedModel,
				    load_tf_weights_in_electra,
				)

		try:
				if not is_tf_available():
						raise OptionalDependencyNotAvailable()
		except OptionalDependencyNotAvailable:
				pass
		else:
				from .modeling_tf_electra import (
				    TF_ELECTRA_PRETRAINED_MODEL_ARCHIVE_LIST,
				    TFElectraForMaskedLM,
				    TFElectraForMultipleChoice,
				    TFElectraForPreTraining,
				    TFElectraForQuestionAnswering,
				    TFElectraForSequenceClassification,
				    TFElectraForTokenClassification,
				    TFElectraModel,
				    TFElectraPreTrainedModel,
				)

		try:
				if not is_flax_available():
						raise OptionalDependencyNotAvailable()
		except OptionalDependencyNotAvailable:
				pass
		else:
				from .modeling_flax_electra import (
				    FlaxElectraForCausalLM,
				    FlaxElectraForMaskedLM,
				    FlaxElectraForMultipleChoice,
				    FlaxElectraForPreTraining,
				    FlaxElectraForQuestionAnswering,
				    FlaxElectraForSequenceClassification,
				    FlaxElectraForTokenClassification,
				    FlaxElectraModel,
				    FlaxElectraPreTrainedModel,
				)

else:
		import sys

		_lowercase				 =					_LazyModule(__name__, globals()['''__file__'''], _import_structure, module_spec=__spec__)