Six ways to land robotic rovers on Mars
Mars Rover problem is a popular problem statement used by companies to check object orientation and test-driven development skills. In this article, we'll take the core problem statement and see how the solution evolves through six different levels. Knowledge of high school level maths and little python helps to follow this article.
The actual Problem Statement:
A squad of robotic rovers is to be landed by NASA on a plateau on Mars.
This plateau, which is curiously rectangular, must be navigated by the rovers so that their on-board cameras can get a complete view of the surrounding terrain to send back to Earth.
A rover's position is represented by a combination of x and y coordinates and a letter representing one of the four cardinal compass points. The plateau is divided up into a grid to simplify navigation. An example position might be 0, 0, N, which means the rover is in the bottom left corner facing North.
In order to control a rover, NASA sends a simple string of letters. The possible letters are 'L', 'R' and 'M'.
'L' and 'R' make the rover spin 90 degrees left or right respectively, without moving from its current spot. 'M' means move forward one grid point, and maintain the same heading.
Assume that the square directly North from (x, y) is (x, y+ 1).
Test Input:
3 3 E
MMRMMRMRRM
Expected Output:
5 1 E
The essence of the Problem Statement:
- A rover is located in a 2-dimensional space facing a direction and it should change its position and direction based on the instruction it receives.
- The initial rover position, direction, and the instructions are the input and the final rover position and direction are the output.
- The possible directions are 'N', 'E','W' and 'S'.
- The possible instructions are 'L','R' and 'M'
Solution 1: (Naive approach)
Let us start with a naive and mundane solution.
Most of the developers from the enterprise applications development background solve this problem in this way.
The advantage of this approach is that it's explicit in documenting the rules. However, the potential downside is that any change in requirement would require considerable changes to the code.
We can do better by building a solution that is more close to the problem space and this leads to Solution 2.
Solution 2: (Rotation approach)
The rover spins 90 degrees left or right. So, we can replace the 'N', 'E', 'W', and 'S' with 90, 0, 180, and 270 degrees. The left spin is 90 degrees rotation and the right spin is 270 degrees rotation.
This is much better than solution 1, as it gives more flexibility as well as more concise.
Since we intend to rotate, we could do it in a more conventional way and this leads to Solution 3.
Since we intend to rotate, we could do it in a more conventional way and this leads to Solution 3.
Solution 3: (Rotation Matrix approach)
Let the direction be represented as vectors. 'N' as [0,1], 'E' as [1, 0], 'W' as [-1, 0] and 'S' as [0, -1]. Multiply the direction vector by following (counter-clockwise and clockwise) rotation matrix.
This does work, however, it is a very generic solution. A simplification of this approach leads to Solution 4.
Solution 4: (Vector Rotation approach)
Since the degree of rotation is 90, the previous solution rotation matrix can be reduced to a vector. A coordinate (x, y) rotated counter-clockwise 90 degrees around (0,0) is (-y, x) and a clockwise 90 degrees is (y,-x).
If we make the assumption that the rotation is going to be only 90 degrees, then this can be solved in an even more elegant way and this leads to Solution 5.
Solution 5: (Complex Numbers approach)
Instead of vector or matrices, using a complex number will give a much elegant solution to this problem. Simply multiplying the direction vector by i or -i will rotate it counter-clockwise and clockwise directions.
The advantage of this solution is that both the position and direction are represented as the same unit (complex numbers) and they can be operated directly and more naturally. If there is a need to extend the problem to the third dimension, then this leads to Solution 6.
Solution 6: (Quaternions approach)
The complex number solution can be extended to the third dimension without significant change by using Quaternions. Quaternions can be visualized using this website.
Conclusion:
All six solutions are valid and acceptable, but each has its own advantages and disadvantages. The choice of solution depends on what kind of extensibility is needed and the maturity of the team members, in case of the collective code ownership. If there are any comments or additional solutions, please do share it in the comments.
Comments