Browsed by
Author: aaron

Using TDD to solve algorithms, Part III

Using TDD to solve algorithms, Part III

After Part I and Part II we were left with the following code and a failing test – our binary tree placed 7 at the trunk, 14 on the right node then 15 in place of the 14. We need the tree to place the 15 as the right node of the 14 node. We had decided that the best way to do this was to create a separate function for adding nodes which I’ve included as add_node.

Refactoring with the new method, but no change in functionality gives us

Sure enough, we get the same failing test as before. We are going to need to go deeper into the btree. It makes sense to define a pointer that refers to the current node and a boolean flag to let us know when we’ve finally placed the node. We know that we should place the new value only into a nil branch, so we’ll check for that.

Instead of failing tests, this hangs our program in an infinite loop as there are cases where placed is never set to true. Something has to happen when we can’t place the value and that, of course is that we set the current_node to move down the tree to the branch we just checked.

This code passes our tests and further testing fails to break it. This is our binary tree sort.

Using TDD to solve algorithms, Part II

Using TDD to solve algorithms, Part II

In Part I, I went over using TDD to turn an existing binary tree into an ordered array of integers. Here in Part II we’ll use TDD to build a sorted binary tree from an unsorted array of integers. So, the entire flow will be [unsorted_integers] –> sorted_binary_tree –> [sorted_integers].

Since we’re starting with an array and ending with an array I didn’t see any need to create an instance of BinaryTree each time we use it. Instead I created a class method that will be called as

Let’s write a test as well as the method signature. Run the code and see a failing test.

Let’s return nil from our method to get a passing test.

We got an edge case out of the way. Let’s add another test.

Test fails. Modify to pass.

Pass. Again, we KNOW this is the wrong answer, but it’s the simplest answer to make our tests pass. Since we know it’s not the final goal we need to write another test.

Still passes. Time to make the test array bigger.

Passes again but we haven’t introduced the binary tree yet. Let’s do that and we’ll see that the code starts to get messier

This still passes but it’s not very pretty. We add another test.

And this, of course fails. The array wasn’t sorted.

Let’s add a conditional statement to our code to get the second integer onto the correct branch.

It passes again, but it’s really looking like a mess. However, we can see two things – 1. We are going to need a recursive function as we have btrees nested in btrees. 2. We are going to need a conditional statement to determine where to put child branches.
Let’s do some minor refactoring. I know the first item in the ary is going to be at the top of the btree and I know I won’t need it again. If I shift it off the array I can easily access the next item without indexing. Next, I recognize that as long as there are numbers left in my array I need to add a branch to the btree so I wrap the if/else/end statement in an unless ary.count == 0. I can then add the next integer as a btree node on the appropriate side using the left and right methods.

It passes. Let’s add more tests.

This still passes. We’re good on 2 integer arrays. Let’s try 3.

Fail. Of course, we’ve only set up our btree to add 2 branches. Change our unless statement to

to create a loop and our test passes. Add another test to try to break it with integers in a different order.

We have a failing test and can look through our method and see why. The 14 was placed on the right of the 7, then it was replaced with the 15. We need to go deeper to find the correct node. This method is starting to do a lot of things so it makes sense to create a new method with the sole responsibility of adding a node in the right place. From inside our unless loop we will call

In Part III we’ll factor out that method and finish up the algorithm. In the meantime, keep adding tests and making them to pass.

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.