

import logging
import os
import threading
import time


try:
   import warnings
except ImportError:
   a_    :						Tuple    		=      None

try:
   import msvcrt
except ImportError:
   a_    :						List[Any]    		=      None

try:
   import fcntl
except ImportError:
   a_    :						List[Any]    		=      None


# Backward compatibility
# ------------------------------------------------
try:
   TimeoutError
except NameError:
   a_    :						Union[str, Any]    		=      OSError


# Data
# ------------------------------------------------
a_    :						str    		=      [
    "Timeout",
    "BaseFileLock",
    "WindowsFileLock",
    "UnixFileLock",
    "SoftFileLock",
    "FileLock",
]

a_    :						Any    		=      "3.0.12"


a_    :						Union[str, Any]    		=      None


def        __lowerCAmelCase    (       )		->							Optional[Any]:
 '''simple docstring'''


 global _logger
 SCREAMING_SNAKE_CASE								=			_logger or logging.getLogger(__name__	)
 return _logger




class      UpperCamelCase (     __a   ):

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

     """simple docstring"""






     SCREAMING_SNAKE_CASE								=			lock_file
     return None




    def __str__(			self :      int    ):

     """simple docstring"""






     SCREAMING_SNAKE_CASE								=			F"""The file lock '{self.lock_file}' could not be acquired."""
     return temp




class      UpperCamelCase :

    def __init__(			self :      Optional[Any]							,    snake_case__ :      Dict    ):

     """simple docstring"""






     SCREAMING_SNAKE_CASE								=			lock
     return None

    def __enter__(			self :      int    ):

     """simple docstring"""






     return self.lock




    def __exit__(			self :      int							,    snake_case__ :      Union[str, Any]							,    snake_case__ :      Dict							,    snake_case__ :      Tuple    ):

     """simple docstring"""






     self.lock.release()
     return None




