Recently, I found an interesting programming exercise, which read:
"A robot is located at the bottom-left corner of a 5x5 grid. The robot can move either up, down, left, or right, but can not visit the same spot twice. The robot is trying to reach the top-right corner of the grid."
I thought this would be a useful problem for demonstrating the real value of unit testing and, in particular, TDD. Also, I thought that it would be something for which multithreading might come in handy as the initial solution is unlikely to scale with increased grid dimensions.
As often with a blank slate the question is where to begin. Let's start with the grid. A square grid should be able to calculate the number of squares it offers given the length of one side:
[code:c#]
[TestFixture]
public class TestBoard
{
[Test]
public void Board_Should_Have_One_Square_For_Board_Length_Equals_One()
{
var boardLength = 1;
var expectedSquareCount = Math.Pow(boardLength, 2);
var board = new Board(boardLength);
Assert.AreEqual(expectedSquareCount, board.SquareCount);
}
}
[/code]
This fails to compile as there isn't yet a Board class!
[code:c#]
public class Board
{
// a 3x3 board has Length = 3
private int Length;
public Board(int length)
{
this.Length = length;
}
// number of squares on board
public int SquareCount
{
get
{
return 1;
}
}
}
[/code]
Fantastic! Test passes but I suspect that this won't be correct for grids of all sizes...
[code:c#]
[Test]
public void Board_Should_Have_Four_Squares_For_Board_Length_Equals_Two()
{
var boardLength = 2;
var expectedSquareCount = Math.Pow(boardLength, 2);
var board = new Board(boardLength);
Assert.AreEqual(expectedSquareCount, board.SquareCount);
}
[/code]
It's no tragedy that the test fails as intuition suggested. It's an easy fix, however, to correct that.
[code:c#]
public class Board
{
// a 3x3 board has Length = 3
private int Length;
public Board(int length)
{
this.Length = length;
}
// number of squares on board
public int SquareCount
{
get
{
return (int) Math.Pow(Length, 2);
}
}
}
[/code]
Once again tests pass! So we've demonstrated mastery of numbers to the power of two. Awesome. How about being able to uniquely identify each square on the board? What's the test for that look like?
[code:c#]
[Test]
public void Board_Squares_Should_Have_Unique_LocationIds()
{
var boardLength = 3;
var board = new Board(boardLength);
var locationIds = new Dictionary<();int, int>();
foreach (var square in board.Squares)
{
if (!locationIds.ContainsKey(square))
locationIds[square] = 0;
locationIds[square]++;
}
const int expectedCount = 1;
foreach (var key in locationIds.Keys)
{
Assert.AreEqual(expectedCount, locationIds[key]);
}
}
[/code]
And the code to make this test pass might even look something like this:
[code:c#]
// a simple way to uniquely identify squares on the board
private int GetLocationId(int x, int y)
{
return y * Length + x;
}
// enumerate all the squares on the board yielding a unique id for each
public IEnumerable<int> Squares
{
get
{
for (int x = 0; x < Length; x++)
{
for (int y = 0; y < Length; y++)
{
yield return GetLocationId(x, y);
}
}
}
}
[/code]
Wait! Did I just write some code without a unit test? Indeed. There is no test for GetLocationId. What was I thinking? That seems almost irresponsible. Actually, do I really care how the board numbers its squares? Not in the slightest! Provided each square can be uniquely identified I do not care in the slightest.
Now onto the matter of movement. From each corner of the grid our robot should be able to move in only two directions. And now we do care about the scheme used by the grid to number squares. It looks like we're going to get some unit testing of the square numbering logic here for free. Really, I'd want to write only a single test case and parameterise the values for robot location and to where the robot may move!
[code:c#]
[TestCase(0, 1, 3)] // should be able to move up and move right from bottom left
[TestCase(2, 1, 5)] // should be able to move up and move left from bottom right
[TestCase(6, 3, 7)] // should be able to move down and move right from top left
[TestCase(8, 5, 7)] // should be able to move down and move right from top left
public void Board_Should_Allow_Moves_From_Corner( int fromLocationId,
int firstMoveLocationId,
int secondMoveLocationId )
{
var expectedAvailableMoves = new List()
{
firstMoveLocationId,
secondMoveLocationId
};
var boardLength = 3;
var board = new Board(boardLength);
foreach (var expectedAvailableMove in expectedAvailableMoves)
Assert.Contains(expectedAvailableMove,
board.GetAvailableMovesFromLocation(fromLocationId));
Assert.AreEqual(expectedAvailableMoves.Count,
board.GetAvailableMovesFromLocation(fromLocationId).Count);
}
[/code]
The test for locations to which the robot may move from the centre of the board is sufficiently different to get its own test. The others are literally edge cases.
[code:c#]
[TestCase(4, 1, 3, 5, 7)] // should be able to move in any direction
// from the middle of the board
public void Board_Should_Allow_Moves_From_Centre( int fromLocationId,
int firstMoveLocationId,
int secondMoveLocationId,
int thirdMoveLocationId,
int fourthMoveLocationId )
{
var expectedAvailableMoves = new List() { firstMoveLocationId,
secondMoveLocationId,
thirdMoveLocationId,
fourthMoveLocationId };
var boardLength = 3;
var board = new Board(boardLength);
foreach (var expectedAvailableMove in expectedAvailableMoves)
Assert.Contains(expectedAvailableMove,
board.GetAvailableMovesFromLocation(fromLocationId));
Assert.AreEqual(expectedAvailableMoves.Count,
board.GetAvailableMovesFromLocation(fromLocationId).Count);
}
[/code]
The code that satisfies both sets of tests is remarkably simple:
[code:c#]
// what are the possible locations a piece can move to given current location
internal Stack<int> GetAvailableMovesFromLocation(int locationId) {
var availableMoves = new Stack<int>();
// if able to move left
if (locationId % Length > 0)
availableMoves.Push(locationId - 1);
// if able to move right
if (locationId % Length < Length - 1)
availableMoves.Push(locationId + 1);
// if able to move down
if (locationId >= Length)
availableMoves.Push(locationId - Length);
// if able to move up
if (locationId < Math.Pow(Length,2) - Length)
availableMoves.Push(locationId + Length);
return availableMoves;
}
[/code]
I had no idea I was going to use a stack until I had. I figured that if a stack was good enough for IL instructions and the Virtual Execution System then it would be good enough for our robot. Next, without showing the code here, there were several things to consider with regards to our robot. Let's give the robot a name, let's call it R2.
- R2 needs to know from where to start
- R2 shouldn't still be at the starting location after a single move
- R2 needs to be able have some notion about where he is
- R2 needs to be able to say where he's been
- R2 needs to be able to say where he hasn't been
- R2 needs to be able to say how far he's been
Thankfully, R2 in this case doesn't need an appreciation of what he knows and what he doesn't know. The difficult thing about R2 is that at any square he'd have up to four options about where to go next and we'd need some way to guide him to each of those options without his becoming unsettled. But there was no need to worry about that yet. I figured that being able to clone R2 and have it's clone take the same journey would later allow a solution in which R2 and each clone could go in different directions. The code for that looks like this:
[code:c#]
// allows new robot to take same journey
internal void TakeJourney(LinkedList<int> journey)
{
Start();
foreach (var step in journey)
if(step > StartLocationId)
MoveTo(step);
}
// clone of existing robot with identical journey history
public BoardExplorer Clone()
{
var explorer = new BoardExplorer();
explorer.TakeJourney(Journey);
return explorer;
}
[/code]
And so this passed on for several iterations until I had a grid (Board), a robot (BoardExplorer) and, finally, a BoardExplorerController so that the grid need not know about R2 and R2 could remain blissfully unaware of the board. Another implementation might have seen the BoardExplorerController made part of the robot. The question is whether we bless R2 with the ability to control its own action or not. Perhaps too much responsibility. The tests for our robot are fairly simple too as a result.
I'll include the code for the BoardExplorerController because there's not much to it. Also it's a chance to point out perhaps the only mildly tricky piece to this solution. The Controller is recursive in that it creates instances of itself within the Explore method in order to allow the robot to explore a number of different squares seemingly at the same time. Note that we're using a queue to record the path the robot takes across the grid and that the grid knows where the robot needs to end up!
[code:c#]
public class BoardExplorerController
{
// maintains grid properties
private Board board;
// robot able to move, give current location, records journey
// and indicates whether any given location has been visited
private BoardExplorer explorer;
// record of successful journeys
private ConcurrentQueue<LinkedList(int)> completeJourneys { get; set; }
public BoardExplorerController(Board board, BoardExplorer explorer)
{
this.board = board;
this.explorer = explorer;
}
// lists all available moves for robot given position on grid
public Stack<int> AvailableMoves
{
get
{
return board.GetAvailableMovesFromLocation(explorer.LocationId);
}
}
// lists all available locations robot may move to without
// revisiting any squares given position on grid
public Stack<int> GetUnexploredLocationsAvailableMoves()
{
var allAvailableMoves = AvailableMoves;
var unexploredAvailableMoves = new Stack<int>();
while (allAvailableMoves.Count > 0)
{
var location = allAvailableMoves.Pop();
if (!explorer.HasVisited(location))
unexploredAvailableMoves.Push(location);
}
return unexploredAvailableMoves;
}
// counts unique paths a robot may take from top-left to bottom-right of grid
internal int GetUniquePathsCount()
{
explorer.Start();
completeJourneys = new ConcurrentQueue<LinkedList<int>>();
ExploreAllUnexploredLocations(completeJourneys);
return completeJourneys.Count;
}
// send robot to each unexplored adjacent square to current location
internal void ExploreAllUnexploredLocations(Queue<LinkedList<int>> completeJourneys) *
{
var unexplored = GetUnexploredLocationsAvailableMoves();
if (unexplored.Count == 0)
return;
this.completeJourneys = completeJourneys;
foreach (var location in unexplored)
Explore(location);
}
// create new robot to explore new location
internal void Explore(int location)
{
var newExplorer = explorer.Clone();
var newController = new BoardExplorerController(board, newExplorer);
newExplorer.MoveTo(location);
if (location == board.FinalSquare)
{
this.completeJourneys.Enqueue(newExplorer.Journey);
return;
}
newController.ExploreAllUnexploredLocations(completeJourneys);
}
}
[/code]
I should confess here that it wasn't entirely a smooth journey. The beauty of this approach was accidentally demonstrated in that one method I wrote prior to any tests were written resulted in a bug that I didn't discover until pretty much all the code had been written... and the application should have been working. Here is the original method prior to the test. It should be fairly obvious to see what's wrong here:
[code:c#]
public void TakeJourney(LinkedList journey, LinkedListNode currentLocation)
{
this.Journey = journey;
this.CurrentLocation = currentLocation;
}
[/code]
The test that this method works making use of existing robot material...
[code:c#]
[Test]
public void BoardExplorer_Journey_Should_Not_Be_Affected_By_Clone_Move()
{
const int randomLocation = 8;
var explorer = new BoardExplorer();
var clone = explorer.Clone();
clone.MoveTo(randomLocation);
Assert.Less(explorer.LocationId, clone.LocationId);
Assert.Less(explorer.Journey.Count, clone.Journey.Count);
}
[/code]
And there you have it - a working solution that will tell you how many unique paths there are from one corner of a grid to its opposite corner. However, running this for a 10x10 grid will result in an Out of Memory Exception and that may be the topic of the next entry.
*Compiler error included for the sake of formatting.