





'''simple docstring'''

from __future__ import annotations

import time

__lowerCamelCase : int											=			list[tuple[int, int]]

__lowerCamelCase : List[str]											=			[
    [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],
]

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

class       UpperCAmelCase :




  def __init__(self      :	Optional[int]							,			A__      :	int							,			A__      :	int							,			A__      :	int							,			A__      :	int							,			A__      :	Node | None				)					-> Tuple:
      lowercase         = pos_x
      lowercase         = pos_y
      lowercase         = (pos_y, pos_x)
      lowercase         = goal_x
      lowercase         = goal_y
      lowercase         = parent




class       UpperCAmelCase :




  def __init__(self      :	int							,			A__      :	tuple[int, int]							,			A__      :	tuple[int, int]				)					-> List[str]:
      lowercase         = Node(start[1]							,			start[0]							,			goal[1]							,			goal[0]							,			A__				)
      lowercase         = Node(goal[1]							,			goal[0]							,			goal[1]							,			goal[0]							,			A__				)

      lowercase         = [self.start]
      lowercase         = False




  def 				UpperCAmelCase__   (self      :	str				)					-> Path | None:




      while self.node_queue:
          lowercase         = self.node_queue.pop(0				)

          if current_node.pos == self.target.pos:
              lowercase         = True
              return self.retrace_path(A__				)

          lowercase         = self.get_successors(A__				)

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

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




  def 				UpperCAmelCase__   (self      :	List[str]							,			A__      :	Node				)					-> list[Node]:
      lowercase         = []
      for action in delta:
          lowercase         = parent.pos_x + action[1]
          lowercase         = parent.pos_y + action[0]
          if not (0 <= pos_x <= len(grid[0]				) - 1 and 0 <= pos_y <= len(A__				) - 1):
              continue

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

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





  def 				UpperCAmelCase__   (self      :	Union[str, Any]							,			A__      :	Node | None				)					-> Path:
      lowercase         = node
      lowercase         = []
      while current_node is not None:
          path.append((current_node.pos_y, current_node.pos_x)				)
          lowercase         = current_node.parent
      path.reverse()
      return path




class       UpperCAmelCase :




  def __init__(self      :	Union[str, Any]							,			A__      :	int							,			A__      :	List[Any]				)					-> Tuple:
      lowercase         = BreadthFirstSearch(A__							,			A__				)
      lowercase         = BreadthFirstSearch(A__							,			A__				)
      lowercase         = False




  def 				UpperCAmelCase__   (self      :	Union[str, Any]				)					-> Path | None:




      while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
          lowercase         = self.fwd_bfs.node_queue.pop(0				)
          lowercase         = self.bwd_bfs.node_queue.pop(0				)

          if current_bwd_node.pos == current_fwd_node.pos:
              lowercase         = True
              return self.retrace_bidirectional_path(
                  A__							,			A__				)

          lowercase         = current_bwd_node
          lowercase         = current_fwd_node

          lowercase         = {
              self.fwd_bfs: self.fwd_bfs.get_successors(A__				),
              self.bwd_bfs: self.bwd_bfs.get_successors(A__				),
          }

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

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





  def 				UpperCAmelCase__   (self      :	Dict							,			A__      :	Node							,			A__      :	Node				)					-> Path:
      lowercase         = self.fwd_bfs.retrace_path(A__				)
      lowercase         = self.bwd_bfs.retrace_path(A__				)
      bwd_path.pop()
      bwd_path.reverse()
      lowercase         = fwd_path + bwd_path
      return path


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

   doctest.testmod()
   __lowerCamelCase : str											=			(0, 0)
   __lowerCamelCase : Optional[Any]											=			(len(grid) - 1, len(grid[0]) - 1)
   for elem in grid:
      print(elem)

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

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

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

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











'''simple docstring'''

from __future__ import annotations

class       UpperCAmelCase :




		def __init__(self      :	Dict							,			A__      :	str							,			A__      :	str				)					-> str:
						lowercase   ,							lowercase         = text, pattern
						lowercase   ,							lowercase         = len(A__				), len(A__				)




		def 				UpperCAmelCase__   (self      :	Any							,			A__      :	str				)					-> int:

						for i in range(self.patLen - 1							,			-1							,			-1				):
										if char == self.pattern[i]:
														return i
						return -1




		def 				UpperCAmelCase__   (self      :	List[Any]							,			A__      :	int				)					-> int:

						for i in range(self.patLen - 1							,			-1							,			-1				):
										if self.pattern[i] != self.text[current_pos + i]:
														return current_pos + i
						return -1





		def 				UpperCAmelCase__   (self      :	Optional[Any]				)					-> list[int]:
						# searches pattern in text and returns index positions
						lowercase         = []
						for i in range(self.textLen - self.patLen + 1				):
										lowercase         = self.mismatch_in_text(A__				)
										if mismatch_index == -1:
														positions.append(A__				)
										else:
														lowercase         = self.match_in_pattern(self.text[mismatch_index]				)
														lowercase         = (
														    mismatch_index - match_index
														)  # shifting index lgtm [py/multiple-definition]
						return positions




__lowerCamelCase : List[str]											=			"ABAABA"
__lowerCamelCase : List[str]											=			"AB"
__lowerCamelCase : Union[str, Any]											=			BoyerMooreSearch(text, pattern)
__lowerCamelCase : List[str]											=			bms.bad_character_heuristic()

if len(positions) == 0:
			print("No match found")
else:
			print("Pattern found in following positions: ")
			print(positions)




