Selecting a First TDD Exercise

Kata “Kata,” courtesy Peter Gordon. License.

Introducing developers to TDD? You want to carefully choose a first exercise. Too short, too long, too simple, too complex, too toy-like, too close to their problems, too whatever, and you might have chosen a turn-off. First impressions matter!

Of course, you can’t please everybody, but you can usually find a good middle ground. Here are some criteria for selecting an appropriate first TDD exercise.

Not frivolous. While very many of us love games and trivialities, there are enough developers that don’t. Their takeaway: “TDD is just for toys, not the ‘professional’ development that I do.” The Bowling Game? Save it and other games for a second or later exercise.
“Real” enough. A dozen years ago, I used to demonstrate a stack example in Java. Its implementation was a trivial four methods that simply delegated to an underlying list. Same takeaway: “Why would I bother building such a thing? TDD is just for toy examples.”
Time frame: Not too short, not too long. For a very first exercise, something that takes learners about 25-40 minutes to implement as a pair is ideal. (For experienced test-drivers like you or me, this translates to about 10-15 minutes as an individual and 20 minutes in a pair.) Any longer and they’ll get frustrated; much shorter and they won’t have had a chance to get into the rhythm.
Promotes incrementalism. Part of TDD’s power is in its ability to help you incrementally grow an implementation in a series of small steps. A ~45 minute example as suggested might involve 5-7 individual tests. As a counter-example: Looking for a Benefactor, a challenge at the kata site CodeWars.com, provides a decent challenge. However, the end-implementation is fully codeable with a second test, and there’s perhaps only one additional (denegerate) test to try.
Allows alternate solutions. Just about everything does, but if there’s one and only one decent way to code it, find something that allows for more interesting choices.
Mild problem solving required. You don’t want learners to bog down on thinking terribly hard about the problem itself. Yes, they need to think, but not so much that they’re distracted away from the core concepts and technique of TDD. For this reason, problems requiring “interesting” math are probably not a great idea for the average IT developer. Think simple.
Promotes refactoring. The ability to refactor with confidence is perhaps the primary reason to do TDD, so this criterion is quite important. You want strong reminders at refactoring steps that the code will get out of hand without incremental cleanup. It’s likely that problems promoting incrementalism and requiring “mild problem solving” will provide enough refactoring opportunities.
Allows mistakes. Mistakes are great learning opportunities! You want the possibility for an average learner to make up to a few stupid (or not so stupid) mistakes when implementing a solution. It’s even better if they are also likely to make mistakes when refactoring.
Minimizes esoteric language knowledge. A good developer shouldn’t have to Google something to figure out how to implement a solution.
Potentially expandable. While there’s something to be said for “done,” having an example you can build on later, or add to for fast learners who are ahead of others, can be worthwhile.
Fun enough. Not a toy example, but something that programmers might enjoy enough to quickly relate to and dig into.

Knowing your audience can help you refine the above to chose an example even better suited to their interests!

One example of an exercise that I’ve found to work well: acronym generator, also at CodeWars. It can be done with or without regex string splitting, and the regex is simple if that’s the route the developer chooses. There are ample additional requirements you could introduce (salutations, suffixes, resolve clashes, etc.).

Mind you, this is all for a first example. Subsequent exercises can be as meaty, long, goofy, or tricky as needed!

My First TDD Exercise

Finding a good first exercise for TDD learners can be challenging. Some of the things I look for:

  • Not so simple that it’s trivial, e.g. Stack, lest students dismiss it as pointless. There should be opportunities for students to make a few simple mistakes, but…
  • …not so complex that students mire in the algorithm itself instead of focusing on technique.
  • Something students can relate to–not so obscure that students struggle with understanding the domain or problem.
  • Games and fluff (bowling, fizz-buzz, e.g.) can create a first impression–and first impressions can be very hard to break–that TDD is for trivialities only, despite what you say. These things can be fine as later exercises.
  • Not something that already exists in the library. (“Why am building a multi-map when C++ already has one?”)
  • Can be test-driven in 10 to 15 minutes by an experienced TDDer, meaning that it’s probably a 30-to-45-minute exercise for newbies pairing up.
  • Provides a good demonstration of the ability to incrementally grow a solution, including opportunities to spot and remove duplication.
  • Provides an opportunity to show how to deal with at least one exceptional case.

I’ve been demoing a stock portfolio tracker for some time–a simple collection class that allows purchases of stock symbols. With Java students, I follow up with a multi-map, a class that would be useful in most shops (though a similar jakarta implementation exists). Both have worked well.

The message an exercise sends can be damaging. As a second or third exercise, lately I’ve been using the Roman numeral converter kata. I think it’s a cool exercise that can show how you can build an elegant algorithm by following a simple, incremental approach. It’s had 99% effectiveness: Out of the past ~100 students, one guy–an algorithm specialist–took a completely negative view of TDD after it. His stance was that he could have derived the algorithm much more quickly using a top-down, non-test-driven approach. From that he dismissed TDD completely. During subsequent pairings, I think he saw some of its benefits (we talk a lot about algorithms and TDD), but it’s an uphill battle and it might have been too late.

