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."
So far we've come up with a solution but not altogether happy it's fit for future purpose. We're currently optimizing and the title gives away the fact that the next optimisation will be to use a Struct rather than a Class for the BoardExplorer. If we're going to be creating well over hundreds of millions of these robots then ideally we'd like them as lightweight as possible. The key aspects noteworthy parts of our new improved robot are shown below:
[code:c#] public struct BoardExplorer
{
public LinkedList Journey;
public int NextLocation;
public BoardExplorer(int location, int nextLocation, LinkedList journey)
{
this.Journey = journey;
this.NextLocation = nextLocation;
}
internal int GetLocation()
{
return Journey.Last.Value;
}
internal void Move()
{
Journey.AddAfter(Journey.Last, NextLocation);
}
public bool IsExploring
{
get
{
return GetLocation() != Program.Board.EndLocation;
}
}
internal LinkedList CopyJourney()
{
var copy = new LinkedList();
var steps = new int[Journey.Count];
Journey.CopyTo(steps, 0);
return new LinkedList(steps);
}
public BoardExplorer Clone(int location)
{
return new BoardExplorer(GetLocation(), location, CopyJourney());
}
}
[/code]
And the metrics for this change confirm this as being the way to go.
There are 1,262,816 unique paths from the top-left corner to the bottom-right corner of a 6x6 grid!
There were 18,470,410 robots used to discover this!
Total memory: 869,039,780
Time elapsed: 74,598ms
Garbage collection gen0: 4740
Garbage collection gen1: 1627
Garbage collection gen2: 0
The surprise here is the performance improvement. Memory use hasn't been affected much. Things to note here is that because a struct is a value type rather than a reference type these BoardExplorers aren't being stored on the heap so we need to explain why there is increased garbage collection activity!
Though our robots aren't being allocated memory on the heap their journeys do appear there as their of type LinkedList. Significantly, these are more transient and are removed more quickly than the earlier type of robots being stored and none of these robots too remain in memory by the time the calculation has been performed. Whilst this is certainly preferable it doesn't promise being able to use this improved solution for a 10x10 grid.
I think we can do better still and so we consider the next refactoring. We consider that the robot need not end on the queue as their journey is all we really care about so we make the following changes without tests driving these. In a contained system as small as this we have the luxury of being able to hold all the code and dependencies inside our developer's head. Ordinarily this may not be the case at all.
It's been a about a minute. How about some more refactoring? The BoardExplorerController is about to lose further responsibility!
[code:c#] public class BoardExplorerController
{
public static Queue<LinkedList<int>> CompleteJourneys = new Queue<LinkedList<int>>();
internal static IEnumerable GetValidMoves(BoardExplorer explorer)
{
var availableMoves = Program.Board.GetAvailableMovesFromLocation(explorer.GetLocation());
while (availableMoves.Count > 0)
{
var location = availableMoves.Pop();
if (!explorer.HasVisited(location))
yield return location;
}
}
}
[/code]
The BoardExplorer has their Clone method replaced by a Move method which now also performs the action of propelling the robot onto the next square and then checking whether they've reached their destination.
[code:c#] public BoardExplorer Move(int location)
{
var journeyBeyond = CopyJourney();
journeyBeyond.AddLast(location);
var moved = new BoardExplorer(journeyBeyond);
if (!moved.IsExploring)
BoardExplorerController.CompleteJourneys.Enqueue(moved.Journey);
return moved;
}
[/code]
This looks like we've reintroduced recursion but the stack for maintaining robots only ever drops one level deep so there's little concern about additional memory requirement. New metrics will show this we're sure. Also the BoardExplorerCloneFactory needs to spit out BoardExplorers based on journeys found on the stack maintaining journeys in progress.
[code:c#]
class BoardExplorerCloneFactory
{
public static int Count = 0;
private Stack<LinkedList<int>> journeys; // <- changed from Stack
public bool HasClones { get; private set; }
public BoardExplorerCloneFactory(Stack<LinkedList<int>> journeys)
{
this.HasClones = true;
this.journeys = journeys;
}
internal IEnumerable GetExplorers()
{
HasClones = false;
while (journeys.Count > 0)
{
var journey = journeys.Pop();
var explorer = new BoardExplorer(journey); // <- new addition here too!
foreach (var location in BoardExplorerController.GetValidMoves(explorer))
{
HasClones = true;
Count++;
yield return explorer.Move(location);
}
}
}
}
[/code]
I didn't think the additional step of constructing a robot from a saved journey would add much overhead either and it didn't:
There are 1262,816 unique paths from the top-left corner to the bottom-right corner of a 6x6 grid!
There were 184,70,410 robots used to discover this!
Total memory: 870,567,144
Time elapsed: 70,736ms
Garbage collection gen0: 4,694
Garbage collection gen1: 1,610
Garbage collection gen2: 0
The four second performance gain is spectacularly inconsequential. The memory requirement hasn't been dented either. To show that this three minute refactoring didn't need a test-first approach the changes to the main program appear below and this compiled first time without errors/warnings:
[code:c#]
Board = new Board(boardLength);
var newJourney = new LinkedList();
newJourney.AddFirst(Board.StartLocation);
var explorer = new BoardExplorer(newJourney);
var journeys = new Stack<LinkedList<int>>();
var factory = new BoardExplorerCloneFactory(journeys);
var warmTimer = GetStartedStopWatch();
journeys.Push(explorer.Journey);
while (factory.HasClones)
{
var explorersCount = 0;
UpdateInstrumentation();
foreach (var movedExplorer in factory.GetExplorers())
{
if (movedExplorer.IsExploring)
journeys.Push(movedExplorer.Journey);
explorersCount++;
}
}
[/code]
So we've abandoned fixing tests until the very end and we're happy with performance. This is because a contrived example allows it. Also, we know that the 'architecture' is going to keep changing and we don't yet know what it will resemble ultimately so many of the tests we write en-route will i) be thrown away almost immediately; and ii) slow us down. These robots are no Mars Rover!
To recap the series of changes, replacing instances of BoardExplorerControllers with a single static version yielded some gains. Replacing the BoardExplorer Class with a Struct had greater benefit too but it's really the BoardExplorerCloneFactory that's had the greatest impact. Storing journeys instead of robots helped only marginally in terms of performance and next we look at changing the representation stored once more and look outside for help in order to allow the size of the stack to grow without having the amount of memory consumed explode. Eventually, we may even be able to calculate the number of paths for a 10x10 grid.