



from __future__ import annotations

_lowerCamelCase						    =  list[tuple[int, int]]

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

class       _SCREAMING_SNAKE_CASE	:





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





     def 	__snake_case    (       self :							Dict				)->float:
      __SCREAMING_SNAKE_CASE       :    Tuple       =	abs(self.pos_x - self.goal_x				)
      __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	abs(self.pos_y - self.goal_y				)
      return dx + dy






     def __lt__(       self :							Any     ,  UpperCamelCase :							int				)->bool:
      return self.f_cost < other.f_cost






class       _SCREAMING_SNAKE_CASE	:





     def __init__(       self :							Dict     ,  UpperCamelCase :							tuple[int, int]     ,  UpperCamelCase :							tuple[int, int]				)->Union[str, Any]:
      __SCREAMING_SNAKE_CASE       :    int       =	Node(start[1]     ,  start[0]     ,  goal[1]     ,  goal[0]     ,  0     ,  UpperCamelCase				)
      __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	Node(goal[1]     ,  goal[0]     ,  goal[1]     ,  goal[0]     ,  9_9_9_9_9     ,  UpperCamelCase				)

      __SCREAMING_SNAKE_CASE       :    int       =	[self.start]
      __SCREAMING_SNAKE_CASE       :    list[Node]       =	[]

      __SCREAMING_SNAKE_CASE       :    Optional[int]       =	False





     def 	__snake_case    (       self :							str				)->Path | None:
      while self.open_nodes:
       # Open Nodes are sorted using __lt__
       self.open_nodes.sort()
       __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	self.open_nodes.pop(0				)

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

       self.closed_nodes.append(UpperCamelCase				)
       __SCREAMING_SNAKE_CASE       :    int       =	self.get_successors(UpperCamelCase				)

       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(UpperCamelCase				)
        else:
         # retrieve the best current path
         __SCREAMING_SNAKE_CASE       :    Tuple       =	self.open_nodes.pop(self.open_nodes.index(UpperCamelCase				)				)

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

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





     def 	__snake_case    (       self :							List[str]     ,  UpperCamelCase :							Node				)->list[Node]:
      __SCREAMING_SNAKE_CASE       :    Any       =	[]
      for action in delta:
       __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	parent.pos_x + action[1]
       __SCREAMING_SNAKE_CASE       :    str       =	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     ,  parent.g_cost + 1     ,  UpperCamelCase     ,  )				)
      return successors






     def 	__snake_case    (       self :							List[Any]     ,  UpperCamelCase :							Node | None				)->Path:
      __SCREAMING_SNAKE_CASE       :    List[Any]       =	node
      __SCREAMING_SNAKE_CASE       :    List[str]       =	[]
      while current_node is not None:
       path.append((current_node.pos_y, current_node.pos_x)				)
       __SCREAMING_SNAKE_CASE       :    str       =	current_node.parent
      path.reverse()
      return path


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

      print("""------""")

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

            for elem in grid:
                  print(elem)











from collections.abc import Generator
from math import sin






def 	_lowerCAmelCase						(				__lowerCamelCase   :     bytes     ):



 """simple docstring"""





 if len(__lowerCamelCase     ) != 32:
  raise ValueError("Input must be of length 32"     )

 __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	b""
 for i in [3, 2, 1, 0]:
  little_endian += string_aa[8 * i : 8 * i + 8]
 return little_endian






def 	_lowerCAmelCase						(				__lowerCamelCase   :     int     ):



 """simple docstring"""





 if i < 0:
  raise ValueError("Input must be non-negative"     )

 __SCREAMING_SNAKE_CASE       :    Any       =	format(__lowerCamelCase		,	"08x"     )[-8:]
 __SCREAMING_SNAKE_CASE       :    Optional[Any]       =	b""
 for i in [3, 2, 1, 0]:
  little_endian_hex += hex_rep[2 * i : 2 * i + 2].encode("utf-8"     )
 return little_endian_hex






def 	_lowerCAmelCase						(				__lowerCamelCase   :     bytes     ):



 """simple docstring"""





 __SCREAMING_SNAKE_CASE       :    Any       =	b""
 for char in message:
  bit_string += format(__lowerCamelCase		,	"08b"     ).encode("utf-8"     )
 __SCREAMING_SNAKE_CASE       :    List[str]       =	format(len(__lowerCamelCase     )		,	"064b"     ).encode("utf-8"     )

 # Pad bit_string to a multiple of 512 chars
 bit_string += b"1"
 while len(__lowerCamelCase     ) % 512 != 448:
  bit_string += b"0"
 bit_string += to_little_endian(start_len[32:]     ) + to_little_endian(start_len[:32]     )

 return bit_string






def 	_lowerCAmelCase						(				__lowerCamelCase   :     bytes     ):



 """simple docstring"""





 if len(__lowerCamelCase     ) % 512 != 0:
  raise ValueError("Input must have length that's a multiple of 512"     )

 for pos in range(0		,	len(__lowerCamelCase     )		,	512     ):
  __SCREAMING_SNAKE_CASE       :    int       =	bit_string[pos : pos + 512]
  __SCREAMING_SNAKE_CASE       :    Tuple       =	[]
  for i in range(0		,	512		,	32     ):
   block_words.append(int(to_little_endian(block[i : i + 32]     )		,	2     )     )
  yield block_words