class      UpperCamelCase :

    def __init__(			self :      List[Any]							,    snake_case__ :      List[Any]							,    snake_case__ :      Dict=-1							,    snake_case__ :      int=None    ):

     """simple docstring"""






     SCREAMING_SNAKE_CASE								=			max_filename_length if max_filename_length is not None else 2_5_5
     # Hash the filename if it's too long
     SCREAMING_SNAKE_CASE								=			self.hash_filename_if_too_long(lowerCAmelCase_							,    lowerCAmelCase_    )
     # The path to the lock file.
     SCREAMING_SNAKE_CASE								=			lock_file

     # The file descriptor for the *_lock_file* as it is returned by the
     # os.open() function.
     # This file lock is only NOT None, if the object currently holds the
     # lock.
     SCREAMING_SNAKE_CASE								=			None

     # The default timeout value.
     SCREAMING_SNAKE_CASE								=			timeout

     # We use this lock primarily for the lock counter.
     SCREAMING_SNAKE_CASE								=			threading.Lock()

     # The lock counter is used for implementing the nested locking
     # mechanism. Whenever the lock is acquired, the counter is increased and
     # the lock is only released, when this value is 0 again.
     SCREAMING_SNAKE_CASE								=			0
     return None

    @property
    def UpperCamelCase			(			self :      Dict    ):

     """simple docstring"""






     return self._lock_file

    @property
    def UpperCamelCase			(			self :      List[Any]    ):

     """simple docstring"""






     return self._timeout

    @timeout.setter
    def UpperCamelCase			(			self :      str							,    snake_case__ :      str    ):

     """simple docstring"""






     SCREAMING_SNAKE_CASE								=			float(lowerCAmelCase_    )
     return None

    def UpperCamelCase			(			self :      Union[str, Any]    ):

     """simple docstring"""






     raise NotImplementedError()

    def UpperCamelCase			(			self :      Union[str, Any]    ):

     """simple docstring"""






     raise NotImplementedError()

    @property
    def UpperCamelCase			(			self :      Any    ):

     """simple docstring"""






     return self._lock_file_fd is not None

    def UpperCamelCase			(			self :      str							,    snake_case__ :      Dict=None							,    snake_case__ :      Optional[int]=0.05    ):

     """simple docstring"""






     if timeout is None:
      SCREAMING_SNAKE_CASE								=			self.timeout

     # Increment the number right at the beginning.
     # We can still undo it, if something fails.
     with self._thread_lock:
      self._lock_counter += 1

     SCREAMING_SNAKE_CASE								=			id(self    )
     SCREAMING_SNAKE_CASE								=			self._lock_file
     SCREAMING_SNAKE_CASE								=			time.time()
     try:
      while True:
       with self._thread_lock:
        if not self.is_locked:
         logger().debug(F"""Attempting to acquire lock {lock_id} on {lock_filename}"""    )
         self._acquire()

       if self.is_locked:
        logger().debug(F"""Lock {lock_id} acquired on {lock_filename}"""    )
        break
       elif timeout >= 0 and time.time() - start_time > timeout:
        logger().debug(F"""Timeout on acquiring lock {lock_id} on {lock_filename}"""    )
        raise Timeout(self._lock_file    )
       else:
        logger().debug(
            F"""Lock {lock_id} not acquired on {lock_filename}, waiting {poll_intervall} seconds ..."""    )
        time.sleep(lowerCAmelCase_    )
     except:  # noqa
      # Something did go wrong, so decrement the counter.
      with self._thread_lock:
       SCREAMING_SNAKE_CASE								=			max(0							,    self._lock_counter - 1    )

      raise
     return _Acquire_ReturnProxy(lock=self    )

    def UpperCamelCase			(			self :      List[Any]							,    snake_case__ :      Optional[int]=False    ):

     """simple docstring"""






     with self._thread_lock:
      if self.is_locked:
       self._lock_counter -= 1

       if self._lock_counter == 0 or force:
        SCREAMING_SNAKE_CASE								=			id(self    )
        SCREAMING_SNAKE_CASE								=			self._lock_file

        logger().debug(F"""Attempting to release lock {lock_id} on {lock_filename}"""    )
        self._release()
        SCREAMING_SNAKE_CASE								=			0
        logger().debug(F"""Lock {lock_id} released on {lock_filename}"""    )

     return None

    def __enter__(			self :      List[Any]    ):

     """simple docstring"""






     self.acquire()
     return self

    def __exit__(			self :      Union[str, Any]							,    snake_case__ :      Any							,    snake_case__ :      List[str]							,    snake_case__ :      Optional[Any]    ):

     """simple docstring"""






     self.release()
     return None

    def __del__(			self :      int    ):

     """simple docstring"""






     self.release(force=lowerCAmelCase_    )
     return None




    def UpperCamelCase			(			self :      Tuple							,    snake_case__ :      Dict							,    snake_case__ :      List[str]    ):

     """simple docstring"""






     SCREAMING_SNAKE_CASE								=			os.path.basename(lowerCAmelCase_    )
     if len(lowerCAmelCase_    ) > max_length and max_length > 0:
      SCREAMING_SNAKE_CASE								=			os.path.dirname(lowerCAmelCase_    )
      SCREAMING_SNAKE_CASE								=			str(hash(lowerCAmelCase_    )    )
      SCREAMING_SNAKE_CASE								=			filename[: max_length - len(lowerCAmelCase_    ) - 8] + '...' + hashed_filename + '.lock'
      return os.path.join(lowerCAmelCase_							,    lowerCAmelCase_    )
     else:
      return path




