Hidden abstractions in the Diamond Kata
Hidden abstractions in the Diamond Kata – mnemonikk.org


	
	
	
	
		
The other day my colleagues and I were doing the “Diamond Kata”. If you haven’t heard about code katas yet: it’s a coding exercise you’re supposed to do repeatedly in order to hone your skills. Each time, you might want to try different approaches, different programming languages or coding disciplines. I found the Diamond Kata interesting in its own right, let me tell you why.
The task
The Diamond Kata is giving you a seemingly simple task: write code that outputs text in a diamond shape. The edges consist of letters, starting with “A”. The last letter is given as an argument and also determines the size of the diamond. The diamond for A⇒B looks like this:
 A
B B
 A

The diamond for A⇒D would look like this:
   A
  B B
 C   C
D     D
 C   C
  B B
   A

Looks pretty simple, right?
A solution
I’m going to present a solution in ruby. Let’s write some end-to-end tests first:
class TestDiamond < Minitest::Test
  def test_end_to_end
    assert_equal <<-EOS, Diamond.new("A").to_s
A
EOS

    assert_equal <<-EOS, Diamond.new("B").to_s
 A 
B B
 A 
    EOS

    assert_equal <<-EOS, Diamond.new("C").to_s
  A  
 B B 
C   C
 B B 
  A  
    EOS
  end
end

That was easy. So how are we going to solve this? Let’s start top down. We need to create the Diamond class and Diamond#to_s first. The string returned will be a concatenation of all the lines.
Diamond = Struct.new(:last) do
  def to_s
    lines.join
  end

  private

  def lines
    [] # ???
  end
end

There’s only ever to be the same letter on every line and lines with the same letter look exactly alike. So we just need to figure out the right sequence of letters and have a method for creating the corresponding line. Let’s work on getting the sequence of letters right.
class TestDiamond < Minitest::Test
  # [...]
  def test_letters
    assert_equal "A".chars, Diamond.new("A").letters
    assert_equal "ABA".chars, Diamond.new("B").letters
    assert_equal "ABCBA".chars, Diamond.new("C").letters
  end
end

Diamond = Struct.new(:last) do
  # [...]
  def lines
    letters.map(&method(:line_for))
  end

  def letters
    (FIRST...last).to_a + (FIRST..last).to_a.reverse
  end

  def line_for(letter)
    "" # ???
  end
end

Well, this will do the job. Now on to implementing #line_for which will construct the string for one line. The tip and the bottom of the diamond are special as they only print one letter. For everything else, there will be some outer padding, repeated left and right, and some inner padding. We will need to do some ugly arithmetic with letters.
class TestDiamond < Minitest::Test
  # [...]
  def test_line_for
    assert_equal "A\n", Diamond.new("A").line_for("A")
    assert_equal " A \n", Diamond.new("B").line_for("A")
    assert_equal "B B\n", Diamond.new("B").line_for("B")
    assert_equal " B B \n", Diamond.new("C").line_for("B")
    assert_equal "C   C\n", Diamond.new("C").line_for("C")
  end
end

Diamond = Struct.new(:last) do
  # [...]
  def line_for(letter)
    outer_padding = " " * (width - (letter.ord - FIRST.ord))
    if letter == FIRST
      outer_padding + letter + outer_padding
    else
      inner_padding = " " * ((letter.ord - FIRST.ord) * 2 - 1)
      outer_padding + letter + inner_padding + letter + outer_padding
    end + "\n"
  end

  private

  def width
    last.ord - FIRST.ord
  end
end

This took a few tries to get right, but seems to work. The end-to-end tests are passing now, we’re done. I wasn’t happy with this solution, though. Why? I was checking my code against Kent Beck’s four rules of simple design. Let me repeat them here:
Simple code

passes test, i.e. works
communicates intent
contains no duplication
uses a minimum amount of classes and methods

