Diamond Kata - TDD with only Property-Based Tests

The Diamond Kata is a simple exercise that Seb Rose described in a recent blog post.

Seb describes the Diamond Kata as:

Given a letter, print a diamond starting with ‘A’ with the supplied letter at the widest point.

For example: print-diamond ‘C’ prints

  A
 B B
C   C
 B B
  A

Seb used the exercise to illustrate how he “recycles” tests to help him work incrementally towards a full solution. Seb’s approach prompted Alastair Cockburn to write an article in response in which he argued for more thinking before programming. Alastair’s article shows how he approached the Diamond Kata with more up-front analysis. Ron Jeffries and George Dinwiddie resonded to Alastair’s article, showing how they approached the Diamond Kata relying on emergent design to produce an elegant solution (“thinking all the time”, as Ron Jeffries put it). There was some discussion on Twitter, and several other people published their approaches. (I’ll list as many as I know about at the end of this article).

The discussion sparked my interest, so I decided to have a go at the exercise myself. The problem seemed to me, at first glance, to be a good fit for property testing. So I decided to test-drive a solution using only property-based tests and see what happens. I wrote the solution in Scala and used ScalaTest to run and organise the tests and ScalaCheck for property testing.

What follows is an unexpurgated, warts-and-all walkthrough of my progress, not just the eventual complete solution. I made wrong turns and stupid mistakes along the way.

The walkthrough is pretty long, so if you want you don’t want to follow through step by step, jump straight to the complete solution and/or my conclusions on how the exercise went and what I learned. Alternatively, if you want to follow the walkthrough in more detail, the entire history is on GitHub, with a commit per TDD step (add a failing test, commit, make the implementation pass the test, commit, refactor, commit, … and repeat).

Walkthrough

Getting Started: Testing the Test Runner

The first thing I like to do when starting a new project is make sure my development environment and test runner are set up right, that I can run tests, and that test failures are detected and reported. I use Gradle to bootstrap a new Scala project with dependencies on the latest versions of ScalaTest and ScalaCheck and import the Gradle project into IntelliJ IDEA.

ScalaTest supports several different styles of test and assertion syntax. The user guide recommends writing an abstract base class that combines traits and annotations for your preferred testing style and test runner, so that’s what I do first:

@RunWith(classOf[JUnitRunner])
abstract class UnitSpec extends FreeSpec with PropertyChecks {
}

My test class extends UnitSpec:

class DiamondSpec extends UnitSpec {
}

I add a test that explicitly fails, to check that the test framework, IDE and build hang together correctly. When I see the test failure, I’m ready to write the first real test.

The First Test

Given that I’m writing property tests, I have to start with a simple property of the diamond function, not a simple example.

The simplest property I can think of is:

For all valid input character, the diamond contains one or more lines of text.

To turn that into a property test, I must define “all valid input characters” as a generator. The description of the Diamond Kata defines valid input as a single upper case character. ScalaCheck has a predefined generator for that:

val inputChar = Gen.alphaUpperChar

At this point, I haven’t decided how I will represent the diamond. I do know that my test will assert on the number of lines of text, so I write the property with respect to an auxiliary function, diamondLines(c:Char):Vector[String], which will generate a diamond for input character c and return the lines of the diamond in a vector.

"produces some lines" in {
  forAll (inputChar) { c => assert(diamondLines(c).nonEmpty) }
}

I like the way that the test reads in ScalaTest/ScalaCheck. It is pretty much a direct translation of my English description of the property into code.

To make the test fail, I write diamondLines as:

def diamondLines(c : Char) : Vector[String] = {
  Vector()
}

The entire test class is:

import org.scalacheck._

class DiamondSpec extends UnitSpec {
  val inputChar = Gen.alphaUpperChar

  "produces some lines" in {
    forAll (inputChar) { c => assert(diamondLines(c).nonEmpty) }
  }

  def diamondLines(c : Char) : Vector[String] = {
    Vector()
  }
}

The simplest implementation that will make that property pass is to return a single string:

object Diamond {
  def diamond(c: Char) : String = {
    "A"
  }
}

