





"""simple docstring"""





from __future__ import annotations

import time

__A											=						list[tuple[int, int]]

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

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






class    _lowerCAmelCase  :
       """simple docstring"""




       def __init__(       self       ,					__UpperCAmelCase       ,					__UpperCAmelCase       ,					__UpperCAmelCase       ,					__UpperCAmelCase       ,					__UpperCAmelCase ):



         '''simple docstring'''

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






class    _lowerCAmelCase  :
       """simple docstring"""




       def __init__(       self       ,					__UpperCAmelCase       ,					__UpperCAmelCase ):



         '''simple docstring'''

         lowerCAmelCase__     :List[str]											=				Node(start[1]       ,					start[0]       ,					goal[1]       ,					goal[0]       ,					__UpperCAmelCase )
         lowerCAmelCase__     :Any											=				Node(goal[1]       ,					goal[0]       ,					goal[1]       ,					goal[0]       ,					__UpperCAmelCase )

         lowerCAmelCase__     :Any											=				[self.start]
         lowerCAmelCase__     :Optional[Any]											=				False






       def 	snake_case		(       self ):



         '''simple docstring'''

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

           if current_node.pos == self.target.pos:
             lowerCAmelCase__     :Dict											=				True
             return self.retrace_path(__UpperCAmelCase )

           lowerCAmelCase__     :Dict											=				self.get_successors(__UpperCAmelCase )

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

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






       def 	snake_case		(       self       ,					__UpperCAmelCase ):



         '''simple docstring'''

         lowerCAmelCase__     :List[str]											=				[]
         for action in delta:
           lowerCAmelCase__     :str											=				parent.pos_x + action[1]
           lowerCAmelCase__     :Optional[int]											=				parent.pos_y + action[0]
           if not (0 <= pos_x <= len(grid[0] ) - 1 and 0 <= pos_y <= len(__UpperCAmelCase ) - 1):
             continue

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

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






       def 	snake_case		(       self       ,					__UpperCAmelCase ):



         '''simple docstring'''

         lowerCAmelCase__     :Union[str, Any]											=				node
         lowerCAmelCase__     :int											=				[]
         while current_node is not None:
           path.append((current_node.pos_y, current_node.pos_x) )
           lowerCAmelCase__     :Any											=				current_node.parent
         path.reverse()
         return path






class    _lowerCAmelCase  :
       """simple docstring"""




       def __init__(       self       ,					__UpperCAmelCase       ,					__UpperCAmelCase ):



         '''simple docstring'''

         lowerCAmelCase__     :int											=				BreadthFirstSearch(__UpperCAmelCase       ,					__UpperCAmelCase )
         lowerCAmelCase__     :Union[str, Any]											=				BreadthFirstSearch(__UpperCAmelCase       ,					__UpperCAmelCase )
         lowerCAmelCase__     :Union[str, Any]											=				False






       def 	snake_case		(       self ):



         '''simple docstring'''

         while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
           lowerCAmelCase__     :List[Any]											=				self.fwd_bfs.node_queue.pop(0 )
           lowerCAmelCase__     :List[str]											=				self.bwd_bfs.node_queue.pop(0 )

           if current_bwd_node.pos == current_fwd_node.pos:
             lowerCAmelCase__     :Dict											=				True
             return self.retrace_bidirectional_path(
                 __UpperCAmelCase       ,					__UpperCAmelCase )

           lowerCAmelCase__     :Tuple											=				current_bwd_node
           lowerCAmelCase__     :int											=				current_fwd_node

           lowerCAmelCase__     :Any											=				{
               self.fwd_bfs: self.fwd_bfs.get_successors(__UpperCAmelCase ),
               self.bwd_bfs: self.bwd_bfs.get_successors(__UpperCAmelCase ),
           }

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

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






       def 	snake_case		(       self       ,					__UpperCAmelCase       ,					__UpperCAmelCase ):



         '''simple docstring'''

         lowerCAmelCase__     :Dict											=				self.fwd_bfs.retrace_path(__UpperCAmelCase )
         lowerCAmelCase__     :Union[str, Any]											=				self.bwd_bfs.retrace_path(__UpperCAmelCase )
         bwd_path.pop()
         bwd_path.reverse()
         lowerCAmelCase__     :List[Any]											=				fwd_path + bwd_path
         return path


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

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

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

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

  __A											=						time.time()
  __A											=						BidirectionalBreadthFirstSearch(init, goal)
  __A											=						bd_bfs.search()
  __A											=						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_tf_available,
    is_tokenizers_available,
    is_torch_available,
)


