





'''simple docstring'''






from __future__ import annotations

A__				:   List[str]      =list[tuple[int, int]]

A__				:   Optional[int]      =[
    [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__				:   int      =([-1, 0], [0, -1], [1, 0], [0, 1])  # up, left, down, right




class  UpperCAmelCase     :




      def __init__(			self			: Optional[int]			,			__snake_case			: int			,			__snake_case			: int			,			__snake_case			: int			,			__snake_case			: int			,			__snake_case			: float			,			__snake_case			: Node | None			,			)				->      Dict:
            _lowerCAmelCase							     =							pos_x
            _lowerCAmelCase							     =							pos_y
            _lowerCAmelCase							     =							(pos_y, pos_x)
            _lowerCAmelCase							     =							goal_x
            _lowerCAmelCase							     =							goal_y
            _lowerCAmelCase							     =							g_cost
            _lowerCAmelCase							     =							parent
            _lowerCAmelCase							     =							self.calculate_heuristic()




      def 				lowercase__    (			self			: str  )				->      float:
            _lowerCAmelCase							     =							abs(self.pos_x - self.goal_x  )
            _lowerCAmelCase							     =							abs(self.pos_y - self.goal_y  )
            return dx + dy




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




class  UpperCAmelCase     :




      def __init__(			self			: Optional[int]			,			__snake_case			: tuple[int, int]			,			__snake_case			: tuple[int, int]  )				->      str:
            _lowerCAmelCase							     =							Node(start[1]			,			start[0]			,			goal[1]			,			goal[0]			,			0			,			__snake_case  )
            _lowerCAmelCase							     =							Node(goal[1]			,			goal[0]			,			goal[1]			,			goal[0]			,			9_99_99			,			__snake_case  )

            _lowerCAmelCase							     =							[self.start]
            _lowerCAmelCase							     =							[]

            _lowerCAmelCase							     =							False




      def 				lowercase__    (			self			: Optional[Any]  )				->      Path | None:
            while self.open_nodes:
                  # Open Nodes are sorted using __lt__
                  self.open_nodes.sort()
                  _lowerCAmelCase							     =							self.open_nodes.pop(0  )

                  if current_node.pos == self.target.pos:
                        _lowerCAmelCase							     =							True
                        return self.retrace_path(__snake_case  )

                  self.closed_nodes.append(__snake_case  )
                  _lowerCAmelCase							     =							self.get_successors(__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(__snake_case  )
                        else:
                              # retrieve the best current path
                              _lowerCAmelCase							     =							self.open_nodes.pop(self.open_nodes.index(__snake_case  )  )

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

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




      def 				lowercase__    (			self			: Optional[int]			,			__snake_case			: Node  )				->      list[Node]:
            _lowerCAmelCase							     =							[]
            for action in delta:
                  _lowerCAmelCase							     =							parent.pos_x + action[1]
                  _lowerCAmelCase							     =							parent.pos_y + action[0]

                  if not (0 <= pos_x <= len(grid[0]  ) - 1 and 0 <= pos_y <= len(__snake_case  ) - 1):
                        continue

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

                  successors.append(
                      Node(
                          __snake_case			,			__snake_case			,			self.target.pos_y			,			self.target.pos_x			,			parent.g_cost + 1			,			__snake_case			,			)  )
            return successors




      def 				lowercase__    (			self			: int			,			__snake_case			: Node | None  )				->      Path:
            _lowerCAmelCase							     =							node
            _lowerCAmelCase							     =							[]
            while current_node is not None:
                  path.append((current_node.pos_y, current_node.pos_x)  )
                  _lowerCAmelCase							     =							current_node.parent
            path.reverse()
            return path


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

      print('''------''')

      A__				:   Union[str, Any]      =GreedyBestFirst(init, goal)
      A__				:   Optional[Any]      =greedy_bf.search()
      if path:
            for pos_x, pos_y in path:
                  A__				:   List[Any]      =2

            for elem in grid:
                  print(elem)











A__								=						[4, 1, 7, 4, 2, 6, 4, 1, 5, 3, 7, 5]
A__								=						[3, 7, 7, 4, 2, 6, 4, 1, 5, 3, 7, 5]
A__								=						{
    0: '''Sunday''',
    1: '''Monday''',
    2: '''Tuesday''',
    3: '''Wednesday''',
    4: '''Thursday''',
    5: '''Friday''',
    6: '''Saturday''',
}



def 			_lowerCAmelCase       (					__lowerCAmelCase  ,  __lowerCAmelCase  ,  __lowerCAmelCase      )   ->					str:


				"""simple docstring"""

				assert len(str(__lowerCAmelCase      )      ) > 2, "year should be in YYYY format"
				assert 1 <= month <= 12, "month should be between 1 to 12"
				assert 1 <= day <= 31, "day should be between 1 to 31"

				# Doomsday algorithm:
				snake_case__	:      Optional[int]     		=	year // 100
				snake_case__	:      List[str]     		=	(5 * (century % 4) + 2) % 7
				snake_case__	:      Dict     		=	year % 100
				snake_case__	:      Union[str, Any]     		=	centurian % 12
				snake_case__	:      List[Any]     		=	(
				    (centurian // 12) + centurian_m + (centurian_m // 4) + century_anchor
				) % 7
				snake_case__	:      List[str]     		=	(
				    DOOMSDAY_NOT_LEAP[month - 1]
				    if (year % 4 != 0) or (centurian == 0 and (year % 400) == 0)
				    else DOOMSDAY_LEAP[month - 1]
				)
				snake_case__	:      List[str]     		=	(dooms_day + day - day_anchor) % 7
				return WEEK_DAY_NAMES[week_day]


if __name__ == "__main__":
				import doctest

				doctest.testmod()

