This is a spin-off of the famous Mars Rover coding assignment.
The Assignment
After NASA’s New Horizon successfully flew past Pluto, they now plan to land a Pluto Rover to further investigate the surface. You are responsible for developing an API that will allow the Rover to move around the planet. As you won’t get a chance to fix your code once it is on board, you are expected to use test driven development.
To simplify navigation, the planet has been divided up into a grid. The rover's position and location is represented by a combination of x and y coordinates and a letter representing one of the four cardinal compass points. An example position might be 0, 0, N, which means the rover is in the bottom left corner and facing North. Assume that the square directly North from (x, y) is (x, y+1).
In order to control a rover, NASA sends a simple string of letters. The only commands you can give the rover are ‘F’,’B’,’L’ and ‘R’
- Implement commands that move the rover forward/backward (‘F’,’B’). The rover may only move forward/backward by one grid point, and must maintain the same heading.
- Implement commands that turn the rover left/right (‘L’,’R’). These commands make the rover spin 90 degrees left or right respectively, without moving from its current spot.
- Implement wrapping from one edge of the grid to another. (Pluto is a sphere after all)
- Implement obstacle detection before each move to a new square. If a given sequence of commands encounters an obstacle, the rover moves up to the last possible point and reports the obstacle.
Here's an example
- Let's say that the rover is located at 0,0 facing North on a 100x100 grid.
- Given the command "FFRFF" would put the rover at 2,2 facing East.
Tips!
- Don't worry about the structure of the rover. Let the structure evolve as you add more tests.
- Start simple. For instance you might start with a test that if at 0,0,N with command F, the robots position should now be 0,1,N.
- Don’t worry about bounds checking until step 3 (implementing wrapping).
- Don't start up/use the debugger, use your tests to implement the kata. If you find that you run into issues, use your tests to assert on the inner workings of the rover (as opposed to starting the debugger).
My Solution
I started with defining a few things:
- Enum
Commandthat represents each command (forward, backward, left and right) - Enum
Orientationthat represents the four cardinal directions (north, east, south and west) - Class
Positionthat represents the current rover's position in the grid
public enum Command
{
Forward,
Backward,
Left,
Right
}
public enum Orientation
{
North,
South,
East,
West
}
public class Position
{
private readonly int x;
private readonly int y;
private readonly Orientation orientation;
public Position(int x, int y, Orientation orientation)
{
this.x = x;
this.y = y;
this.orientation = orientation;
}
}
Then I define a static class InputParser that knows how to parse a character from the string of input letters eg. "FFRFF" into a Command. For simplicity, I won't show the code here, it's just a bunch of switch case statements.
Next I define a class Pluto which represents the surface/grid where the rover can move around on. I also think it makes sense to have this class responsible for holding information of the obstacles.
public class Pluto
{
private readonly int width;
private readonly int length;
private readonly List<Tuple<int, int>> obstacles;
public Pluto(int width, int length)
{
this.width = width;
this.length = length;
obstacles = new List<Tuple<int, int>>();
}
public int Width
{
get { return width; }
}
public int Length
{
get { return length; }
}
public List<Tuple<int, int>> Obstacles
{
get { return obstacles; }
}
public void AddObstacle(Tuple<int, int> obstacle)
{
if (obstacles.Contains(obstacle))
{
obstacles.Remove(obstacle);
}
obstacles.Add(obstacle);
}
}
Finally I define a Rover class that can be initiated as so:
public Rover(int x, int y, Orientation orientation)
{
this.x = x;
this.y = y;
this.orientation = orientation;
}
This class holds a reference to Pluto with the help of a DeployTo function:
public void DeployTo(Pluto pluto)
{
this.pluto = pluto;
}and implements each single move logic as so:
- Determine the candidate new position
- Ask Pluto for positions of the obstacles
- If there is an obstacle on this
candidateXandcandidateYposition, the Rover just stays on its currentxandyposition, although it still can change its orientation. If there is no obstacle,candidateXandcandidateYis the new position. - If
candidateXorcandidateYposition exceedsPluto's width and length, adjustcandidateXandcandidateYaccordingly by deducting the width and length.
int candidateX = x;
int candidateY = y;
switch (command)
{
case Command.Forward:
if (orientation == Orientation.North) candidateY = candidateY + 1;
else if (orientation == Orientation.South) candidateY = candidateY - 1;
else if (orientation == Orientation.East) candidateX = candidateX + 1;
else candidateX = candidateX - 1;
break;
case Command.Backward:
if (orientation == Orientation.North) candidateY = candidateY - 1;
else if (orientation == Orientation.South) candidateY = candidateY + 1;
else if (orientation == Orientation.East) candidateX = candidateX - 1;
else candidateX = candidateX + 1;
break;
case Command.Left:
if (orientation == Orientation.North) orientation = Orientation.West;
else if (orientation == Orientation.South) orientation = Orientation.East;
else if (orientation == Orientation.East) orientation = Orientation.North;
else orientation = Orientation.South;
break;
case Command.Right:
if (orientation == Orientation.North) orientation = Orientation.East;
else if (orientation == Orientation.South) orientation = Orientation.West;
else if (orientation == Orientation.East) orientation = Orientation.South;
else orientation = Orientation.North;
break;
default:
throw new Exception($"Command '{command}' is not valid.");
}Things to Improve
If I have more time, here are a few things I want to improve:
- Replace
Tuple<int,int>withCoordinateclass - Replace
Rover(int x, int y, ...)with thisCoordinateclass if elsestatements inMove()strikes me as a bit of a code smell (see below my thoughts of how to possibly improve this)Move()function is too long, there's code smell here. Moving logic is tangled with obstacles detection logic. They need to be separated. Think of a change of requirement for example if the Rover is deployed to a planet that's not a wrapped grid, but a torus or an infinite grid.- Abstract out
Plutoto guard for change of requirement as mentioned before. Maybe call itIPlanet?
My thoughts to improve Command Left and Right
We could use some mathematical tricks like assigning integer number to the Orientation enum. Pick an orientation, assign integer value 1 then go clockwise and assign the next integer value, so something like: East = 1, South = 2, West = 3, North = 4.
Apply the following for Left:
if (current orientation - 1) < 1, then get the previous orientation as if the enum is a circle else (current orientation - 1)
Example:
- current orientation: N ==> (4 - 1) = 3 (West)
- current orientation: S ==> (2 - 1) = 1 (East)
- current orientation: E ==> (1 - 1) = 0 (the previous orientation is North)
- current orientation: W ==> (3 - 1) = 2 (South)
Apply similar trick to Right, it is the opposite of Left after all:
if (current orientation + 1) > 4, then get the next orientation as if the enum is a circle else (current orientation + 1)
Example:
- current orientation: N ==> (4 + 1) = 5 (the next orientation is East)
- current orientation: S ==> (2 + 1) = 3 (West)
- current orientation: E ==> (1 + 1) = 2 (South)
- current orientation: W ==> (3 + 1) = 4 (North)
This trick would reduce the 8 if else statements to 2 functions.
Note however that I haven't thought about whether the two above pseudocodes would work for different enumeration value ie. if you start with North = 1 for example.
For Command Forward and Backward, we can see the following pattern:
- Forward North = Backward South
- Foward South = Backward North
- Forward East = Backward West
- Forward West = Backward East
So perhaps we can reduce some of the if else statements based on these facts.
