

import re





def       __lowerCamelCase			(				UpperCamelCase__   ):







							'''simple docstring'''






							snake_case_           =					re.compile(
							    r'^(?:0|94|\+94|0{2}94)' r'7(0|1|2|4|5|6|7|8)' r'(-| |)' r'\d{7}$'   )

							return bool(re.search(UpperCamelCase__     ,							UpperCamelCase__   )   )


if __name__ == "__main__":
					_UpperCAmelCase	:     Optional[Any]		       = """0094702343221"""

					print(is_sri_lankan_phone_number(phone))







import heapq
import sys

import numpy as np

_UpperCAmelCase	:     str		       = tuple[int, int]







class 				lowercase       :




				def __init__(      self ):
											snake_case_           =					[]
											snake_case_           =					set()




				def 					a							(      self ):
											if not self.empty():
																		return self.elements[0][0]
											else:
																		return float('inf' )




				def 					a							(      self ):
											return len(self.elements ) == 0




				def 					a							(      self   ,     snake_case   ,     snake_case ):
											if item not in self.set:
																		heapq.heappush(self.elements   ,     (priority, item) )
																		self.set.add(snake_case )
											else:
																		# update
																		# print("update", item)
																		snake_case_           =					[]
																		((snake_case_)       ,					(snake_case_))           =					heapq.heappop(self.elements )
																		while x != item:
																									temp.append((pri, x) )
																									((snake_case_)       ,					(snake_case_))           =					heapq.heappop(self.elements )
																		temp.append((priority, item) )
																		for pro, xxx in temp:
																									heapq.heappush(self.elements   ,     (pro, xxx) )




				def 					a							(      self   ,     snake_case ):
											if item in self.set:
																		self.set.remove(snake_case )
																		snake_case_           =					[]
																		((snake_case_)       ,					(snake_case_))           =					heapq.heappop(self.elements )
																		while x != item:
																									temp.append((pro, x) )
																									((snake_case_)       ,					(snake_case_))           =					heapq.heappop(self.elements )
																		for prito, yyy in temp:
																									heapq.heappush(self.elements   ,     (prito, yyy) )




				def 					a							(      self ):
											return self.elements[0][1]




				def 					a							(      self ):
											((snake_case_)       ,					(snake_case_))           =					heapq.heappop(self.elements )
											self.set.remove(snake_case )
											return (priority, item)





def       __lowerCamelCase			(				UpperCamelCase__     ,							UpperCamelCase__   ):







							'''simple docstring'''






							snake_case_           =					np.array(UpperCamelCase__   )
							snake_case_           =					np.array(UpperCamelCase__   )
							return np.linalg.norm(a - b   )





def       __lowerCamelCase			(				UpperCamelCase__     ,							UpperCamelCase__   ):







							'''simple docstring'''






							return consistent_heuristic(UpperCamelCase__     ,							UpperCamelCase__   ) // t





def       __lowerCamelCase			(				UpperCamelCase__     ,							UpperCamelCase__   ):







							'''simple docstring'''






							return abs(p[0] - goal[0]   ) + abs(p[1] - goal[1]   )





def       __lowerCamelCase			(				UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__   ):







							'''simple docstring'''






							snake_case_           =					g_function[start] + Wa * heuristics[i](UpperCamelCase__     ,							UpperCamelCase__   )
							return ans





def       __lowerCamelCase			(				UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__   ):







							'''simple docstring'''






							snake_case_           =					np.chararray((n, n)   )
							for i in range(UpperCamelCase__   ):
														for j in range(UpperCamelCase__   ):
																					snake_case_           =					'*'

							for i in range(UpperCamelCase__   ):
														for j in range(UpperCamelCase__   ):
																					if (j, (n - 1) - i) in blocks:
																												snake_case_           =					'#'

							snake_case_           =					'-'
							snake_case_           =					back_pointer[goal]
							while x != start:
														((snake_case_)       ,					(snake_case_))           =					x
														# print(x)
														snake_case_           =					'-'
														snake_case_           =					back_pointer[x]
							snake_case_           =					'-'

							for i in range(UpperCamelCase__   ):
														for j in range(UpperCamelCase__   ):
																					if (i, j) == (0, n - 1):
																												print(grid[i][j]     ,							end=' '   )
																												print('<-- End position'     ,							end=' '   )
																					else:
																												print(grid[i][j]     ,							end=' '   )
														print()
							print('^'   )
							print('Start position'   )
							print()
							print('# is an obstacle'   )
							print('- is the path taken by algorithm'   )
							print('PATH TAKEN BY THE ALGORITHM IS:-'   )
							snake_case_           =					back_pointer[goal]
							while x != start:
														print(UpperCamelCase__     ,							end=' '   )
														snake_case_           =					back_pointer[x]
							print(UpperCamelCase__   )
							sys.exit()





def       __lowerCamelCase			(				UpperCamelCase__   ):







							'''simple docstring'''






							if p[0] < 0 or p[0] > n - 1:
														return False
							if p[1] < 0 or p[1] > n - 1:
														return False
							return True





