Find the accessible area of a robot in a 2D graph using BFS algorithm

find_robot_area_bfs.py

#! /usr/bin/env python
# Author: Trinh Nguyen (Jin)
# 12 Dec 2020

from queue import Queue


SAFE_RANGE = 23
AXIS_LEN = 1000


def abs_sum(number):
    """Return the sum of absolute value of all digits

    Parameters:
    number (int): the integer to calculate

    Returns:
    int:Returning value
    """ 

    number = abs(number)
    the_sum = 0
    while number:
        the_sum += number % 10
        number = int(number/10)
    return the_sum


def is_safe(x, y):
    """Check whether the sum digits of abs(x) plus the sum of the
    digits of abs(y) are less than or equal to 23.

    Parameters:
    x (int): the x coordinate
    y (int): the y coordinate

    Returns:
    bool:Returning value
    """

    return bool(abs_sum(x)+abs_sum(y) <= SAFE_RANGE)


def get_safe_area():
    """Calculate the area that the robot can access

    Parameters: N/A

    Returns:
    integer:Returning value
    """

    # visited locations, our map
    my_map = {}
    # last positions
    positions = Queue()
    # possible moves
    steps = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # starting point
    positions.put((0, 0))
    # actual location of the starting point in our map
    my_map[(AXIS_LEN, AXIS_LEN)] = True
    # include the starting point
    area = 1
    while positions.qsize() > 0:
        # get the last location
        last_pos = positions.get()
        for step in steps:
            # new x position
            new_x = last_pos[0] + step[0]
            # new y position
            new_y = last_pos[1] + step[1]

            # actual x in our map
            x = new_x + AXIS_LEN
            # actual y in our map
            y = new_y + AXIS_LEN

            # check if the position is new and safe
            if ((x, y) not in my_map) and is_safe(new_x, new_y):
                # mark the new position as visited
                my_map[(x, y)] = True
                area += 1
                positions.put((new_x, new_y))

    return area


if __name__ == "__main__":
    print("The area that the robot can access is: %d" % get_safe_area())