


from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
UpperCamelCase								=	0

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

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

UpperCamelCase								=	tuple[int, int]






class   _lowerCamelCase :




       """simple docstring"""



       def __init__(      self				,       _SCREAMING_SNAKE_CASE				,       _SCREAMING_SNAKE_CASE				,       _SCREAMING_SNAKE_CASE				,       _SCREAMING_SNAKE_CASE				,       _SCREAMING_SNAKE_CASE				,       _SCREAMING_SNAKE_CASE				,       )->None:




         '''simple docstring'''





         A_      :				str		     =					pos_x
         A_      :				Tuple		     =					pos_y
         A_      :				str		     =					(pos_y, pos_x)
         A_      :				List[str]		     =					goal_x
         A_      :				List[str]		     =					goal_y
         A_      :				Optional[int]		     =					g_cost
         A_      :				Optional[int]		     =					parent
         A_      :				Optional[Any]		     =					self.calculate_heuristic()
         A_      :				List[Any]		     =					self.g_cost + self.h_cost



       def        _snake_case       (      self		)->float:




         '''simple docstring'''





         A_      :				Any		     =					self.pos_x - self.goal_x
         A_      :				Union[str, Any]		     =					self.pos_y - self.goal_y
         if HEURISTIC == 1:
           return abs(_SCREAMING_SNAKE_CASE		) + abs(_SCREAMING_SNAKE_CASE		)
         else:
           return sqrt(dy**2 + dx**2		)







       def __lt__(      self				,       _SCREAMING_SNAKE_CASE		)->bool:




         '''simple docstring'''





         return self.f_cost < other.f_cost






class   _lowerCamelCase :




       """simple docstring"""



       def __init__(      self				,       _SCREAMING_SNAKE_CASE				,       _SCREAMING_SNAKE_CASE		)->List[Any]:




         '''simple docstring'''





         A_      :				Any		     =					Node(start[1]				,       start[0]				,       goal[1]				,       goal[0]				,       0				,       _SCREAMING_SNAKE_CASE		)
         A_      :				Tuple		     =					Node(goal[1]				,       goal[0]				,       goal[1]				,       goal[0]				,       9_9999				,       _SCREAMING_SNAKE_CASE		)

         A_      :				int		     =					[self.start]
         A_      :				List[Any]		     =					[]

         A_      :				List[str]		     =					False



       def        _snake_case       (      self		)->list[TPosition]:




         '''simple docstring'''





         while self.open_nodes:
           # Open Nodes are sorted using __lt__
           self.open_nodes.sort()
           A_      :				List[str]		     =					self.open_nodes.pop(0		)

           if current_node.pos == self.target.pos:
             return self.retrace_path(_SCREAMING_SNAKE_CASE		)

           self.closed_nodes.append(_SCREAMING_SNAKE_CASE		)
           A_      :				Optional[int]		     =					self.get_successors(_SCREAMING_SNAKE_CASE		)

           for child_node in successors:
             if child_node in self.closed_nodes:
               continue

             if child_node not in self.open_nodes:
               self.open_nodes.append(_SCREAMING_SNAKE_CASE		)
             else:
               # retrieve the best current path
               A_      :				Tuple		     =					self.open_nodes.pop(self.open_nodes.index(_SCREAMING_SNAKE_CASE		)		)

               if child_node.g_cost < better_node.g_cost:
                 self.open_nodes.append(_SCREAMING_SNAKE_CASE		)
               else:
                 self.open_nodes.append(_SCREAMING_SNAKE_CASE		)

         return [self.start.pos]



       def        _snake_case       (      self				,       _SCREAMING_SNAKE_CASE		)->list[Node]:




         '''simple docstring'''





         A_      :				Dict		     =					[]
         for action in delta:
           A_      :				Optional[Any]		     =					parent.pos_x + action[1]
           A_      :				str		     =					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				,       parent.g_cost + 1				,       _SCREAMING_SNAKE_CASE				,       )		)
         return successors







       def        _snake_case       (      self				,       _SCREAMING_SNAKE_CASE		)->list[TPosition]:




         '''simple docstring'''





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