Currently I’m experimenting with an exercise to implement the soundex algorithm. More on that in an upcoming blog post.

Dave Thomas’s PragProg CodeKata site is a great place to get ideas. You might also check out the TDD Problems site (to which I contributed a handful of problems).

Test-Driving a Heap-Based Priority Queue

It’s been over 25 years since I had to code a priority queue. Should I really need to? Java now supplies a priority queue, and an important lesson of software development is that you should first seek to reuse what you can. But it’s worthwhile to know how to build such things yourself, in case you’re in an environment where one doesn’t exist.

As usual, though, I’m mostly interested in honing my ability to incrementally grow things, including interesting data structures. What can I learn from test-driving a priority queue?

All a priority queue does is return elements from a queue in priority order. Per the Wikipedia page, there are many ways to implement a priority queue, including a couple bad ways. Right off the bat, there’s no way I could force a priority queue to use a binary heap–one of the better choices–given only the client needs. Test-driving a solution and building the “simplest” possible implementation would result in the worst-performing solution.

So how to force the issue? Well, the nice thing about a binary heap is that it has a very concisely defined structure, one that I can verify easily. (I’ll refer to a binary heap as simply a heap for the rest of this article.) A binary heap is a tree where:

  • The key for each node is greater than or equal to each of its children.
  • The tree is complete–the last level is filled left-to-right, and all other levels are filled.

I know I want to end up with a heap–I need the performance–and will use that as a guiding factor in test-driving a solution. Does this violate YAGNI? Maybe. Other options? I could introduce a performance-related test, one where I tried to verify the big-O of each of the three operations (adding a new item, peeking at the highest priority item, and removing the highest priority item–the last two of which are often combined into a poll method). That would be tough to do well, and still might not guarantee an implementation that used a binary heap.

No, I need to be able to peek at the implementation. TDD will still be a great help. I still want to build the heap incrementally–there’s a decent amount of code involved, and plenty of opportunities to get it wrong. I’ll start simple, however, and not worry about heap characteristics until I get basic queue functionality working:

import org.junit.*;
import static org.junit.Assert.*;
import static org.hamcrest.CoreMatchers.*;

public class PriorityQueueTest {
   private static final Object ITEM_50 = "50";
   private static final Object ITEM_100 = "100";

   PriorityQueue queue;

   @Before
   public void create() {
      queue = new PriorityQueue();
   }

   @Test
   public void emptyWhenCreated() {
      assertThat(queue.isEmpty(), is(true));
   }

   @Test
   public void noLongerEmptyAfterAdd() {
      queue.add(ITEM_50, 50);

      assertThat(queue.isEmpty(), is(false));
   }

   @Test
   public void singletonQueueReturnsSoleItemOnPoll() {
      queue.add(ITEM_50, 50);

      assertThat(queue.poll(), is(ITEM_50));
   }

   @Test
   public void isEmptyAfterSoleElementRemoved() {
      queue.add(ITEM_50, 50);
      queue.poll();

      assertThat(queue.isEmpty(), is(true));
   }

   @Test
   public void returnsFIFOWithTwoAlreadyOrderedItems() {
      queue.add(ITEM_100, 100);
      queue.add(ITEM_50, 50);

      assertThat(queue.poll(), is(ITEM_100));
      assertThat(queue.poll(), is(ITEM_50));
      assertThat(queue.isEmpty(), is(true));
   }
}

I won’t bore you with the rote, incremental steps used to get to this point. For now the solution is simply a class that wraps an ordered list. There’s no support for pulling things out in other than FIFO order, since there are yet no tests that demand the capability.

import java.util.*;

public class PriorityQueue {
   private List<Object> heap = new ArrayList<Object>();

   public boolean isEmpty() {
      return heap.isEmpty();
   }

   public void add(Object item, int priority) {
      heap.add(item);
   }

   public Object poll() {
      return heap.remove(0);
   }
}

All those tests to get to this trivial bit of code? No big deal. About five minutes of work, and I’ve gotten some good cases documented and clamped down.

The next test makes things a little more interesting:

   @Test
   public void returnsInPriorityOrder() {
      queue.add(ITEM_50, 50);
      queue.add(ITEM_100, 100);

      assertThat(queue.poll(), is(ITEM_100));
      assertThat(queue.poll(), is(ITEM_50));
      assertThat(queue.isEmpty(), is(true));
   }

The implementation now requires actually using the priority, associating it with each item, hence the introduction of the Node class. It also means I need a little bit of “real heap logic” in the add method: If the second item is higher priority than the first, sift it to the front. Since there are only two items, it’s a hard-coded swap. The way I coded it also happens to work for single-element heaps.

import java.util.*;

public class PriorityQueue {
   private List<Node> heap = new ArrayList<Node>();

   class Node {
   final Object object;
   final int priority;

   Node(Object object, int priority) {
      this.object = object;
      this.priority = priority;
   }
   

   public boolean isEmpty() {
      return heap.isEmpty();
   }

