





'''simple docstring'''






from __future__ import annotations

import time

__lowerCamelCase						: Union[str, Any]		=   list[tuple[int, int]]

__lowerCamelCase						: Dict		=   [
    [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[str]		=   [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right







class 		UpperCAmelCase   :


  """simple docstring"""







  def __init__(				self    :					Dict							,	UpperCamelCase__    :					int							,	UpperCamelCase__    :					int							,	UpperCamelCase__    :					int							,	UpperCamelCase__    :					int							,	UpperCamelCase__    :					Node | None  )     ->						List[Any]:
    _UpperCamelCase       			=pos_x
    _UpperCamelCase       			=pos_y
    _UpperCamelCase       			=(pos_y, pos_x)
    _UpperCamelCase       			=goal_x
    _UpperCamelCase       			=goal_y
    _UpperCamelCase       			=parent







class 		UpperCAmelCase   :


  """simple docstring"""







  def __init__(				self    :					Optional[int]							,	UpperCamelCase__    :					tuple[int, int]							,	UpperCamelCase__    :					tuple[int, int]  )     ->						Optional[int]:
    _UpperCamelCase       			=Node(start[1]							,	start[0]							,	goal[1]							,	goal[0]							,	UpperCamelCase__  )
    _UpperCamelCase       			=Node(goal[1]							,	goal[0]							,	goal[1]							,	goal[0]							,	UpperCamelCase__  )

    _UpperCamelCase       			=[self.start]
    _UpperCamelCase       			=False


  def   UpperCamelCase__      (				self    :					List[Any]  )     ->						Path | None:
    while self.node_queue:
      _UpperCamelCase       			=self.node_queue.pop(0  )

      if current_node.pos == self.target.pos:
        _UpperCamelCase       			=True
        return self.retrace_path(UpperCamelCase__  )

      _UpperCamelCase       			=self.get_successors(UpperCamelCase__  )

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

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


  def   UpperCamelCase__      (				self    :					List[Any]							,	UpperCamelCase__    :					Node  )     ->						list[Node]:
    _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(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   UpperCamelCase__      (				self    :					Dict							,	UpperCamelCase__    :					Node | None  )     ->						Path:
    _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 		UpperCAmelCase   :


  """simple docstring"""







  def __init__(				self    :					Any							,	UpperCamelCase__    :					List[str]							,	UpperCamelCase__    :					str  )     ->						Optional[int]:
    _UpperCamelCase       			=BreadthFirstSearch(UpperCamelCase__							,	UpperCamelCase__  )
    _UpperCamelCase       			=BreadthFirstSearch(UpperCamelCase__							,	UpperCamelCase__  )
    _UpperCamelCase       			=False


  def   UpperCamelCase__      (				self    :					Tuple  )     ->						Path | None:
    while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
      _UpperCamelCase       			=self.fwd_bfs.node_queue.pop(0  )
      _UpperCamelCase       			=self.bwd_bfs.node_queue.pop(0  )

      if current_bwd_node.pos == current_fwd_node.pos:
        _UpperCamelCase       			=True
        return self.retrace_bidirectional_path(
            UpperCamelCase__							,	UpperCamelCase__  )

      _UpperCamelCase       			=current_bwd_node
      _UpperCamelCase       			=current_fwd_node

      _UpperCamelCase       			={
          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   UpperCamelCase__      (				self    :					str							,	UpperCamelCase__    :					Node							,	UpperCamelCase__    :					Node  )     ->						Path:
    _UpperCamelCase       			=self.fwd_bfs.retrace_path(UpperCamelCase__  )
    _UpperCamelCase       			=self.bwd_bfs.retrace_path(UpperCamelCase__  )
    bwd_path.pop()
    bwd_path.reverse()
    _UpperCamelCase       			=fwd_path + bwd_path
    return path


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

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

      __lowerCamelCase						: Any		=   time.time()
      __lowerCamelCase						: Any		=   BreadthFirstSearch(init, goal)
      __lowerCamelCase						: Dict		=   bfs.search()
      __lowerCamelCase						: Tuple		=   time.time() - start_bfs_time

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

      __lowerCamelCase						: Optional[Any]		=   time.time()
      __lowerCamelCase						: Optional[int]		=   BidirectionalBreadthFirstSearch(init, goal)
      __lowerCamelCase						: Any		=   bd_bfs.search()
      __lowerCamelCase						: Optional[int]		=   time.time() - start_bd_bfs_time

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













'''simple docstring'''






import contextlib
from multiprocessing import Pool, RLock

from tqdm.auto import tqdm

from ..utils import experimental, logging


__lowerCamelCase						: Union[str, Any]		=   logging.get_logger(__name__)







class 		UpperCAmelCase   :


  """simple docstring"""







  lowerCAmelCase_					=				None




@experimental
def 					_a   (__SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE   ):


  """simple docstring"""

  if ParallelBackendConfig.backend_name is None:
    return _map_with_multiprocessing_pool(
        __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE   )

  return _map_with_joblib(__SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE   )


def 					_a   (__SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE   ):


  """simple docstring"""

  _UpperCamelCase       			=num_proc if num_proc <= len(__SCREAMING_SNAKE_CASE   ) else len(__SCREAMING_SNAKE_CASE   )
  _UpperCamelCase       			=[]  # We organize the splits ourselve (contiguous splits)
  for index in range(__SCREAMING_SNAKE_CASE   ):
    _UpperCamelCase       			=len(__SCREAMING_SNAKE_CASE   ) // num_proc
    _UpperCamelCase       			=len(__SCREAMING_SNAKE_CASE   ) % num_proc
    _UpperCamelCase       			=div * index + min(__SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE   )
    _UpperCamelCase       			=start + div + (1 if index < mod else 0)
    split_kwds.append((function, iterable[start:end], types, index, disable_tqdm, desc)   )

  if len(__SCREAMING_SNAKE_CASE   ) != sum(len(i[1]   ) for i in split_kwds   ):
    raise ValueError(
        f'''Error dividing inputs iterable among processes. '''
        f'''Total number of objects {len(__SCREAMING_SNAKE_CASE   )}, '''
        f'''length: {sum(len(i[1]   ) for i in split_kwds   )}'''   )

  logger.info(
      f'''Spawning {num_proc} processes for {len(__SCREAMING_SNAKE_CASE   )} objects in slices of {[len(i[1]   ) for i in split_kwds]}'''   )
  _UpperCamelCase			,     _UpperCamelCase       			=None, None
  if not disable_tqdm:
    _UpperCamelCase			,     _UpperCamelCase       			=(RLock(),), tqdm.set_lock
  with Pool(__SCREAMING_SNAKE_CASE  ,      initargs=__SCREAMING_SNAKE_CASE  ,      initializer=__SCREAMING_SNAKE_CASE   ) as pool:
    _UpperCamelCase       			=pool.map(__SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE   )
  logger.info(f'''Finished {num_proc} processes'''   )
  _UpperCamelCase       			=[obj for proc_res in mapped for obj in proc_res]
  logger.info(f'''Unpacked {len(__SCREAMING_SNAKE_CASE   )} objects'''   )

  return mapped


def 					_a   (__SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE  ,      __SCREAMING_SNAKE_CASE   ):


  """simple docstring"""

  import joblib

  with joblib.parallel_backend(ParallelBackendConfig.backend_name  ,      n_jobs=__SCREAMING_SNAKE_CASE   ):
    return joblib.Parallel()(
        joblib.delayed(__SCREAMING_SNAKE_CASE   )((function, obj, types, None, True, None)   ) for obj in iterable   )


@experimental
@contextlib.contextmanager
def 					_a   (__SCREAMING_SNAKE_CASE   ):


  """simple docstring"""

  _UpperCamelCase       			=backend_name

  if backend_name == "spark":
    from joblibspark import register_spark

    register_spark()

    # TODO: call create_cache_and_write_probe if "download" in steps
    # TODO: raise NotImplementedError when Dataset.map etc is called

  try:
    yield
  finally:
    _UpperCamelCase       			=None