My problem was with rule 2., that the code doesn’t reflect the nature of the problem. You would never figure what the code does without running it or looking at the tests. It took me a few days to figure out another way.
The hidden abstraction
The task of the kata is not to output a certain random string. The diamond is a geometrical shape, it’s symmetrical. In math, you would draw something like this in a two dimensional coordinate system. So if we had some kind of canvas that we can render down to a string we could express the problem in a much nicer way. Let’s try this out! Here’s a really simple (square) text canvas:
class TestCanvas < Minitest::Test
  def test_draw
    canvas = Canvas.new(3)
    canvas[0, 0] = "X"
    canvas[1, 1] = "Y"
    canvas[0, 2] = "Z"
    canvas[2, 0] = "A"
    assert_equal <<-EOS, canvas.to_s
X A
 Y 
Z  
    EOS
  end
end

Canvas = Struct.new(:size) do
  def to_s
    rows.map { |row| row + "\n" }.join
  end

  def []=(x, y, value)
    rows.fetch(y)[x] = value
  end

  private

  def rows
    @rows ||= Array.new(size) { " " * size }
  end
end

On this canvas we need to paint every letter four times. We don’t need a special case for the tips any more: the tips will get painted more than once, at the same position. I introduce the radius of the diamond. We need to shift everything by this value in X and Y direction as our origin 0, 0 is in the top left corner. Here’s something that works:
Diamond = Struct.new(:last) do
  FIRST = "A"

  def to_s
    draw!
    canvas.to_s
  end

  private

  def draw!
    FIRST.upto(last).zip(
      0.upto(radius),
      radius.downto(0)
    ).each do |letter, x, y|
      canvas[ x + radius,  y + radius] = letter
      canvas[-x + radius,  y + radius] = letter
      canvas[ x + radius, -y + radius] = letter
      canvas[-x + radius, -y + radius] = letter
    end
  end

  def canvas
    @canvas ||= Canvas.new(width)
  end

  def radius
    @radius ||= last.ord - FIRST.ord
  end

  def width
    radius * 2 + 1
  end
end

I already like this solution much better.

We got rid of the special case.
The symmetry of the diamond shape is reflected by the drawing operations.
The Canvas class can be tested independently and is a component that we can easily reuse.

There’s also a thing I didn’t mention previously: we had to make Diamond#letters and Diamond#line_for public so that they could be tested. But they are really an implementation detail that no other code should depend upon. With the current implementation I’m quite happy with the feedback that the end-to-end test provides. Maybe some minor thing: the #draw! method still has some duplication, the drawing of letter looks repetitive as we always need to add the radius. According to the Four Rules of Simple Design, this is something to look out for. So let’s see if we can improve.
More abstractions
Operations in 2D space are a well known subject. Moving around by a fixed amount is called translation. Let’s implement this as a decorator:
class TestCanvas < Minitest::Test
  def test_translation
    canvas = Translation.new(Canvas.new(3), 1, 1)
    canvas[0, 0] = "A"
    assert_equal <<-EOS, canvas.to_s

 A 

    EOS
  end
end

class Translation < SimpleDelegator
  def initialize(canvas, offset_x, offset_y)
    super(canvas)
    @offset_x = offset_x
    @offset_y = offset_y
  end

  def []=(x, y, value)
    __getobj__[x + offset_x, y + offset_y] = value
  end

  private

  attr_reader :offset_x, :offset_y
end

The decorator logic calls for a bit of boilerplate, but the end result is nice and simple. Let’s see how we can put this to good use. Two methods in Diamond will need to change, Diamond#draw! and Diamond#canvas.
Diamond = Struct.new(:last) do
  # [...]

  private

  def draw!
    FIRST.upto(last).zip(
      0.upto(radius),
      radius.downto(0)
    ).each do |letter, x, y|
      canvas[ x,  y] = letter
      canvas[-x,  y] = letter
      canvas[ x, -y] = letter
      canvas[-x, -y] = letter
    end
  end

  def canvas
    @canvas ||=
      Translation.new(
        Canvas.new(width),
        radius, radius
      )
  end

