Using TDD to solve algorithms, Part I

Using TDD to solve algorithms, Part I

When I started a Rails bootcamp through the Firehose Project, I liked the idea of test driven development but it took a while to slowly appreciate its importance. Working on a collaborative group project we all got into the habit of writing code, then going back and writing obligatory tests to show that it worked. It didn’t take long, as code changed, for errors to start popping up though our tests were still passing. We quickly realized that 1 – our tests weren’t always testing exactly what we thought they were and 2 – we hadn’t been testing enough cases. Testing quickly moved up in priority on our project!

However, it was after a chat with an acquaintance who works in the industry that I decided to try using TDD to actually drive development. I was working on a sorting algorithm using a binary tree and the pattern wasn’t jumping out at me as some of the others had. OK, let’s put TDD to work.

The problem

A binary tree is a data structure that consists of nodes with each node having at most 2 child nodes. An example is given below.

binary-tree

We needed to write an algorithm to take an array of integers and return the sorted array. I realized the problem needed to be broken into two parts – turning an integer array into a sorted binary tree and turning the tree back into an array. The second problem is easier, so let’s tackle that first.

Turning a btree into an array

We want to convert the binary tree into an array from left to right. The tree above should return [4, 2, 5, 1, 3, 6, 7]. Let’s set up an instance method called to_a and a simple test to go with it

Running

from the terminal shows us a failing test of course. The next step is to write the SIMPLEST code that will pass the test. At this step it seems a bit silly, but it sets up the pattern for TDD. Modify our method to return 7.

This gives us a passing test. Ok, let’s add another assertion to our test.

Again, we have a failing test. Fixing it is very simple as we recognize that in each case we are returning the payload attribute.

Passing, again. We can add an assertion for our other childless node if we want to assure ourselves that the method will still work and we can convince ourselves that this method will work for any childless node. Now let’s add an assertion for a node with a child.

Once again, we have a failing test. In order to get this to pass we’ll need to add right into our array – but adding right into our array would fail the previous tests, so it needs to be conditional.

This passes our test but it sure doesn’t look clean or repeatable. Let’s add another failing assertion to see where it takes us.

Now, we will need more complex code, because this example wants a return value of

which tells us that a recursive function is definitely a good way to go. We quickly realize that right.payload is just right.to_a. Let’s try a recursive function.

It worked! Try adding a new assertion

and we find that it fails again, of course, because we’ve only given the right side of the tree. We can fill in the left side to get our test to pass. Then, check that the method passes our remaining assertion.

In part II I’ll cover using TDD to create the sorting algorithm.

Comments are closed.