_lowerCAmelCase            =	{
    'configuration_mobilebert': [
        'MOBILEBERT_PRETRAINED_CONFIG_ARCHIVE_MAP',
        'MobileBertConfig',
        'MobileBertOnnxConfig',
    ],
    'tokenization_mobilebert': ['MobileBertTokenizer'],
}

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

try:
				if not is_torch_available():
								raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
				pass
else:
				_lowerCAmelCase            =	[
				    'MOBILEBERT_PRETRAINED_MODEL_ARCHIVE_LIST',
				    'MobileBertForMaskedLM',
				    'MobileBertForMultipleChoice',
				    'MobileBertForNextSentencePrediction',
				    'MobileBertForPreTraining',
				    'MobileBertForQuestionAnswering',
				    'MobileBertForSequenceClassification',
				    'MobileBertForTokenClassification',
				    'MobileBertLayer',
				    'MobileBertModel',
				    'MobileBertPreTrainedModel',
				    'load_tf_weights_in_mobilebert',
				]

try:
				if not is_tf_available():
								raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
				pass
else:
				_lowerCAmelCase            =	[
				    'TF_MOBILEBERT_PRETRAINED_MODEL_ARCHIVE_LIST',
				    'TFMobileBertForMaskedLM',
				    'TFMobileBertForMultipleChoice',
				    'TFMobileBertForNextSentencePrediction',
				    'TFMobileBertForPreTraining',
				    'TFMobileBertForQuestionAnswering',
				    'TFMobileBertForSequenceClassification',
				    'TFMobileBertForTokenClassification',
				    'TFMobileBertMainLayer',
				    'TFMobileBertModel',
				    'TFMobileBertPreTrainedModel',
				]


if TYPE_CHECKING:
				from .configuration_mobilebert import (
				    MOBILEBERT_PRETRAINED_CONFIG_ARCHIVE_MAP,
				    MobileBertConfig,
				    MobileBertOnnxConfig,
				)
				from .tokenization_mobilebert import MobileBertTokenizer

				try:
								if not is_tokenizers_available():
												raise OptionalDependencyNotAvailable()
				except OptionalDependencyNotAvailable:
								pass
				else:
								from .tokenization_mobilebert_fast import MobileBertTokenizerFast

				try:
								if not is_torch_available():
												raise OptionalDependencyNotAvailable()
				except OptionalDependencyNotAvailable:
								pass
				else:
								from .modeling_mobilebert import (
								    MOBILEBERT_PRETRAINED_MODEL_ARCHIVE_LIST,
								    MobileBertForMaskedLM,
								    MobileBertForMultipleChoice,
								    MobileBertForNextSentencePrediction,
								    MobileBertForPreTraining,
								    MobileBertForQuestionAnswering,
								    MobileBertForSequenceClassification,
								    MobileBertForTokenClassification,
								    MobileBertLayer,
								    MobileBertModel,
								    MobileBertPreTrainedModel,
								    load_tf_weights_in_mobilebert,
								)

				try:
								if not is_tf_available():
												raise OptionalDependencyNotAvailable()
				except OptionalDependencyNotAvailable:
								pass
				else:
								from .modeling_tf_mobilebert import (
								    TF_MOBILEBERT_PRETRAINED_MODEL_ARCHIVE_LIST,
								    TFMobileBertForMaskedLM,
								    TFMobileBertForMultipleChoice,
								    TFMobileBertForNextSentencePrediction,
								    TFMobileBertForPreTraining,
								    TFMobileBertForQuestionAnswering,
								    TFMobileBertForSequenceClassification,
								    TFMobileBertForTokenClassification,
								    TFMobileBertMainLayer,
								    TFMobileBertModel,
								    TFMobileBertPreTrainedModel,
								)

else:
				import sys

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