A C# App From Start to Finish – Part 3

Posted on by

Continued

Last time we left our puzzle in a state where we could move around tiles, but we hadn’t implemented the concept of a solution. We’ll change that over the next few commits.

Commit 10 – A Solved Puzzle

We can create a puzzle with a set of tiles, but how does the puzzle know when it’s solved? There are a couple of ways we could go about this that come to mind. We could expect the solution in the constructor as another Object[,] parameter. That would require just as much validation as the parameter we currently have, plus we’d need to validate that the solution contained the exact same tiles that were passed in to describe the initial setup. The other option would be to assume that the puzzle is in a solved state when it’s created – that the initial configuration of tiles is the solution.

The second option looks the most attractive to me as it keeps the API simple. However, it does mean that either consuming code will have to move around the tiles to un-solve it, or we’ll need to supply some sort of ‘shuffle’ method. The shuffle method seems like a good idea, so we’ll press on.

I’ll add a Boolean property to Puzzle named IsSolved. Here are my tests:

  1. [Test, TestCaseSource("GetIsSolvedTestCases")]
  2. public Boolean TestIsSolved(Puzzle puzzle)
  3. {
  4.  return puzzle.IsSolved;
  5. }
  6.  
  7. public IEnumerable<ITestCaseData> GetIsSolvedTestCases()
  8. {
  9.  yield return new TestCaseData(new Puzzle(new Object[,]
  10.  {
  11.   { 1, 2, 3 },
  12.   { 4, 5, 6 },
  13.   { 7, 8, Puzzle.EmptyTile }
  14.  }))
  15.  .Returns(true)
  16.  .SetName("When a puzzle has just been constructed then it is solved");
  17.  
  18.  var messedWithPuzzle = new Puzzle(new Object[,]
  19.  {
  20.   { 1, 2, 3 },
  21.   { 4, 5, 6 },
  22.   { 7, 8, Puzzle.EmptyTile }
  23.  });
  24.  messedWithPuzzle.TryMove(8);
  25.  messedWithPuzzle.TryMove(5);
  26.  
  27.  yield return new TestCaseData(messedWithPuzzle)
  28.  .Returns(false)
  29.  .SetName("A puzzle whose state no longer matches its starting state is not solved");
  30. }

The tests simply state that a puzzle just after creation is solved, and that a puzzle that has had its tiles moved out of place is not solved.

To get the Puzzle class to satisfy the tests, I’ll need to record a copy of the tiles passed into the constructor so I can reference it when checking for a solution. The new constructor looks like this:

  1. private readonly Object[,] solution;
  2.  
  3. private readonly Object[,] tiles;
  4.  
  5. public Puzzle(Object[,] tiles)
  6. {
  7.     if (tiles == null)
  8.     {
  9.         throw new ArgumentNullException("tiles");
  10.     }
  11.     if (tiles.GetLength(0) < 2 || tiles.GetLength(1) < 2)
  12.     {
  13.         throw new ArgumentException("tiles must be an array of at least 2 x 2", "tiles");
  14.     }
  15.     if (tiles.Cast<Object>().Any(tile => tile == null))
  16.     {
  17.         throw new ArgumentException("tiles cannot contain any null tiles", "tiles");
  18.     }
  19.  
  20.     var width = tiles.GetLength(0);
  21.     var height = tiles.GetLength(1);
  22.     var numberOfTiles = width * height;
  23.     var numberOfUniqueTiles = tiles.Cast<Object>().Distinct().Count();
  24.  
  25.     if (numberOfTiles != numberOfUniqueTiles)
  26.     {
  27.         throw new ArgumentException("tiles cannot contain duplicate tiles", "tiles");
  28.     }
  29.     if (tiles.Cast<Object>().Count(tile => tile == EmptyTile) != 1)
  30.     {
  31.         throw new ArgumentException("tiles must contain a single reference to Puzzle.EmptyTile", "tiles");
  32.     }
  33.  
  34.     this.tiles = new Object[width, height];
  35.     this.solution = new Object[width, height];
  36.     Array.Copy(tiles, solution, tiles.Length);
  37.     Array.Copy(tiles, this.tiles, tiles.Length);
  38. }

I use Array.Copy to fill in a brand new array here and store it in the solution member variable. I’ve also decided that I might as well bite the bullet and do the same for the tiles member variable. That should help avoid any unexpected issues if consuming code decides to modify the tiles array after it’s passed to the constructor.

Now I know what the solution is, it should simply be a case of comparing the tiles in both the tiles and solution arrays to check if the puzzle is solved. This is quite a generic requirement, so I decide to create a method in ArrayExtensions named AreEqualTo which takes two 2D arrays.

  1. public static Boolean AreEqualTo<T>(this T[,] array1, T[,] array2)
  2. {
  3.     var query = from x in Enumerable.Range(0, array1.GetLength(0))
  4.                 from y in Enumerable.Range(0, array1.GetLength(1))
  5.                 select array1[x, y].Equals(array2[x, y]);
  6.  
  7.     return query.All(c => c);
  8. }

