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.

# binary_tree_sort.rb
require_relative 'binary_tree_sort_test'

class BinaryTree
  attr_accessor :payload, :left, :right

  def initialize(payload, left, right)
    @payload = payload
    @left = left
    @right = right
  end

  def to_a
    return left.to_a + [payload] + right.to_a
  end

  def add_node(value)
  end

  def self.sort(ary)
    return nil if ary.nil?
    btree = BinaryTree.new(ary.shift, nil, nil)
    until ary.count == 0
      if ary[0] > btree.payload
        btree.right = BinaryTree.new(ary.shift, nil, nil)
      else
        btree.left = BinaryTree.new(ary.shift, nil, nil)
      end
    end
    return btree.to_a
  end

# binary_tree_sort_test.rb
require 'minitest/autorun'

class Tester < Minitest::Unit::TestCase
  def setup
    @seven = BinaryTree.new(7, nil, nil)
    @five  = BinaryTree.new(5, nil, nil)
    @four  = BinaryTree.new(4, nil, nil)
    @six   = BinaryTree.new(6, nil, @seven)
    @three = BinaryTree.new(3, nil, @six)
    @two   = BinaryTree.new(2, @four, @five)
    @trunk = BinaryTree.new(1, @two, @three)
  end

  def test_btree_to_array
    assert_equal [7], @seven.to_a
    assert_equal [5], @five.to_a
    assert_equal [4], @four.to_a
    assert_equal [6, 7], @six.to_a
    assert_equal [3, 6, 7], @three.to_a
    assert_equal [4, 2, 5], @two.to_a
    assert_equal [4, 2, 5, 1, 3, 6, 7], @trunk.to_a
  end

  def test_btree_nil
    assert_equal nil, BinaryTree.sort(nil)
  end

  def test_btree_sort_ary_n_1
    assert_equal [1], BinaryTree.sort([1])
    assert_equal [7], BinaryTree.sort([7])
  end

  def test_btree_sort_ary_n_2
    assert_equal [1, 7], BinaryTree.sort([1, 7])
    assert_equal [1, 7], BinaryTree.sort([7, 1])
    assert_equal [6, 6], BinaryTree.sort([6, 6])
    assert_equal [-5, 0], BinaryTree.sort([0, -5])
  end

  def test_btree_sort_ary_n_3
    assert_equal [4, 7, 15], BinaryTree.sort([7, 4, 15])
    assert_equal [7, 14, 15], BinaryTree.sort([7, 14, 15])
  end
end

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

# binary_tree_sort.rb
  def add_node(new_value)
    if new_value > self.payload
      self.right = BinaryTree.new(new_value, nil, nil)
    else
      self.left = BinaryTree.new(new_value, nil, nil)
    end
  end


  def self.sort(ary)
    return nil if ary.nil?
    btree = BinaryTree.new(ary.shift, nil, nil)
    until ary.count == 0
      btree.add_node(ary.shift)
    end
    return btree.to_a
  end

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.

# binary_tree_sort.rb
  def add_node(new_value)
    placed = false
    current_node = self
    until placed
      if new_value > current_node.payload 
        if current_node.right.nil?
          current_node.right = BinaryTree.new(new_value, nil, nil)
          placed = true
        end
      else
        if current_node.left.nil?
          current_node.left = BinaryTree.new(new_value, nil, nil)
          placed = true
        end
      end
    end
  end

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.

# binary_tree_sort.rb
  def add_node(new_value)
    placed = false
    current_node = self
    until placed
      if new_value > current_node.payload 
        if current_node.right.nil?
          current_node.right = BinaryTree.new(new_value, nil, nil)
          placed = true
        else
          current_node = current_node.right
        end
      else
        if current_node.left.nil?
          current_node.left = BinaryTree.new(new_value, nil, nil)
          placed = true
        else
          current_node = current_node.left
        end
      end
    end
  end

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

sorted_array = BinaryTree.sort(unsorted_array)

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

# binary_tree_sort_test.rb
  def test_nil
    assert nil, BinaryTree.sort(nil), 'Should return nil on nil input'
  end

#binary_tree_sort.rb
  def self.sort(ary)
  end

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

#binary_tree_sort.rb
  def self.sort(ary)
    nil
  end

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

# binary_tree_sort_test.rb
  def test_ary_of_n_1
    assert [1], BinaryTree.sort([1]), 'Should return array of n=1 unchanged'
  end

Test fails. Modify to pass.

#binary_tree_sort.rb
  def self.sort(ary)
    ary
  end

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.

# binary_tree_sort_test.rb
  def test_ary_of_n_1
    assert [1], BinaryTree.sort([1]), 'Should return array of n=1 unchanged'
    assert [7], BinaryTree.sort([7]), 'Should return array of n=1 unchanged'
  end

Still passes. Time to make the test array bigger.

