
"""simple docstring"""






from __future__ import annotations

import time

__SCREAMING_SNAKE_CASE							=     list[tuple[int, int]]

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

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





class 				a__					:



     def __init__(							self :List[str]      ,  _lowerCamelCase :int      ,  _lowerCamelCase :int      ,  _lowerCamelCase :int      ,  _lowerCamelCase :int      ,  _lowerCamelCase :Node | None   ):







      '''simple docstring'''



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





class 				a__					:



     def __init__(							self :Dict      ,  _lowerCamelCase :tuple[int, int]      ,  _lowerCamelCase :tuple[int, int]   ):







      '''simple docstring'''



      UpperCamelCase_     :					str   	=Node(start[1]      ,  start[0]      ,  goal[1]      ,  goal[0]      ,  _lowerCamelCase   )
      UpperCamelCase_     :					Dict   	=Node(goal[1]      ,  goal[0]      ,  goal[1]      ,  goal[0]      ,  _lowerCamelCase   )

      UpperCamelCase_     :					Optional[Any]   	=[self.start]
      UpperCamelCase_     :					Union[str, Any]   	=False



     def  lowerCamelCase_						(							self :int   ):







      '''simple docstring'''



      while self.node_queue:
       UpperCamelCase_     :					Union[str, Any]   	=self.node_queue.pop(0   )

       if current_node.pos == self.target.pos:
        UpperCamelCase_     :					Any   	=True
        return self.retrace_path(_lowerCamelCase   )

       UpperCamelCase_     :					str   	=self.get_successors(_lowerCamelCase   )

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

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



     def  lowerCamelCase_						(							self :Any      ,  _lowerCamelCase :Node   ):







      '''simple docstring'''



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

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

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




     def  lowerCamelCase_						(							self :List[Any]      ,  _lowerCamelCase :Node | None   ):







      '''simple docstring'''



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





class 				a__					:



     def __init__(							self :Any      ,  _lowerCamelCase :Optional[Any]      ,  _lowerCamelCase :Union[str, Any]   ):







      '''simple docstring'''



      UpperCamelCase_     :					List[Any]   	=BreadthFirstSearch(_lowerCamelCase      ,  _lowerCamelCase   )
      UpperCamelCase_     :					int   	=BreadthFirstSearch(_lowerCamelCase      ,  _lowerCamelCase   )
      UpperCamelCase_     :					Optional[Any]   	=False



     def  lowerCamelCase_						(							self :List[str]   ):







      '''simple docstring'''



      while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
       UpperCamelCase_     :					Tuple   	=self.fwd_bfs.node_queue.pop(0   )
       UpperCamelCase_     :					Any   	=self.bwd_bfs.node_queue.pop(0   )

       if current_bwd_node.pos == current_fwd_node.pos:
        UpperCamelCase_     :					List[Any]   	=True
        return self.retrace_bidirectional_path(
            _lowerCamelCase      ,  _lowerCamelCase   )

       UpperCamelCase_     :					List[Any]   	=current_bwd_node
       UpperCamelCase_     :					List[Any]   	=current_fwd_node

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

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

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




     def  lowerCamelCase_						(							self :Optional[int]      ,  _lowerCamelCase :Node      ,  _lowerCamelCase :Node   ):







      '''simple docstring'''



      UpperCamelCase_     :					str   	=self.fwd_bfs.retrace_path(_lowerCamelCase   )
      UpperCamelCase_     :					str   	=self.bwd_bfs.retrace_path(_lowerCamelCase   )
      bwd_path.pop()
      bwd_path.reverse()
      UpperCamelCase_     :					Any   	=fwd_path + bwd_path
      return path


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

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

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

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

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

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


"""simple docstring"""






# This code is adapted from OpenAI's release
# https://github.com/openai/human-eval/blob/master/human_eval/execution.py

import contextlib
import faulthandler
import io
import multiprocessing
import os
import platform
import signal
import tempfile




def       A_  (				__lowercase						,	__lowercase						,	__lowercase						,	__lowercase	):
 UpperCamelCase_     :					Tuple   	=multiprocessing.Manager()
 UpperCamelCase_     :					Dict   	=manager.list()

 UpperCamelCase_     :					Union[str, Any]   	=multiprocessing.Process(target=__lowercase						,	args=(check_program, result, timeout)	)
 p.start()
 p.join(timeout=timeout + 1	)
 if p.is_alive():
  p.kill()

 if not result:
  result.append('timed out'	)

 return {
     "task_id": task_id,
     "passed": result[0] == "passed",
     "result": result[0],
     "completion_id": completion_id,
 }




def       A_  (				__lowercase						,	__lowercase						,	__lowercase	):
 with create_tempdir():
  # These system calls are needed when cleaning up tempdir.
  import os
  import shutil

  UpperCamelCase_     :					Tuple   	=shutil.rmtree
  UpperCamelCase_     :					List[str]   	=os.rmdir
  UpperCamelCase_     :					Any   	=os.chdir

  # Disable functionalities that can make destructive changes to the test.
  reliability_guard()

  # Run program.
  try:
   UpperCamelCase_     :					List[str]   	={}
   with swallow_io():
    with time_limit(__lowercase	):
     exec(__lowercase						,	__lowercase	)
   result.append('passed'	)
  except TimeoutException:
   result.append('timed out'	)
  except BaseException as e:
   result.append(F'''failed: {e}'''	)

  # Needed for cleaning up.
  UpperCamelCase_     :					Optional[Any]   	=rmtree
  UpperCamelCase_     :					str   	=rmdir
  UpperCamelCase_     :					Dict   	=chdir




