M Bellucci

Posted on Jun 26, 2019

A TDD Example

#tdd #ruby

Introduction

As part of my TDD learning process I faced this problem and found hard to solve it following the TDD rules.
So I started this discussion --> https://dev.to/delbetu/solve-this-simple-problem-with-tdd-5e41

The TDD process I tried to follow at that point was:

Write a set of tests (input--->expected-output)
Pick the simplest test case to solve. (RED)(Write a failing spec)
Write the most naive code change that solves the current set of tests. (GREEN)
Check if DRY is needed (Refactor)
Go back to 2

The change that made me reach the solution

Instead of creating a predefined set of test I created a new test conveniently for each TDD cycle.

Write a test case conveniently for the current state of the algorithm (RED)
Write the most naive code change that solves the current set of tests. (GREEN)
DRY if needed (Refactor)
Go back to 1

In the example we will understand what conveniently means.

The Problem

flatten an array of arbitrarily nested arrays of integers into a flat array of integers. e.g. [[1,2,[3]],4] -> [1,2,3,4].

Before you continue reading try to solve it with TDD.

Hands on!

Cycle 1

def test_empty
  assert_equal [], flatten([])
end

def flatten(array_tree)
  []
end

Cycle 2

def test_no_subarray_one_element
  assert_equal [1], flatten([1])
end

def flatten(array_tree)
  array_tree
end

Cycle 3

The first and only element is an array.
At this point I decided decided to tackle the recursiveness behavior of the algorithm.
So I conveniently chose the next set of test cases.

def test_with_subarray_one_element
  assert_equal [1], flatten([[1]])
end

def flatten(array_tree)
 if array_tree[0].is_a?(Array)
   array_tree[0]
 else
   array_tree
 end
end

Cycle 4

def test_with_subarray_one_element
  assert_equal [1], flatten([[1]])
end

def flatten(array_tree)
  if array_tree[0].is_a?(Array)
    array_tree[0]
  else
    array_tree
  end
end

Cycle 5

def test_with_subsubarray_one_element
  assert_equal [1], flatten([[[1]]])
end

def flatten(array_tree)
  if array_tree[0].is_a?(Array)
    if array_tree[0][0].is_a?(Array)
      array_tree[0][0]
    else
      array_tree[0]
    end
  else
    array_tree
  end
end

Cycle 6

At this point you can recognize a recursive pattern.

def test_with_subsubarray_one_element
  assert_equal [1], flatten([[[[1]]]])
end

def flatten(array_tree)
  if array_tree[0].is_a?(Array)
    if array_tree[0][0].is_a?(Array)
      if array_tree[0][0][0].is_a?(Array)
        array_tree[0][0][0]
      else
        array_tree[0][0]
      end
    else
      array_tree[0]
    end
  else
    array_tree
  end
end

# Refactor
def flatten(array_tree)
  if array_tree[0].is_a?(Array)
    flatten(array_tree[0])
  else
    array_tree
  end
end

Cycle 7

At this point I realized of two things about the generalization of the algorithm.
(Left in comments)
These two points will make me pick the test for generalize that part of the behavior in future tests.

def test_when_first_and_second_are_subarray
  assert_equal [1,2], flatten([[1], [2]])
end

def flatten(array_tree)
  if array_tree[0].is_a?(Array)
    result = flatten(array_tree[0]) # I will need this for each sub_array
    if array_tree[1].is_a?(Array)
      result = result + flatten(array_tree[1])
    end
    result
  else
    array_tree # This should return only the numbers not the subarrays
  end
end

Cycle 8

At this point I realized how to combine the recursive calls, so I decided to refactor.

def test_when_all_are_subarrays
  assert_equal [1, 2, 3], flatten([[1], [2], [3]])
end

def flatten(array_tree)
  if array_tree[0].is_a?(Array)
    result = flatten(array_tree[0]) # call flatten for each sub_array and concatenate results
    if array_tree[1].is_a?(Array)
      result = result + flatten(array_tree[1])
      if array_tree[2].is_a?(Array)
        result = result + flatten(array_tree[2])
      end
    end

    result
  else
    array_tree # elements without subarrays
  end
end

# Refactor --> Generalize the ifs
def flatten(array_tree)
  if array_tree[0].is_a?(Array)
    sub_arrays = array_tree.select {|x| x.is_a?(Array)}
    sub_arrays.reduce([]) do |result, sub_array|
      result + flatten(sub_array)
    end
  else
    array_tree
  end
end

Cycle 9

Tackling one of the pending behaviors found in cycle 5.
The else branch should return only the numbers not the subarrays
If the first element of the input is a number but the second is a subarray then the else branch would fail.
So the next test could be:
[1, [2]] --> [1, 2]

def test_when_first_is_number_and_second_is_subarray
  assert_equal [1, 2], flatten([1, [2]])
end

def flatten(array_tree)
  result = array_tree.reject {|x| x.is_a?(Array)} # elements without subarrays
  sub_arrays = array_tree.select {|x| x.is_a?(Array)}
  result = result + sub_arrays.reduce([]) do |accumulator, sub_array|
    accumulator + flatten(sub_array)
  end
end

Cycle 10

At this point I think I found the generalized solution so the next test is a complicated case.

def test_complicated_case
  assert_same_elements [1, 2, 3, 4, 5, 6, 7, 8, 9, 0], flatten([[[1, 2, 3]], [4, [5, 6]], 7, [[[[8]], 9]], 0])
end

def flatten(array_tree)
  result = array_tree.reject {|x| x.is_a?(Array)} # elements without subarrays
  sub_arrays = array_tree.select {|x| x.is_a?(Array)}
  result = result + sub_arrays.reduce([]) do |accumulator, sub_array|
    accumulator + flatten(sub_array)
  end
end

private

def assert_same_elements(array1, array2)
  assert array1 - array2 == []
end

Thanks for reading,
Comments are welcome!

DEV Community