   public void add(Object item, int priority) {
      Node node = new Node(item, priority);
      heap.add(node);
      if (node.priority > heap.get(0).priority)
         siftUp();
   }

   private void siftUp() {
      Node temp = heap.get(0);
      heap.set(0, heap.get(1));
      heap.set(1, temp);
   }

   public Object poll() {
      return heap.remove(0).object;
   }
}

Interestingly, I still don’t have a proper tree with parents and children–just a list with a couple slots filled in. In looking about at ways to implement a binary tree, the most appealing is to simply build it in-place in an array–something easily done given the constraint that the tree must be complete. Using an array will make it easy (and fast) to navigate from parent to child and vice versa.

The tests could use a bit of clarity. I add a helper method to simplify my assertion (and distill it to one line):

   @Test
   public void returnsFIFOWithTwoAlreadyOrderedItems() {
      queue.add(ITEM_100, 100);
      queue.add(ITEM_50, 50);

      assertQueuePollingOrder(ITEM_100, ITEM_50);
   }

   @Test
   public void returnsInPriorityOrder() {
      queue.add(ITEM_50, 50);
      queue.add(ITEM_100, 100);

      assertQueuePollingOrder(ITEM_100, ITEM_50);
   }

   private void assertQueuePollingOrder(Object... expectedItems) {
      List<Object> items = new ArrayList<Object>();
      while (!queue.isEmpty())
         items.add(queue.poll());
      assertThat(items, is(Arrays.asList(expectedItems)));
   }

Time to move on to the more interesting cases.

Thinking a bit about the next test (thinking is allowed, in fact encouraged, in TDD, particularly when determining what to do next)… Adding a third element to the heap will require a bit more generalized logic, and a fourth element (which would represent the third level of the heap’s tree) even more so. All complex enough without worrying about the complexity of removal, which requires re-heapifying.

One thing at a time. Rather than solve both challenges at once, I’ll first build out support for adding elements. Instead of using polling to verify that adding worked properly, I’ll verify that the priority queue’s underlying heap is valid.

Instead of creating a new test, I introduce a new assertion in each of my two existing tests (abusing the guideline of one assert per test).

   @Test
   public void returnsFIFOWithTwoAlreadyOrderedItems() {
      queue.add(ITEM_100, 100);
      queue.add(ITEM_50, 50);

      assertQueuePollingOrder(ITEM_100, ITEM_50);
      assertValid(queue.heap());
   }

   @Test
   public void returnsInPriorityOrder() {
      queue.add(ITEM_50, 50);
      queue.add(ITEM_100, 100);

      assertQueuePollingOrder(ITEM_100, ITEM_50);
      assertValid(queue.heap());
   }

   private void assertValid(List<PriorityQueue.Node> heap) {
      assertSubheap(heap, Integer.MAX_VALUE, 0);
   }

   private void assertSubheap(
         List<PriorityQueue.Node> heap, int priority, int root) {
      if (root > heap.size() - 1)
         return;

      PriorityQueue.Node node = heap.get(root);
      assertThat(priority > node.priority, is(true));

      assertSubheap(heap, node.priority, leftChild(root));
      assertSubheap(heap, node.priority, rightChild(root));
   }

   private int rightChild(int index) {
      return index * 2 + 2;
   }

   private int leftChild(int index) {
      return index * 2 + 1;
   }

Now I can quickly write the next failing test (with a lame name):

   @Test
   public void heapifiesThreeElements() {
      queue.add(ITEM_50, 50);
      queue.add(ITEM_75, 75);
      queue.add(ITEM_100, 100);

      assertValid(queue.heap());
   }

… and get it to pass quickly too:

   public void add(Object item, int priority) {
      Node node = new Node(item, priority);
      heap.add(node);
      int rightmost = heap.size() - 1;
      if (node.priority > heap.get(0).priority)
         siftUp(rightmost);
   }

   private void siftUp(int rightmost) {
      Node temp = heap.get(0);
      heap.set(0, heap.get(rightmost));
      heap.set(rightmost, temp);
   }

relevant lines: 4,6,9,11,12

Another test:

   @Test
   public void heapifiesMultipleLevels() {
      add(50, 75, 100, 125);
      assertValid(queue.heap());
   }

This time it requires a bit more manipulation of existing code. I rename siftUp to simply swap, because that’s all it does, and the “sift up” algorithm is in the body of the add method.

   public void add(Object item, int priority) {
      heap.add(new Node(item, priority));
      int current = heap.size() - 1;
      while (priority > parentPriority(current)) {
         swap(current, parent(current));
         current = parent(current);
      }
   }

   private int parentPriority(int index) {
      return heap.get(parent(index)).priority;
   }

   private int parent(int index) {
      return (index - 1) / 2;
   }

   private void swap(int x, int y) {
      Node temp = heap.get(x);
      heap.set(x, heap.get(y));
      heap.set(y, temp);
   }

It’s not bad, but I want each method to be at one level of abstraction, so I modify the add method:

   public void add(Object item, int priority) {
      addNewNode(item, priority);
      siftUpFromLast(priority);
   }

