A few weeks ago I came across this Mars Rover programming challenge/kata which intrigued me and being a bit of a space/robotics buff, I thought I will take a crack at it. These are one of those problems that you might see in a programming competitions like Facebook Hacker Cup or Google Code Jam.

Usually programming competitions judge on algorithmic efficiency and in the more advanced stages require a very solid understanding of mathematics. They are not the ones to judge on clean architecture, domain driven design, TDD or documentation etc, things which are more valuable in the day to day job of a professional developer. So I decided to DDD/TDDify this and build it using the Ports and Adapters architectural style. Let’s see how it went!

Starting with the domain model:

The way I see it, 2 main domain concepts jump out at me straight away:

  • Rover
  • Terrain

Before I get to the Rover itself, I’m going to define the terrain and write some tests for it:

public sealed class Terrain
{
private const int ORIGIN = 0;
public Terrain(int maxX, int maxY)
{
if (maxX < ORIGIN || maxY < ORIGIN)
throw new ArgumentOutOfRangeException(
$"{nameof(maxX)}, {nameof(maxY)}",
$"This terrain can only contain " +
$"positive co-ordinatesm with origin at ({ORIGIN},{ORIGIN})");
MaxX = maxX;
MaxY = maxY;
MinX = ORIGIN;
MinY = ORIGIN;
}
public int MaxX { get; }
public int MaxY { get; }
public int MinX { get; }
public int MinY { get; }
}
view raw Terrain.cs hosted with ❤ by GitHub

According to the brief, the minimum coordinates are 0,0 and the max coordinates can be configured per sequence of commands. This is what the Terrain entity encapsulates. I am assuming that the terrain starts at bottom left (0,0) and ends at top right corner of the screen (maxX, maxY) if you were to look at it top down.

Terrain Layout with Sample Command Sequence & Relative Rover Position

Next is the Rover bit, now the rover needs to know the terrain that it will run on when commanded to do so. For this I can compose Terrain inside the Rover itself i.e. load the map into the rover, this way I can ensure that rover never goes out of the terrain limits. Ok, this would be a spot to write some tests for these expectations.

The rover also needs to know its:

  • Starting position i.e. coordinates
  • Current position i.e. coordinates, and
  • Heading i.e. the direction ‘North (N)’, ‘East (E)’, ‘West (W)’ or ‘South (S)’

These parameters can be initialised and validated in the constructor of the Rover entity:

public sealed class Rover
{
private readonly Terrain terrain;
public Rover(
Terrain terrain,
int startingPositionX,
int startingPositionY,
Direction startingHeading)
{
if (terrain == null)
throw new ArgumentNullException(
nameof(terrain),
"Rover cannot navigate on a non-existent terrain!");
if (IsStartingPositionOutsideTerrain(
terrain,
startingPositionX,
startingPositionY))
throw new ArgumentOutOfRangeException(
$"{nameof(startingPositionX)},{nameof(startingPositionY)}",
"Rover cannot start outside the terrain");
if (!Enum.IsDefined(typeof(Direction), startingHeading))
throw new ArgumentOutOfRangeException(
nameof(startingHeading),
"Starting heading is invalid, must be one of NORTH, EAST, WEST or SOUTH");
this.terrain = terrain;
StartingPositionX = startingPositionX;
StartingPositionY = startingPositionY;
NewPositionX = StartingPositionX;
NewPositionY = StartingPositionY;
StartingHeading = startingHeading;
NewHeading = StartingHeading;
Id = Guid.NewGuid();
}
}
view raw RoverInit.cs hosted with ❤ by GitHub

I also want to make sure that the rover doesn’t start outside the terrain bounds that way I can enforce validity and integrity of the domain model from the start.

As the rover is commanded to change heading, I am going to have to compute the new numeric value for the heading but then map them onto string representations for output/display reason. For this I will create an enum for all four directions and give them ASCII numeric values for N, E, W and S (no particular reason for ASCII, you could use any fixed number scheme and that will be just fine as well):

public enum Direction
{
North = 78,
East = 69,
West = 87,
South = 83
}
view raw Direction.cs hosted with ❤ by GitHub

Other assumptions related to rover movement that I am making are:

  • On the terrain, N-S movement is vertical along the Y-axis and E-W movement is horizontal along the X-axis.
  • Left and Right rotations are always in 90 degrees increments or decrements. For e.g. if the rover is pointing N and asked to turn right, it will end up pointing E. If its pointing S and asked to turn right, it will end up pointing W and so on.
  • Rover only moves 1 unit along either axis at any given time and doesn’t move diagonally.

Based on these assumptions, I will start by implementing the TurnLeft() method on the Rover like so, first:

public CurrentRoverPosition TurnLeft()
{
switch (NewHeading)
{
case Direction.North:
NewHeading = NewHeading + 9;
break;
case Direction.East:
NewHeading = NewHeading + 9;
break;
case Direction.West:
NewHeading = NewHeading - 4;
break;
case Direction.South:
NewHeading = NewHeading - 14;
break;
default:
break;
}
return new CurrentRoverPosition(
Id,
NewPositionX,
NewPositionY,
NewHeading);
}
view raw TurnLeft.cs hosted with ❤ by GitHub

Essentially just adding/subtracting appropriate deltas to/from the current heading value to arrive at the final heading value.

Trivia: I used to build simple rovers as a hobby about 17 years ago, and the way I would start with software/hardware programming for those was by first implementing a TurnLeft method. Because once that works, all other rotations are just evolution of the same basic idea! It also proves your hardware-software interface! Worked then, works now! ๐Ÿ™‚

back then I journalled all of that in my trusty old raggedy diary that I still have to this day.