def       __lowerCamelCase			(				UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__     ,							):







							'''simple docstring'''






							for itera in range(UpperCamelCase__   ):
														open_list[itera].remove_element(UpperCamelCase__   )
							# print("s", s)
							# print("j", j)
							((snake_case_)       ,					(snake_case_))           =					s
							snake_case_           =					(x - 1, y)
							snake_case_           =					(x + 1, y)
							snake_case_           =					(x, y + 1)
							snake_case_           =					(x, y - 1)

							for neighbours in [left, right, up, down]:
														if neighbours not in blocks:
																					if valid(UpperCamelCase__   ) and neighbours not in visited:
																												# print("neighbour", neighbours)
																												visited.add(UpperCamelCase__   )
																												snake_case_           =					-1
																												snake_case_           =					float('inf'   )

																					if valid(UpperCamelCase__   ) and g_function[neighbours] > g_function[s] + 1:
																												snake_case_           =					g_function[s] + 1
																												snake_case_           =					s
																												if neighbours not in close_list_anchor:
																																			open_list[0].put(UpperCamelCase__     ,							key(UpperCamelCase__     ,							0     ,							UpperCamelCase__     ,							UpperCamelCase__   )   )
																																			if neighbours not in close_list_inad:
																																										for var in range(1     ,							UpperCamelCase__   ):
																																																	if key(UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__   ) <= Wa * key(
																																																	    UpperCamelCase__     ,							0     ,							UpperCamelCase__     ,							UpperCamelCase__   ):
																																																								open_list[j].put(
																																																								    UpperCamelCase__     ,							key(UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__   )   )





def       __lowerCamelCase			(				):







							'''simple docstring'''






							snake_case_           =					[]
							for x in range(1     ,							5   ):
														for y in range(1     ,							6   ):
																					some_list.append((x, y)   )

							for x in range(15     ,							20   ):
														some_list.append((x, 17)   )

							for x in range(10     ,							19   ):
														for y in range(1     ,							15   ):
																					some_list.append((x, y)   )

    # L block
							for x in range(1     ,							4   ):
														for y in range(12     ,							19   ):
																					some_list.append((x, y)   )
							for x in range(3     ,							13   ):
														for y in range(16     ,							19   ):
																					some_list.append((x, y)   )
							return some_list


_UpperCAmelCase	:     Tuple		       = {0: consistent_heuristic, 1: heuristic_a, 2: heuristic_a}

_UpperCAmelCase	:     List[str]		       = [
    (0, 1),
    (1, 1),
    (2, 1),
    (3, 1),
    (4, 1),
    (5, 1),
    (6, 1),
    (7, 1),
    (8, 1),
    (9, 1),
    (10, 1),
    (11, 1),
    (12, 1),
    (13, 1),
    (14, 1),
    (15, 1),
    (16, 1),
    (17, 1),
    (18, 1),
    (19, 1),
]
_UpperCAmelCase	:     Tuple		       = make_common_ground()


_UpperCAmelCase	:     Dict		       = blocks_blk
# hyper parameters
_UpperCAmelCase	:     int		       = 1
_UpperCAmelCase	:     int		       = 1
_UpperCAmelCase	:     Tuple		       = 20
_UpperCAmelCase	:     Tuple		       = 3  # one consistent and two other inconsistent

# start and end destination
_UpperCAmelCase	:     Tuple		       = (0, 0)
_UpperCAmelCase	:     List[Any]		       = (n - 1, n - 1)

_UpperCAmelCase	:     Optional[int]		       = 1





def       __lowerCamelCase			(				UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__   ):







							'''simple docstring'''






							snake_case_           =					{start: 0, goal: float('inf'   )}
							snake_case_           =					{start: -1, goal: -1}
							snake_case_           =					[]
							snake_case_           =					set()

							for i in range(UpperCamelCase__   ):
														open_list.append(PriorityQueue()   )
														open_list[i].put(UpperCamelCase__     ,							key(UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__   )   )

							snake_case_           =					[]
							snake_case_           =					[]
							while open_list[0].minkey() < float('inf'   ):
														for i in range(1     ,							UpperCamelCase__   ):
																					# print(open_list[0].minkey(), open_list[i].minkey())
																					if open_list[i].minkey() <= Wa * open_list[0].minkey():
																												global t
																												t += 1
																												if g_function[goal] <= open_list[i].minkey():
																																			if g_function[goal] < float('inf'   ):
																																										do_something(UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__   )
																												else:
																																			snake_case_       ,					snake_case_           =					open_list[i].top_show()
																																			visited.add(UpperCamelCase__   )
																																			expand_state(
																																			    UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__     ,							)
																																			close_list_inad.append(UpperCamelCase__   )
																					else:
																												if g_function[goal] <= open_list[0].minkey():
																																			if g_function[goal] < float('inf'   ):
																																										do_something(UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__   )
																												else:
																																			snake_case_           =					open_list[0].top_show()
																																			visited.add(UpperCamelCase__   )
																																			expand_state(
																																			    UpperCamelCase__     ,							0     ,							UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__     ,							UpperCamelCase__     ,							)
																																			close_list_anchor.append(UpperCamelCase__   )
							print('No path found to goal'   )
							print()
							for i in range(n - 1     ,							-1     ,							-1   ):
														for j in range(UpperCamelCase__   ):
																					if (j, i) in blocks:
																												print('#'     ,							end=' '   )
																					elif (j, i) in back_pointer:
																												if (j, i) == (n - 1, n - 1):
																																			print('*'     ,							end=' '   )
																												else:
																																			print('-'     ,							end=' '   )
																					else:
																												print('*'     ,							end=' '   )
																					if (j, i) == (n - 1, n - 1):
																												print('<-- End position'     ,							end=' '   )
														print()
							print('^'   )
							print('Start position'   )
							print()
							print('# is an obstacle'   )
							print('- is the path taken by algorithm'   )


if __name__ == "__main__":
					multi_a_star(start, goal, n_heuristic)




