

"""simple docstring"""




from __future__ import annotations

import time

snake_case_        =			list[tuple[int, int]]

snake_case_        =			[
    [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],
]

snake_case_        =			[[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right


class 				SCREAMING_SNAKE_CASE__ :





    def __init__(				self						,       a						,       a						,       a						,       a						,       a):
         lowercase__   :       Any				=	pos_x
         lowercase__   :       List[Any]				=	pos_y
         lowercase__   :       Any				=	(pos_y, pos_x)
         lowercase__   :       List[Any]				=	goal_x
         lowercase__   :       Tuple				=	goal_y
         lowercase__   :       int				=	parent



class 				SCREAMING_SNAKE_CASE__ :





    def __init__(				self						,       a						,       a):
         lowercase__   :       List[Any]				=	Node(start[1]						,       start[0]						,       goal[1]						,       goal[0]						,       SCREAMING_SNAKE_CASE_)
         lowercase__   :       Union[str, Any]				=	Node(goal[1]						,       goal[0]						,       goal[1]						,       goal[0]						,       SCREAMING_SNAKE_CASE_)

         lowercase__   :       Optional[int]				=	[self.start]
         lowercase__   :       Dict				=	False





    def 				snake_case_    (				self):
         while self.node_queue:
              lowercase__   :       Dict				=	self.node_queue.pop(0)

              if current_node.pos == self.target.pos:
                   lowercase__   :       Optional[Any]				=	True
                   return self.retrace_path(SCREAMING_SNAKE_CASE_)

              lowercase__   :       Tuple				=	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 				snake_case_    (				self						,       a):
         lowercase__   :       Optional[Any]				=	[]
         for action in delta:
              lowercase__   :       str				=	parent.pos_x + action[1]
              lowercase__   :       List[str]				=	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 				snake_case_    (				self						,       a):
         lowercase__   :       int				=	node
         lowercase__   :       List[Any]				=	[]
         while current_node is not None:
              path.append((current_node.pos_y, current_node.pos_x))
              lowercase__   :       Optional[int]				=	current_node.parent
         path.reverse()
         return path



class 				SCREAMING_SNAKE_CASE__ :





    def __init__(				self						,       a						,       a):
         lowercase__   :       List[str]				=	BreadthFirstSearch(SCREAMING_SNAKE_CASE_						,       SCREAMING_SNAKE_CASE_)
         lowercase__   :       List[str]				=	BreadthFirstSearch(SCREAMING_SNAKE_CASE_						,       SCREAMING_SNAKE_CASE_)
         lowercase__   :       Dict				=	False





    def 				snake_case_    (				self):
         while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
              lowercase__   :       str				=	self.fwd_bfs.node_queue.pop(0)
              lowercase__   :       Optional[int]				=	self.bwd_bfs.node_queue.pop(0)

              if current_bwd_node.pos == current_fwd_node.pos:
                   lowercase__   :       List[str]				=	True
                   return self.retrace_bidirectional_path(
                       SCREAMING_SNAKE_CASE_						,       SCREAMING_SNAKE_CASE_)

              lowercase__   :       Optional[int]				=	current_bwd_node
              lowercase__   :       List[Any]				=	current_fwd_node

              lowercase__   :       Optional[int]				=	{
                  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 				snake_case_    (				self						,       a						,       a):
         lowercase__   :       List[Any]				=	self.fwd_bfs.retrace_path(SCREAMING_SNAKE_CASE_)
         lowercase__   :       Optional[int]				=	self.bwd_bfs.retrace_path(SCREAMING_SNAKE_CASE_)
         bwd_path.pop()
         bwd_path.reverse()
         lowercase__   :       Union[str, Any]				=	fwd_path + bwd_path
         return path


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

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

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

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

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

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




from __future__ import annotations

import math

def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   int      ):



     '''simple docstring'''





     if 1 < number < 4:
          # 2 and 3 are primes
          return True
     elif number < 2 or number % 2 == 0 or number % 3 == 0:
          # Negatives, 0, 1, all even numbers, all multiples of 3 are not primes
          return False

     # All primes number are in format of 6k +/- 1
     for i in range(5     ,					int(math.sqrt(SCREAMING_SNAKE_CASE_      ) + 1      )     ,					6      ):
          if number % i == 0 or number % (i + 2) == 0:
               return False
     return True

def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   int      ):



     '''simple docstring'''





     lowercase__   :       int				=	str(SCREAMING_SNAKE_CASE_      )
     lowercase__   :       Union[str, Any]				=	[n]
     for i in range(1     ,					len(SCREAMING_SNAKE_CASE_      )      ):
          list_nums.append(int(str_num[i:]      )      )
          list_nums.append(int(str_num[:-i]      )      )
     return list_nums

def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   int      ):



     '''simple docstring'''





     if len(str(SCREAMING_SNAKE_CASE_      )      ) > 3:
          if not is_prime(int(str(SCREAMING_SNAKE_CASE_      )[-3:]      )      ) or not is_prime(int(str(SCREAMING_SNAKE_CASE_      )[:3]      )      ):
               return False
     return True

def      snake_case__      (   SCREAMING_SNAKE_CASE_		:   int = 11      ):



     '''simple docstring'''





     lowercase__   :       list[int]				=	[]
     lowercase__   :       Tuple				=	13
     while len(SCREAMING_SNAKE_CASE_      ) != count:
          if validate(SCREAMING_SNAKE_CASE_      ):
               lowercase__   :       Optional[int]				=	list_truncated_nums(SCREAMING_SNAKE_CASE_      )
               if all(is_prime(SCREAMING_SNAKE_CASE_      ) for i in list_nums      ):
                    list_truncated_primes.append(SCREAMING_SNAKE_CASE_      )
          num += 2
     return list_truncated_primes

def      snake_case__      (   ):



     '''simple docstring'''





     return sum(compute_truncated_primes(11      )      )


if __name__ == "__main__":
       print(F'''{sum(compute_truncated_primes(11)) = }''')

