






from __future__ import annotations

__A					=	list[tuple[int, int]]

__A					=	[
    [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					=	([-1, 0], [0, -1], [1, 0], [0, 1])  # up, left, down, right



class 				_A			:
    """simple docstring"""

    def __init__(				self      :     List[str] ,     __SCREAMING_SNAKE_CASE      :     int ,     __SCREAMING_SNAKE_CASE      :     int ,     __SCREAMING_SNAKE_CASE      :     int ,     __SCREAMING_SNAKE_CASE      :     int ,     __SCREAMING_SNAKE_CASE      :     float ,     __SCREAMING_SNAKE_CASE      :     Node | None ,     )      ->							List[str]:
           __UpperCAmelCase     				=pos_x
           __UpperCAmelCase     				=pos_y
           __UpperCAmelCase     				=(pos_y, pos_x)
           __UpperCAmelCase     				=goal_x
           __UpperCAmelCase     				=goal_y
           __UpperCAmelCase     				=g_cost
           __UpperCAmelCase     				=parent
           __UpperCAmelCase     				=self.calculate_heuristic()



    def _a							(				self      :     Optional[int]      )      ->							float:
           __UpperCAmelCase     				=abs(self.pos_x - self.goal_x      )
           __UpperCAmelCase     				=abs(self.pos_y - self.goal_y      )
           return dx + dy



    def __lt__(				self      :     str ,     __SCREAMING_SNAKE_CASE      :     Optional[int]      )      ->							bool:
           return self.f_cost < other.f_cost




class 				_A			:
    """simple docstring"""

    def __init__(				self      :     int ,     __SCREAMING_SNAKE_CASE      :     tuple[int, int] ,     __SCREAMING_SNAKE_CASE      :     tuple[int, int]      )      ->							Tuple:
           __UpperCAmelCase     				=Node(start[1] ,     start[0] ,     goal[1] ,     goal[0] ,     0 ,     __SCREAMING_SNAKE_CASE      )
           __UpperCAmelCase     				=Node(goal[1] ,     goal[0] ,     goal[1] ,     goal[0] ,     99999 ,     __SCREAMING_SNAKE_CASE      )

           __UpperCAmelCase     				=[self.start]
           __UpperCAmelCase     				=[]

           __UpperCAmelCase     				=False



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







           while self.open_nodes:
                  # Open Nodes are sorted using __lt__
                  self.open_nodes.sort()
                  __UpperCAmelCase     				=self.open_nodes.pop(0      )

                  if current_node.pos == self.target.pos:
                         __UpperCAmelCase     				=True
                         return self.retrace_path(__SCREAMING_SNAKE_CASE      )

                  self.closed_nodes.append(__SCREAMING_SNAKE_CASE      )
                  __UpperCAmelCase     				=self.get_successors(__SCREAMING_SNAKE_CASE      )

                  for child_node in successors:
                         if child_node in self.closed_nodes:
                                continue

                         if child_node not in self.open_nodes:
                                self.open_nodes.append(__SCREAMING_SNAKE_CASE      )
                         else:
                                # retrieve the best current path
                                __UpperCAmelCase     				=self.open_nodes.pop(self.open_nodes.index(__SCREAMING_SNAKE_CASE      )      )

                                if child_node.g_cost < better_node.g_cost:
                                       self.open_nodes.append(__SCREAMING_SNAKE_CASE      )
                                else:
                                       self.open_nodes.append(__SCREAMING_SNAKE_CASE      )

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



    def _a							(				self      :     Optional[Any] ,     __SCREAMING_SNAKE_CASE      :     Node      )      ->							list[Node]:
           __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(__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 ,     parent.g_cost + 1 ,     __SCREAMING_SNAKE_CASE ,     )      )
           return successors



    def _a							(				self      :     Optional[int] ,     __SCREAMING_SNAKE_CASE      :     Node | None      )      ->							Path:
           __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


if __name__ == "__main__":
   __A					=	(0, 0)
   __A					=	(len(grid) - 1, len(grid[0]) - 1)
   for elem in grid:
      print(elem)

   print("------")

   __A					=	GreedyBestFirst(init, goal)
   __A					=	greedy_bf.search()
   if path:
      for pos_x, pos_y in path:
         __A					=	2

      for elem in grid:
         print(elem)










import argparse
import hashlib  # hashlib is only used inside the Test class
import struct


class    SCREAMING_SNAKE_CASE_				:



	"""simple docstring"""


	def __init__(					self		:						Tuple					,     lowerCAmelCase		:						Tuple	)	->       Dict:







						"""simple docstring"""







						__UpperCamelCase					:	Any             =      data
						__UpperCamelCase					:	List[str]             =      [0x6_7_4_5_2_3_0_1, 0xe_f_c_d_a_b_8_9, 0x9_8_b_a_d_c_f_e, 0x1_0_3_2_5_4_7_6, 0xc_3_d_2_e_1_f_0]






	@staticmethod
	def 					lowerCamelCase__     (					lowerCAmelCase		:						str					,     lowerCAmelCase		:						Union[str, Any]	)	->       str:







						"""simple docstring"""







						return ((n << b) | (n >> (32 - b))) & 0xf_f_f_f_f_f_f_f






	def 					lowerCamelCase__     (					self		:						Optional[int]	)	->       Dict:







						"""simple docstring"""







						__UpperCamelCase					:	int             =      b"""\x80""" + b"""\x00""" * (63 - (len(self.data	) + 8) % 64)
						__UpperCamelCase					:	int             =      self.data + padding + struct.pack(""">Q"""					,     8 * len(self.data	)	)
						return padded_data






	def 					lowerCamelCase__     (					self		:						str	)	->       str:







						"""simple docstring"""







						return [
						    self.padded_data[i : i + 64] for i in range(0					,     len(self.padded_data	)					,     64	)
						]






	def 					lowerCamelCase__     (					self		:						Union[str, Any]					,     lowerCAmelCase		:						Tuple	)	->       List[Any]:







						"""simple docstring"""







						__UpperCamelCase					:	Tuple             =      list(struct.unpack(""">16L"""					,     lowerCAmelCase	)	) + [0] * 64
						for i in range(16					,     80	):
											__UpperCamelCase					:	Dict             =      self.rotate((w[i - 3] ^ w[i - 8] ^ w[i - 14] ^ w[i - 16])					,     1	)
						return w






	def 					lowerCamelCase__     (					self		:						Union[str, Any]	)	->       Dict:







						"""simple docstring"""







						__UpperCamelCase					:	Dict             =      self.padding()
						__UpperCamelCase					:	int             =      self.split_blocks()
						for block in self.blocks:
											__UpperCamelCase					:	Union[str, Any]             =      self.expand_block(lowerCAmelCase	)
											__UpperCamelCase      ,			__UpperCamelCase      ,			__UpperCamelCase      ,			__UpperCamelCase      ,			__UpperCamelCase					:	str             =      self.h
											for i in range(0					,     80	):
																if 0 <= i < 20:
																					__UpperCamelCase					:	List[Any]             =      (b & c) | ((~b) & d)
																					__UpperCamelCase					:	str             =      0x5_a_8_2_7_9_9_9
																elif 20 <= i < 40:
																					__UpperCamelCase					:	Tuple             =      b ^ c ^ d
																					__UpperCamelCase					:	List[Any]             =      0x6_e_d_9_e_b_a_1
																elif 40 <= i < 60:
																					__UpperCamelCase					:	Tuple             =      (b & c) | (b & d) | (c & d)
																					__UpperCamelCase					:	List[str]             =      0x8_f_1_b_b_c_d_c
																elif 60 <= i < 80:
																					__UpperCamelCase					:	Optional[int]             =      b ^ c ^ d
																					__UpperCamelCase					:	Tuple             =      0xc_a_6_2_c_1_d_6
																__UpperCamelCase      ,			__UpperCamelCase      ,			__UpperCamelCase      ,			__UpperCamelCase      ,			__UpperCamelCase					:	Tuple             =      (
																    self.rotate(lowerCAmelCase					,     5	) + f + e + k + expanded_block[i] & 0xf_f_f_f_f_f_f_f,
																    a,
																    self.rotate(lowerCAmelCase					,     30	),
																    c,
																    d,
																)
											__UpperCamelCase					:	List[Any]             =      (
											    self.h[0] + a & 0xf_f_f_f_f_f_f_f,
											    self.h[1] + b & 0xf_f_f_f_f_f_f_f,
											    self.h[2] + c & 0xf_f_f_f_f_f_f_f,
											    self.h[3] + d & 0xf_f_f_f_f_f_f_f,
											    self.h[4] + e & 0xf_f_f_f_f_f_f_f,
											)
						return ("{:08x}" * 5).format(*self.h	)






def 				A__ ()     ->						int:
					__UpperCamelCase					:	Optional[int]             =      b"""Test String"""
					assert SHAaHash(snake_case				).final_hash() == hashlib.shaa(snake_case				).hexdigest()  # noqa: S324





def 				A__ ()     ->						Tuple:
					__UpperCamelCase					:	Optional[Any]             =      argparse.ArgumentParser(description="""Process some strings or files"""				)
					parser.add_argument(
					    """--string"""		,	dest="""input_string"""		,	default="""Hello World!! Welcome to Cryptography"""		,	help="""Hash the string"""		,	)
					parser.add_argument("""--file"""		,	dest="""input_file"""		,	help="""Hash contents of a file"""				)
					__UpperCamelCase					:	List[Any]             =      parser.parse_args()
					__UpperCamelCase					:	List[str]             =      args.input_string
					# In any case hash input should be a bytestring
					if args.input_file:
										with open(args.input_file		,	"""rb"""				) as f:
															__UpperCamelCase					:	Tuple             =      f.read()
					else:
										__UpperCamelCase					:	Any             =      bytes(snake_case		,	"""utf-8"""				)
					print(SHAaHash(snake_case				).final_hash()				)


if __name__ == "__main__":
	main()
	import doctest

	doctest.testmod()