class      UpperCamelCase (     __a   ):

    def __init__(			self :      Union[str, Any]							,    snake_case__ :      Union[str, Any]							,    snake_case__ :      Tuple=-1							,    snake_case__ :      int=None    ):

     """simple docstring"""






     from .file_utils import relative_to_absolute_path

     super().__init__(lowerCAmelCase_							,    timeout=lowerCAmelCase_							,    max_filename_length=lowerCAmelCase_    )
     SCREAMING_SNAKE_CASE								=			'\\\\?\\' + relative_to_absolute_path(self.lock_file    )

    def UpperCamelCase			(			self :      int    ):

     """simple docstring"""






     SCREAMING_SNAKE_CASE								=			os.O_RDWR | os.O_CREAT | os.O_TRUNC

     try:
      SCREAMING_SNAKE_CASE								=			os.open(self._lock_file							,    lowerCAmelCase_    )
     except OSError:
      pass
     else:
      try:
       msvcrt.locking(lowerCAmelCase_							,    msvcrt.LK_NBLCK							,    1    )
      except OSError:
       os.close(lowerCAmelCase_    )
      else:
       SCREAMING_SNAKE_CASE								=			fd
     return None




    def UpperCamelCase			(			self :      Tuple    ):

     """simple docstring"""






     SCREAMING_SNAKE_CASE								=			self._lock_file_fd
     SCREAMING_SNAKE_CASE								=			None
     msvcrt.locking(lowerCAmelCase_							,    msvcrt.LK_UNLCK							,    1    )
     os.close(lowerCAmelCase_    )

     try:
      os.remove(self._lock_file    )
     # Probably another instance of the application
     # that acquired the file lock.
     except OSError:
      pass
     return None




class      UpperCamelCase (     __a   ):

    def __init__(			self :      Optional[int]							,    snake_case__ :      Tuple							,    snake_case__ :      List[Any]=-1							,    snake_case__ :      int=None    ):

     """simple docstring"""






     SCREAMING_SNAKE_CASE								=			os.statvfs(os.path.dirname(lowerCAmelCase_    )    ).f_namemax
     super().__init__(lowerCAmelCase_							,    timeout=lowerCAmelCase_							,    max_filename_length=lowerCAmelCase_    )

    def UpperCamelCase			(			self :      List[str]    ):

     """simple docstring"""






     SCREAMING_SNAKE_CASE								=			os.O_RDWR | os.O_CREAT | os.O_TRUNC
     SCREAMING_SNAKE_CASE								=			os.open(self._lock_file							,    lowerCAmelCase_    )

     try:
      fcntl.flock(lowerCAmelCase_							,    fcntl.LOCK_EX | fcntl.LOCK_NB    )
     except OSError:
      os.close(lowerCAmelCase_    )
     else:
      SCREAMING_SNAKE_CASE								=			fd
     return None




    def UpperCamelCase			(			self :      Tuple    ):

     """simple docstring"""






     SCREAMING_SNAKE_CASE								=			self._lock_file_fd
     SCREAMING_SNAKE_CASE								=			None
     fcntl.flock(lowerCAmelCase_							,    fcntl.LOCK_UN    )
     os.close(lowerCAmelCase_    )
     return None




class      UpperCamelCase (     __a   ):

    def UpperCamelCase			(			self :      Union[str, Any]    ):

     """simple docstring"""






     SCREAMING_SNAKE_CASE								=			os.O_WRONLY | os.O_CREAT | os.O_EXCL | os.O_TRUNC
     try:
      SCREAMING_SNAKE_CASE								=			os.open(self._lock_file							,    lowerCAmelCase_    )
     except OSError:
      pass
     else:
      SCREAMING_SNAKE_CASE								=			fd
     return None




    def UpperCamelCase			(			self :      List[Any]    ):

     """simple docstring"""






     os.close(self._lock_file_fd    )
     SCREAMING_SNAKE_CASE								=			None

     try:
      os.remove(self._lock_file    )
     # The file is already deleted and that's what we want.
     except OSError:
      pass
     return None


a_    :						Optional[int]    		=      None

if msvcrt:
   a_    :						List[str]    		=      WindowsFileLock
elif fcntl:
   a_    :						List[str]    		=      UnixFileLock
else:
   a_    :						Tuple    		=      SoftFileLock

   if warnings is not None:
      warnings.warn("only soft file lock is available")




import heapq
import sys

import numpy as np

a_    :						Optional[int]    		=      tuple[int, int]




