Understanding State Pattern
I came across an interesting problem and would like to share implementation in a way that seemed appropriate to me. The problem as it was listed:
A squad of robotic rovers are 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 and location is represented by a combination of x and y co-ordinates 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 and 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' makes 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).
INPUT:
The first line of input is the upper-right coordinates of the plateau, the lower-left coordinates are assumed to be 0,0.
The rest of the input is information pertaining to the rovers that have been deployed. Each rover has two lines of input. The first line gives the rover's position, and the second line is a series of instructions telling the rover how to explore the plateau.
The position is made up of two integers and a letter separated by spaces, corresponding to the x and y co-ordinates and the rover's orientation.
Each rover will be finished sequentially, which means that the second rover won't start to move until the first one has finished moving.
OUTPUT
The output for each rover should be its final co-ordinates and heading.
INPUT AND OUTPUT
Test Input:
5 5
1 2 N
LM LM LM LM M
3 3 E
MMR MMR M RRM
Expected Output:
1 3 N
5 1 E
It feels like a typical state management problem, so I decided to go with the State design pattern. Rather than handling all the complexity of direction and position, a state would encapsulate that knowledge and determine what are the sequences of actions based on that given state (i.e. state machine logic).
The base abstract class for any state was supposed to capture anything that is common for a state:
1: public abstract class MovingDirection
2: {
3: protected Rover rover;
4:
5: protected MovingDirection(Rover rover)
6: {
7: this.rover = rover;
8: }
9:
10: public abstract void TurnRight();
11: public abstract void TurnLeft();
12: public abstract void Move();
13: }
I decided to pass in Rover into the constructor to force any concrete state class to have it. Reason - rover is the one that has the knowledge where it's located on the plateau and is the one that should be updating it when the state is changing. One of the 4 possible moving directions looks very similar to the rest of them and coded as such:
1: public class MovingNorth : MovingDirection
2: {
3: public MovingNorth(Rover rover) : base(rover){}
4:
5: public override void TurnRight()
6: {
7: rover.SetDirectionTo(new MovingEast(rover));
8: }
9:
10: public override void TurnLeft()
11: {
12: rover.SetDirectionTo(new MovingWest(rover));
13: }
14:
15: public override void Move()
16: {
17: var oldPosition = rover.Position;
18: rover.SetPositionTo(oldPosition.X, oldPosition.Y + 1);
19: }
20:
21: public override string ToString()
22: {
23: return "N";
24: }
25: }
As you can see, Position is an immutable object. This pattern simplifies work with object and managing its' state becomes simple - to mutate it you have to generate a new one. TurnLeft and TurnRight state changes are simply causing rover to update its' state to the right object state. Here I could use some factory and eliminate the need in new keyword, to make it more abstract, but that's not required for just an exercise.
Now comes the Rover turn.
1: public Rover(int x, int y, string cardinalCompasLetter, IPlateau plateau, IDirectionFactory directionFactory)
2: {
3: Plateau = plateau;
4: Position = SetPositionTo(x, y);
5: Direction = directionFactory.SetDirectionFor(this,
cardinalCompasLetter);
6: }
7:
8: public IPlateau Plateau { get; private set; }
9:
10: public MovingDirection Direction { get; private set; }
11:
12: public Position Position { get; private set; }
13:
14: public MovingDirection SetDirectionTo(
MovingDirection newDirection)
15: {
16: Direction = newDirection;
17: return Direction;
18: }
19:
20: public Position SetPositionTo(int x, int y)
21: {
22: Position = Plateau.GetPosotionFor(x, y);
23: return Position;
24: }
25:
26: public string Report()
27: {
28: return string.Format("{0} {1}", Position, Direction);
29: }
30:
31: public Rover Execute(string commands)
32: {
33: foreach (var command in commands)
34: {
35: switch (command)
36: {
37: case 'R':
38: Direction.TurnRight();
39: break;
40: case 'L':
41: Direction.TurnLeft();
42: break;
43: case 'M':
44: Direction.Move();
45: break;
46: }
47: }
48: return this;
49: }
Now it is the time to enjoy the benefit of the state pattern. The logic of what's next based on the current state and given action is encapsulated in self organized sub objects. Execute receives a command and delegates it to the current Direction (aka State in this case), which is by default set by IDirectionFactory injected object (finally a factory that is responsible for creation of an object and not a hard coded concrete type instantiated with a "new" keyword).
Note: personally this switch does not make me happy, because it smells. But i decided to keep it simple and leave as is.
The decision to convert X and Y coordinates into Position using Plateau object was not random. I wanted to have some error checking for cases like Rover is going out of Plateau. But who should be responsible for checking that? Not the Rover, it just follows the orders. Not the direction, it just stores the position. The design decision felt on Plateau:
1: public class Plateau : IPlateau
2: {
3: public Plateau(int width, int height)
4: {
5: Width = width;
6: Height = height;
7: }
8:
9: public int Width { get; private set; }
10: public int Height { get; private set; }
11:
12: public Position GetPosotionFor(int x, int y)
13: {
14: if (DoesNotContainCooridnates(x, y))
15: {
16: throw new InvalidOperationException(
string.Format("Coordinates do not belong to plateau ({0}, {1})", x, y));
17: }
18: return new Position(x, y);
19: }
20:
21: private bool DoesNotContainCooridnates(int x, int y)
22: {
23: return !(IsCoordinateXOnPlateau(x) && IsCoordinateYOnPlateau(y));
24: }
25:
26: private bool IsCoordinateYOnPlateau(int y)
27: {
28: return y >= 0 && y <= Height;
29: }
30:
31: private bool IsCoordinateXOnPlateau(int x)
32: {
33: return x >= 0 && x <= Width;
34: }
35: }
This way I felt good about it, Plateau object knows it's dimensions, so it should react when someone wants a position outside of its' dimensions by raising an exception.
To finalize it:
State design pattern helps localize state-specific behaviour to classes that implement concrete states, which promotes reuse and extensibility. This removes the need for conditional statements that would otherwise be scattered throughout the code, making life difficult for maintenance programmers, who vastly outnumber implementers in the real world.