

from __future__ import annotations

import time

_a:    Union[str, Any] 							=			list[tuple[int, int]]

_a:    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],
]

_a:    str 							=			[[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

class 						__UpperCamelCase    :




	def __init__(		self	:						Union[str, Any]		,	lowerCAmelCase	:						int		,	lowerCAmelCase	:						int		,	lowerCAmelCase	:						int		,	lowerCAmelCase	:						int		,	lowerCAmelCase	:						Node | None							):


		'''simple docstring'''







		UpperCAmelCase_       				=			pos_x
		UpperCAmelCase_       				=			pos_y
		UpperCAmelCase_       				=			(pos_y, pos_x)
		UpperCAmelCase_       				=			goal_x
		UpperCAmelCase_       				=			goal_y
		UpperCAmelCase_       				=			parent


class 						__UpperCamelCase    :




	def __init__(		self	:						Any		,	lowerCAmelCase	:						tuple[int, int]		,	lowerCAmelCase	:						tuple[int, int]							):


		'''simple docstring'''







		UpperCAmelCase_       				=			Node(start[1]		,	start[0]		,	goal[1]		,	goal[0]		,	lowerCAmelCase							)
		UpperCAmelCase_       				=			Node(goal[1]		,	goal[0]		,	goal[1]		,	goal[0]		,	lowerCAmelCase							)

		UpperCAmelCase_       				=			[self.start]
		UpperCAmelCase_       				=			False




	def       __A					(		self	:						List[str]							):


		'''simple docstring'''







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

			if current_node.pos == self.target.pos:
				UpperCAmelCase_       				=			True
				return self.retrace_path(lowerCAmelCase							)

			UpperCAmelCase_       				=			self.get_successors(lowerCAmelCase							)

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

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




	def       __A					(		self	:						str		,	lowerCAmelCase	:						Node							):


		'''simple docstring'''







		UpperCAmelCase_       				=			[]
		for action in delta:
			UpperCAmelCase_       				=			parent.pos_x + action[1]
			UpperCAmelCase_       				=			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		,	lowerCAmelCase							)							)
		return successors




	def       __A					(		self	:						Dict		,	lowerCAmelCase	:						Node | None							):


		'''simple docstring'''







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


class 						__UpperCamelCase    :




	def __init__(		self	:						Any		,	lowerCAmelCase	:						List[Any]		,	lowerCAmelCase	:						Optional[int]							):


		'''simple docstring'''







		UpperCAmelCase_       				=			BreadthFirstSearch(lowerCAmelCase		,	lowerCAmelCase							)
		UpperCAmelCase_       				=			BreadthFirstSearch(lowerCAmelCase		,	lowerCAmelCase							)
		UpperCAmelCase_       				=			False




	def       __A					(		self	:						Tuple							):


		'''simple docstring'''







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

			if current_bwd_node.pos == current_fwd_node.pos:
				UpperCAmelCase_       				=			True
				return self.retrace_bidirectional_path(
				    lowerCAmelCase		,	lowerCAmelCase							)

			UpperCAmelCase_       				=			current_bwd_node
			UpperCAmelCase_       				=			current_fwd_node

			UpperCAmelCase_       				=			{
			    self.fwd_bfs: self.fwd_bfs.get_successors(lowerCAmelCase							),
			    self.bwd_bfs: self.bwd_bfs.get_successors(lowerCAmelCase							),
			}

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

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




	def       __A					(		self	:						int		,	lowerCAmelCase	:						Node		,	lowerCAmelCase	:						Node							):


		'''simple docstring'''







		UpperCAmelCase_       				=			self.fwd_bfs.retrace_path(lowerCAmelCase							)
		UpperCAmelCase_       				=			self.bwd_bfs.retrace_path(lowerCAmelCase							)
		bwd_path.pop()
		bwd_path.reverse()
		UpperCAmelCase_       				=			fwd_path + bwd_path
		return path


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

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

				_a:    Any 							=			time.time()
				_a:    List[str] 							=			BreadthFirstSearch(init, goal)
				_a:    Any 							=			bfs.search()
				_a:    Dict 							=			time.time() - start_bfs_time

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

				_a:    Union[str, Any] 							=			time.time()
				_a:    Tuple 							=			BidirectionalBreadthFirstSearch(init, goal)
				_a:    int 							=			bd_bfs.search()
				_a:    int 							=			time.time() - start_bd_bfs_time

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


from __future__ import annotations

class 						__UpperCamelCase    :




	def __init__(		self	:						Optional[Any]		,	lowerCAmelCase	:						str		,	lowerCAmelCase	:						str							):


		'''simple docstring'''







		UpperCAmelCase_				,   UpperCAmelCase_       				=			text, pattern
		UpperCAmelCase_				,   UpperCAmelCase_       				=			len(lowerCAmelCase							), len(lowerCAmelCase							)




	def       __A					(		self	:						List[str]		,	lowerCAmelCase	:						str							):


		'''simple docstring'''







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




	def       __A					(		self	:						int		,	lowerCAmelCase	:						int							):


		'''simple docstring'''







		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       __A					(		self	:						str							):


		'''simple docstring'''







		UpperCAmelCase_       				=			[]
		for i in range(self.textLen - self.patLen + 1							):
			UpperCAmelCase_       				=			self.mismatch_in_text(lowerCAmelCase							)
			if mismatch_index == -1:
				positions.append(lowerCAmelCase							)
			else:
				UpperCAmelCase_       				=			self.match_in_pattern(self.text[mismatch_index]							)
				UpperCAmelCase_       				=			(
				    mismatch_index - match_index
				)  # shifting index lgtm [py/multiple-definition]
		return positions


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

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