class      UpperCamelCase :

    def __init__(			self :      Dict    ):

     """simple docstring"""






     SCREAMING_SNAKE_CASE								=			[]
     SCREAMING_SNAKE_CASE								=			set()

    def UpperCamelCase			(			self :      List[Any]    ):

     """simple docstring"""






     if not self.empty():
      return self.elements[0][0]
     else:
      return float('inf'    )

    def UpperCamelCase			(			self :      List[str]    ):

     """simple docstring"""






     return len(self.elements    ) == 0

    def UpperCamelCase			(			self :      Union[str, Any]							,    snake_case__ :      Optional[Any]							,    snake_case__ :      List[Any]    ):

     """simple docstring"""






     if item not in self.set:
      heapq.heappush(self.elements							,    (priority, item)    )
      self.set.add(snake_case__    )
     else:
      # update
      # print("update", item)
      SCREAMING_SNAKE_CASE								=			[]
      ((SCREAMING_SNAKE_CASE)						,	(SCREAMING_SNAKE_CASE))								=			heapq.heappop(self.elements    )
      while x != item:
       temp.append((pri, x)    )
       ((SCREAMING_SNAKE_CASE)						,	(SCREAMING_SNAKE_CASE))								=			heapq.heappop(self.elements    )
      temp.append((priority, item)    )
      for pro, xxx in temp:
       heapq.heappush(self.elements							,    (pro, xxx)    )

    def UpperCamelCase			(			self :      Dict							,    snake_case__ :      Dict    ):

     """simple docstring"""






     if item in self.set:
      self.set.remove(snake_case__    )
      SCREAMING_SNAKE_CASE								=			[]
      ((SCREAMING_SNAKE_CASE)						,	(SCREAMING_SNAKE_CASE))								=			heapq.heappop(self.elements    )
      while x != item:
       temp.append((pro, x)    )
       ((SCREAMING_SNAKE_CASE)						,	(SCREAMING_SNAKE_CASE))								=			heapq.heappop(self.elements    )
      for prito, yyy in temp:
       heapq.heappush(self.elements							,    (prito, yyy)    )

    def UpperCamelCase			(			self :      str    ):

     """simple docstring"""






     return self.elements[0][1]




    def UpperCamelCase			(			self :      Tuple    ):

     """simple docstring"""






     ((SCREAMING_SNAKE_CASE)						,	(SCREAMING_SNAKE_CASE))								=			heapq.heappop(self.elements    )
     self.set.remove(snake_case__    )
     return (priority, item)


def        __lowerCAmelCase    (       _UpperCamelCase		:  TPos		,							_UpperCamelCase		:  TPos	)		->							Optional[Any]:
 '''simple docstring'''


 SCREAMING_SNAKE_CASE								=			np.array(_UpperCamelCase	)
 SCREAMING_SNAKE_CASE								=			np.array(_UpperCamelCase	)
 return np.linalg.norm(a - b	)


def        __lowerCAmelCase    (       _UpperCamelCase		:  TPos		,							_UpperCamelCase		:  TPos	)		->							Dict:
 '''simple docstring'''


 return consistent_heuristic(_UpperCamelCase		,							_UpperCamelCase	) // t


def        __lowerCAmelCase    (       _UpperCamelCase		:  TPos		,							_UpperCamelCase		:  TPos	)		->							Optional[int]:
 '''simple docstring'''


 return abs(p[0] - goal[0]	) + abs(p[1] - goal[1]	)


def        __lowerCAmelCase    (       _UpperCamelCase		:  TPos		,							_UpperCamelCase		:  int		,							_UpperCamelCase		:  TPos		,							_UpperCamelCase		:  dict[TPos, float]	)		->							List[str]:
 '''simple docstring'''


 SCREAMING_SNAKE_CASE								=			g_function[start] + Wa * heuristics[i](_UpperCamelCase		,							_UpperCamelCase	)
 return ans


