The greatness of TDD illustrated

Arseni Mourzenko
Founder and lead developer
161
articles
February 12, 2017
Tags: featured 8 refactoring 11 unit-testing 5

Dur­ing an in­ter­view, I was asked to solve the fol­low­ing prob­lem:

A val­i­da­tion func­tion takes as in­put a string con­tain­ing paren­the­sis and square brack­ets. It should re­turn true if the clos­ing paren­the­sis and brack­ets are match­ing the open­ing ones, or false oth­er­wise. For in­stance, ([]())[] should be con­sid­ered valid; how­ev­er, ([)] will not.

We'll as­sume that the string con­tains at least one char­ac­ter, and con­tains only valid char­ac­ters.

This is one of the prob­lems which is ex­treme­ly easy to solve when you know the an­swer, and much more dif­fi­cult when you don't (which makes it a poor choice for an in­ter­view ques­tion). Some­how, I achieved to an­swer it cor­rect­ly by writ­ing the cor­re­spond­ing code. Af­ter get­ting back home, I de­cid­ed to retry the prob­lem from the per­spec­tive of TDD and was sur­prised how eas­i­er was it to find the al­go­rithm. In this case, TDD re­al­ly helped split­ting the prob­lem in small chunks, and solve it step by step. Let me show you how it works.

I'll start by cre­at­ing the di­rec­to­ry struc­ture:

/example/
    validator/
        __init__.py
        test_validator.py
        validator.py
    __init__.py

Both __init__.py files are emp­ty. The orig­i­nal con­tents of the oth­er files are:

test_validator.py
import unittest
from .validator import is_valid


class ValidatorTests(unittest.TestCase):
    pass
validator.py
def is_valid(pattern):
    pass

What could be the most ba­sic test which could show that our im­ple­men­ta­tion is yet slight­ly im­per­fect? What about a valid string?

Test 1: valid string

def test_valid(self):
    self.assertTrue(is_valid("([])"))

As a re­sult of run­ning the tests (python3 -m unittest), we get the fol­low­ing er­ror:

AssertionError: None is not true

Great. Let's fix our code:

def is_valid(pattern):
    return True

Now, the test pass­es. What about a sec­ond most ba­sic test we could add to show that the code is still not fin­ished?

Test 2: in­valid string

def test_invalid(self):
    self.assertFalse(is_valid("([])["))

Let's check it. In­deed, it fails:

AssertionError: True is not false

How to fix the code? We could start by imag­in­ing our fu­ture al­go­rithm which will some­how do the match of the brack­ets, or we can get re­al­ly lazy and sim­ply do:

def is_valid(pattern):
    return not len(pattern) % 2

The sud­den ben­e­fit of our TDD ap­proach is that with­out think­ing much about the prob­lem, we fig­ured out one of its pos­si­ble op­ti­miza­tions: when­ev­er the string con­tains an odd num­ber of char­ac­ters, it is in­valid. There is no need to check what's in­side: we know it can­not be valid in­de­pen­dent­ly of the con­tents. I missed this point en­tire­ly dur­ing the in­ter­view, while it rep­re­sents an im­por­tant (and very sim­ple) op­ti­miza­tion.

Let's refac­tor the method to em­pha­size the edge case of the string con­tain­ing an odd num­ber of char­ac­ters:

def is_valid(pattern):
    if len(pattern) % 2:
        # Patterns with an odd number of characters are necessarily invalid.
        return False
    
    return True

All tests still pass af­ter the refac­tor­ing.

What oth­er test could be per­formed to in­val­i­date the cur­rent code? Since strings con­tain­ing odd num­ber of char­ac­ters are fil­tered out, our next test should con­cern those with the even num­ber of char­ac­ters; and since for those ones, the method will re­turn true every time, we need to find a string which should be con­sid­ered in­valid.

Test 3: in­valid string with an even num­ber of char­ac­ters

def test_invalid_even(self):
    self.assertFalse(is_valid("([[)"))

Run­ning the tests gives the fol­low­ing er­ror for the last one:

AssertionError: True is not false

Fix­ing the code re­quires to in­tro­duce a counter:

def is_valid(pattern):
    if len(pattern) % 2:
        # Patterns with an odd number of characters are necessarily invalid.
        return False
    
    counter = 0
    for c in pattern:
        counter += (1 if c in ('(', '[') else -1)

    return counter == 0

I don't like this code. It's over­ly com­plex. Since all three tests now pass, I'll slight­ly refac­tor the method. The first pass con­sists of mov­ing the new­ly in­tro­duced log­ic into a sep­a­rate method:

def is_valid(pattern):
    if len(pattern) % 2:
        # Patterns with an odd number of characters are necessarily invalid.
        return False
    
    return _is_valid_odd(pattern)

def _is_valid_odd(pattern):
    counter = 0
    for c in pattern:
        counter += (1 if c in ('(', '[') else -1)

    return counter == 0

The sec­ond pass fo­cus­es on the cryp­tic con­di­tion:

def _is_valid_odd(pattern):
    counter = 0
    for c in pattern:
        counter += 1 if _is_opening(c) else -1

    return counter == 0

def _is_opening(bracket):
    return bracket in ('(', '[')

Al­though the += 1 if x else -1 frag­ment looks a bit too “clever,” I de­cide to keep it, since a more ex­plic­it vari­ant with two counter op­er­a­tions in­side an if/else block will take too much place while hav­ing only a slight read­abil­i­ty ben­e­fit.

What else could be test­ed? Seems like the new­ly in­tro­duced counter is easy to trick. Since it makes no dif­fer­ence be­tween paren­the­sis and brack­ets, let's use it to our ad­van­tage.

Test 4: trick­ing the counter

def test_invalid_type_mismatch(self):
    self.assertFalse(is_valid("((]]"))

Seems like we need to add an ex­tra counter:

def _is_valid_odd(pattern):
    counters = { "parenthesis": 0, "square": 0 }
    for c in pattern:
        counter_type = "parenthesis" if _is_parenthesis(c) else "square"
        change = 1 if _is_opening(c) else -1
        counters[counter_type] += change

    return all(x == 0 for x in counters.values())

def _is_opening(bracket):
    return bracket in ('(', '[')

def _is_parenthesis(bracket):
    return bracket in ('(', ')')

The test pass­es, but I don't like the code. Let's refac­tor it. The keys of the coun­ters, how­ev­er ex­plic­it they are, feel too long. There is a way to short­en them while keep­ing them ex­plic­it enough:

def _is_valid_odd(pattern):
    counters = { "(...)": 0, "[...]": 0 }
    for c in pattern:
        counter_type = "(...)" if _is_parenthesis(c) else "[...]"
        change = 1 if _is_opening(c) else -1
        counters[counter_type] += change

    return all(x == 0 for x in counters.values())

That looks right. I could have in­tro­duced con­stants to re­place the four strings, but I don't think it would en­hance the read­abil­i­ty of the code, while mak­ing it quite longer. An­oth­er refac­tor­ing short­ens the _is_* meth­ods:

def _is_opening(bracket):
    return bracket in "(["

def _is_parenthesis(bracket):
    return bracket in "()"

It looks like we now han­dled most of the cas­es, but there is still one which will make our code fail: the one where paren­the­sis and brack­ets are in­ter­mixed.

Test 5: in­ter­mixed brack­ets

The prob­lem is the fol­low­ing. If paren­the­sis and brack­ets are not closed in the in­verse or­der com­pared to the one in which they were opened, the string should be con­sid­ered in­valid. How­ev­er, coun­ters we are ac­tu­al­ly use don't have any no­tion of or­der.

def test_invalid_intermixed(self):
    self.assertFalse(is_valid("([)]"))

This test fails, be­cause the coun­ters blind­ly match the clos­ing brack­ets to the open­ing ones. Since both coun­ters are equal to zero at the end of the string, the test­ed method re­turns True, de­spite the fact that the string is in­valid.

To make this test pass, we may re­place the coun­ters by a stack:

def _is_valid_odd(pattern):
    stack = []
    for c in pattern:
        if _is_opening(c):
            stack.append(c)
        elif _get_matching_opening(c) != stack.pop():
            return False

    return True

def _is_opening(bracket):
    return bracket in "(["

def _get_matching_opening(bracket):
    return {
        ")": "(",
        "]": "[",
    }[bracket]