I make the diamondLines function in the test call the new function and split its result into lines:

def diamondLines(c : Char) = {
  Diamond.diamond(c).lines.toVector
}

The implementation can be used like this:

object DiamondApp extends App {
  import Diamond.diamond

  println(diamond(args.lift(0).getOrElse("Z").charAt(0)))
}

A Second Test, But It Is Not Very Helpful

I now need to add another property, to more tightly constrain the solution. I notice that the diamond always has an odd number of lines, and decide to test that:

For all valid input character, the diamond has an odd number of lines.

This implies that the number of lines is greater than zero (because vectors cannot have a negative number of elements and zero is even), so I change the existing test rather than adding another one:

"produces an odd number lines" in {
  forAll (inputChar) { c => assert(isOdd(diamondLines(c).length)) }
}

def isOdd(n : Int) = n % 2 == 1

But this new test has a problem: my existing solution already passes it. The diamond function returns a single line, and 1 is an odd number. This choice of property is not helping drive the development forwards.

A Failing Test To Drive Development, But a Silly Mistake

The next simplest property I can think of is the number of lines of the diamond. If ‘ord(c)’ is the number of letters between ‘A’ and c, (zero for A, 1 for B, 2 for C, etc.) then:

For all valid input characters, c, the number of lines in a diamond for c is 2*ord(c)+1.

At this point I make a silly mistake. I write my property as:

"number of lines" in {
  forAll (inputChar) { c => assert(diamondLines(c).length == ord(c)+1) }
}

def ord(c: Char) : Int = c - 'A'

I don’t notice the mistake immediately. When I do, I decide to leave it in the code as an experiment to see if the property tests will detect the error by becoming inconsistent, and how long it will take before they do so.

This kind of mistake would easily be caught by an example test. It’s a good idea to have a few examples, as well as properties, to act as smoke tests.

I make the test pass with the smallest amount of production code possible. I move the ord function from the test into the production code and use it to return the required number of lines that are all the same.

def diamond(c: Char) : String = {
  "A\n" * (ord(c)+1)
}

def ord(c: Char) : Int = c - 'A'

Despite sharing the ord function between the test and production code, there’s still some duplication. Both the production and test code calculate ord(c)+1. I want to address that before writing the next test.

Refactor: Duplicated Calculation

I replace ord(c)+1 with lineCount(c), which calculates number of lines generated for an input letter, and inline the ord(c) function, because it’s now only used in one place.

object Diamond {
  def diamond(c: Char) : String = {
    "A\n" * lineCount(c)
  }

  def lineCount(c: Char) : Int = (c - 'A')+1
}

And I use lineCount in the test as well:

"number of lines" in {
  forAll (inputChar) { c => assert(diamondLines(c).length == lineCount(c)) }
}

On reflection, using the lineCount calculation from production code in the test feels like a mistake.

Squareness

The next property I add is:

For all valid input character, the text containing the diamond is square

Where “is square” means:

The length of each line is equal to the total number of lines

In Scala, this is:

"squareness" in {
  forAll (inputChar) { c => assert(diamondLines(c) forall {_.length == lineCount(c)}) }
}

I can make the test pass like this:

object Diamond {
  def diamond(c: Char) : String = {
    val side: Int = lineCount(c)

    ("A" * side + "\n") * side
  }

  def lineCount(c: Char) : Int = (c - 'A')+1
}

Refactor: Rename the lineCount Function

The lineCount is also being used to calculate the length of each line, so I rename it to squareSide.

object Diamond {
  def diamond(c: Char) : String = {
    val side: Int = squareSide(c)

    ("A" * side + "\n") * side
  }

  def squareSide(c: Char) : Int = (c - 'A')+1
}

Refactor: Clarify the Tests

I’m now a little dissatisfied with the way the tests read:

"number of lines" in {
  forAll (inputChar) { c => assert(diamondLines(c).length == squareSide(c)) }
}

"squareness" in {
  forAll (inputChar) { c => assert(diamondLines(c) forall {_.length == squareSide(c)}) }
}

