

from __future__ import annotations

import time

_a:    List[Any] 							=			list[tuple[int, int]]

_a:    int 							=			[
    [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],
]

_a:    Dict 							=			[[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

class 						__UpperCamelCase    :




	def __init__(		self	:						Any		,	lowerCAmelCase	:						List[str]		,	lowerCAmelCase	:						List[Any]		,	lowerCAmelCase	:						int		,	lowerCAmelCase	:						Dict		,	lowerCAmelCase	:						Any							):


		'''simple docstring'''







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


class 						__UpperCamelCase    :




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


		'''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       __A					(		self	:						Optional[Any]							):


		'''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       __A					(		self	:						List[str]		,	lowerCAmelCase	:						str							):


		'''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       __A					(		self	:						List[Any]		,	lowerCAmelCase	:						List[str]							):


		'''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 						__UpperCamelCase    :




	def __init__(		self	:						str		,	lowerCAmelCase	:						Optional[int]		,	lowerCAmelCase	:						int							):


		'''simple docstring'''







		UpperCAmelCase_       				=			BreadthFirstSearch(_SCREAMING_SNAKE_CASE		,	_SCREAMING_SNAKE_CASE							)
		UpperCAmelCase_       				=			BreadthFirstSearch(_SCREAMING_SNAKE_CASE		,	_SCREAMING_SNAKE_CASE							)
		UpperCAmelCase_       				=			False




	def       __A					(		self	:						Optional[int]							):


		'''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       __A					(		self	:						List[str]		,	lowerCAmelCase	:						List[str]		,	lowerCAmelCase	:						Tuple							):


		'''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()
				_a:    Tuple 							=			(0, 0)
				_a:    List[str] 							=			(len(grid) - 1, len(grid[0]) - 1)
				for elem in grid:
								print(elem)

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

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

				_a:    Union[str, Any] 							=			time.time()
				_a:    Tuple 							=			BidirectionalBreadthFirstSearch(init, goal)
				_a:    List[Any] 							=			bd_bfs.search()
				_a:    Union[str, Any] 							=			time.time() - start_bd_bfs_time

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







def       __lowerCAmelCase      (						A    ):
	UpperCAmelCase_       				=			generate_pascal_triangle(A    )
	for row_idx in range(A    ):
		# Print left spaces
		for _ in range(num_rows - row_idx - 1    ):
			print(end=" "    )
		# Print row values
		for col_idx in range(row_idx + 1    ):
			if col_idx != row_idx:
				print(triangle[row_idx][col_idx]       ,     end=" "    )
			else:
				print(triangle[row_idx][col_idx]       ,     end=""    )
		print()



def       __lowerCAmelCase      (						A    ):

	if not isinstance(A       ,     A    ):
		raise TypeError("The input value of 'num_rows' should be 'int'"    )

	if num_rows == 0:
		return []
	elif num_rows < 0:
		raise ValueError(
		    "The input value of 'num_rows' should be greater than or equal to 0"    )

	UpperCAmelCase_       				=			[]
	for current_row_idx in range(A    ):
		UpperCAmelCase_       				=			populate_current_row(A       ,     A    )
		triangle.append(A    )
	return triangle



def       __lowerCAmelCase      (						A       ,     A    ):
	UpperCAmelCase_       				=			[-1] * (current_row_idx + 1)
	# first and last elements of current row are equal to 1
	UpperCAmelCase_				,   UpperCAmelCase_       				=			1, 1
	for current_col_idx in range(1       ,     A    ):
		calculate_current_element(
		    A       ,     A       ,     A       ,     A    )
	return current_row



def       __lowerCAmelCase      (						A       ,     A       ,     A       ,     A       ,     ):
	UpperCAmelCase_       				=			triangle[current_row_idx - 1][current_col_idx - 1]
	UpperCAmelCase_       				=			triangle[current_row_idx - 1][current_col_idx]
	UpperCAmelCase_       				=			above_to_left_elt + above_to_right_elt



def       __lowerCAmelCase      (						A    ):

	if not isinstance(A       ,     A    ):
		raise TypeError("The input value of 'num_rows' should be 'int'"    )

	if num_rows == 0:
		return []
	elif num_rows < 0:
		raise ValueError(
		    "The input value of 'num_rows' should be greater than or equal to 0"    )

	UpperCAmelCase_       				=			[[1]]

	for row_index in range(1       ,     A    ):
		UpperCAmelCase_       				=			[0] + result[-1] + [0]
		UpperCAmelCase_       				=			row_index + 1
		# Calculate the number of distinct elements in a row
		UpperCAmelCase_       				=			sum(divmod(A       ,     2    )    )
		UpperCAmelCase_       				=			[
		    temp_row[i - 1] + temp_row[i] for i in range(1       ,     distinct_elements + 1    )
		]
		UpperCAmelCase_       				=			row_first_half[: (row_index + 1) // 2]
		row_second_half.reverse()
		UpperCAmelCase_       				=			row_first_half + row_second_half
		result.append(A    )

	return result



def       __lowerCAmelCase      (						):
	from collections.abc import Callable
	from timeit import timeit

	def benchmark_a_function(A       ,     A    ) -> None:
		UpperCAmelCase_       				=			F"{func.__name__}({value})"
		UpperCAmelCase_       				=			timeit(F"__main__.{call}"       ,     setup="import __main__"    )
		# print(f"{call:38} = {func(value)} -- {timing:.4f} seconds")
		print(F"{call:38} -- {timing:.4f} seconds"    )

	for value in range(15    ):  # (1, 7, 14):
		for func in (generate_pascal_triangle, generate_pascal_triangle_optimized):
			benchmark_a_function(A       ,     A    )
		print()


if __name__ == "__main__":
				import doctest

				doctest.testmod()
				benchmark()