You’ve gotta love that query comprehension syntax. With that method in place, all I need to do is add the IsSolved property to Puzzle:

  1. public Boolean IsSolved
  2. {
  3.  get { return tiles.AreEqualTo(solution); }
  4. }

I compile and run the tests. All is well, so I commit the changes.

Commit 11 – Random Numbers

Now we know what a solved puzzle is. However, the puzzle is solved as soon as it’s created. That’s not great for consuming code. We could offer an easy way for consumers to ‘un-solve’ the puzzle in the form of a Shuffle method.

The nature of a shuffle involves randomness. We can obtain random numbers from .NET using the Random class. However, if we implemented our Shuffle method using an instance of the Random class it would be difficult to test. If shuffling is truly random, how can we test that the shuffle algorithm has been implemented properly?

The answer would be to treat random number generation as a service. We can represent the service as an interface. Puzzle can use the interface to obtain random numbers for shuffling. In a real application, we can create a Puzzle instance by passing in an implementation of the interface which uses .NET’s random class. In a test, we can mock random number generation so that we get predictable shuffles.

I add an interface and an implementation using .NET’s built in Random class.

  1. public interface IRandomNumberGenerator
  2. {
  3.     Int32 Next(Int32 maxExclusiveValue);
  4. }
  5.  
  6. public class RandomNumberGenerator : IRandomNumberGenerator
  7. {
  8.     private readonly Random random;
  9.  
  10.     public RandomNumberGenerator()
  11.     {
  12.         this.random = new Random();
  13.     }
  14.  
  15.     public Int32 Next(Int32 maxExclusiveValue)
  16.     {
  17.         return random.Next(maxExclusiveValue);
  18.     }
  19. }

I then modify Puzzle to accept an IRandomNumberGenerator in its constructor and store it in a member variable. I update the tests to use a mock IRandomNumberGenerator implemented using the popular mocking library Moq. I add a basic test for RandomNumberGenerator which checks that each random number returned is within the constraints implied by Next’s maxExclusiveValue parameter.

  1. public class RandomNumberGeneratorTestFixture
  2. {
  3.     [Test]
  4.     public void WhenWeCallTheConstructorThenAnInstanceIsCreatedSuccessfully()
  5.     {
  6.         new RandomNumberGenerator();
  7.     }
  8.  
  9.     [Test]
  10.     public void WhenWeCallNextThenANumberIsReturnedWhichIsNonNegativeAndBelowThePassedInMaximum()
  11.     {
  12.         var rng = new RandomNumberGenerator();
  13.         var max = 100;
  14.         var randomNumber = rng.Next(max);
  15.         Assert.Less(randomNumber, max);
  16.         Assert.GreaterOrEqual(randomNumber, 0);
  17.     }
  18. }

A build, run and test confirms that all is OK, so I commit.

Commit 12 – Shuffling

Now we add our Shuffle method to Puzzle. This is where testing gets a little less than ideal. I can control the behaviour of whatever Shuffle’s implementation is by supplying a mocked IRandomNumberGenerator. However, I have to know the implementation details of Shuffle to know how to setup my mocked IRandomNumberGenerator. Therefore I add a Shuffle implementation that I think should work.

  1. public void Shuffle()
  2. {
  3.     var tilesToGo = solution.Cast<Object>().ToList();
  4.  
  5.     for (var x = 0; x < tiles.GetLength(0); x++)
  6.     {
  7.         for (var y = 0; y < tiles.GetLength(1); y++)
  8.         {
  9.             var indexOfTileToUse = randomNumberGenerator.Next(tilesToGo.Count);
  10.             var tileToUse = tilesToGo[indexOfTileToUse];
  11.             tilesToGo.Remove(tileToUse);
  12.             tiles[x, y] = tileToUse;
  13.         }
  14.     }
  15. }

It’s not a fantastically efficient algorithm, but I reckon it’ll work. Looking at this implementation, if the random number generator generates all 0’s then the puzzle won’t be shuffled at all. If it always generates the highest allowed number, then the puzzle’s tiles will be reversed. I write a test that confirms the tile reversal.

  1. [Test]
  2. public void WhenWeShuffleAPuzzleUsingAWorkingRandomNumberGeneratorThenTheTilesGetRearrangedCorrectly()
  3. {
  4.     var validRandomNumberGenerator = GetDefaultRandomNumberGenerator();
  5.     var validTiles = new Object[,]
  6.     {
  7.         { 1, 2, 3 },
  8.         { 4, 5, 6 },
  9.         { 7, 8, Puzzle.EmptyTile }
  10.     };
  11.     var puzzle = new Puzzle(validTiles, validRandomNumberGenerator);
  12.  
  13.     puzzle.Shuffle();
  14.  
  15.     Assert.AreEqual(new Object[][]
  16.     {
  17.         new Object[] { Puzzle.EmptyTile, 8, 7 },
  18.         new Object[] { 6, 5, 4 },
  19.         new Object[] { 3, 2, 1 }
  20.     }, puzzle);
  21. }
  22.  
  23. private static IRandomNumberGenerator GetDefaultRandomNumberGenerator()
  24. {
  25.     var rng = new Mock<IRandomNumberGenerator>();
  26.     rng.Setup(r => r.Next(It.IsAny<Int32>())).Returns<Int32>(m => m – 1);
  27.     return rng.Object;
  28. }

I’m satisfied with that for the time being, so I commit.

Commits 13, 14, 15 and 16 – Consolidation

I feel we’ve nearly finished for now with our tiles library. I have a puzzle that can be created, shuffled, and solved. However, it’s always worth checking your code by eye to see if anything strange pops out. Here’re some potential issues I can see:

  • The extension methods in ArrayExtensions have no parameter checking. This is down to the fact that Puzzle is the only caller of these methods, and it will never call the methods with invalid parameters. However, ArrayExtensions is public, so it could potentially be called from outside its assembly. I wouldn’t say it’s fit for that purpose just yet – there’s plenty of possibility for NullReferenceExceptions, so perhaps making it internal would be better.
  • In Puzzle, is EmptyTile such a great name? What does an ’empty’ tile mean in the real world? Perhaps ‘missing’ tile makes more sense?
  • Puzzle’s constructor is huge! And it’s mostly just parameter checking. In fact, if we threw away the parameter checking, the constructor would be a measly 5 lines of code! However, the validation is necessary to ensure that the puzzle will work correctly. Perhaps the validation logic could be factored out somehow?
  • Puzzle implementing IEnumerable<IEnumerable<Object>>? I’d usually expose an instance of the aforementioned type via a public property, and I’m not sure why I didn’t here, after all, the phrase ‘a Puzzle is tiles’ makes less sense than ‘a Puzzle has tiles’.
  • Puzzle.TryMove will probably throw an unexpected exception if we try to move a tile which is non-null, non-empty, but not in the puzzle. It should really return false.
  • Although I’m fairly sure my Shuffle implementation works, I’m not sure about its fairness and the test I wrote feels like it knows too much about the internals.
  • While we’re on about Shuffle, why can’t Shuffle accept an instance of IRandomNumberGenerator rather than it going into the constructor? Hell, IRandomNumberGenerator only has one method, would a Func<Int32, Int32> be simpler? More easy to understand?
  • The first three lines of AreTilesAdjacent and SwapTiles are exactly the same. Could I refactor to avoid duplication?
  • Would it be worth making Puzzle generic so it worked with a T[,] rather than Object[,]?

I’ve gotta say, I didn’t expect to come up with a list like that for a project only containing four files (three of them not even being a page long). I could run around in circles fixing a lot of this stuff, but the truth is much of it doesn’t really matter, and some points are difficult to argue either for or against. Here’s what I decide to do:

  • Make ArrayExtensions internal to ShyAlex.Tiles. I don’t think I’ll need it elsewhere, and it’s easier than adding tests and parameter validation.
  • Rename Puzzle.EmptyTile to MissingTile.
  • Add a Tiles property which exposes the tiles, rather than exposing them through the IEnumerable interface.
  • Fix TryMove so that it doesn’t throw if we try to move a tile that’s not in the puzzle.

I won’t paste the code changes here as they’re fairly minor. Needless to say, all changes are in the repository. The biggest difference is that for the Tiles property, I moved the code to produce an IEnumerable<IEnumerable<Object>> to ArrayExtensions in order to keep Puzzle clean. In fact, Puzzle’s public interface is pretty easy to understand:

  1. class Puzzle
  2. {
  3.     Boolean IsSolved { get; }
  4.     IEnumerable<IEnumerable<Object>> Tiles { get; }
  5.     void Shuffle();
  6.     Boolean TryMove(Object tile);
  7. }

We basically have a puzzle type through which we can shuffle some tiles, look at the tiles, move them around, and determine if the puzzle is solved. That’s not too far from the things we’d do with a real-life sliding tiles puzzle!

Next time, I’ll have a go at putting together a UI.

Share and Enjoy:
  • Print
  • Digg
  • StumbleUpon
  • del.icio.us
  • Facebook
  • Yahoo! Buzz
  • Twitter
  • Google Bookmarks
  • email
  • LinkedIn
  • Technorati

Leave a Reply

Your email address will not be published. Required fields are marked *

 

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