The “squareness” property does not stand alone. It doesn’t communicate that the output is square unless combined with “number of lines” property.

I refactor the test to disentangle the two properties:

"squareness" in {
  forAll (inputChar) { c =>
    val lines = diamondLines(c)
    assert(lines forall {line => line.length == lines.length}) }
}

"size of square" in {
  forAll (inputChar) { c => assert(diamondLines(c).length == squareSide(c)) }
}

The Letter on Each Line

The next property I write specifies which characters are printed on each line. The characters of each line should be either a letter that depends on the index of the line, or a space.

Because the diamond is vertically symmetrical, I only need to consider the lines from the top to the middle of the diamond. This makes the calculation of the letter for each line much simpler.

I make a note to add a property for the vertical symmetry once I have made the implementation pass this test.

"single letter per line" in {
  forAll (inputChar) { c =>
    val allLines = diamondLines(c)
    val topHalf = allLines.slice(0, allLines.size/2 + 1)

    for ((line, index) <- topHalf.zipWithIndex) {
      val lettersInLine = line.toCharArray.toSet diff Set(' ')
      val expectedOnlyLetter = ('A' + index).toChar
      assert(lettersInLine == Set(expectedOnlyLetter), 
             "line " + index + ": \"" + line + "\"")
    }
  }
}

To make this test pass, I change the diamond function to:

def diamond(c: Char) : String = {
  val side: Int = squareSide(c)

  (for (lc <- 'A' to c) yield lc.toString * side) mkString "\n"
}

This repeats the correct letter for the top half of the diamond, but the bottom half of the diamond is wrong. This will be fixed by the property for vertical symmetry, which I’ve noted down to write next.

Vertical Symmetry

The property for vertical symmetry is:

For all input character, c, the lines from the top to the middle of the diamond, inclusive, are equal to the reversed lines from the middle to the bottom of the diamond, inclusive.

"is vertically symmetrical" in {
  forAll(inputChar) { c =>
    val allLines = diamondLines(c)
    val topHalf = allLines.slice(0, allLines.size / 2 + 1)
    val bottomHalf = allLines.slice(allLines.size / 2, allLines.size)

    assert(topHalf == bottomHalf.reverse)
  }
}

The implementation is:

def diamond(c: Char) : String = {
  val side: Int = squareSide(c)
  val topHalf = for (lc <- 'A' to c) yield lineFor(side, lc)
  val bottomHalf = topHalf.slice(0, topHalf.length-1).reverse

  (topHalf ++ bottomHalf).mkString("\n")
}

But this fails the “squareness” and “size of square” tests! My properties are now inconsistent. The test suite has detected the erroneous implementation of the squareSide function.

The correct implementation of squareSide is:

def squareSide(c: Char) : Int = 2*(c - 'A') + 1

With this change, the implementation passes all of the tests.

The Position Of The Letter In Each Line

Now I add a property that specifies the position and value of the letter in each line, and that all other characters in a line are spaces. Like the previous test, I can rely on symmetry in the output to simplify the arithmetic. This time, because the diamond has horizontal symmetry, I only need specify the position of the letter in the first half of the line. I add a specification for horizontal symmetry, and factor out generic functions to return the first and second half of strings and sequences.

"is vertically symmetrical" in {
  forAll (inputChar) { c =>
    val lines = diamondLines(c)
    assert(firstHalfOf(lines) == secondHalfOf(lines).reverse)
  }
}
  
"is horizontally symmetrical" in {
  forAll (inputChar) { c =>
    for ((line, index) <- diamondLines(c).zipWithIndex) {
      assert(firstHalfOf(line) == secondHalfOf(line).reverse,
        "line " + index + " should be symmetrical")
    }
  }
}

"position of letter in line of spaces" in {
  forAll (inputChar) { c =>
    for ((line, lineIndex) <- firstHalfOf(diamondLines(c)).zipWithIndex) {
      val firstHalf = firstHalfOf(line)
      val expectedLetter = ('A'+lineIndex).toChar
      val letterIndex = firstHalf.length - (lineIndex + 1)

      assert (firstHalf(letterIndex) == expectedLetter, firstHalf)
      assert (firstHalf.count(_==' ') == firstHalf.length-1, 
              "number of spaces in line " + lineIndex + ": " + line)
    }
  }
}

