Use BFS algorithm to find the accessible area of a robot in a 2D graph

Recently, I found myself started to love working with algorithms. The funny thing is I was never interested in algorithms back in my university time. Maybe because I'm more attracted to something that has a visual appearance or has real-life applications, something like Physics I thought. After more than 10 years working in the field of cloud computing, networks, and computer system, I realized everything are operating by algorithms. Algorithms to optimize network configurations, algorithms to make the application process faster, algorithms to auto-scale the clusters, etc. It may be a little bit too late but right now I can tell algorithms are beautiful.

I tried some HackerRank coding challenges and the problem below caught my eye because it's used in pathfinder, searching, etc. They can be very useful for a cloud architect like myself when optimizing network configurations or building some automation apps.

The Problem:

There is a robot that can move around on a grid. The robot is placed at point (0,0). From (x, y) the robot can move to (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Some points are dangerous and contain EMP Mines. To know which points are safe, we check whether the sum digits of abs(x) plus the sum of the digits of abs(y) are less than or equal to 23. For example, the point (59, 75) is not safe because 5 + 9 + 7 + 5 = 26, which is greater than 23. The point (-51, -7) is safe because 5 + 1 + 7 = 13, which is less than 23.

How large is the area that the robot can access?

The Answer:

We can easily translate the problem into searching for the vertices and edges of a 2D-graph where the points are the 2-coordinate vertices and edges are the connections of points. So here we can tell the area in which the robot can move is the total number of edges. In that case, we can use one of the search algorithms such as depth-first search (DFS), breadth-first search (BFS), etc. to solve it. I chose BFS because it’s quite intuitive to me. For implementing the BFS algorithm, I tried with list data structure at first but it took a huge amount of time to process so I switched to use dictionary data structure and my code speed improved significantly.

First, let review a little bit about BFS:

Basically, "Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. It uses the opposite strategy of depth-first search, which instead explores the node branch as far as possible before being forced to backtrack and expand other nodes."

Source: Wikipedia

Source: guru99.com

Next, let's go through the steps and assumptions. In order to solve the problem, the source code must do these things:

A. Calculate the absolute sum of any given number. This can be easily accomplished using the modular operation to extract each digit out of a number. For example, to calculate the absolute sum of 23, we have a pseudo-code below:

- First digit = 23 % 10 = 3

- Second digit = Integer (23/10) = 2

- Absolute sum = absolute(3) + absolute(2) = 5

B. Check if the absolute sum of each point (x, y) is less than or equal to 23. For example, check if (4, 16) is safe:

- Absolute sum of 4 = 4

- Absolute sum of 16 = 7

- Is (4, 16) safe? 4 + 7 = 11 < 23 => safe

C. Use BFS to traverse the area starting from point (0, 0) and collect the points that do not violate (B). We have a couple of observation here:

1. To represent the possible locations (our map) in a 2D graph using code we could use a 2D array (in Python it can be illustrated by lists in a list data structure) but I figured that because we don’t care about the order of the points, we can actually use a dictionary to represent the area and because the average time complexity of dictionary which is O(1) will give us a performance advantage over a list which is O(N) when searching or loop through the object. (https://wiki.python.org/moin/TimeComplexity)

2. Unlike the 2 axises graph (x, y) as we always know, the data structure representation of the graph (array, or list) cannot have negative indices. Therefore, we need to have an array/list that has the length is as twice the length of an axis. For example, if you want to have the x-axis (-1000, …, 0, …, +1000) (AXIS_LEN=1000), your array/list length must be 1000 * 2 = 2000

3. Because of the same reason of (b), the point (x, y) is represented in our array/list as (x+AXIS_LEN, y+AXIS_LEN). For example, (0, 0) in our array/list with AXIS_LEN=1000 is represented as (0+1000, 0+1000)

4. We can also easily draw the square boundaries of the search area is at: (0,999), (0, -999), (999, 0), (-999, 0) because their absolute sum is 9 + 9+ 9 = 24 > 23. Therefore, we can narrow down the possible axis length for the search to 1000. So, the full length of X = Y axises = 1000 * 2 = 2000. This could reduce our search time significantly.

D. Pseudo-code

1. Firstly, we need to create data structures:

a. A dictionary to store our visited locations or our map, my_map. We store the actual positions of the points in the array/list here. For example my_map{(1000, 1000)} to store (0, 0)

b. A queue to keep the last positions, positions. We store the original position of the points (XY axis style) here. For example, position((0,0))

c. An array of possible moves, steps = [(-1, 0), (1, 0), (0, -1), (0, 1)]. When moving the robot, we use the original positions. For example, moving the robot from (0, 0) to the right 1 unit => (0+1, 0)

2. Our robot will start at point (0, 0) so we store it in the positions queue and set it as True to mark it as visited in our my_map. We also initialize our area which is our final result with 1 value to include the starting point. 

3. Now we can start scanning the positions queue to store the last known positions of the robot to move it in the directions which were specified in the steps.

4. For each new point the robot visits we check if it is a safe one, increase the area counter, set it as visited, and add the new position to the queue. Then we can move on with the scanning.

When our last now positions queue is empty or size 0, our robot has moved to every possible position in our map, we can end the iteration

The final value of our area counter is the area that our robot can access: 592597

E. Python implementation

Enjoy!