# binary_tree_sort_test.rb
  def test_ary_of_n_2
    assert [1, 7], BinaryTree.sort([1, 7]), 'Should return sorted array of n=2 sorted'
  end

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

  def self.sort(ary)
    return nil if ary.nil?
    btree = BinaryTree.new(ary[0], nil, nil) if ary.count == 1
    btree = BinaryTree.new(ary[0], nil, BinaryTree.new(ary[1], nil, nil) )
    return btree.to_a
  end

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

# binary_tree_sort_test.rb
  def test_ary_of_n_2
    assert [1, 7], BinaryTree.sort([1, 7]), 'Should return sorted array of n=2 sorted'
    assert [1, 7], BinaryTree.sort([7, 1]), 'Should return unsorted array of n=2 sorted'
  end

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

Expected: [1, 7]
Actual: [7, 1]

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

# binary_tree_sort.rb
  def self.sort(ary)
    return nil if ary.nil?
    btree = BinaryTree.new(ary[0], nil, nil) if ary.count == 1
    if ary[0] > ary[1]
      btree = BinaryTree.new(ary[0], BinaryTree.new(ary[1], nil, nil), nil)
    else
      btree = BinaryTree.new(ary[0], nil, BinaryTree.new(ary[1], nil, nil))
    end

    return btree.to_a
  end

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.

# binary_tree_sort.rb
  def self.sort(ary)
    return nil if ary.nil?
    
    btree = BinaryTree.new(ary.shift, nil, nil)

    unless ary.count == 0
      if ary[0] > btree.payload
        btree.right = BinaryTree.new(ary.shift, nil, nil)
      else
        btree.left = BinaryTree.new(ary.shift, nil, nil)
      end
    end

    return btree.to_a
  end

It passes. Let’s add more tests.

# binary_tree_sort_test.rb
  def test_btree_sort_ary_n_2
    assert_equal [1, 7], BinaryTree.sort([1, 7])
    assert_equal [1, 7], BinaryTree.sort([7, 1])
    assert_equal [6, 6], BinaryTree.sort([6, 6])
    assert_equal [-5, 0], BinaryTree.sort([0, -5])
  end

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

# binary_tree_sort_test.rb
  def test_btree_sort_ary_n_3
    assert_equal [4, 7, 15], BinaryTree.sort([7, 4, 15])
  end

# outcome
Expected: [4, 7, 15]
Actual: [4, 7]

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

      until ary.count == 0

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

# binary_tree_sort_test.rb
  def test_btree_sort_ary_n_3
    assert_equal [4, 7, 15], BinaryTree.sort([7, 4, 15])
    assert_equal [7, 14, 15], BinaryTree.sort([7, 14, 15])
  end

#outcome
Expected: [7, 14, 15]
Actual: [7, 15]

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

      btree.add_node(ary.shift)

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

# binary_tree_sort.rb
require_relative 'binary_tree_sort_test'

class BinaryTree
    attr_accessor :payload, :left, :right

    def initialize(payload, left, right)
        @payload = payload
        @left = left
        @right = right
    end

end

# binary_tree_sort_test.rb
require 'minitest/autorun'

class Tester < Minitest::Unit::TestCase
  def setup
    @seven = BinaryTree.new(7, nil, nil)
    @five  = BinaryTree.new(5, nil, nil)
    @four  = BinaryTree.new(4, nil, nil)
    @six   = BinaryTree.new(6, nil, @seven)
    @three = BinaryTree.new(3, nil, @six)
    @two   = BinaryTree.new(2, @four, @five)
    @trunk = BinaryTree.new(1, @two, @three)
  end
end

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

# binary_tree_sort.rb
  def to_a
  end

# binary_tree_sort_test.rb
  test 'Should return array from tree'
    assert_equal [7], @seven.to_a
  end

Running

ruby binary_tree_sort.rb

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.

# binary_tree_sort.rb
  def to_a
    [7]
  end

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

# binary_tree_sort_test.rb
    assert_equal [5], @five.to_a

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

# binary_tree_sort.rb
  def to_a
    [payload]
  end

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.

# binary_tree_sort_test.rb
    assert_equal [6, 7], @six.to_a

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.

# binary_tree_sort.rb
  def to_a
    if right.nil?
      return [payload]
    else
      return [payload, right.payload]
    end
  end

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.

# binary_tree_sort_test.rb
    assert_equal [3, 6, 7], @three.to_a

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

    [payload, right.payload, right.right.payload]

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.

# binary_tree_sort.rb
  def to_a
    return [payload] + right.to_a
  end

It worked! Try adding a new assertion

# binary_tree_sort_test.rb
    assert_equal [4, 2, 5], @two.to_a

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.

# binary_tree_sort.rb
  def to_a
    return left.to_a + [payload] + right.to_a
  end

# binary_tree_sort_test.rb
    assert_equal [4, 2, 5, 1, 3, 6, 7], @trunk.to_a

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