


"""simple docstring"""




from __future__ import annotations

import time

lowerCAmelCase	=							list[tuple[int, int]]

lowerCAmelCase	=							[
    [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	=							[[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right


class 	_a							:

							def __init__(							self:     str   ,						UpperCamelCase_:     int   ,						UpperCamelCase_:     int   ,						UpperCamelCase_:     int   ,						UpperCamelCase_:     int   ,						UpperCamelCase_:     Node | None							)      ->       Dict:





									"""simple docstring"""







									lowercase__						=				pos_x
									lowercase__						=				pos_y
									lowercase__						=				(pos_y, pos_x)
									lowercase__						=				goal_x
									lowercase__						=				goal_y
									lowercase__						=				parent


class 	_a							:

							def __init__(							self:     str   ,						UpperCamelCase_:     tuple[int, int]   ,						UpperCamelCase_:     tuple[int, int]							)      ->       List[Any]:





									"""simple docstring"""







									lowercase__						=				Node(start[1]   ,						start[0]   ,						goal[1]   ,						goal[0]   ,						UpperCamelCase_							)
									lowercase__						=				Node(goal[1]   ,						goal[0]   ,						goal[1]   ,						goal[0]   ,						UpperCamelCase_							)

									lowercase__						=				[self.start]
									lowercase__						=				False

							def 				lowerCamelCase_			(							self:     Any							)      ->       Path | None:





									"""simple docstring"""







									while self.node_queue:
											lowercase__						=				self.node_queue.pop(0							)

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

											lowercase__						=				self.get_successors(UpperCamelCase_							)

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

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

							def 				lowerCamelCase_			(							self:     Dict   ,						UpperCamelCase_:     Node							)      ->       list[Node]:





									"""simple docstring"""







									lowercase__						=				[]
									for action in delta:
											lowercase__						=				parent.pos_x + action[1]
											lowercase__						=				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 				lowerCamelCase_			(							self:     Optional[Any]   ,						UpperCamelCase_:     Node | None							)      ->       Path:





									"""simple docstring"""







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


class 	_a							:

							def __init__(							self:     Union[str, Any]   ,						UpperCamelCase_:     Dict   ,						UpperCamelCase_:     Any							)      ->       Tuple:





									"""simple docstring"""







									lowercase__						=				BreadthFirstSearch(UpperCamelCase_   ,						UpperCamelCase_							)
									lowercase__						=				BreadthFirstSearch(UpperCamelCase_   ,						UpperCamelCase_							)
									lowercase__						=				False

							def 				lowerCamelCase_			(							self:     Any							)      ->       Path | None:





									"""simple docstring"""







									while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
											lowercase__						=				self.fwd_bfs.node_queue.pop(0							)
											lowercase__						=				self.bwd_bfs.node_queue.pop(0							)

											if current_bwd_node.pos == current_fwd_node.pos:
													lowercase__						=				True
													return self.retrace_bidirectional_path(
													    UpperCamelCase_   ,						UpperCamelCase_							)

											lowercase__						=				current_bwd_node
											lowercase__						=				current_fwd_node

											lowercase__						=				{
											    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 				lowerCamelCase_			(							self:     int   ,						UpperCamelCase_:     Node   ,						UpperCamelCase_:     Node							)      ->       Path:





									"""simple docstring"""







									lowercase__						=				self.fwd_bfs.retrace_path(UpperCamelCase_							)
									lowercase__						=				self.bwd_bfs.retrace_path(UpperCamelCase_							)
									bwd_path.pop()
									bwd_path.reverse()
									lowercase__						=				fwd_path + bwd_path
									return path


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

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

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

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

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

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






import math_equivalence  # From: git+https://github.com/hendrycks/math.git

import datasets


lowerCAmelCase	=							'\\n@article{hendrycksmath2021,\n  title={Measuring Mathematical Problem Solving With the MATH Dataset},\n  author={Dan Hendrycks\n    and Collin Burns\n    and Saurav Kadavath\n    and Akul Arora\n    and Steven Basart\n    and Eric Tang\n    and Dawn Song\n    and Jacob Steinhardt},\n  journal={arXiv preprint arXiv:2103.03874},\n  year={2021}\n}\n'


lowerCAmelCase	=							'\\nThis metric is used to assess performance on the Mathematics Aptitude Test of Heuristics (MATH) dataset.\nIt first canonicalizes the inputs (e.g., converting "1/2" to "\\frac{1}{2}") and then computes accuracy.\n'


lowerCAmelCase	=							R'\nCalculates accuracy after canonicalizing inputs.\n\nArgs:\n    predictions: list of predictions to score. Each prediction\n        is a string that contains natural language and LaTex.\n    references: list of reference for each prediction. Each\n        reference is a string that contains natural language\n        and LaTex.\nReturns:\n    accuracy: accuracy after canonicalizing inputs\n        (e.g., converting "1/2" to "\\frac{1}{2}")\n\nExamples:\n    >>> metric = datasets.load_metric("competition_math")\n    >>> results = metric.compute(references=["\\frac{1}{2}"], predictions=["1/2"])\n    >>> print(results)\n    {\'accuracy\': 1.0}\n'


@datasets.utils.file_utils.add_end_docstrings(_DESCRIPTION					,     _KWARGS_DESCRIPTION      )
class 	_a							(      datasets.Metric      ):

							def 				lowerCamelCase_			(							self:     List[str]							)      ->       Tuple:





									"""simple docstring"""







									return datasets.MetricInfo(
									    description=_DESCRIPTION   ,						citation=_CITATION   ,						inputs_description=_KWARGS_DESCRIPTION   ,						features=datasets.Features(
									        {
									            '''predictions''': datasets.Value('''string'''							),
									            '''references''': datasets.Value('''string'''							),
									        }							)   ,						homepage='''https://github.com/hendrycks/math'''   ,						codebase_urls=['''https://github.com/hendrycks/math''']   ,						)


							def 				lowerCamelCase_			(							self:     Union[str, Any]   ,						UpperCamelCase_:     Any   ,						UpperCamelCase_:     int							)      ->       List[str]:





									"""simple docstring"""







									lowercase__						=				0.0
									for i, j in zip(UpperCamelCase_   ,						UpperCamelCase_							):
											n_correct += 1.0 if math_equivalence.is_equiv(UpperCamelCase_   ,						UpperCamelCase_							) else 0.0
									lowercase__						=				n_correct / len(UpperCamelCase_							)
									return {
									    "accuracy": accuracy,
									}