It's time for refac­tor­ing. I don't think hav­ing a _get_matching_opening and a sep­a­rate com­par­i­son with the re­sult of stack.pop() makes much sense. Why not mov­ing the com­par­i­son in a method?

def _is_valid_odd(pattern):
    stack = []
    for c in pattern:
        if _is_opening(c):
            stack.append(c)
        elif not _is_match(stack.pop(), c):
            return False
        
    return True

def _is_opening(bracket):
    return bracket in "(["
    
def _is_match(opening, closing):
    return opening + closing in ("()", "[]")

For those of you who know Python, you may no­tice that I in­tro­duced a po­ten­tial bug. stack.pop()will fail when­ev­er the stack is emp­ty. Let's test this case.

Test 6: clos­ing be­fore open­ing

def test_invalid_closing(self):
    self.assertFalse(is_valid(")("))

gives us a scary:

IndexError: pop from empty list

Wow. An ex­cep­tion. Al­though the orig­i­nal spec doesn't tell any­thing about the case where the brack­et is closed be­fore be­ing opened, I would as­sume that the string should be con­sid­ered in­valid.

The case can be han­dled in two ways: ei­ther by ex­plic­it­ly check­ing the length of the stack be­fore ex­e­cut­ing stack.pop(), or by han­dling the cor­re­spond­ing ex­cep­tion. I'll use the first one, since it makes my code sim­pler:

def _is_valid_odd(pattern):
    stack = []
    for c in pattern:
        if _is_opening(c):
            stack.append(c)
        elif len(stack) == 0:
            return False
        elif not _is_match(stack.pop(), c):
            return False
        
    return True

I find that the re­peat­ed return False looks ugly here. Let's refac­tor that.

def _is_valid_odd(pattern):
    stack = []
    for c in pattern:
        if _is_opening(c):
            stack.append(c)
        elif len(stack) == 0 or not _is_match(stack.pop(), c):
            return False
        
    return True

But now, I have no freak­ing idea what's the elif con­di­tion is all about. Seems like a sit­u­a­tion where one could in­tro­duce a method:

def _is_valid_odd(pattern):
    stack = []
    for c in pattern:
        if _is_opening(c):
            stack.append(c)
        elif not _is_match_from_stack(stack, c):
            return False
        
    return True

def _is_match_from_stack(stack, closing):
    if len(stack) == 0:
        return False
    
    return _is_match(stack.pop(), closing)

Test 7: open­ing, but not clos­ing

What else could we add as a test which will fail with the cur­rent im­ple­men­ta­tion? If we close a brack­et which wasn't opened pre­vi­ous­ly, the code will fail, giv­en the pre­vi­ous change. But what if we open a brack­et with­out clos­ing it?

def test_invalid_closing_missing(self):
    self.assertFalse(is_valid("(("))

In­deed, the ac­tu­al use of the stack fails in this case. A tiny change fix­es that:

def _is_valid_odd(pattern):
    stack = []
    for c in pattern:
        if _is_opening(c):
            stack.append(c)
        elif not _is_match_from_stack(stack, c):
            return False

    return len(stack) == 0

A few oth­er refac­tor­ings con­sist­ing of re­order­ing the meth­ods, chang­ing the names of vari­ables and mak­ing len(stack) == 0 ex­plic­it leads to the fol­low­ing fi­nal piece of code:

def is_valid(pattern):
    if len(pattern) % 2:
        # Patterns with an odd number of characters are necessarily invalid.
        return False

    return _is_valid_odd(pattern)

def _is_valid_odd(pattern):
    stack = []
    for bracket in pattern:
        if _is_opening(bracket):
            stack.append(bracket)
        elif not _is_match_from_stack(stack, bracket):
            return False

    return _is_empty(stack)

def _is_match_from_stack(stack, closing):
    if _is_empty(stack):
        return False

    return _is_match(stack.pop(), closing)

def _is_match(opening, closing):
    return opening + closing in ("()", "[]")

def _is_opening(bracket):
    return bracket in "(["

def _is_empty(stack):
    return len(stack) == 0

As you can see, TDD helped:

There­fore, TDD is great. Use it. Se­ri­ous­ly.