def firstHalfOf[AS, A, That](v: AS)(implicit asSeq: AS => Seq[A], cbf: CanBuildFrom[AS, A, That]) = {
  v.slice(0, (v.length+1)/2)
}

def secondHalfOf[AS, A, That](v: AS)(implicit asSeq: AS => Seq[A], cbf: CanBuildFrom[AS, A, That]) = {
  v.slice(v.length/2, v.length)
}

The implementation is:

object Diamond {
  def diamond(c: Char) : String = {
    val side: Int = squareSide(c)
    val topHalf = for (letter <- 'A' to c) yield lineFor(side, letter)

    (topHalf ++ topHalf.reverse.tail).mkString("\n")
  }

  def lineFor(length: Int, letter: Char): String = {
    val halfLength = length/2
    val letterIndex = halfLength - ord(letter)
    val halfLine = " "*letterIndex + letter + " "*(halfLength-letterIndex)

    halfLine ++ halfLine.reverse.tail
  }

  def squareSide(c: Char) : Int = 2*ord(c) + 1

  def ord(c: Char): Int = c - 'A'
}

It turns out the ord function, which I inlined into squareSide a while ago, is needed after all.

The implementation is now complete. Running the DiamondApp application prints out diamonds. But there’s plenty of scope for refactoring both the production and test code.

Refactoring: Delete the “Single Letter Per Line” Property

The “position of letter in line of spaces” property makes the “single letter per line” property superflous, so I delete “single letter per line”.

Refactoring: Simplify the Diamond Implementation

I rename some parameters and simplify the implementation of the diamond function.

object Diamond {
  def diamond(maxLetter: Char) : String = {
    val topHalf = for (letter <- 'A' to maxLetter) yield lineFor(maxLetter, letter)
    (topHalf ++ topHalf.reverse.tail).mkString("\n")
  }

  def lineFor(maxLetter: Char, letter: Char): String = {
    val halfLength = ord(maxLetter)
    val letterIndex = halfLength - ord(letter)
    val halfLine = " "*letterIndex + letter + " "*(halfLength-letterIndex)

    halfLine ++ halfLine.reverse.tail
  }

  def squareSide(c: Char) : Int = 2*ord(c) + 1

  def ord(c: Char): Int = c - 'A'
}

The implementation no longer uses the squareSide function. It’s only used by the “size of square” property.

Refactoring: Inline the squareSide function

I inline the squareSide function into the test.

"size of square" in {
  forAll (inputChar) { c => assert(diamondLines(c).length == 2*ord(c) + 1) }
}

I believe the erroneous calculation would have been easier to notice if I had done this from the start.

Refactoring: Common Implementation of Symmetry

There’s one last bit of duplication in the implementation. The expressions that create the horizontal and vertical symmetry of the diamond can be replaced with calls to a generic function. I’ll leave that as an exercise for the reader…

Complete Tests and Implementation

Tests:

import Diamond.ord
import org.scalacheck._
import scala.collection.generic.CanBuildFrom

class DiamondSpec extends UnitSpec {
  val inputChar = Gen.alphaUpperChar

  "squareness" in {
    forAll (inputChar) { c =>
      val lines = diamondLines(c)
      assert(lines forall {line => line.length == lines.length}) }
  }

  "size of square" in {
    forAll (inputChar) { c => assert(diamondLines(c).length == 2*ord(c) + 1) }
  }

  "is vertically symmetrical" in {
    forAll (inputChar) { c =>
      val lines = diamondLines(c)

      assert(firstHalfOf(lines) == secondHalfOf(lines).reverse)
    }
  }
  
  "is horizontally symmetrical" in {
    forAll (inputChar) { c =>
      for ((line, index) <- diamondLines(c).zipWithIndex) {
        assert(firstHalfOf(line) == secondHalfOf(line).reverse,
          "line " + index + " should be symmetrical")
      }
    }
  }