The Move() method is even simpler because its essentially incrementing and decrementing the current coordinate position to arrive at the new coordinate position. At each position making sure that the rover stays within the terrain bounds.

At the end of each movement, I will return the current position of the rover back to the caller so it can be used for other functions for e.g. to emit the current position to the remote operator so they can do course corrections or send salvage missions to save the rover.

With the core domain model (and tests) out of the way, I now need to find a way orchestrate the rover and give it commands from the outside world. This is where I can bring in Ports and Adapters style, where ports are the interfaces the adapters must implement to get commands or data into and out of the core domain.

The reasons for this architectural style are simple:

  • It allows for decoupling between the domain i.e. the inside and the infrastructure i.e. the outside worlds.
  • It allows for the domain/app to be driven by tests just as well.

In this case, I need the following two ports:

  • IRetrieveRoverCommands: for loading all the commands that the rover needs to execute, from a given source. This source initially will be console based but no reason it couldn’t be a file or a GUI.
    public interface IRetrieveRoverCommands
    {
    Task<IReadOnlyCollection<RoverCommandParameters>> GetAll();
    }
  • ITransmitRoverPosition: for transmitting/publishing rover’s current position after a movement command has been processed. This is basically the output port for the system.
    public interface ITransmitRoverPosition
    {
    Task Transmit(CurrentRoverPosition currentRoverPosition);
    }
Hexagonal Ports and Adapters for the Mars Rover

To orchestrate between the ports and the rover, I will create a use case in my domain model with the following outline:

public sealed class RoverOperationUsecase
{
private readonly IRetrieveRoverCommands roverCommandRetriever;
private readonly ITransmitRoverPosition roverPositionTransmitter;
public RoverOperationUsecase(
IRetrieveRoverCommands roverCommandRetriever,
ITransmitRoverPosition roverPositionTransmitter)
{
this.roverCommandRetriever = roverCommandRetriever;
this.roverPositionTransmitter = roverPositionTransmitter;
}
public async Task StartRoverOperation()
{
// 1. Get all commands from the IRetrieveRoverCommands port
// 2. Loop over all the commands and execute them against the rover one by one
// 3. Publish rover's current position to the output port ITransmitRoverPosition
}
}
view raw Usecase.cs hosted with ❤ by GitHub

I also want to decouple my domain/use case from the finicky complexities of string based command parsing. In order to do this, I am going to create custom domain data structures that will hold the commands and initialisation parameters that one or more rovers will execute. The values for this commands will come in via the IRetrieveRoverCommands port or more accurately, the console based command parsing adapter at runtime.

public readonly struct RoverCommandParameters
{
public RoverCommandParameters(
int terrainMaxX,
int terrainMaxY,
int currentRoverPositionX,
int currentRoverPositionY,
Direction currentRoverHeading,
params RoverCommands[] manouvreCommands)
{
Terrain = new Terrain(terrainMaxX, terrainMaxY);
RoverInitialisationParameters = new RoverInitialisationParameters(
currentRoverPositionX,
currentRoverPositionY,
currentRoverHeading);
ManouvreCommands = manouvreCommands;
}
public Terrain Terrain { get; }
public RoverInitialisationParameters RoverInitialisationParameters { get; }
public RoverCommands[] ManouvreCommands { get; }
}
public enum RoverCommands
{
TurnLeft = 0,
TurnRight = 1,
Move = 2
}
public readonly struct RoverInitialisationParameters
{
public RoverInitialisationParameters(
int currentRoverPositionX,
int currentRoverPositionY,
Direction currentRoverHeading)
{
CurrentRoverPositionX = currentRoverPositionX;
CurrentRoverPositionY = currentRoverPositionY;
CurrentRoverHeading = currentRoverHeading;
}
public int CurrentRoverPositionX { get; }
public int CurrentRoverPositionY { get; }
public Direction CurrentRoverHeading { get; }
}

This way I can also drive my domain use case from tests without having to bother about consoles, files, regular expressions etc. and get faster feedback about whether my domain model works or not. It’s the classical separation between policy and mechanism – the basic tenet of SOLID.

Finally, all I need to do is write the console adapter which will be a bit messy because…regular expressions! But thanks to the clean architecture afforded by ports and adapters style, I can abstract away all that mess in one place and keep my domain well insulated from all that madness! ๐Ÿ™‚ Eventually, I might decide to change my command grammar for e.g. I want “@” to mean move or “&” to mean turn left or “*” to mean turn right or what have you, I can do that by simply writing a new adapter and swapping it in for the existing one. Easy-peasy!

This kind of design also allows me to write focused and isolated tests for my domain behaviour separate from my command parsing adapters separate yet from the integration between the two, at the right granularity and be fairly confident that the system works!

I also find the use case driven approach to be quite useful in building extensible systems for e.g. if I want to support manual commanding of the rover instead of loading up the full sequence upfront, I can create a new use case and separate port interfaces to drive the same rover. Nothing about the rover itself will need to change! Of course, real rovers are built and extended very differently.

That is pretty much it, I am fairly confident this will work but no program is really proven until it runs, so…I am going to hit F5 and type in some sample commands:

Rover doing rovery things…

Seems to work! Ship it!! ๐Ÿ˜

The full code replete with documentation is on Github! Hope NASA recognises the latent rocket engineer in me! ๐Ÿ˜‰ BTW, if you are one of those, “Oh what an overengineered crap, just solve the darn problem and be done with it!”, you will also find a QuickAndDirtyRover project in the Github repo, revel in its gory design and ignore the cleaner implementation! ๐Ÿ‘

Header image source

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Category

Algorithms, architecture, design, best practices, design, domain driven design, refactoring, software architecture, SOLID principles, tdd, Uncategorized

Tags

, , , , , , , , , , , , , ,