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.
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?
Before we code this solution, it’s important to understand the coordinate system of a graph in the real world vs its programmatic representation.
The Coordinate System
To start off you first need to remember that an
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
length of an axis. For example, if you need the x-axis to range from
you will need an array of length
to accommodate these coordinates where
AXIS_LENGTH * 2
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.
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
will point to the upper-left most coordinate at (-5, -5), and not the coordinate at the centre of the grid. The actual origin of the graph in the real-world as well as for our solution should 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 (
) — however, we know that both the rows and columns were set to
, therefore, the origin should be at (
AXIS_LENGTH * 2
) which would translate to
We can use the same logic to translate a coordinate on a real-world graph into our grid by adding the
to its x and y values.
e.x. If you were to fetch the location of coordinate (3, 4) in a graph where
you would need to add the
AXIS_LENGTH = 5
to each coordinate point to identify this position on our 2D grid, therefore you would find your actual coordinate at (3 +
, 4 +
) 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
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.
grid is the primary data structure and will be used to maintain a record of where the character visited — so as to avoid duplicates. An
is used as a
(I know its a double-ended queue, but for the sake of simplicity I’m going to call it a
) to maintain a record of the last visited locations of the character. This will be the main driver of the iterative loop. An
is 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
and set the origin point in the grid to true.
3. We can now start iterating the
to fetch the last known positions of the character in order to move it in the directions specified by the
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
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
(since we pop them before we compute new positions), which brings us to the end of our iterative loop.
variable will now contain a count of all the safe locations in the grid.
For some reason as long as the threshold value is constant and the length of the axes is above 1,000 the final count will always be the same — so there might be a mathematical concept to help solve this with an O(n) complexity without over-engineering it as I did.
You should be able to adapt this to a Dynamic Programming solution by migrating the iterative logic to a recursive method, but I personally find this approach to be both simplistic and readable.