class   _lowerCamelCase :




       """simple docstring"""



       def __init__(      self				,       _SCREAMING_SNAKE_CASE				,       _SCREAMING_SNAKE_CASE		)->None:




         '''simple docstring'''





         A_      :				Tuple		     =					AStar(_SCREAMING_SNAKE_CASE				,       _SCREAMING_SNAKE_CASE		)
         A_      :				Union[str, Any]		     =					AStar(_SCREAMING_SNAKE_CASE				,       _SCREAMING_SNAKE_CASE		)
         A_      :				str		     =					False



       def        _snake_case       (      self		)->list[TPosition]:




         '''simple docstring'''





         while self.fwd_astar.open_nodes or self.bwd_astar.open_nodes:
           self.fwd_astar.open_nodes.sort()
           self.bwd_astar.open_nodes.sort()
           A_      :				List[str]		     =					self.fwd_astar.open_nodes.pop(0		)
           A_      :				Optional[Any]		     =					self.bwd_astar.open_nodes.pop(0		)

           if current_bwd_node.pos == current_fwd_node.pos:
             return self.retrace_bidirectional_path(
                 _SCREAMING_SNAKE_CASE				,       _SCREAMING_SNAKE_CASE		)

           self.fwd_astar.closed_nodes.append(_SCREAMING_SNAKE_CASE		)
           self.bwd_astar.closed_nodes.append(_SCREAMING_SNAKE_CASE		)

           A_      :				List[Any]		     =					current_bwd_node
           A_      :				Optional[int]		     =					current_fwd_node

           A_      :				Optional[int]		     =					{
               self.fwd_astar: self.fwd_astar.get_successors(_SCREAMING_SNAKE_CASE		),
               self.bwd_astar: self.bwd_astar.get_successors(_SCREAMING_SNAKE_CASE		),
           }

           for astar in [self.fwd_astar, self.bwd_astar]:
             for child_node in successors[astar]:
               if child_node in astar.closed_nodes:
                 continue

               if child_node not in astar.open_nodes:
                 astar.open_nodes.append(_SCREAMING_SNAKE_CASE		)
               else:
                 # retrieve the best current path
                 A_      :				Optional[Any]		     =					astar.open_nodes.pop(
                     astar.open_nodes.index(_SCREAMING_SNAKE_CASE		)		)

                 if child_node.g_cost < better_node.g_cost:
                   astar.open_nodes.append(_SCREAMING_SNAKE_CASE		)
                 else:
                   astar.open_nodes.append(_SCREAMING_SNAKE_CASE		)

         return [self.fwd_astar.start.pos]







       def        _snake_case       (      self				,       _SCREAMING_SNAKE_CASE				,       _SCREAMING_SNAKE_CASE		)->list[TPosition]:




         '''simple docstring'''





         A_      :				List[str]		     =					self.fwd_astar.retrace_path(_SCREAMING_SNAKE_CASE		)
         A_      :				Optional[Any]		     =					self.bwd_astar.retrace_path(_SCREAMING_SNAKE_CASE		)
         bwd_path.pop()
         bwd_path.reverse()
         A_      :				Optional[Any]		     =					fwd_path + bwd_path
         return path


if __name__ == "__main__":
     # all coordinates are given in format [y,x]
     UpperCamelCase								=	(0, 0)
     UpperCamelCase								=	(len(grid) - 1, len(grid[0]) - 1)
     for elem in grid:
          print(elem)

     UpperCamelCase								=	time.time()
     UpperCamelCase								=	AStar(init, goal)
     UpperCamelCase								=	a_star.search()
     UpperCamelCase								=	time.time() - start_time
     print(F'''AStar execution time = {end_time:f} seconds''')

     UpperCamelCase								=	time.time()
     UpperCamelCase								=	BidirectionalAStar(init, goal)
     UpperCamelCase								=	time.time() - bd_start_time
     print(F'''BidirectionalAStar execution time = {bd_end_time:f} seconds''')











"""simple docstring"""





import re
import string

import numpy as np

import datasets


SCREAMING_SNAKE_CASE__					=   "\nReturns the rate at which the input predicted strings exactly match their references, ignoring any strings input as part of the regexes_to_ignore list.\n"

