

'''simple docstring'''
from __future__ import annotations

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


def        _lowerCAmelCase					(						_UpperCamelCase						:     list[list[int]]							, _UpperCamelCase						:     list[int]							, _UpperCamelCase						:     list[int]							, _UpperCamelCase						:     int							, _UpperCamelCase						:     list[list[int]]							, )      ->			tuple[list[list[int]], list[list[int]]]:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE							    =[
         [0 for col in range(len(grid[0]				)				)] for row in range(len(_UpperCamelCase				)				)
     ]  # the reference grid
     _SCREAMING_SNAKE_CASE							    =1
     _SCREAMING_SNAKE_CASE							    =[
         [0 for col in range(len(grid[0]				)				)] for row in range(len(_UpperCamelCase				)				)
     ]  # the action grid

     _SCREAMING_SNAKE_CASE							    =init[0]
     _SCREAMING_SNAKE_CASE							    =init[1]
     _SCREAMING_SNAKE_CASE							    =0
     _SCREAMING_SNAKE_CASE							    =g + heuristic[x][y]  # cost from starting cell to destination cell
     _SCREAMING_SNAKE_CASE							    =[[f, g, x, y]]

     _SCREAMING_SNAKE_CASE							    =False  # flag that is set when search is complete
     _SCREAMING_SNAKE_CASE							    =False  # flag set if we can't find expand

     while not found and not resign:
          if len(_UpperCamelCase				) == 0:
               raise ValueError('Algorithm is unable to find solution'				)
          else:  # to choose the least costliest action so as to move closer to the goal
               cell.sort()
               cell.reverse()
               _SCREAMING_SNAKE_CASE							    =cell.pop()
               _SCREAMING_SNAKE_CASE							    =next_cell[2]
               _SCREAMING_SNAKE_CASE							    =next_cell[3]
               _SCREAMING_SNAKE_CASE							    =next_cell[1]

               if x == goal[0] and y == goal[1]:
                    _SCREAMING_SNAKE_CASE							    =True
               else:
                    for i in range(len(_UpperCamelCase				)				):  # to try out different valid actions
                         _SCREAMING_SNAKE_CASE							    =x + DIRECTIONS[i][0]
                         _SCREAMING_SNAKE_CASE							    =y + DIRECTIONS[i][1]
                         if xa >= 0 and xa < len(_UpperCamelCase				) and ya >= 0 and ya < len(grid[0]				):
                              if closed[xa][ya] == 0 and grid[xa][ya] == 0:
                                   _SCREAMING_SNAKE_CASE							    =g + cost
                                   _SCREAMING_SNAKE_CASE							    =ga + heuristic[xa][ya]
                                   cell.append([fa, ga, xa, ya]				)
                                   _SCREAMING_SNAKE_CASE							    =1
                                   _SCREAMING_SNAKE_CASE							    =i
     _SCREAMING_SNAKE_CASE							    =[]
     _SCREAMING_SNAKE_CASE							    =goal[0]
     _SCREAMING_SNAKE_CASE							    =goal[1]
     invpath.append([x, y]				)  # we get the reverse path from here
     while x != init[0] or y != init[1]:
          _SCREAMING_SNAKE_CASE							    =x - DIRECTIONS[action[x][y]][0]
          _SCREAMING_SNAKE_CASE							    =y - DIRECTIONS[action[x][y]][1]
          _SCREAMING_SNAKE_CASE							    =xa
          _SCREAMING_SNAKE_CASE							    =ya
          invpath.append([x, y]				)

     _SCREAMING_SNAKE_CASE							    =[]
     for i in range(len(_UpperCamelCase				)				):
          path.append(invpath[len(_UpperCamelCase				) - 1 - i]				)
     return path, action


if __name__ == "__main__":
     lowerCamelCase :      Optional[Any]					 =     [
         [0, 1, 0, 0, 0, 0],
         [0, 1, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
         [0, 1, 0, 0, 0, 0],
         [0, 1, 0, 0, 1, 0],
         [0, 0, 0, 0, 1, 0],
     ]

     lowerCamelCase :      Any					 =     [0, 0]
     # all coordinates are given in format [y,x]
     lowerCamelCase :      Union[str, Any]					 =     [len(grid) - 1, len(grid[0]) - 1]
     lowerCamelCase :      List[Any]					 =     1

     # the cost map which pushes the path closer to the goal
     lowerCamelCase :      Any					 =     [[0 for row in range(len(grid[0]))] for col in range(len(grid))]
     for i in range(len(grid)):
          for j in range(len(grid[0])):
               lowerCamelCase :      Optional[Any]					 =     abs(i - goal[0]) + abs(j - goal[1])
               if grid[i][j] == 1:
                    # added extra penalty in the heuristic map
                    lowerCamelCase :      List[Any]					 =     9_9

     lowerCamelCase ,    lowerCamelCase :      str					 =     search(grid, init, goal, cost, heuristic)

     print("ACTION MAP")
     for i in range(len(action)):
          print(action[i])

     for i in range(len(path)):
          print(path[i])







from __future__ import annotations

import math


def        SCREAMING_SNAKE_CASE      (       _UpperCAmelCase )			->     bool:

    if 1 < number < 4:
        # 2 and 3 are primes
        return True
    elif number < 2 or number % 2 == 0 or number % 3 == 0:
        # Negatives, 0, 1, all even numbers, all multiples of 3 are not primes
        return False

    # All primes number are in format of 6k +/- 1
    for i in range(5						,	int(math.sqrt(_UpperCAmelCase ) + 1 )						,	6 ):
        if number % i == 0 or number % (i + 2) == 0:
            return False
    return True


_UpperCAmelCase				:       Any	   =				[num for num in range(3, 10_00_01, 2) if not is_prime(num)]


def        SCREAMING_SNAKE_CASE      (       _UpperCAmelCase )			->     list[int]:
    if not isinstance(_UpperCAmelCase						,	_UpperCAmelCase ):
        raise ValueError('n must be an integer' )
    if n <= 0:
        raise ValueError('n must be >= 0' )

    lowerCamelCase__    :      int					 =		[]
    for num in range(len(_UpperCAmelCase ) ):
        lowerCamelCase__    :      Union[str, Any]					 =		0
        while 2 * i * i <= odd_composites[num]:
            lowerCamelCase__    :      Dict					 =		odd_composites[num] - 2 * i * i
            if is_prime(_UpperCAmelCase ):
                break
            i += 1
        else:
            list_nums.append(odd_composites[num] )
            if len(_UpperCAmelCase ) == n:
                return list_nums

    return []


def        SCREAMING_SNAKE_CASE      (       )			->     int:
    return compute_nums(1 )[0]


if __name__ == "__main__":
    print(F"""{solution() = }""")





