


"""simple docstring"""
from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
__SCREAMING_SNAKE_CASE							:			Any						=			0

__SCREAMING_SNAKE_CASE							:			Dict						=			[
    [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],
]

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

__SCREAMING_SNAKE_CASE							:			Union[str, Any]						=			tuple[int, int]





class    __A   :





							'''simple docstring'''

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



														"""simple docstring"""



														snake_case_							=						pos_x
														snake_case_							=						pos_y
														snake_case_							=						(pos_y, pos_x)
														snake_case_							=						goal_x
														snake_case_							=						goal_y
														snake_case_							=						g_cost
														snake_case_							=						parent
														snake_case_							=						self.calculate_heuristic()
														snake_case_							=						self.g_cost + self.h_cost



							def 						lowerCAmelCase				( self							:					int				)    ->Union[str, Any]:



														"""simple docstring"""



														snake_case_							=						self.pos_x - self.goal_x
														snake_case_							=						self.pos_y - self.goal_y
														if HEURISTIC == 1:
																					return abs(lowerCAmelCase_				) + abs(lowerCAmelCase_				)
														else:
																					return sqrt(dy**2 + dx**2				)



							def __lt__( self							:					str						,				UpperCAmelCase_							:					List[str]				)    ->Union[str, Any]:



														"""simple docstring"""



														return self.f_cost < other.f_cost





class    __A   :





							'''simple docstring'''

							def __init__( self							:					Tuple						,				UpperCAmelCase_							:					int						,				UpperCAmelCase_							:					str				)    ->Dict:



														"""simple docstring"""



														snake_case_							=						Node(start[1]						,				start[0]						,				goal[1]						,				goal[0]						,				0						,				lowerCAmelCase_				)
														snake_case_							=						Node(goal[1]						,				goal[0]						,				goal[1]						,				goal[0]						,				99_999						,				lowerCAmelCase_				)

														snake_case_							=						[self.start]
														snake_case_							=						[]

														snake_case_							=						False



							def 						lowerCAmelCase				( self							:					Union[str, Any]				)    ->List[Any]:



														"""simple docstring"""



														while self.open_nodes:
																					# Open Nodes are sorted using __lt__
																					self.open_nodes.sort()
																					snake_case_							=						self.open_nodes.pop(0				)

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

																					self.closed_nodes.append(lowerCAmelCase_				)
																					snake_case_							=						self.get_successors(lowerCAmelCase_				)

																					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(lowerCAmelCase_				)
																												else:
																																			# retrieve the best current path
																																			snake_case_							=						self.open_nodes.pop(self.open_nodes.index(lowerCAmelCase_				)				)

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

														return [self.start.pos]



							def 						lowerCAmelCase				( self							:					Dict						,				UpperCAmelCase_							:					int				)    ->List[Any]:



														"""simple docstring"""



														snake_case_							=						[]
														for action in delta:
																					snake_case_							=						parent.pos_x + action[1]
																					snake_case_							=						parent.pos_y + action[0]
																					if not (0 <= pos_x <= len(grid[0]				) - 1 and 0 <= pos_y <= len(lowerCAmelCase_				) - 1):
																												continue

																					if grid[pos_y][pos_x] != 0:
																												continue

																					successors.append(
																					    Node(
																					        lowerCAmelCase_						,				lowerCAmelCase_						,				self.target.pos_y						,				self.target.pos_x						,				parent.g_cost + 1						,				lowerCAmelCase_						,				)				)
														return successors



							def 						lowerCAmelCase				( self							:					List[str]						,				UpperCAmelCase_							:					Optional[Any]				)    ->Union[str, Any]:



														"""simple docstring"""



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





class    __A   :





							'''simple docstring'''

							def __init__( self							:					List[Any]						,				UpperCAmelCase_							:					Union[str, Any]						,				UpperCAmelCase_							:					Union[str, Any]				)    ->Optional[Any]:



														"""simple docstring"""



														snake_case_							=						AStar(lowerCAmelCase_						,				lowerCAmelCase_				)
														snake_case_							=						AStar(lowerCAmelCase_						,				lowerCAmelCase_				)
														snake_case_							=						False



							def 						lowerCAmelCase				( self							:					List[str]				)    ->Any:



														"""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()
																					snake_case_							=						self.fwd_astar.open_nodes.pop(0				)
																					snake_case_							=						self.bwd_astar.open_nodes.pop(0				)

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

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

																					snake_case_							=						current_bwd_node
																					snake_case_							=						current_fwd_node

																					snake_case_							=						{
																					    self.fwd_astar: self.fwd_astar.get_successors(lowerCAmelCase_				),
																					    self.bwd_astar: self.bwd_astar.get_successors(lowerCAmelCase_				),
																					}

																					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(lowerCAmelCase_				)
																																			else:
																																										# retrieve the best current path
																																										snake_case_							=						astar.open_nodes.pop(
																																										    astar.open_nodes.index(lowerCAmelCase_				)				)

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

														return [self.fwd_astar.start.pos]



							def 						lowerCAmelCase				( self							:					Union[str, Any]						,				UpperCAmelCase_							:					Union[str, Any]						,				UpperCAmelCase_							:					int				)    ->List[str]:



														"""simple docstring"""



														snake_case_							=						self.fwd_astar.retrace_path(lowerCAmelCase_				)
														snake_case_							=						self.bwd_astar.retrace_path(lowerCAmelCase_				)
														bwd_path.pop()
														bwd_path.reverse()
														snake_case_							=						fwd_path + bwd_path
														return path


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

				__SCREAMING_SNAKE_CASE							:			Dict						=			time.time()
				__SCREAMING_SNAKE_CASE							:			Tuple						=			AStar(init, goal)
				__SCREAMING_SNAKE_CASE							:			Optional[int]						=			a_star.search()
				__SCREAMING_SNAKE_CASE							:			str						=			time.time() - start_time
				print(f"""AStar execution time = {end_time:f} seconds""")

				__SCREAMING_SNAKE_CASE							:			List[str]						=			time.time()
				__SCREAMING_SNAKE_CASE							:			int						=			BidirectionalAStar(init, goal)
				__SCREAMING_SNAKE_CASE							:			str						=			time.time() - bd_start_time
				print(f"""BidirectionalAStar execution time = {bd_end_time:f} seconds""")





'''simple docstring'''







def 				SCREAMING_SNAKE_CASE__	(   __A = 1_000_000	)       ->	int:
	_snake_case   						=		limit + 1
	_snake_case   						=		[0] * limit
	for first_term in range(1			,				__A	):
		for n in range(__A			,				__A			,				__A	):
			_snake_case   						=		first_term + n / first_term
			if common_difference % 4:  # d must be divisble by 4
				continue
			else:
				common_difference /= 4
				if (
				    first_term > common_difference
				    and first_term < 4 * common_difference
				):  # since x,y,z are positive integers
					frequency[n] += 1  # so z>0 and a>d ,also 4d<a

	_snake_case   						=		sum(1 for x in frequency[1:limit] if x == 10	)

	return count


if __name__ == "__main__":
					print(F'''{solution() = }''')

