Finding the Maximum Accessible Area on a 2D Grid
Using a Programmatic Representation of Graphs
I came across this question on StackOverflow listed under Dynamic Programming, but there didn’t seem to be an accepted solution with an explanation — so I figured I’d give it a shot and document the solution along-with my thought process.
Enjoy!
The Problem
There is a character who can move around on a two-dimensional (x,y) coordinate grid. The character is placed at point (0,0).
From (x, y) the character can move to (x+1, y), (x-1, y), (x, y+1), and (x, y-1).
Some points are dangerous and contain land mines. To know which points are safe, we check whether the sum of the digits of abs(x) plus the sum of the digits of abs(y) are less than or equal to 23.
For example, the point (64, -59) is not safe because 6 + 4 + 5 + 9 = 24, which is greater than 23. The point (105, -17) is safe because 1 + 0 + 5 + 1 + 7 = 14, which is less than 23.
How large is the area that the character can access?
The Solution
You need to output the count of points in the graph that the character can move to safely — there has to be a linear progression in the movement, you cannot simply count the number of coordinates in the graph where the sum of its values is less than 24.
Before we code this solution, it’s important to understand the coordinate system in the real world vs its programmatic representation.
The Coordinate System
To start off you first need to remember that an Array cannot have negative indices, therefore in order to create a graph that has both negative and positive coordinates you need to have an array twice as long as the 0..n length of an axis. For example, if you need the x-axis to range from -100..100 you will need an array of length AXIS_LENGTH * 2 to accommodate these coordinates where AXIS_LENGTH = 100.
Since a graph is technically a data structure represented using rows and columns, we can easily represent it using a 2D array.
Important Note: When representing a graph using a 2D array the y-axis will become inverted (i.e. the positives of the values of the y-axis will be below the origin point) because in the real-world the y-axis is represented bottom-up whereas in an array we cannot maintain inverted indices.
We consider the origin point of a real-world graph to be at (0,0) — however, if we attempt to use these same coordinates to map the origin point in our 2D array, you’ll see that graph[0][0] will map to the upper-left most element, and not the element at the centre of the grid. The actual origin of the graph would be the coordinate at the centre of the grid.
In order to get the middle element of both rows and columns, we would need to divide the actual length of an axis by 2, which would mean that the origin point would be at (row.length/2, col.length/2) — however, we know that both the rows and columns were set to AXIS_LENGTH * 2, therefore, the origin should be at (AXIS_LENGTH, AXIS_LENGTH) which would translate to (5,5).
We can use this same logic to translate a coordinate on a real-world graph into our grid by adding the AXIS_LENGTH to its x and y values.
e.x. If you were to fetch the location of coordinate (3,4) in a graph where AXIS_LENGTH = 5 you would need to add the AXIS_LENGTH to each coordinate point to identify this position on our 2D grid, therefore you would find your actual coordinate at (3 + AXIS_LENGTH, 4 + AXIS_LENGTH) which would be (8,9). As you can see below, the coordinates of point β read (3,4) when you consider its location along the x and y axes, but its actual position in our 2D array is at graph[8][9].
Pseudocode
Now that we’ve established the coordinate system in our grid, we can explore the practical aspects of our solution.
1 - First, you will need to create your data structures.
- A 2D
Booleangrid is the primary data structure and will be used to maintain a record of where the character visited — so as to avoid duplicates. - An
ArrayDequeis used as aStack(I know its a double-ended queue, but for the sake of simplicity I’m going to call it aStack) to maintain a record of the last visited locations of the character. This will be the main driver of the iterative loop. - An
ArrayListis used to maintain the list of possible directions that a character can move in at any given coordinate.
2 - Before we start the iterative loop, we need to establish the origin point of the character. For this purpose, we will push the point of origin to the Stack and set the origin point in the grid to true.
3 - We can now start iterating the Stack to fetch the last known positions of the character in order to move it in the directions specified by the ArrayList.
4 - As and when you find a new safe coordinate to move to, increment the counter, mark it as visited and push this location to the Stack so that we can continue the iteration.
Once the character has moved to every possible coordinate in our grid there will no longer be any last known locations in the Stack (since we pop them before we compute new positions), which brings us to the end of our iterative loop.
Your area variable will now contain a count of all the safe locations in the grid.
A Java-based solution that I coded can be found below.
Final Thoughts
For some reason as long as the threshold value is constant and the length of the axes is above 1,000 the final count is always 592,597 — so there might be a mathematical concept to help solve this with an O(n) complexity without over-engineering it as I did.
