TDD and small steps

The Christmas tree kata

In my previous post on test-driven development (TDD), I already introduced the concepts of coding katas and coding dojos. As an example, this post works out one of the most deceptively simple yet familiar katas, the Christmas tree kata.

The task in this kata is to print a Christmas tree with an arbitrary number of layers, optionally with a trunk:

    *
   ***
  *****
 *******
*********
    |

Although this kata may seem trivial at first glance, the real challenge immediately becomes apparent once you add the constraint that only small steps are allowed.

Most people tend to hardcode the first two or three layers, then throw everything overboard and start coding the general algorithm. I have even seen people who blatantly replace the initial hardcoded return values with an algorithm from ChatGPT!

Of course, this defeats the whole purpose of the kata, which is to take very small steps towards a generalization of an initial solution obtained by applying the faking and cheating heuristic.

This is also the reason why I think this kata deserves all the attention: generalizing some code in really small steps is a difficult but crucial skill to acquire, as it is needed over and over again when writing code. Moreover, it also neatly illustrates how one may find and implement an algorithm using very small steps only!

Writing our first tests

Our first test is going to validate for a tree of height zero:

Note that we have intentionally decided in our test that our algorithm returns a tree as an array of layers as strings.

Let’s implement this most simply and add a new test for a tree with height one:

The code base after we implemented the first test and added the second test.

We can easily make this test pass by adding an if-statement:

An implementation that makes our second test pass.

Now the question is, how many more tests do we want to add before we start generalizing the code? If have seen people successfully generalizing the code with just one more test for a tree of height two, but in this write-up, we will opt for the addition of two more tests, as it eases generalization quite a bit:

Our complete set of passing tests. Note that trailing spaces are not strictly needed for a correct print of the Christmas trees, but that we have included them nonetheless.

The challenge is to resist the urge to throw away the quick-and-dirty implementation and write the generic algorithm from scratch by trial and error. Instead, we should try to arrive at an algorithm in (extremely) small steps, keeping our tests green along the way.

Generalizing the code in small steps

Let’s first observe that depending on the height of each layer, a variable number of spaces needs to be applied. We can move this logic into a separate function:

Make the padding with spaces explicit.

We also observe a pattern in the number of stars in each layer. We can try to construct some generic formula for the number of stars in each layer by experimenting with each layer (i.e. line) in the code separately and check if the tests are still green.

Ideally, we would like to have one unique parameter per layer. This constraint gives us an additional direction to move into. This way, we eventually end up with:

Generate each layer more generically.

The generation of each layer is now similar enough to easily move that logic into its dedication function. However, we would prefer the first parameter of each call to the layer generator function to reflect the actual layer number.

Parameterize the generation of each layer with a self-explanatory layer parameter.

The rest of the generalization in small steps should now be pretty straightforward (including the generalization for the trunk).

Conclusion

In this article, we have used a simple example to show how you can discover an algorithm using TDD and small steps. As a consequence, you don’t need to design up front, even if you’re not sure what the algorithm will be.