


from __future__ import annotations

import time

lowerCAmelCase__    :Dict       =				list[tuple[int, int]]

lowerCAmelCase__    :Optional[Any]       =				[
    [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__    :Any       =				[[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

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




									"""simple docstring"""





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



class 						__a :
		def __init__(     self     ,       _SCREAMING_SNAKE_CASE     ,       _SCREAMING_SNAKE_CASE		)					->			int:




									"""simple docstring"""





									_UpperCAmelCase											=     Node(start[1]     ,       start[0]     ,       goal[1]     ,       goal[0]     ,       _SCREAMING_SNAKE_CASE		)
									_UpperCAmelCase											=     Node(goal[1]     ,       goal[0]     ,       goal[1]     ,       goal[0]     ,       _SCREAMING_SNAKE_CASE		)

									_UpperCAmelCase											=     [self.start]
									_UpperCAmelCase											=     False
		def       UpperCAmelCase__							(     self		)					->			Path | None:




									"""simple docstring"""





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

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

																_UpperCAmelCase											=     self.get_successors(_SCREAMING_SNAKE_CASE		)

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

									if not self.reached:
																return [self.start.pos]
									return None
		def       UpperCAmelCase__							(     self     ,       _SCREAMING_SNAKE_CASE		)					->			list[Node]:




									"""simple docstring"""





									_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(_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     ,       _SCREAMING_SNAKE_CASE		)		)
									return successors






		def       UpperCAmelCase__							(     self     ,       _SCREAMING_SNAKE_CASE		)					->			Path:




									"""simple docstring"""





									_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 						__a :
		def __init__(     self     ,       _SCREAMING_SNAKE_CASE     ,       _SCREAMING_SNAKE_CASE		)					->			Dict:




									"""simple docstring"""





									_UpperCAmelCase											=     BreadthFirstSearch(_SCREAMING_SNAKE_CASE     ,       _SCREAMING_SNAKE_CASE		)
									_UpperCAmelCase											=     BreadthFirstSearch(_SCREAMING_SNAKE_CASE     ,       _SCREAMING_SNAKE_CASE		)
									_UpperCAmelCase											=     False
		def       UpperCAmelCase__							(     self		)					->			Path | None:




									"""simple docstring"""





									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(
																							    _SCREAMING_SNAKE_CASE     ,       _SCREAMING_SNAKE_CASE		)

																_UpperCAmelCase											=     current_bwd_node
																_UpperCAmelCase											=     current_fwd_node

																_UpperCAmelCase											=     {
																    self.fwd_bfs: self.fwd_bfs.get_successors(_SCREAMING_SNAKE_CASE		),
																    self.bwd_bfs: self.bwd_bfs.get_successors(_SCREAMING_SNAKE_CASE		),
																}

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

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






		def       UpperCAmelCase__							(     self     ,       _SCREAMING_SNAKE_CASE     ,       _SCREAMING_SNAKE_CASE		)					->			Path:




									"""simple docstring"""





									_UpperCAmelCase											=     self.fwd_bfs.retrace_path(_SCREAMING_SNAKE_CASE		)
									_UpperCAmelCase											=     self.bwd_bfs.retrace_path(_SCREAMING_SNAKE_CASE		)
									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__    :int       =				(0, 0)
		lowerCAmelCase__    :Union[str, Any]       =				(len(grid) - 1, len(grid[0]) - 1)
		for elem in grid:
				print(elem)

		lowerCAmelCase__    :Tuple       =				time.time()
		lowerCAmelCase__    :List[str]       =				BreadthFirstSearch(init, goal)
		lowerCAmelCase__    :int       =				bfs.search()
		lowerCAmelCase__    :Union[str, Any]       =				time.time() - start_bfs_time

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

		lowerCAmelCase__    :List[str]       =				time.time()
		lowerCAmelCase__    :Any       =				BidirectionalBreadthFirstSearch(init, goal)
		lowerCAmelCase__    :Dict       =				bd_bfs.search()
		lowerCAmelCase__    :Optional[Any]       =				time.time() - start_bd_bfs_time

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




import os
import tempfile
import unittest
from pathlib import Path

from transformers import AutoConfig, is_tf_available
from transformers.testing_utils import require_tf


if is_tf_available():
		import tensorflow as tf

		from transformers import TensorFlowBenchmark, TensorFlowBenchmarkArguments

@require_tf
class 						__a (							unittest.TestCase     ):
		def       UpperCAmelCase__							(     self     ,       _SCREAMING_SNAKE_CASE		)					->			List[str]:




									"""simple docstring"""





									for model_result in results.values():
																for batch_size, sequence_length in zip(model_result['bs']     ,       model_result['ss']		):
																							_UpperCAmelCase											=     model_result['result'][batch_size][sequence_length]
																							self.assertIsNotNone(_SCREAMING_SNAKE_CASE		)
		def       UpperCAmelCase__							(     self		)					->			Optional[int]:




									"""simple docstring"""





									_UpperCAmelCase											=     'sshleifer/tiny-gpt2'
									_UpperCAmelCase											=     TensorFlowBenchmarkArguments(
									    models=[MODEL_ID]     ,       training=_SCREAMING_SNAKE_CASE     ,       inference=_SCREAMING_SNAKE_CASE     ,       sequence_lengths=[8]     ,       batch_sizes=[1]     ,       eager_mode=_SCREAMING_SNAKE_CASE     ,       multi_process=_SCREAMING_SNAKE_CASE     ,       )
									_UpperCAmelCase											=     TensorFlowBenchmark(_SCREAMING_SNAKE_CASE		)
									_UpperCAmelCase											=     benchmark.run()
									self.check_results_dict_not_empty(results.time_inference_result		)
									self.check_results_dict_not_empty(results.memory_inference_result		)
		def       UpperCAmelCase__							(     self		)					->			int:




									"""simple docstring"""





									_UpperCAmelCase											=     'sgugger/tiny-distilbert-classification'
									_UpperCAmelCase											=     TensorFlowBenchmarkArguments(
									    models=[MODEL_ID]     ,       training=_SCREAMING_SNAKE_CASE     ,       inference=_SCREAMING_SNAKE_CASE     ,       sequence_lengths=[8]     ,       batch_sizes=[1]     ,       multi_process=_SCREAMING_SNAKE_CASE     ,       only_pretrain_model=_SCREAMING_SNAKE_CASE     ,       )
									_UpperCAmelCase											=     TensorFlowBenchmark(_SCREAMING_SNAKE_CASE		)
									_UpperCAmelCase											=     benchmark.run()
									self.check_results_dict_not_empty(results.time_inference_result		)
									self.check_results_dict_not_empty(results.memory_inference_result		)
		def       UpperCAmelCase__							(     self		)					->			List[Any]:




									"""simple docstring"""





									_UpperCAmelCase											=     'sshleifer/tiny-gpt2'
									_UpperCAmelCase											=     TensorFlowBenchmarkArguments(
									    models=[MODEL_ID]     ,       training=_SCREAMING_SNAKE_CASE     ,       inference=_SCREAMING_SNAKE_CASE     ,       sequence_lengths=[8]     ,       batch_sizes=[1]     ,       multi_process=_SCREAMING_SNAKE_CASE     ,       )
									_UpperCAmelCase											=     TensorFlowBenchmark(_SCREAMING_SNAKE_CASE		)
									_UpperCAmelCase											=     benchmark.run()
									self.check_results_dict_not_empty(results.time_inference_result		)
									self.check_results_dict_not_empty(results.memory_inference_result		)
		def       UpperCAmelCase__							(     self		)					->			List[Any]:




									"""simple docstring"""





									_UpperCAmelCase											=     'sshleifer/tiny-gpt2'
									_UpperCAmelCase											=     AutoConfig.from_pretrained(_SCREAMING_SNAKE_CASE		)
									_UpperCAmelCase											=     TensorFlowBenchmarkArguments(
									    models=[MODEL_ID]     ,       training=_SCREAMING_SNAKE_CASE     ,       inference=_SCREAMING_SNAKE_CASE     ,       sequence_lengths=[8]     ,       batch_sizes=[1]     ,       eager_mode=_SCREAMING_SNAKE_CASE     ,       multi_process=_SCREAMING_SNAKE_CASE     ,       )
									_UpperCAmelCase											=     TensorFlowBenchmark(_SCREAMING_SNAKE_CASE     ,       [config]		)
									_UpperCAmelCase											=     benchmark.run()
									self.check_results_dict_not_empty(results.time_inference_result		)
									self.check_results_dict_not_empty(results.memory_inference_result		)
		def       UpperCAmelCase__							(     self		)					->			List[Any]:




									"""simple docstring"""





									_UpperCAmelCase											=     'sshleifer/tiny-gpt2'
									_UpperCAmelCase											=     AutoConfig.from_pretrained(_SCREAMING_SNAKE_CASE		)
									_UpperCAmelCase											=     TensorFlowBenchmarkArguments(
									    models=[MODEL_ID]     ,       training=_SCREAMING_SNAKE_CASE     ,       inference=_SCREAMING_SNAKE_CASE     ,       sequence_lengths=[8]     ,       batch_sizes=[1]     ,       multi_process=_SCREAMING_SNAKE_CASE     ,       )
									_UpperCAmelCase											=     TensorFlowBenchmark(_SCREAMING_SNAKE_CASE     ,       [config]		)
									_UpperCAmelCase											=     benchmark.run()
									self.check_results_dict_not_empty(results.time_inference_result		)
									self.check_results_dict_not_empty(results.memory_inference_result		)
		def       UpperCAmelCase__							(     self		)					->			List[Any]:




									"""simple docstring"""





									_UpperCAmelCase											=     'sshleifer/tiny-gpt2'
									_UpperCAmelCase											=     TensorFlowBenchmarkArguments(
									    models=[MODEL_ID]     ,       training=_SCREAMING_SNAKE_CASE     ,       inference=_SCREAMING_SNAKE_CASE     ,       sequence_lengths=[8]     ,       batch_sizes=[1]     ,       multi_process=_SCREAMING_SNAKE_CASE     ,       )
									_UpperCAmelCase											=     TensorFlowBenchmark(_SCREAMING_SNAKE_CASE		)
									_UpperCAmelCase											=     benchmark.run()
									self.check_results_dict_not_empty(results.time_train_result		)
									self.check_results_dict_not_empty(results.memory_train_result		)
		def       UpperCAmelCase__							(     self		)					->			List[Any]:




									"""simple docstring"""





									_UpperCAmelCase											=     'sshleifer/tiny-gpt2'
									_UpperCAmelCase											=     AutoConfig.from_pretrained(_SCREAMING_SNAKE_CASE		)
									_UpperCAmelCase											=     TensorFlowBenchmarkArguments(
									    models=[MODEL_ID]     ,       training=_SCREAMING_SNAKE_CASE     ,       inference=_SCREAMING_SNAKE_CASE     ,       sequence_lengths=[8]     ,       batch_sizes=[1]     ,       multi_process=_SCREAMING_SNAKE_CASE     ,       )
									_UpperCAmelCase											=     TensorFlowBenchmark(_SCREAMING_SNAKE_CASE     ,       [config]		)
									_UpperCAmelCase											=     benchmark.run()
									self.check_results_dict_not_empty(results.time_train_result		)
									self.check_results_dict_not_empty(results.memory_train_result		)
		def       UpperCAmelCase__							(     self		)					->			Any:




									"""simple docstring"""





									_UpperCAmelCase											=     'patrickvonplaten/t5-tiny-random'
									_UpperCAmelCase											=     AutoConfig.from_pretrained(_SCREAMING_SNAKE_CASE		)
									_UpperCAmelCase											=     TensorFlowBenchmarkArguments(
									    models=[MODEL_ID]     ,       training=_SCREAMING_SNAKE_CASE     ,       inference=_SCREAMING_SNAKE_CASE     ,       sequence_lengths=[8]     ,       batch_sizes=[1]     ,       multi_process=_SCREAMING_SNAKE_CASE     ,       )
									_UpperCAmelCase											=     TensorFlowBenchmark(_SCREAMING_SNAKE_CASE     ,       configs=[config]		)
									_UpperCAmelCase											=     benchmark.run()
									self.check_results_dict_not_empty(results.time_inference_result		)
									self.check_results_dict_not_empty(results.memory_inference_result		)
		@unittest.skipIf(is_tf_available() and len(tf.config.list_physical_devices('GPU'		)		) == 0     ,       'Cannot do xla on CPU.'		)
		def       UpperCAmelCase__							(     self		)					->			int:




									"""simple docstring"""





									_UpperCAmelCase											=     'sshleifer/tiny-gpt2'
									_UpperCAmelCase											=     TensorFlowBenchmarkArguments(
									    models=[MODEL_ID]     ,       training=_SCREAMING_SNAKE_CASE     ,       inference=_SCREAMING_SNAKE_CASE     ,       sequence_lengths=[8]     ,       batch_sizes=[1]     ,       use_xla=_SCREAMING_SNAKE_CASE     ,       multi_process=_SCREAMING_SNAKE_CASE     ,       )
									_UpperCAmelCase											=     TensorFlowBenchmark(_SCREAMING_SNAKE_CASE		)
									_UpperCAmelCase											=     benchmark.run()
									self.check_results_dict_not_empty(results.time_inference_result		)
									self.check_results_dict_not_empty(results.memory_inference_result		)
		def       UpperCAmelCase__							(     self		)					->			str:




									"""simple docstring"""





									_UpperCAmelCase											=     'sshleifer/tiny-gpt2'
									with tempfile.TemporaryDirectory() as tmp_dir:
																_UpperCAmelCase											=     TensorFlowBenchmarkArguments(
																    models=[MODEL_ID]     ,       inference=_SCREAMING_SNAKE_CASE     ,       save_to_csv=_SCREAMING_SNAKE_CASE     ,       sequence_lengths=[8]     ,       batch_sizes=[1]     ,       inference_time_csv_file=os.path.join(_SCREAMING_SNAKE_CASE     ,       'inf_time.csv'		)     ,       inference_memory_csv_file=os.path.join(_SCREAMING_SNAKE_CASE     ,       'inf_mem.csv'		)     ,       env_info_csv_file=os.path.join(_SCREAMING_SNAKE_CASE     ,       'env.csv'		)     ,       multi_process=_SCREAMING_SNAKE_CASE     ,       )
																_UpperCAmelCase											=     TensorFlowBenchmark(_SCREAMING_SNAKE_CASE		)
																benchmark.run()
																self.assertTrue(Path(os.path.join(_SCREAMING_SNAKE_CASE     ,       'inf_time.csv'		)		).exists()		)
																self.assertTrue(Path(os.path.join(_SCREAMING_SNAKE_CASE     ,       'inf_mem.csv'		)		).exists()		)
																self.assertTrue(Path(os.path.join(_SCREAMING_SNAKE_CASE     ,       'env.csv'		)		).exists()		)






		def       UpperCAmelCase__							(     self		)					->			Tuple:




									"""simple docstring"""





									_UpperCAmelCase											=     'sshleifer/tiny-gpt2'

									def _check_summary_is_not_empty(_SCREAMING_SNAKE_CASE		):
																self.assertTrue(hasattr(_SCREAMING_SNAKE_CASE     ,       'sequential'		)		)
																self.assertTrue(hasattr(_SCREAMING_SNAKE_CASE     ,       'cumulative'		)		)
																self.assertTrue(hasattr(_SCREAMING_SNAKE_CASE     ,       'current'		)		)
																self.assertTrue(hasattr(_SCREAMING_SNAKE_CASE     ,       'total'		)		)

									with tempfile.TemporaryDirectory() as tmp_dir:
																_UpperCAmelCase											=     TensorFlowBenchmarkArguments(
																    models=[MODEL_ID]     ,       inference=_SCREAMING_SNAKE_CASE     ,       sequence_lengths=[8]     ,       batch_sizes=[1]     ,       log_filename=os.path.join(_SCREAMING_SNAKE_CASE     ,       'log.txt'		)     ,       log_print=_SCREAMING_SNAKE_CASE     ,       trace_memory_line_by_line=_SCREAMING_SNAKE_CASE     ,       eager_mode=_SCREAMING_SNAKE_CASE     ,       multi_process=_SCREAMING_SNAKE_CASE     ,       )
																_UpperCAmelCase											=     TensorFlowBenchmark(_SCREAMING_SNAKE_CASE		)
																_UpperCAmelCase											=     benchmark.run()
																_check_summary_is_not_empty(result.inference_summary		)
																self.assertTrue(Path(os.path.join(_SCREAMING_SNAKE_CASE     ,       'log.txt'		)		).exists()		)