@contextlib.contextmanager
def       A_  (				__lowercase	):
 def signal_handler(__lowercase						,	__lowercase	):
  raise TimeoutException('Timed out!'	)

 signal.setitimer(signal.ITIMER_REAL						,	__lowercase	)
 signal.signal(signal.SIGALRM						,	__lowercase	)
 try:
  yield
 finally:
  signal.setitimer(signal.ITIMER_REAL						,	0	)




@contextlib.contextmanager
def       A_  (				):
 UpperCamelCase_     :					str   	=WriteOnlyStringIO()
 with contextlib.redirect_stdout(__lowercase	):
  with contextlib.redirect_stderr(__lowercase	):
   with redirect_stdin(__lowercase	):
    yield




@contextlib.contextmanager
def       A_  (				):
 with tempfile.TemporaryDirectory() as dirname:
  with chdir(__lowercase	):
   yield dirname





class 				a__					(						A__       ):
     pass





class 				a__					(						io.StringIO       ):



     def  lowerCamelCase_						(							self :Any      ,  *_lowerCamelCase :Any      ,  **_lowerCamelCase :Tuple   ):







      '''simple docstring'''



      raise OSError



     def  lowerCamelCase_						(							self :Union[str, Any]      ,  *_lowerCamelCase :Any      ,  **_lowerCamelCase :Tuple   ):







      '''simple docstring'''



      raise OSError



     def  lowerCamelCase_						(							self :Tuple      ,  *_lowerCamelCase :str      ,  **_lowerCamelCase :List[str]   ):







      '''simple docstring'''



      raise OSError




     def  lowerCamelCase_						(							self :List[str]      ,  *_lowerCamelCase :Optional[int]      ,  **_lowerCamelCase :str   ):







      '''simple docstring'''



      return False





class 				a__					(						contextlib._RedirectStream       ):  # type: ignore
     UpperCAmelCase__         =      '''stdin'''




@contextlib.contextmanager
def       A_  (				__lowercase	):
 if root == ".":
  yield
  return
 UpperCamelCase_     :					List[str]   	=os.getcwd()
 os.chdir(__lowercase	)
 try:
  yield
 except BaseException as exc:
  raise exc
 finally:
  os.chdir(__lowercase	)





def       A_  (				__lowercase=None	):

 if maximum_memory_bytes is not None:
  import resource

  resource.setrlimit(resource.RLIMIT_AS						,	(maximum_memory_bytes, maximum_memory_bytes)	)
  resource.setrlimit(resource.RLIMIT_DATA						,	(maximum_memory_bytes, maximum_memory_bytes)	)
  if not platform.uname().system == "Darwin":
   resource.setrlimit(resource.RLIMIT_STACK						,	(maximum_memory_bytes, maximum_memory_bytes)	)

 faulthandler.disable()

 import builtins

 UpperCamelCase_     :					Any   	=None
 UpperCamelCase_     :					Any   	=None

 import os

 UpperCamelCase_     :					Union[str, Any]   	='1'

 UpperCamelCase_     :					Union[str, Any]   	=None
 UpperCamelCase_     :					Optional[Any]   	=None
 UpperCamelCase_     :					Optional[Any]   	=None
 UpperCamelCase_     :					Optional[Any]   	=None
 UpperCamelCase_     :					Dict   	=None
 UpperCamelCase_     :					List[Any]   	=None
 UpperCamelCase_     :					Any   	=None
 UpperCamelCase_     :					str   	=None
 UpperCamelCase_     :					Optional[int]   	=None
 UpperCamelCase_     :					Union[str, Any]   	=None
 UpperCamelCase_     :					str   	=None
 UpperCamelCase_     :					str   	=None
 UpperCamelCase_     :					List[Any]   	=None
 UpperCamelCase_     :					Optional[Any]   	=None
 UpperCamelCase_     :					str   	=None
 UpperCamelCase_     :					List[str]   	=None
 UpperCamelCase_     :					Optional[Any]   	=None
 UpperCamelCase_     :					int   	=None
 UpperCamelCase_     :					Optional[Any]   	=None
 UpperCamelCase_     :					Tuple   	=None
 UpperCamelCase_     :					List[Any]   	=None
 UpperCamelCase_     :					Tuple   	=None
 UpperCamelCase_     :					Dict   	=None
 UpperCamelCase_     :					Optional[int]   	=None
 UpperCamelCase_     :					str   	=None
 UpperCamelCase_     :					Union[str, Any]   	=None
 UpperCamelCase_     :					int   	=None

 import shutil

 UpperCamelCase_     :					List[str]   	=None
 UpperCamelCase_     :					Optional[Any]   	=None
 UpperCamelCase_     :					Dict   	=None

 import subprocess

 UpperCamelCase_     :					Optional[int]   	=None  # type: ignore

 UpperCamelCase_     :					Union[str, Any]   	=None

 import sys

 UpperCamelCase_     :					Union[str, Any]   	=None
 UpperCamelCase_     :					Tuple   	=None
 UpperCamelCase_     :					Union[str, Any]   	=None
 UpperCamelCase_     :					Dict   	=None
 UpperCamelCase_     :					Any   	=None