SCREAMING_SNAKE_CASE__					=   "\nArgs:\n    predictions: List of predicted texts.\n    references: List of reference texts.\n    regexes_to_ignore: List, defaults to None. Regex expressions of characters to\n        ignore when calculating the exact matches. Note: these regexes are removed\n        from the input data before the changes based on the options below (e.g. ignore_case,\n        ignore_punctuation, ignore_numbers) are applied.\n    ignore_case: Boolean, defaults to False. If true, turns everything\n        to lowercase so that capitalization differences are ignored.\n    ignore_punctuation: Boolean, defaults to False. If true, removes all punctuation before\n        comparing predictions and references.\n    ignore_numbers: Boolean, defaults to False. If true, removes all punctuation before\n        comparing predictions and references.\nReturns:\n    exact_match: Dictionary containing exact_match rate. Possible values are between 0.0 and 100.0, inclusive.\nExamples:\n    >>> exact_match = datasets.load_metric(\"exact_match\")\n    >>> refs = [\"the cat\", \"theater\", \"YELLING\", \"agent007\"]\n    >>> preds = [\"cat?\", \"theater\", \"yelling\", \"agent\"]\n    >>> results = exact_match.compute(references=refs, predictions=preds)\n    >>> print(round(results[\"exact_match\"], 1))\n    25.0\n\n    >>> exact_match = datasets.load_metric(\"exact_match\")\n    >>> refs = [\"the cat\", \"theater\", \"YELLING\", \"agent007\"]\n    >>> preds = [\"cat?\", \"theater\", \"yelling\", \"agent\"]\n    >>> results = exact_match.compute(references=refs, predictions=preds, regexes_to_ignore=[\"the \", \"yell\"], ignore_case=True, ignore_punctuation=True)\n    >>> print(round(results[\"exact_match\"], 1))\n    50.0\n\n\n    >>> exact_match = datasets.load_metric(\"exact_match\")\n    >>> refs = [\"the cat\", \"theater\", \"YELLING\", \"agent007\"]\n    >>> preds = [\"cat?\", \"theater\", \"yelling\", \"agent\"]\n    >>> results = exact_match.compute(references=refs, predictions=preds, regexes_to_ignore=[\"the \", \"yell\", \"YELL\"], ignore_case=True, ignore_punctuation=True)\n    >>> print(round(results[\"exact_match\"], 1))\n    75.0\n\n    >>> exact_match = datasets.load_metric(\"exact_match\")\n    >>> refs = [\"the cat\", \"theater\", \"YELLING\", \"agent007\"]\n    >>> preds = [\"cat?\", \"theater\", \"yelling\", \"agent\"]\n    >>> results = exact_match.compute(references=refs, predictions=preds, regexes_to_ignore=[\"the \", \"yell\", \"YELL\"], ignore_case=True, ignore_punctuation=True, ignore_numbers=True)\n    >>> print(round(results[\"exact_match\"], 1))\n    100.0\n\n    >>> exact_match = datasets.load_metric(\"exact_match\")\n    >>> refs = [\"The cat sat on the mat.\", \"Theaters are great.\", \"It's like comparing oranges and apples.\"]\n    >>> preds = [\"The cat sat on the mat?\", \"Theaters are great.\", \"It's like comparing apples and oranges.\"]\n    >>> results = exact_match.compute(references=refs, predictions=preds)\n    >>> print(round(results[\"exact_match\"], 1))\n    33.3\n\n"

SCREAMING_SNAKE_CASE__					=   "\n"

@datasets.utils.file_utils.add_start_docstrings(_DESCRIPTION     ,  _KWARGS_DESCRIPTION					)
class 		lowercase					(					datasets.Metric					):





      def     _snake_case			(       self )		->     Optional[int]:
            return datasets.MetricInfo(
                description=_DESCRIPTION      ,						citation=_CITATION      ,						inputs_description=_KWARGS_DESCRIPTION      ,						features=datasets.Features(
                    {
                        """predictions""": datasets.Value("""string"""      ,						id="""sequence""" ),
                        """references""": datasets.Value("""string"""      ,						id="""sequence""" ),
                    } )      ,						reference_urls=[]      ,						)





      def     _snake_case			(       self      ,						lowercase      ,						lowercase      ,						lowercase=None      ,						lowercase=False      ,						lowercase=False      ,						lowercase=False      ,						)		->     Optional[Any]:
            if regexes_to_ignore is not None:
                  for s in regexes_to_ignore:
                        lowerCAmelCase  						=       np.array([re.sub(lowercase      ,						""""""      ,						lowercase ) for x in predictions] )
                        lowerCAmelCase  						=       np.array([re.sub(lowercase      ,						""""""      ,						lowercase ) for x in references] )
            else:
                  lowerCAmelCase  						=       np.asarray(lowercase )
                  lowerCAmelCase  						=       np.asarray(lowercase )

            if ignore_case:
                  lowerCAmelCase  						=       np.char.lower(lowercase )
                  lowerCAmelCase  						=       np.char.lower(lowercase )

            if ignore_punctuation:
                  lowerCAmelCase  						=       string.punctuation.maketrans(""""""      ,						""""""      ,						string.punctuation )
                  lowerCAmelCase  						=       np.char.translate(lowercase      ,						table=lowercase )
                  lowerCAmelCase  						=       np.char.translate(lowercase      ,						table=lowercase )

            if ignore_numbers:
                  lowerCAmelCase  						=       string.digits.maketrans(""""""      ,						""""""      ,						string.digits )
                  lowerCAmelCase  						=       np.char.translate(lowercase      ,						table=lowercase )
                  lowerCAmelCase  						=       np.char.translate(lowercase      ,						table=lowercase )

            lowerCAmelCase  						=       predictions == references

            return {"exact_match": np.mean(lowercase ) * 100}