  "position of letter in line of spaces" in {
    forAll (inputChar) { c =>
      for ((line, lineIndex) <- firstHalfOf(diamondLines(c)).zipWithIndex) {
        val firstHalf = firstHalfOf(line)
        val expectedLetter = ('A'+lineIndex).toChar
        val letterIndex = firstHalf.length - (lineIndex + 1)

        assert (firstHalf(letterIndex) == expectedLetter, firstHalf)
        assert (firstHalf.count(_==' ') == firstHalf.length-1, 
          "number of spaces in line " + lineIndex + ": " + line)
      }
    }
  }

  def firstHalfOf[AS, A, That](v: AS)(implicit asSeq: AS => Seq[A], cbf: CanBuildFrom[AS, A, That]) = {
    v.slice(0, (v.length+1)/2)
  }

  def secondHalfOf[AS, A, That](v: AS)(implicit asSeq: AS => Seq[A], cbf: CanBuildFrom[AS, A, That]) = {
    v.slice(v.length/2, v.length)
  }
  
  def diamondLines(c : Char) = {
    Diamond.diamond(c).lines.toVector
  }
}

Implementation:

object Diamond {
  def diamond(maxLetter: Char) : String = {
    val topHalf = for (letter <- 'A' to maxLetter) yield lineFor(maxLetter, letter)
    (topHalf ++ topHalf.reverse.tail).mkString("\n")
  }

  def lineFor(maxLetter: Char, letter: Char): String = {
    val halfLength = ord(maxLetter)
    val letterIndex = halfLength - ord(letter)
    val halfLine = " "*letterIndex + letter + " "*(halfLength-letterIndex)

    halfLine ++ halfLine.reverse.tail
  }

  def ord(c: Char): Int = c - 'A'
}

Conclusions

In his article, “Thinking Before Programming”, Alastair Cockburn writes:

The advantage of the Dijkstra-Gries approach is the simplicity of the solutions produced.

The advantage of TDD is modern fine-grained incremental development.

Can we combine the two?

I think property-based tests in the TDD process combined the two quite successfully in this exercise. I could record my half-formed thoughts about the problem and solution as generators and properties while using “modern fine-grained incremental development” to tighten up the properties and grow the code that met them.

In Seb’s original article, he writes that when working from examples…

it’s easy enough to get [the tests for ‘A’ and ‘B’] to pass by hardcoding the result. Then we move on to the letter ‘C’.

The code is now screaming for us to refactor it, but to keep all the tests passing most people try to solve the entire problem at once. That’s hard, because we’ll need to cope with multiple lines, varying indentation, and repeated characters with a varying number of spaces between them.

I didn’t encounter this problem when driving the implementation with properties. Adding a new property always required an incremental improvement to the implementation to get the tests passing again.

Neither did I need to write throw-away tests for behaviour that was not actually desired of the final implementation, as Seb did with his “test recycling” approach. Every property I added applied to the complete solution. I only deleted properties that were implied by properties I added later, and so had become unnecessary duplication.

I took the approach of starting from very generic properties and incrementally adding more specific properties as I refine the implementation. Generic properties were easy to come up with, and helped me make progress in the problem. The suite of properties reinforced one another, testing the tests, and detected the mistake I made in one property that caused it to be inconsistent with the rest.

I didn’t know Scala, ScalaTest or ScalaCheck well. Now I’ve learned them better I wish I had written a minimisation strategy for the input character. This would have made test failure messages easier to understand.

I also didn’t address what the diamond function would do with input outside the range of ‘A’ to ‘Z’. Scala doesn’t let one define a subtype of Char, so I can’t enforce the input constraint in the type system. I guess the Scala way would be to define diamond as a PartialFunction[Char,String].

I haven’t yet looked at any other people’s solutions in detail. I’ll post a follow up article if I find any interesting differences.

Other Solutions

Other solutions to the Diamond Kata that I know about are:

Copyright © 2015 Nat Pryce. Posted 2015-01-10. (Permalink, Share it)

Comments powered by Disqus