def 	_lowerCAmelCase						(				__lowerCamelCase   :     int     ):



 """simple docstring"""





 if i < 0:
  raise ValueError("Input must be non-negative"     )

 __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	format(__lowerCamelCase		,	"032b"     )
 __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	""
 for c in i_str:
  new_str += "1" if c == "0" else "0"
 return int(__lowerCamelCase		,	2     )






def 	_lowerCAmelCase						(				__lowerCamelCase   :     int		,	__lowerCamelCase   :     int     ):



 """simple docstring"""





 return (a + b) % 2**32






def 	_lowerCAmelCase						(				__lowerCamelCase   :     int		,	__lowerCamelCase   :     int     ):



 """simple docstring"""





 if i < 0:
  raise ValueError("Input must be non-negative"     )
 if shift < 0:
  raise ValueError("Shift must be non-negative"     )
 return ((i << shift) ^ (i >> (32 - shift))) % 2**32






def 	_lowerCAmelCase						(				__lowerCamelCase   :     bytes     ):



 """simple docstring"""





 __SCREAMING_SNAKE_CASE       :    Tuple       =	preprocess(__lowerCamelCase     )

 __SCREAMING_SNAKE_CASE       :    List[Any]       =	[int(2**32 * abs(sin(i + 1     )     )     ) for i in range(64     )]

 # Starting states
 __SCREAMING_SNAKE_CASE       :    Tuple       =	0X67452301
 __SCREAMING_SNAKE_CASE       :    Optional[Any]       =	0Xefcdab89
 __SCREAMING_SNAKE_CASE       :    Optional[int]       =	0X98badcfe
 __SCREAMING_SNAKE_CASE       :    Optional[Any]       =	0X10325476

 __SCREAMING_SNAKE_CASE       :    List[Any]       =	[
     7,
     12,
     17,
     22,
     7,
     12,
     17,
     22,
     7,
     12,
     17,
     22,
     7,
     12,
     17,
     22,
     5,
     9,
     14,
     20,
     5,
     9,
     14,
     20,
     5,
     9,
     14,
     20,
     5,
     9,
     14,
     20,
     4,
     11,
     16,
     23,
     4,
     11,
     16,
     23,
     4,
     11,
     16,
     23,
     4,
     11,
     16,
     23,
     6,
     10,
     15,
     21,
     6,
     10,
     15,
     21,
     6,
     10,
     15,
     21,
     6,
     10,
     15,
     21,
 ]

 # Process bit string in chunks, each with 16 32-char words
 for block_words in get_block_words(__lowerCamelCase     ):
  __SCREAMING_SNAKE_CASE       :    Any       =	aa
  __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	ba
  __SCREAMING_SNAKE_CASE       :    str       =	ca
  __SCREAMING_SNAKE_CASE       :    Dict       =	da

  # Hash current chunk
  for i in range(64     ):
   if i <= 15:
    # f = (b & c) | (not_32(b) & d)     # Alternate definition for f
    __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	d ^ (b & (c ^ d))
    __SCREAMING_SNAKE_CASE       :    Optional[Any]       =	i
   elif i <= 31:
    # f = (d & b) | (not_32(d) & c)     # Alternate definition for f
    __SCREAMING_SNAKE_CASE       :    int       =	c ^ (d & (b ^ c))
    __SCREAMING_SNAKE_CASE       :    int       =	(5 * i + 1) % 16
   elif i <= 47:
    __SCREAMING_SNAKE_CASE       :    List[str]       =	b ^ c ^ d
    __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	(3 * i + 5) % 16
   else:
    __SCREAMING_SNAKE_CASE       :    Any       =	c ^ (b | not_aa(__lowerCamelCase     ))
    __SCREAMING_SNAKE_CASE       :    str       =	(7 * i) % 16
   __SCREAMING_SNAKE_CASE       :    List[str]       =	(f + a + added_consts[i] + block_words[g]) % 2**32
   __SCREAMING_SNAKE_CASE       :    Dict       =	d
   __SCREAMING_SNAKE_CASE       :    str       =	c
   __SCREAMING_SNAKE_CASE       :    Tuple       =	b
   __SCREAMING_SNAKE_CASE       :    Optional[int]       =	sum_aa(__lowerCamelCase		,	left_rotate_aa(__lowerCamelCase		,	shift_amounts[i]     )     )

  # Add hashed chunk to running total
  __SCREAMING_SNAKE_CASE       :    Dict       =	sum_aa(__lowerCamelCase		,	__lowerCamelCase     )
  __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	sum_aa(__lowerCamelCase		,	__lowerCamelCase     )
  __SCREAMING_SNAKE_CASE       :    Union[str, Any]       =	sum_aa(__lowerCamelCase		,	__lowerCamelCase     )
  __SCREAMING_SNAKE_CASE       :    str       =	sum_aa(__lowerCamelCase		,	__lowerCamelCase     )

 __SCREAMING_SNAKE_CASE       :    List[str]       =	reformat_hex(__lowerCamelCase     ) + reformat_hex(__lowerCamelCase     ) + reformat_hex(__lowerCamelCase     ) + reformat_hex(__lowerCamelCase     )
 return digest


if __name__ == "__main__":
      import doctest

      doctest.testmod()