   private void addNewNode(Object item, int priority) {
      heap.add(new Node(item, priority));
   }

   private void siftUpFromLast(int priority) {
      int current = heap.size() - 1;
      while (priority > parentPriority(current)) {
         swap(current, parent(current));
         current = parent(current);
      }
   }

I think that’s it for add! To confirm, I use the example from Wikipedia:

   @Test
   public void integrationTest() {
      add(1, 2, 3, 7, 17, 19, 25, 36, 100);
      assertValid(queue.heap());
   }

Oh yeah–all those test lines required to add elements were getting annoying, so I added the following helper in the test (and updated other tests correspondingly):

   private void add(int... priorities) {
      for (int priority: priorities)
         queue.add(String.valueOf(priority), priority);
   }

On to polling. The general algorithm: capture value at front of heap (the highest priority per add‘s post-condition), move the rightmost item to the front, and re-heapify. To re-heapify: compare the item at the root with both its children, swap with the larger if necessary, and re-heapify the subtree.

From a test perspective, all we need to verify is that the highest priority item was returned and that the completeness post-condition held.

   @Test
   public void removeAnswersHighest() {
      add(20, 30, 40, 100, 50, 60);
      assertThat(queue.poll(), is((Object)"100"));
   }
   @Test
   public void removeReheapifies() {
      add(20, 30, 40);
      queue.poll();
      assertValid(queue.heap());
   }

After incrementally introducing changes based on those two test failures, here’s the explicit bit of code that covers lists up to three elements:

   public Object poll() {
      Object result = heap.remove(0).object;
      if (heap.size() == 2) {
         if (heap.get(0).priority < heap.get(1).priority)
            swap(0, 1);
      }
      return result;
   }

The addition of another item generates the next test failure:

   @Test
   public void removeReheapifyMustConsiderBothChildren() {
      add(40, 20, 30, 10);
      queue.poll();
      assertValid(queue.heap());
   }

I use programming by intention to express the algorithm clearly, starting with the poll method:

   public Object poll() {
      if (heap.size() == 1)
         return heap.remove(0).object;

      Object result = heap.get(0).object;
      reheapify();
      return result;
   }

   private void reheapify() {
      moveLastToFirstSlot();
      if (priorityLessThanEitherChild(0))
         swap(0, highestPriorityChild(0));
   }

The reheapify method has the odd side effect of eliminating the first (highest) element by overwriting it. That this is not explicit in the poll method suggests there’s probably a better expression of the entire algorithm.

I flesh out the trivial supporting methods:

   private void moveLastToFirstSlot() {
      Node rightmost = heap.remove(heap.size() - 1);
      heap.set(0, rightmost);
   }
private boolean priorityLessThanEitherChild(int index) {
      int priority = heap.get(index).priority;
      return priority < leftPriority(index) ||
             priority < rightPriority(index);
   }

   private int highestPriorityChild(int index) {
      return leftPriority(index) > rightPriority(index)
             ? leftChild(index)
             : rightChild(index);
   }

   private int rightPriority(int index) {
      return priority(rightChild(index));
   }

   private int leftPriority(int index) {
      return priority(leftChild(index));
   }

   private int priority(int index) {
      if (index > heap.size() - 1)
         return Integer.MIN_VALUE;
      return heap.get(index).priority;
   }

   private int leftChild(int index) {
      return index * 2 + 1;
   }

   private int rightChild(int index) {
      return index * 2 + 2;
   }

It’s a good chunk of code, but it still fit comfortably within my five-minute cycle limit.

Hey–I recognize those leftChild and rightChild methods from my test! I’ll go make ’em static so the test can re-use them.

About the only other interesting logic is rooted in the priority method, which returns Integer.MIN_VALUE if there’s no item at an index. That allows comparisons in priorityLessThanEitherChild to quietly fail when no child exists.

Almost there.  The final push is to force repeated swaps from root down through multiple subtrees:

   @Test
   public void removeMustReheapifyMultipleLevels() {
      add(50, 40, 20, 30, 10);
      queue.poll();
      assertValid(queue.heap());
   }

Getting a passing test requires a nice, small increment of code (and a TPP transformation from if=>while. Recursion is one up in the priority list–should I refactor this method?).

   private void reheapify() {
      moveLastToFirstSlot();
      int i = 0;
      while (priorityLessThanEitherChild(i)) {
         int child = highestPriorityChild(i);
         swap(i, child);
         i = child;
      }
   }

Both add and poll methods appear to be complete. Here’s a passing test that fires end-to-end:

   @Test
   public void pollsInPriorityOrder() {
      add(40, 20, 60, 80, 10, 30, 90, 70, 50);
      assertQueuePollingOrder(
         "90", "80", "70", "60", "50", "40", "30", "20", "10");
   }

Boy, do those quotes suck. Well, it’s time to do some global clean-up, so I’ll fix that along with some other things. Here’s the test class after some various cleanup for expressiveness:

import static org.hamcrest.CoreMatchers.*;
import static org.junit.Assert.*;
import java.util.*;
import org.junit.*;

public class PriorityQueueTest {
   PriorityQueue queue;