def        __lowerCAmelCase    (       _UpperCamelCase		:  List[str]		,							_UpperCamelCase		:  int		,							_UpperCamelCase		:  Tuple	)		->							int:
 '''simple docstring'''


 SCREAMING_SNAKE_CASE								=			np.chararray((n, n)	)
 for i in range(_UpperCamelCase	):
  for j in range(_UpperCamelCase	):
   SCREAMING_SNAKE_CASE								=			'*'

 for i in range(_UpperCamelCase	):
  for j in range(_UpperCamelCase	):
   if (j, (n - 1) - i) in blocks:
    SCREAMING_SNAKE_CASE								=			'#'

 SCREAMING_SNAKE_CASE								=			'-'
 SCREAMING_SNAKE_CASE								=			back_pointer[goal]
 while x != start:
  ((SCREAMING_SNAKE_CASE)						,	(SCREAMING_SNAKE_CASE))								=			x
  # print(x)
  SCREAMING_SNAKE_CASE								=			'-'
  SCREAMING_SNAKE_CASE								=			back_pointer[x]
 SCREAMING_SNAKE_CASE								=			'-'

 for i in range(_UpperCamelCase	):
  for j in range(_UpperCamelCase	):
   if (i, j) == (0, n - 1):
    print(grid[i][j]		,							end=' '	)
    print('<-- End position'		,							end=' '	)
   else:
    print(grid[i][j]		,							end=' '	)
  print()
 print('^'	)
 print('Start position'	)
 print()
 print('# is an obstacle'	)
 print('- is the path taken by algorithm'	)
 print('PATH TAKEN BY THE ALGORITHM IS:-'	)
 SCREAMING_SNAKE_CASE								=			back_pointer[goal]
 while x != start:
  print(_UpperCamelCase		,							end=' '	)
  SCREAMING_SNAKE_CASE								=			back_pointer[x]
 print(_UpperCamelCase	)
 sys.exit()


def        __lowerCAmelCase    (       _UpperCamelCase		:  TPos	)		->							Any:
 '''simple docstring'''


 if p[0] < 0 or p[0] > n - 1:
  return False
 if p[1] < 0 or p[1] > n - 1:
  return False
 return True


def        __lowerCAmelCase    (       _UpperCamelCase		:  List[Any]		,							_UpperCamelCase		:  Tuple		,							_UpperCamelCase		:  Any		,							_UpperCamelCase		:  Union[str, Any]		,							_UpperCamelCase		:  Union[str, Any]		,							_UpperCamelCase		:  Tuple		,							_UpperCamelCase		:  List[Any]		,							_UpperCamelCase		:  Optional[Any]		,							)		->							List[Any]:
 '''simple docstring'''


 for itera in range(_UpperCamelCase	):
  open_list[itera].remove_element(_UpperCamelCase	)
 # print("s", s)
 # print("j", j)
 ((SCREAMING_SNAKE_CASE)						,	(SCREAMING_SNAKE_CASE))								=			s
 SCREAMING_SNAKE_CASE								=			(x - 1, y)
 SCREAMING_SNAKE_CASE								=			(x + 1, y)
 SCREAMING_SNAKE_CASE								=			(x, y + 1)
 SCREAMING_SNAKE_CASE								=			(x, y - 1)

 for neighbours in [left, right, up, down]:
  if neighbours not in blocks:
   if valid(_UpperCamelCase	) and neighbours not in visited:
    # print("neighbour", neighbours)
    visited.add(_UpperCamelCase	)
    SCREAMING_SNAKE_CASE								=			-1
    SCREAMING_SNAKE_CASE								=			float('inf'	)

   if valid(_UpperCamelCase	) and g_function[neighbours] > g_function[s] + 1:
    SCREAMING_SNAKE_CASE								=			g_function[s] + 1
    SCREAMING_SNAKE_CASE								=			s
    if neighbours not in close_list_anchor:
     open_list[0].put(_UpperCamelCase		,							key(_UpperCamelCase		,							0		,							_UpperCamelCase		,							_UpperCamelCase	)	)
     if neighbours not in close_list_inad:
      for var in range(1		,							_UpperCamelCase	):
       if key(_UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase	) <= Wa * key(
           _UpperCamelCase		,							0		,							_UpperCamelCase		,							_UpperCamelCase	):
        open_list[j].put(
            _UpperCamelCase		,							key(_UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase	)	)


