"""simple docstring"""
from __future__ import annotations

lowercase__ 	=     [
    [-1, 0],  # left
    [0, -1],  # down
    [1, 0],  # right
    [0, 1],  # up
]







def 						__a       (     _SCREAMING_SNAKE_CASE		,					_SCREAMING_SNAKE_CASE		,					_SCREAMING_SNAKE_CASE		,					_SCREAMING_SNAKE_CASE		,					_SCREAMING_SNAKE_CASE		,					)     ->tuple[list[list[int]], list[list[int]]]:
  a__:					Optional[int]      							=     [
      [0 for col in range(len(grid[0]       )       )] for row in range(len(_SCREAMING_SNAKE_CASE       )       )
  ]  # the reference grid
  a__:					Any      							=     1
  a__:					Union[str, Any]      							=     [
      [0 for col in range(len(grid[0]       )       )] for row in range(len(_SCREAMING_SNAKE_CASE       )       )
  ]  # the action grid

  a__:					List[str]      							=     init[0]
  a__:					List[Any]      							=     init[1]
  a__:					Tuple      							=     0
  a__:					Dict      							=     g + heuristic[x][y]  # cost from starting cell to destination cell
  a__:					int      							=     [[f, g, x, y]]

  a__:					str      							=     False  # flag that is set when search is complete
  a__:					List[str]      							=     False  # flag set if we can't find expand

  while not found and not resign:
    if len(_SCREAMING_SNAKE_CASE       ) == 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()
      a__:					Optional[Any]      							=     cell.pop()
      a__:					Dict      							=     next_cell[2]
      a__:					Union[str, Any]      							=     next_cell[3]
      a__:					Tuple      							=     next_cell[1]

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

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


if __name__ == "__main__":
 lowercase__ 	=     [
     [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],
 ]

 lowercase__ 	=     [0, 0]
 # all coordinates are given in format [y,x]
 lowercase__ 	=     [len(grid) - 1, len(grid[0]) - 1]
 lowercase__ 	=     1

 # the cost map which pushes the path closer to the goal
 lowercase__ 	=     [[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])):
   lowercase__ 	=     abs(i - goal[0]) + abs(j - goal[1])
   if grid[i][j] == 1:
    # added extra penalty in the heuristic map
    lowercase__ 	=     99

 lowercase__	, lowercase__ 	=     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])



"""simple docstring"""
def 						__a       (     _SCREAMING_SNAKE_CASE       )     ->bool:
  return credit_card_number.startswith(('34', '35', '37', '4', '5', '6')       )







def 						__a       (     _SCREAMING_SNAKE_CASE       )     ->bool:
  a__:					Any      							=     credit_card_number
  a__:					Tuple      							=     0
  a__:					List[str]      							=     len(_SCREAMING_SNAKE_CASE       ) - 2
  for i in range(_SCREAMING_SNAKE_CASE		,					-1		,					-2       ):
    #  double the value of every second digit
    a__:					Tuple      							=     int(cc_number[i]       )
    digit *= 2
    # If doubling of a number results in a two digit number
    # i.e greater than 9(e.g., 6 × 2 = 12),
    # then add the digits of the product (e.g., 12: 1 + 2 = 3, 15: 1 + 5 = 6),
    # to get a single digit number.
    if digit > 9:
      digit %= 10
      digit += 1
    a__:					Optional[Any]      							=     cc_number[:i] + str(_SCREAMING_SNAKE_CASE       ) + cc_number[i + 1 :]
    total += digit

  # Sum up the remaining digits
  for i in range(len(_SCREAMING_SNAKE_CASE       ) - 1		,					-1		,					-2       ):
    total += int(cc_number[i]       )

  return total % 10 == 0







def 						__a       (     _SCREAMING_SNAKE_CASE       )     ->bool:
  a__:					Optional[int]      							=     F'{credit_card_number} is an invalid credit card number because'
  if not credit_card_number.isdigit():
    print(F'{error_message} it has nonnumerical characters.'       )
    return False

  if not 13 <= len(_SCREAMING_SNAKE_CASE       ) <= 16:
    print(F'{error_message} of its length.'       )
    return False

  if not validate_initial_digits(_SCREAMING_SNAKE_CASE       ):
    print(F'{error_message} of its first two digits.'       )
    return False

  if not luhn_validation(_SCREAMING_SNAKE_CASE       ):
    print(F'{error_message} it fails the Luhn check.'       )
    return False

  print(F'{credit_card_number} is a valid credit card number.'       )
  return True


if __name__ == "__main__":
 import doctest

 doctest.testmod()
 validate_credit_card_number('4111111111111111')
 validate_credit_card_number('32323')