So each drawing operation got simpler at the expense of a more complicated canvas setup. We still have four drawing operations going on, though. The obvious solution is to use a loop instead like this
Diamond = Struct.new(:last) do
  # [...]
  def draw!
    FIRST.upto(last).zip(
      0.upto(radius),
      radius.downto(0)
    ).each do |letter, x, y|
      [[x, y], [-x, y], [x, -y], [-x, -y]].each do |coords|
        canvas[*coords] = letter
      end
    end
  end

This removes duplication but makes the #draw! method harder to read. Maybe we can solve this in a similar fashion? Let’s look at it from another angle: we’re drawing a symmetrical shape, this means that we are mirroring over the X and Y axes. So the thing we need is a reflection. This should be pretty simple to do.
class TestReflection < Minitest::Test
  def test_reflection
    canvas =
      Reflection.new(
        Translation.new(
          Canvas.new(3),
          1, 1
        ),
        -1, 1
      )
    canvas[0, 0] = "A"
    canvas[1, 1] = "B"
    assert_equal <<-EOS, canvas.to_s

 A 
B B
    EOS
  end
end

class Reflection  < SimpleDelegator
  def initialize(canvas, factor_x, factor_y)
    super(canvas)
    @factor_x = factor_x
    @factor_y = factor_y
  end

  def []=(x, y, value)
    __getobj__[x, y] = value
    __getobj__[x * factor_x, y * factor_y] = value
  end

  private

  attr_reader :factor_x, :factor_y
end

This looks very similar to Translation, using multiplication instead of addition. The difference is that we’re still drawing in the original location. In order to be even more general, you could introduce a stack of canvases that get layered on top of each other during rendering. I chose not to go this route here. So what does this mean for our Diamond class?
Diamond = Struct.new(:last) do
  # [...]
  def draw!
    FIRST.upto(last).zip(
      0.upto(radius),
      radius.downto(0)
    ).each do |letter, x, y|
      canvas[x, y] = letter
    end
  end

  def canvas
    @canvas ||=
      Reflection.new(
        Reflection.new(
          Translation.new(
            Canvas.new(width),
            radius, radius
          ),
          1, -1
        ),
        -1, 1
      )
  end

The setup of our canvas looks pretty complex now. Is this still simple design? Duplication is reduced, but we have more classes working together. Whether this is all worth it depends on the context. For me this is just an exercise, so I can do what I please. But what if this was happening in a business context? If the business is trying to create a terminal-based text-only drawing program for UNIX-nerds, there’s a high likelyhood that our investment in composable classes will pay off quickly. If on the other hand this task was only a one-off job to help in creating a new company logo, our efforts would have been wasteful and our first version would have been good enough.
A parable for hidden abstractions
In hindsight the value of introducing the Canvas abstraction is obvious. Why didn’t I see it earlier? I think this is due to my upbringing as a programmer. A programmer learns how to do useful stuff with a dumb machine. We’re aware of the limits of our programming environments and take pride in how we’re still getting useful stuff done. So it’s only logical that start to think like the machine, we break the output up into individual lines and start to solve the smaller problem of creating a single line. The problem is that this is disregarding the outside context and therefore obscures the nature of the task.
This reminded me of the history of astronomy. In antiquity, astronomers were able to calculate the motion of the planets pretty accurately even though they were using the geocentric model. The Ptolemaic system was pretty complex, it assumed that planets were moving in epicycles along deferents. Similar to our first implementation, it worked just fine. But as we know today, it’s more useful to put the sun in the center. Contemporary programmers struggle with finding a better point of view just as much as the astronomers of yore.
][1][1] Representation of the apparent motion of the Sun, Mercury, and Venus from the earth.
Abstractions and TDD
People have been saying that TDD leads to better design and I tend to agree. But TDD doesn’t write code, it doesn’t create abstractions and it doesn’t always make it obvious what next step to take. A nicely factored implementation is easy to test – it’s our job as programmers to conceive it.
References

Source code on github
Original description of the diamond kata on Seb Rose’s blog
A solution in Scala using TDD with property-based tests by Nat Pryce
Jon Jagger found another interesting solution
Ptolemaic system on Wikipedia

			

	