   @Before
   public void create() {
      queue = new PriorityQueue();
   }

   @Test
   public void emptyWhenCreated() {
      assertThat(queue.isEmpty(), is(true));
   }

   @Test
   public void noLongerEmptyAfterAdd() {
      queue.add("", 50);

      assertThat(queue.isEmpty(), is(false));
   }

   @Test
   public void singletonQueueReturnsSoleItemOnPoll() {
      queue.add("abc", 50);

      assertThat(queue.poll(), is((Object)"abc"));
   }

   @Test
   public void isEmptyAfterSoleItemRemoved() {
      queue.add("", 50);
      queue.poll();

      assertThat(queue.isEmpty(), is(true));
   }

   @Test
   public void returnsFIFOWithTwoAlreadyOrderedItems() {
      add(100, 50);
      assertQueuePollingOrder(100, 50);
      assertValid(queue.heap());
   }

   @Test
   public void returnsTwoUnorderedItemsInPriorityOrder() {
      add(50, 100);
      assertQueuePollingOrder(100, 50);
      assertValid(queue.heap());
   }

   @Test
   public void heapifiesThreeItems() {
      add(50, 75, 100);
      assertValid(queue.heap());
   }

   @Test
   public void heapifiesMultipleLevels() {
      add(50, 75, 100, 125);
      assertValid(queue.heap());
   }

   @Test
   public void removeAnswersHighest() {
      add(20, 30, 40, 100, 50, 60);
      assertThat(queue.poll(), is((Object)"100"));
   }

   @Test
   public void removeReheapifiesTwoItems() {
      add(20, 30, 40);
      queue.poll();
      assertValid(queue.heap());
   }

   @Test
   public void removeReheapifyMustConsiderBothChildren() {
      add(40, 20, 30, 10);
      queue.poll();
      assertValid(queue.heap());
   }

   @Test
   public void removeMustReheapifyMultipleLevels() {
      add(50, 40, 20, 30, 10);
      queue.poll();
      assertValid(queue.heap());
   }

   @Test
   public void pollExhaustsHeapInPriorityOrder() {
      add(40, 20, 60, 80, 10, 30, 90, 70, 50);
      assertQueuePollingOrder(90, 80, 70, 60, 50, 40, 30, 20, 10);
   }

   private void assertQueuePollingOrder(Integer... expectedItems) {
      List<Integer> items = new ArrayList<Integer>();
      while (!queue.isEmpty())
         items.add(Integer.parseInt((String)queue.poll()));
      assertThat(items, is(Arrays.asList(expectedItems)));
   }

   private void add(int... priorities) {
      for (int priority: priorities)
         queue.add(String.valueOf(priority), priority);
   }

   private void assertValid(List<PriorityQueue.Node> heap) {
      assertSubheap(heap, Integer.MAX_VALUE, 0);
   }

   private void assertSubheap(List<PriorityQueue.Node> heap, int priority, int root) {
      if (root > heap.size() - 1)
         return;

      PriorityQueue.Node node = heap.get(root);
      assertThat(priority > node.priority, is(true));

      assertSubheap(
         heap, node.priority, PriorityQueue.leftChild(root));
      assertSubheap(
         heap, node.priority, PriorityQueue.rightChild(root));
   }
}

And here’s the implementation:

import java.util.*;

public class PriorityQueue {
   private List<Node> heap = new ArrayList<Node>();

   static class Node {
      final Object object;
      final int priority;

      Node(Object object, int priority) {
         this.object = object;
         this.priority = priority;
      }

      public String toString() {
         return String.valueOf(priority);
      }
   }

   public boolean isEmpty() {
      return heap.isEmpty();
   }

   public void add(Object item, int priority) {
      addNewNode(item, priority);
      siftUpFromLast(priority);
   }

   private void addNewNode(Object item, int priority) {
      heap.add(new Node(item, priority));
   }

   private void siftUpFromLast(int priority) {
      int current = heap.size() - 1;
      while (priority > parentPriority(current)) {
         swap(current, parent(current));
         current = parent(current);
      }
   }

   private int parentPriority(int index) {
      return heap.get(parent(index)).priority;
   }

   private int parent(int index) {
      return (index - 1) / 2;
   }

   private void swap(int x, int y) {
      Node temp = heap.get(x);
      heap.set(x, heap.get(y));
      heap.set(y, temp);
   }

   public Object poll() {
      if (heap.size() == 1)
         return heap.remove(0).object;

      Object result = heap.get(0).object;
      reheapify();
      return result;
   }

   private void reheapify() {
      moveLastToFirstSlot();
      int i = 0;
      while (priorityLessThanEitherChild(i)) {
         int child = highestPriorityChild(i);
         swap(i, child);
         i = child;
      }
   }

   private void moveLastToFirstSlot() {
      Node rightmost = heap.remove(heap.size() - 1);
      heap.set(0, rightmost);
   }

   private boolean priorityLessThanEitherChild(int index) {
      int priority = heap.get(index).priority;
      return priority < leftPriority(index)
          || priority < rightPriority(index);
   }

   private int highestPriorityChild(int index) {
      return leftPriority(index) > rightPriority(index)
         ? PriorityQueue.leftChild(index)
         : PriorityQueue.rightChild(index);
   }

   int rightPriority(int index) {
      return priority(rightChild(index));
   }

   int leftPriority(int index) {
      return priority(leftChild(index));
   }

   private int priority(int index) {
      if (index > heap.size() - 1)
         return Integer.MIN_VALUE;
      return heap.get(index).priority;
   }

   List<Node> heap() {
      return heap;
   }

   static int rightChild(int index) {
      return index * 2 + 2;
   }

   static int leftChild(int index) {
      return index * 2 + 1;
   }
}

What else is there to complain about?

  • My test names could use some work. It’s hard to derive good test names when you’re driving incremental implementation of an algorithm, instead of an interface.
  • I probably have some tests I can get rid of.
  • The tests could be composed better. Worse, the test knows about the Node class (which the client need not know about). Maybe binary heap verification should be built into the heap implementation itself.
  • Should there be a PriorityQueue class and a separate Heap class? I thought about this a while and didn’t see the value.
  • I don’t use the Comparable interface to “simplify” and externalize comparisons (i.e. allow the client to specify how priorities compare).
  • I don’t have any tests that show what happens when priorities are equal.
  • I don’t use safety braces (i.e. braces around single-line if statements)–that’s why I have tests. I don’t make everything private that could be private (package access is fine by me, particularly in tests since I don’t have to type the access modifier).

What do I like?

  • I was able to test-drive the implementation, sticking to the five-minute rule for getting green bars. Things were a bit close a couple times (was there a more incremental way?).
  • I think the algorithm as implemented is very easy to follow (read each of the add and poll methods), particularly when compared to what is typically built (here’s one implementation; see, for example, the percolateDown method).

What do you think? Is test-driving a priority queue a good kata? I lay down the challenge flag for a better progression and implementation (shouldn’t be hard).

TDD Kata: Roman number converter

I’ve introduced the whole-number-to-Roman-numeral kata in my test-driven development training, not out of sadistic interest, but because I think it offers some excellent lessons about TDD. I do find it a bit amusing that good developers often struggle badly with the derivation of the algorithm, even after I give them my guidelines for the exercise:

  • Don’t assume that your tests must go in order 1, 2, 3, 4, 5, 6, 7, … Seek the test that would make for the next simplest increment of code. Seek patterns–if you’ve figured out the pattern for 1, 2, 3, then what’s the next series of numbers that follows the same pattern?
  • When you refactor incrementally, make similar code look exactly alike, and then get rid of the duplication.
  • Do not prematurely optimize code. Avoid using code-expressiveness “optimizations:” use while loops and simple decrement constructs instead of for loops and post-decrement operators, and let them stand until your algorithm is complete.

After they complete the exercise, we discuss Uncle Bob’s Transformation Priority Premise (TPP), and I ask them to re-run the exercise for homework (and to get them used to the idea of a kata) with the TPP in mind.

The first time I attempted the Kata some years ago, I got lost in the weeds. I didn’t give up; I scrapped a good amount of code, thought a bit harder about the ordering of tests, and eventually made my way to the finish line. I noted at least a couple insights were required, and came up with the guidelines above as a result in order to help students keep on track.

“Let’s start at the beginning, a very good place to start:”

   @Test
   public void convertIntToRoman() {
      assertThat(convert(1), is("I"));
   }

The implementation is the topmost TPP transform, ({}->nil):

   String convert(int arabic) {
      return null;
   }

Quickly following, the passing implementation (nil->constant):

   String convert(int arabic) {
      return "I";
   }

Moving along to the next test:

assertThat(convert(2), is("II"));

There might be a way to get a higher-level transform, but (unconditional->if) seems simplest to me:

   String convert(int arabic) {
      if (arabic == 2) return "II";
      return "I";
   }

The conversion for 3 indicates a repeating pattern:

   assertThat(convert(3), is("III"));

…which begs for a loop (if->while):

   String convert(int arabic) {
      String roman = "";
      while (arabic-- > 0)
         roman += "I";
      return roman;
   }

Performance geeks: never mind the use of String vs StringBuilder/StringBuffer. I want to get the algorithm working first, and all that rot clutters up the code a bit.

Hmm. I didn’t follow my guideline, and used post-decrement where I probably should have just introduced a separate statement to decrement the arabic variable. (Oh and another sin, I’m manipulating the argument. Ah well.)

Now a bit of thought. One, two, three, ten! No, four sir! No, ten. I have support for I, II, III. If I seek a similar pattern, it’s likely to do the least to my code in terms of transforms required, so what if I head to X, XX, and XXX?

   assertThat(convert(10), is("X"));

I can get that to work with a simple (unconditional->if), but it’s horrid:

   String convert(int arabic) {
      if (arabic == 10) return "X";
      String roman = "";
      while (arabic-- > 0)
         roman += "I";
      return roman;
   }

That’s ok–adding a test for 20:

   assertThat(convert(20), is("XX"));

…starts to make things look better, as I introduce (if->while) again:

   String convert(int arabic) {
      String roman = "";
      while (arabic >= 10) {
         roman += "X";
         arabic -= 10;
      }
      while (arabic-- > 0)
         roman += "I";
      return roman;
   }

Those two while loops look an awful lot alike. I can make them look almost exactly alike–I replace my post-decrement (see, shouldn’t have introduced it yet) with a separate statement at the end of the loop body, and adjust my comparison expression:

  String convert(int arabic) {
      String roman = "";
      while (arabic >= 10) {
         roman += "X";
         arabic -= 10;
      }
      while (arabic >= 1) {
         roman += "I";
         arabic -= 1;
      }
      return roman;
   }

It’s clear that these while loops differ only by their data. A bit of insight suggests introducing a table-lookup, allowing the implementation to be factored to the following:

   static int[] ARABIC_DIGITS = { 10, 1 };
   static String[] ROMAN_DIGITS = { "X", "I" };

   String convert(int arabic) {
      String roman = "";
      for (int i = 0; i < ARABIC_DIGITS.length; i++) {
         while (arabic >= ARABIC_DIGITS[i]) {
            roman += ROMAN_DIGITS[i];
            arabic -= ARABIC_DIGITS[i];
         }
      }
      return roman;
   }

(In Java, I tried once building the above as a map, but since the algorithm demands traversing the digits in reverse order, it ends up being a good deal more code than the simple but slightly obnoxious paired arrays.)

Huh. Look at that. A test for 30 should pass too, and it does.

But is it a bit too much implementation? Maybe–now that I support I’s and X’s, I want to be able to combine them, yet it looks like the following tests will pass right off the bat:

   assertThat(convert(11), is("XI"));
   assertThat(convert(33), is("XXXIII"));

And they do! I wonder if there’s a way I could have coded so those tests failed first, but I’ve not thought about it much. Maybe I could have put the second loop in an else block. Ideas?

What about 5?

  assertThat(convert(5), is("V"));

It’s just another digit; adding support for 5 to the table gets this test to pass:

   static int[] ARABIC_DIGITS = { 10, 5, 1 };
   static String[] ROMAN_DIGITS = { "X", "V", "I" };

And now these little combinations involving 5 also pass:

   assertThat(convert(8), is("VIII"));
   assertThat(convert(27), is("XXVII"));

I have to imagine similar tests involving L, C, D, and M should all pass too.

Instead, I’ll hit that pesky one, 4:

   assertThat(convert(4), is("IV"));

The joy of four is that if I try to get there with subtraction, I’m in a world of hurt. This is where students usually go really, really wrong. But, wait… insight! What if I consider that “IV” is just another digit, like any other Roman digit, except that it requires two characters instead of one to represent?

   static int[] ARABIC_DIGITS = { 10, 5, 4, 1 };
   static String[] ROMAN_DIGITS = { "X", "V", "IV", "I" };

Voila. At this point, I’ve covered the various scenarios, now it’s just a matter of fleshing out the table with support for all of the Roman digits. How about I just write a couple tests that fire across all cylinders?

      assertThat(convert(2499), is("MMCDXCIX"));
      assertThat(convert(3949), is("MMMCMXLIX"));

The final “table:”

static int[] ARABIC_DIGITS =
{ 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
static String[] ROMAN_DIGITS =
{ "M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I" };

We haven’t had to touch the algorithm for a while. It still holds up!

   String convert(int arabic) {
      String roman = "";
      for (int i = 0; i < ARABIC_DIGITS.length; i++) {
         while (arabic >= ARABIC_DIGITS[i]) {
            roman += ROMAN_DIGITS[i];
            arabic -= ARABIC_DIGITS[i];
         }
      }
      return roman;
   }

I did a search for code that solves this challenge, and had to laugh at the ugliness of a number of the implementations. There were some clever but convoluted ones, some awful ones, and a few that had the same implementation here.

TDD can’t derive algorithms, so they say. I take a different view. An algorithm is simply a “step-by-step procedure for calculations,” per Wikipedia. And TDD is great at helping drive out the vast majority of step-by-step procedures.

Oh–they mean complex algorithms. I see. That’s ok: Most of what we must implement on a day-to-day basis can be done with reasonably simple algorithms. In fact, I’d warrant that far less than a percent of any given system requires anything but simple algorithms that any journeyman programmer can easily devise. (And I’ve seen some very “complex” systems, such as BaBar and the Sabre GDS.)

Complex algorithms do require leaps achieved often only by appropriate insights, sometimes gained only after extensive thought about the problem, and sometimes never reached by a given single mind. TDD will not necessarily help your mind achieve those insights. However, its incremental nature can in some cases give you enough pause and isolation on a small piece of the problem, to the point where the insight needed almost screams at you.

What’s the Next Test?

I coded the “Roman numeral kata” for the first time last night. I thought it was a reasonably straightforward exercise, but then I looked at the solutions of others by searching the web.

In agile, there’s this notion of “doing the simplest thing that could possibly work,” and I think it applies to TDD just fine. It helps keep me in the red-green-refactor rhythm. More importantly, it prevents me from pre-building complexity. It also keeps me in a mode of extreme incrementalism: DSTTCPW keeps teaching me how to truly grow a system incrementally, as agile demands.

From looking at the solutions on the web, however, I suspect that some people translate “do the simplest thing” to “don’t think at all.” Specifically, I’m referring to their progression of tests. At all times, once I complete a single test method, I spend some time thinking about what the next test should be. I don’t spend too much time, but nor do I blindly jump into the next apparently obvious test.

The task in the Roman numeral kata is to convert a positive integer to a Roman numeral. Doing this kata in a TDD fashion, the first test is converting 1 to I, which is a hard-coded return. The second test is converting 2 to II, which is simply done with an if statement. One might refactor at this step to a loop/count construct, or one might wait until 3 (III).

From 3, though, I noted that many of the coders insisted on jumping directly to 4 (IV). Certainly, this works, but most of the solutions I saw derived in this fashion either ended up more complex, or resulted in a fairly excessive solution that scaled back dramatically with some last-step refactoring.

One could argue that this is in the true spirit of incrementalism. After all, we should be able to tackle requirements in any order. Perhaps we need only support the numbers 1 through 4 initially, and later someone will insist on adding 5+.

An argument currently brewing on the XP list goes into the whole YAGNI thing, with one poster suggesting that if you have comprehensive information, there is nothing wrong with taking that into account. Kent Beck subsequently updated his take on YAGNI: “Here’s what I do: consider [forthcoming feature] a little, but try not to get so caught up in it that I freeze.”

In a similar fashion, TDD doesn’t mean “don’t think.” Determining the next test to write should incorporate some thought about what represents the simpler path to a more complete solution. Sometimes this is a guess, but with more experience, the wiser choices are more apparent. Sometimes you make the wrong choice, but you can still end up in the right place, particularly if you refactor with diligence.

With respect to the Roman numeral solution, the better answer is, try 5 (V) before 4 (IV). Then add combinations of V and I (6, 7); then finalize this logic with X, which pretty much demands a table-driven solution.

A last intuitive leap can dramatically improve the solution, but is not essential: Table entries don’t have to represent a single Roman letter. Thus you end up with an entry in the table for 4 (IV), 9 (IX), 40 (XL), 90 (XC), and so on. The logic stays clean and simple:

import java.util.*;

public class Roman {
  private final int number;
  private static final TreeMap&lt;Integer, String&gt; digits = new TreeMap&lt;Integer, String&gt;();
  {
     digits.put(1, "I");
     digits.put(4, "IV");
     digits.put(5, "V");
     digits.put(9, "IX");
     digits.put(10, "X");
     digits.put(40, "XL");
     digits.put(50, "L");
     digits.put(90, "XC");
     digits.put(100, "C");
     digits.put(400, "CD");
     digits.put(500, "D");
     digits.put(900, "CM");
     digits.put(1000, "M");
  }

  public Roman(int number) {
     this.number = number;
  }

  @Override
  public String toString() {
     StringBuilder roman = new StringBuilder();
     int remaining = number;
     for (Map.Entry&lt;Integer,String&gt; entry: digits.descendingMap().entrySet()) {
        int decimalDigit = entry.getKey();
        String romanDigit = entry.getValue();
        while (remaining &gt;= decimalDigit) {
           roman.append(romanDigit);
           remaining -= decimalDigit;
        }
     }
     return roman.toString();
  }
}

If you don’t make the intuitive leap, the final solution is a bit more muddy (as I saw in a few solutions out there). But you have a second chance: Since you have all those wonderful tests, you can refactor the heck out of your muddy solution, looking for a more concise expression, and often you’ll find it.

Practicing Programming

I was able to entice Ron Jeffries to speak at the Colorado Springs Agile Users Group (cosAgile) a few months ago. As usual, the talk was very entertaining. Ron, deck of 3×5 cards in hand, went through a number of topics, talking about “why software development is easy.” Or not.

One of the central messages was about practicing the craft of programming. Musicians do scales, professional sports teams have scrimmages, and firemen run drills. But most programmers I know don’t seem to practice much.

Or maybe they do, but I just don’t hear about it. There are gobs of open source projects out there, and geeks who just sit at home working on pet projects. Do these count as “practice?”

Ron is one of those guys who practices the bowling game, over and over, to see how his solution improves each time. I’ve done the same thing, working on building a database interface layer. It comes out a little differently and a little better each time. The last place I was at, we used this database interface layer as the basis for a weekly lesson in TDD.

CosAgile meets weekly to work on a password manager application, PeakPassMan. While the result will be a functional, usable product, that’s not the primary goal. The goal is for programmers to get together, share ideas, and work on a common source base while trying to learn more about things like test-driven development. CosAgile is certainly not the first group to promote the idea of getting together weekly to practice building code, but it sets a good, shining public example.

Practice makes perfect! Well, there is no “perfect” in programming, but honing your skills by practicing a problem is a great idea.

Atom