The Diamond Kata Revisited

A few years ago, Seb Rose published an article about the Diamond Kata. The problem statement is simple, but solving it with TDD is not straightforward.

Problem: write a function that receives a positive integer and returns a string in the shape of a diamond. For example: `diamond(3)` should return

``````  A
B B
C   C
B B
A
``````

The interesting bit for TDD enthusiasts is that, while it’s easy to get started returning hard-coded responses, there’s no easy way to evolve the hardcoded values into general code.

Seb wrote that the best you can do is to start with tests for an approximate solution, and iterate both tests and code towards solving the full problem. His blog post led to a number of interesting responses:

The challenge with this kata is “what is the sequence of tests that will incrementally lead to a solution?”

*                *
*

Interestingly, it seems none of the above published solutions use a compositional approach; they all try to arrive at a “single algorithm” that will solve the problem, in spite of so many authors proposing that good programming is compositional.

This problem really looks like a compositional one if you think of it: the diamond

``````    A
B B
C   C
D     D
C   C
B B
A
``````

Looks like a composition of four “lines”. What if we started with test-driving a single diagonal “line”? It’s not too hard to test-drive a function that passes these tests:

``````diag(1) == "A"
diag(2) == ".A
B."
diag(3) == "..A
.B.
C.."
``````

The output of the function is a string that can be thought of as 2-dimensional image, composed of successive lines.

The diagonal is a quarter of the diamond. Now all we need is operations for manipulating images. Flipping an image orizontally:

``````flipHor("ABC") == "CBA"
flipHor(diag(3)) == "A..
.B.
..C"
``````

and vertically:

``````flipVert("AA
BB") == "BB
AA"
``````

Joining two images horizontally:

``````composeHor("ABC", "CBA") == "ABCBA"
composeHor(diag(3), flipHor(diag(3))) == "..A..
.B.B.
C...C"
``````

and vertically

``````composeVert("AA
BB
CC", "CC
BB
AA") == "AA
BB
CC
BB
AA"
``````

With these tools, composing a diamond becomes very easy:

``````String diamond(int size) {
var d = diag(size);
var upper = composeHor(d, flipHor(d));
var lower = flipVert(upper);
return composeVert(upper, lower);
}
``````
*                *
*

I always thought that TDD, or rather, good design, ought to lead not simply to a solution, but to a toolkit that makes expressing the solution easy. Decomposing this problem into a composition of “images” seems natural to me; it does not require a lot of mathematical thinking, except perhaps a little bit in the `diag` function about the correct amount of dots surrounding the letter. We could say that this solution is incremental rather than iterative: instead of refining a single algorithm towards the solution, we compose many simple algorithms together, so that the solution becomes easy.

All we needed is a single primitive operation `diag`, and four composition operators: `flipHor`, `flipVert` `composeHor` and `composeVert`.

As an added bonus, generating different and possibly more complicated images becomes easy: for instance, `ecs(4)`, that returns the image

``````D     D
C   C
B B
A
B B
C   C
D     D
``````

can be defined as

``````String ecs(int size) {
var d = diag(size);
var upper = composeHor(flipVert(d), flipHor(flipVert(d)));
var lower = flipVert(upper);
return composeVert(upper, lower);
}
``````

Update 2024-06-26 Géza Mihala pointed me at his solution; it’s a similar way of thinking, and his solution is more elegant than mine. He uses two operations `mirrorLeft` and `mirrorDown`, which combine my `flip` and `compose` operations, and as a result the solution can be expressed as a linear chain of transformations:

``````diag(n).mirrorLeft().mirrorDown()
``````

This works in Ruby because he’s adding methods to the String class; in Java I would achieve the same effect by wrapping the string in a domain-specific class, perhaps `Image`. The `mirrorLeft` operation can be defined as

``````String mirrorLeft(String s) {
return composeHor(s, flipHor(s));
}
``````

Good job Géza!