def        __lowerCAmelCase    (       )		->							Tuple:
 '''simple docstring'''


 SCREAMING_SNAKE_CASE								=			[]
 for x in range(1		,							5	):
  for y in range(1		,							6	):
   some_list.append((x, y)	)

 for x in range(15		,							20	):
  some_list.append((x, 17)	)

 for x in range(10		,							19	):
  for y in range(1		,							15	):
   some_list.append((x, y)	)

    # L block
 for x in range(1		,							4	):
  for y in range(12		,							19	):
   some_list.append((x, y)	)
 for x in range(3		,							13	):
  for y in range(16		,							19	):
   some_list.append((x, y)	)
 return some_list


a_    :						str    		=      {0: consistent_heuristic, 1: heuristic_a, 2: heuristic_a}

a_    :						List[str]    		=      [
    (0, 1),
    (1, 1),
    (2, 1),
    (3, 1),
    (4, 1),
    (5, 1),
    (6, 1),
    (7, 1),
    (8, 1),
    (9, 1),
    (10, 1),
    (11, 1),
    (12, 1),
    (13, 1),
    (14, 1),
    (15, 1),
    (16, 1),
    (17, 1),
    (18, 1),
    (19, 1),
]
a_    :						Union[str, Any]    		=      make_common_ground()


a_    :						Tuple    		=      blocks_blk
# hyper parameters
a_    :						Any    		=      1
a_    :						List[str]    		=      1
a_    :						Union[str, Any]    		=      20
a_    :						Optional[Any]    		=      3  # one consistent and two other inconsistent

# start and end destination
a_    :						int    		=      (0, 0)
a_    :						Optional[int]    		=      (n - 1, n - 1)

a_    :						Union[str, Any]    		=      1


def        __lowerCAmelCase    (       _UpperCamelCase		:  TPos		,							_UpperCamelCase		:  TPos		,							_UpperCamelCase		:  int	)		->							List[Any]:
 '''simple docstring'''


 SCREAMING_SNAKE_CASE								=			{start: 0, goal: float('inf'	)}
 SCREAMING_SNAKE_CASE								=			{start: -1, goal: -1}
 SCREAMING_SNAKE_CASE								=			[]
 SCREAMING_SNAKE_CASE								=			set()

 for i in range(_UpperCamelCase	):
  open_list.append(PriorityQueue()	)
  open_list[i].put(_UpperCamelCase		,							key(_UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase	)	)

 SCREAMING_SNAKE_CASE								=			[]
 SCREAMING_SNAKE_CASE								=			[]
 while open_list[0].minkey() < float('inf'	):
  for i in range(1		,							_UpperCamelCase	):
   # print(open_list[0].minkey(), open_list[i].minkey())
   if open_list[i].minkey() <= Wa * open_list[0].minkey():
    global t
    t += 1
    if g_function[goal] <= open_list[i].minkey():
     if g_function[goal] < float('inf'	):
      do_something(_UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase	)
    else:
     SCREAMING_SNAKE_CASE						,	SCREAMING_SNAKE_CASE								=			open_list[i].top_show()
     visited.add(_UpperCamelCase	)
     expand_state(
         _UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase		,							)
     close_list_inad.append(_UpperCamelCase	)
   else:
    if g_function[goal] <= open_list[0].minkey():
     if g_function[goal] < float('inf'	):
      do_something(_UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase	)
    else:
     SCREAMING_SNAKE_CASE								=			open_list[0].top_show()
     visited.add(_UpperCamelCase	)
     expand_state(
         _UpperCamelCase		,							0		,							_UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase		,							)
     close_list_anchor.append(_UpperCamelCase	)
 print('No path found to goal'	)
 print()
 for i in range(n - 1		,							-1		,							-1	):
  for j in range(_UpperCamelCase	):
   if (j, i) in blocks:
    print('#'		,							end=' '	)
   elif (j, i) in back_pointer:
    if (j, i) == (n - 1, n - 1):
     print('*'		,							end=' '	)
    else:
     print('-'		,							end=' '	)
   else:
    print('*'		,							end=' '	)
   if (j, i) == (n - 1, n - 1):
    print('<-- End position'		,							end=' '	)
  print()
 print('^'	)
 print('Start position'	)
 print()
 print('# is an obstacle'	)
 print('- is the path taken by algorithm'	)


if __name__ == "__main__":
      multi_a_star(start, goal, n_heuristic)

