Skip to content

Instantly share code, notes, and snippets.

@dangtrinhnt
Created December 26, 2020 11:36
Show Gist options
  • Save dangtrinhnt/c91250834acd7dbd23ecc448239d8bc6 to your computer and use it in GitHub Desktop.
Save dangtrinhnt/c91250834acd7dbd23ecc448239d8bc6 to your computer and use it in GitHub Desktop.
Find the accessible area of a robot in a 2D graph using BFS algorithm
#! /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())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment