Let’s Talk About TDD

One should be prepared to receive ninety-nine percent of an enemy’s attack and stare death right in the face in order to illumine the Path.” – Morihei Ueshiba

The first white-board question from the horrible interview that I had recently was a question that a great number of computer science students are familiar with. The question was stated as follows:

Devise an algorithm for detecting whether a given string is a palindrome (spelled the same way forwards and backwards). For example, “kayak”

After the interview I decided that I wanted to explore the idea in more depth using TDD as a development tool to ensure that as new code was added none of the previous editions were broken without my knowledge. I decided that since I was using C# and the methods would only affect strings that the IsPalindrome() methods should be extension methods. The entire solution, including the unit tests, can be found in my PalindromeExtension repository on BitBucket.

To begin with, I decided that I would implement IsPalindrome() the classical way. I started with a single static class set up as follows:

namespace PalindromeExtension
{
    public static class PalindromeExtensionMethod
    {
    }
}

The easiest place to start, in my opinion, is the most common case; therefore, my first unit test tested the case where the given string is not a palindrome, and was written as follows:

public class When_using_the_palindrome_extension_method
     {
         [TestMethod]
        public void And_the_given_string_is_not_a_palindrome_then_the_extension_returns_false()
         {
            //arrange
            
            const string notApalindrome = "This is not a palindrome";

            //act

            var observedResult = notApalindrome.IsPalindrome();

            //assert

            Assert.IsFalse(observedResult);
         }
     }

This test is easy enough to get passing and will pass with the following implementation of IsPalindrome():

public static class PalindromeExtensionMethod
     {
        public static bool IsPalindrome(this string value)
        {
            return false;
        }
     }

That implementation may seem like a “cop-out” to those of you not familiar with test driven development, but writing the minimum amount of code to make the test pass is a key concept in test driven development. This does two very important things to the development process. First, and most importantly, it keeps the development cycle on any piece of code short and keeps iterations fast. Second it keeps things that are extra and unnecessary out of the code base, because YAGNI. When it all comes down to it, the method should return false if the given string is not a palindrome. Don’t worry about when the string is a palindrome yet. That is not what this test is testing.

The next unit test should test the minimal positive case. That is to say, my next test case was, “if the string was a palindrome with a length of 2 then the extension should return true”. My test was written like this:

        const string twoLetterPalindrome = "oo";

        [TestMethod]
        public void And_the_given_string_is_a_palindrome_with_2_letters_then_the_extension_returns_true()
        {
            //act

            var observedResult = twoLetterPalindrome.IsPalindrome();

            //assert

            Assert.IsTrue(observedResult);
        }

The next step was to get this test to pass. This iteration is where most of the functionality in all three implementations came about. That can be expected in fairly simple problems like this one. Larger problems, however, grow slower with each unit test, but there is always exponentially more and more implementation per iteration until a certain point is reached in the implementation. The classical solution uses a pair of stacks. The string is pushed onto one stack and, character by character, popped of the first stack and then pushed onto the second stack. The stacks are then check to see if their elements are equivalent and if they are, then the string is a palindrome, otherwise loop until the first stack is empty. Here is the code to get the most recent test passing:

public static class PalindromeExtensionMethod
     {
         public static bool IsPalindrome(this string value)
         {
            var startingStack = StringToStack(value);
            var stackToCompareTo = new Stack<char>();

            while (startingStack.Count > 0)
            {
                stackToCompareTo.Push(startingStack.Pop());

                if (startingStack.ToString() == stackToCompareTo.ToString()) return true;
            }

             return false;
         }

        private static Stack<char>; StringToStack(string theStringToConvert)
        {
            var backwardStringAsArray = theStringToConvert.Reverse().ToArray();
            var stackToReturn = new Stack<char>();

            foreach (var charater in backwardStringAsArray)
            {
                stackToReturn.Push(charater);   
            }

            return stackToReturn;
        }

This gets the code to pass, but surprisingly for the wrong reason. Using the ToString() method on a stack in C# does not change the stack’s elements back into a string, it gives a little bit of information on what type of data structure it is and how many elements it contains. I didn’t think of this and didn’t realize that there was a problem until I wrote the next test, but that is how test driven development works at times. On to the next test which tests the case where the beginning of the palindrome is upper-case and the end is lower-case. Here is the test:

        [TestMethod]
        public void And_the_given_string_is_a_palindrome_with_2_letters_with_one_capital_then_the_extension_returns_true()
        {
            var testString = twoLetterPalindrome.First().ToString(CultureInfo.InvariantCulture).ToUpper() +
                             String.Join("", twoLetterPalindrome.Skip(1));
            //act

            var observedResult = testString.IsPalindrome();

            //assert

            Assert.IsTrue(observedResult);
        }

The LINQ expression is some magic so that I could change my two letter palindrome into a palindrome with the beginning upper-case and the ending lower-case. This unit test passed out of the gate. This befuddled me and after realizing the mistake that I had made earlier, I changed the previous implementation to read as follows:

         public static bool IsPalindrome(this string value)
         {
            var startingStack = StringToStack(value);
            var stackToCompareTo = new Stack<char>();

            while (startingStack.Count > 0)
            {
                stackToCompareTo.Push(startingStack.Pop());
                
                var first = new String(startingStack.ToArray());
                var second = new String(stackToCompareTo.ToArray());
                
                if (first == second) return true;
            }

             return false;
         }

With these changes, my most recent test is now failing for the reason I expected it to fail. Getting this test to pass is as easy as making sure that the input is all lower-case before doing any operations on it:

         public static bool IsPalindrome(this string value)
         {
            var startingStack = StringToStack(value.ToLower());
            var stackToCompareTo = new Stack<char>();

            while (startingStack.Count > 0)
            {
                stackToCompareTo.Push(startingStack.Pop());
                
                var first = new String(startingStack.ToArray());
                var second = new String(stackToCompareTo.ToArray());
                
                if (first == second) return true;
            }

             return false;
         }

The next case to test is when the string is 3 letters long an is a palindrome. Here is the test for that case:

        private const string threeLetterPalindrome = "mom";
        [TestMethod]
        public void And_the_given_string_is_a_palindrome_with_3_letters_then_the_extension_returns_true()
        {
            //act

            var observedResult = threeLetterPalindrome.IsPalindrome();

            //assert

            Assert.IsTrue(observedResult);
        }

To get this test to pass, it is sufficient to pop an extra character off the stack so that the the middle character is not being compared when the comparison is being done. However, doing this breaks all the unit tests for the 2 character palindromes. In order to test for the even cases and still return true when the palindrome is even. here are the changes that I made:

         public static bool IsPalindrome(this string value)
         {
            var startingStack = StringToStack(value.ToLower());
            var stackToCompareTo = new Stack<char>();

            while (startingStack.Count > 0)
            {
                stackToCompareTo.Push(startingStack.Pop());

                var middleCharacter = startingStack.Pop();                

                var first = new String(startingStack.ToArray());
                var second = new String(stackToCompareTo.ToArray());
                
                if (first == second || (middleCharacter + first == second)) return true;
            }

             return false;
         }

All the unit tests are green again and we can move on to the next test. This tests for an even length palindrome of size 4. I thought that this test was going to pass out the gate, but strictly following the principle of only writing enough code to get the tests passing has yielded an anomaly. Here is the test:

        private const string fourLetterPalindrome = "noon";
        [TestMethod]
        public void And_the_given_string_is_a_palindrome_with_4_letters_then_the_extension_returns_true()
        {
            //act

            var observedResult = fourLetterPalindrome.IsPalindrome();

            //assert

            Assert.IsTrue(observedResult);
        }

After a bit of searching, I realized that the reason that this case wasn’t passing, even though the other cases with palindromes of even length were passing, is because I had forgotten to put the middle character back on the beginning stack before proceeding to the next step. To fix this I added the following code right before the closing bracket for the loop:

     startingStack.Push(middleCharacter);

Expecting this to work, I ran all the tests, but the last test was still failing because an InvalidOperationException was being thrown. This was because there was a point at which I was trying to pop the starting stack and there was nothing to pop. To fix this I changed the test in the loop to read as follows:

     while (startingStack.Count > 1)

This completed the functionality of the classical approach to deciding if a string is a palindrome and all the unit tests passed. Before I go on to talk about the other two implementations I got out of this exercise, I want to talk a little about my testing setup. I use the Visual Studio Unit Testing Framework for my testing framework. This is mainly because I get it for free with Visual Studio and it is what I am familiar with. For my mocking framework I use RhinoMocks using Arange-Act-Assert style test writing instead of Record-Replay. In my opinion, Record-Replay unit testing is better suited for larger more complex objects and it is also a more difficult concept to teach in a text based forum.

With the more classical general solution completed, I began to think of ways to implement IsPalindrome() using some of the nice libraries that are provided by the .NET framework. LINQ came to mind and after writing a few unit tests that looked similar to the ones written above, I came up with this implementation:

public static bool LinqOnlyIsPalindrome(this string value)
        {
            return value.IsEvenLength() ? value.ToLower().Substring(0, (value.Count()/2)) == new string(value.ToLower().Substring((value.Count()/2)).Reverse().ToArray())
                : value.ToLower().Substring(0, (value.Count()/2)) == new string(value.ToLower().Substring((value.Count()/2) + 1).Reverse().ToArray());
        }

private static bool IsEvenLength(this string value)
        {
            return ((value.Count() & 1)==0);
        }

This is an impressively ugly solution to the problem, but it works and all unit tests pass. After some time it dawned on me that this is ugly because I had become hampered by the notion that the string needed to be split in half and the two halves to be check for equality. Splitting the word in half is not necessary per the definition of a palindrome “A palindrome is a word, phrase, number, or other sequence of symbols or elements that reads the same forward or reversed …” LINQ helps with this implementation as well and reduces the code to an elegant on line of code:

public static bool RidiculouslyEasyLinqOnlyIsPalindrome(this string value)
        {
           return value.ToLower().Equals(new string(value.ToLower().Reverse().ToArray()));
        }

That is all for palindromes and TDD for now.

Advertisements

4 thoughts on “Let’s Talk About TDD

    • I have added a recursive solution, along with tests, to my solution on BitBucket. Here is the implementation:

      public static bool RecursiveIsPalindrome(this string value, int i, int j)
              {
                  if (i >= j) return true;
      
                  var stringAsArray = value.ToLower().ToCharArray();
      
                  if (stringAsArray[i] == stringAsArray[j])
                  {
                      i++;
                      j--;
                      return value.RecursiveIsPalindrome(i, j);
                  }
                  
                  return false;
              }
      

      As an extension method this is a bit clunky. I don’t know of a way to pass the string’s length as a default parameter, but if there were a way to do it this would be a pretty sweet implementation.

  1. Glad to see you posting again and sharing your thoughts as you work through a problem. There could have been an intermediate step between the “return false” and use-a-stack approach — check whether the first and last chars are the same. Thanks for the post!

  2. Pingback: Professional Development – 2014 – Week 38

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s