


'''simple docstring'''

from __future__ import annotations

import time

lowercase__				     =		list[tuple[int, int]]

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

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





class 						__SCREAMING_SNAKE_CASE					:






     def __init__(			self     ,							__UpperCamelCase     ,							__UpperCamelCase     ,							__UpperCamelCase     ,							__UpperCamelCase     ,							__UpperCamelCase		)       ->    Tuple:
          _a						=		pos_x
          _a						=		pos_y
          _a						=		(pos_y, pos_x)
          _a						=		goal_x
          _a						=		goal_y
          _a						=		parent







class 						__SCREAMING_SNAKE_CASE					:






     def __init__(			self     ,							__UpperCamelCase     ,							__UpperCamelCase		)       ->    Tuple:
          _a						=		Node(start[1]     ,							start[0]     ,							goal[1]     ,							goal[0]     ,							__UpperCamelCase		)
          _a						=		Node(goal[1]     ,							goal[0]     ,							goal[1]     ,							goal[0]     ,							__UpperCamelCase		)

          _a						=		[self.start]
          _a						=		False






     def  a_					(			self		)       ->    Path | None:
          while self.node_queue:
               _a						=		self.node_queue.pop(0		)

               if current_node.pos == self.target.pos:
                    _a						=		True
                    return self.retrace_path(__UpperCamelCase		)

               _a						=		self.get_successors(__UpperCamelCase		)

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

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






     def  a_					(			self     ,							__UpperCamelCase		)       ->    list[Node]:
          _a						=		[]
          for action in delta:
               _a						=		parent.pos_x + action[1]
               _a						=		parent.pos_y + action[0]
               if not (0 <= pos_x <= len(grid[0]		) - 1 and 0 <= pos_y <= len(__UpperCamelCase		) - 1):
                    continue

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

               successors.append(
                   Node(__UpperCamelCase     ,							__UpperCamelCase     ,							self.target.pos_y     ,							self.target.pos_x     ,							__UpperCamelCase		)		)
          return successors






     def  a_					(			self     ,							__UpperCamelCase		)       ->    Path:
          _a						=		node
          _a						=		[]
          while current_node is not None:
               path.append((current_node.pos_y, current_node.pos_x)		)
               _a						=		current_node.parent
          path.reverse()
          return path







class 						__SCREAMING_SNAKE_CASE					:






     def __init__(			self     ,							__UpperCamelCase     ,							__UpperCamelCase		)       ->    List[Any]:
          _a						=		BreadthFirstSearch(__UpperCamelCase     ,							__UpperCamelCase		)
          _a						=		BreadthFirstSearch(__UpperCamelCase     ,							__UpperCamelCase		)
          _a						=		False






     def  a_					(			self		)       ->    Path | None:
          while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
               _a						=		self.fwd_bfs.node_queue.pop(0		)
               _a						=		self.bwd_bfs.node_queue.pop(0		)

               if current_bwd_node.pos == current_fwd_node.pos:
                    _a						=		True
                    return self.retrace_bidirectional_path(
                        __UpperCamelCase     ,							__UpperCamelCase		)

               _a						=		current_bwd_node
               _a						=		current_fwd_node

               _a						=		{
                   self.fwd_bfs: self.fwd_bfs.get_successors(__UpperCamelCase		),
                   self.bwd_bfs: self.bwd_bfs.get_successors(__UpperCamelCase		),
               }

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

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






     def  a_					(			self     ,							__UpperCamelCase     ,							__UpperCamelCase		)       ->    Path:
          _a						=		self.fwd_bfs.retrace_path(__UpperCamelCase		)
          _a						=		self.bwd_bfs.retrace_path(__UpperCamelCase		)
          bwd_path.pop()
          bwd_path.reverse()
          _a						=		fwd_path + bwd_path
          return path


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

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

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

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

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

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





'''simple docstring'''

lowercase__				     =		256
# Modulus to hash a string
lowercase__				     =		1_000_003






def __UpperCamelCase   (			__lowerCamelCase		: str      ,  __lowerCamelCase		: str				)      ->     bool:







     '''simple docstring'''






     _a						=		len(__lowerCamelCase				)
     _a						=		len(__lowerCamelCase				)
     if p_len > t_len:
          return False

     _a						=		0
     _a						=		0
     _a						=		1

     # Calculating the hash of pattern and substring of text
     for i in range(__lowerCamelCase				):
          _a						=		(ord(pattern[i]				) + p_hash * alphabet_size) % modulus
          _a						=		(ord(text[i]				) + text_hash * alphabet_size) % modulus
          if i == p_len - 1:
               continue
          _a						=		(modulus_power * alphabet_size) % modulus

     for i in range(0      ,  t_len - p_len + 1				):
          if text_hash == p_hash and text[i : i + p_len] == pattern:
               return True
          if i == t_len - p_len:
               continue
          # Calculate the https://en.wikipedia.org/wiki/Rolling_hash
          _a						=		(
              (text_hash - ord(text[i]				) * modulus_power) * alphabet_size
              + ord(text[i + p_len]				)
          ) % modulus
     return False






def __UpperCamelCase   (			)      ->     None:







     '''simple docstring'''






     _a						=		"abc1abc12"
     _a						=		"alskfjaldsabc1abc1abc12k23adsfabcabc"
     _a						=		"alskfjaldsk23adsfabcabc"
     assert rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				) and not rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)

     # Test 2)
     _a						=		"ABABX"
     _a						=		"ABABZABABYABABX"
     assert rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)

     # Test 3)
     _a						=		"AAAB"
     _a						=		"ABAAAAAB"
     assert rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)

     # Test 4)
     _a						=		"abcdabcy"
     _a						=		"abcxabcdabxabcdabcdabcy"
     assert rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)

     # Test 5)
     _a						=		"Lü"
     _a						=		"Lüsai"
     assert rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)
     _a						=		"Lue"
     assert not rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)
     print("Success."				)


if __name__ == "__main__":
   test_rabin_karp()

