The greatness of TDD illustrated
During an interview, I was asked to solve the following problem:
A validation function takes as input a string containing parenthesis and square brackets. It should return
trueif the closing parenthesis and brackets are matching the opening ones, orfalseotherwise. For instance,([]())[]should be considered valid; however,([)]will not.
We'll assume that the string contains at least one character, and contains only valid characters.
This is one of the problems which is extremely easy to solve when you know the answer, and much more difficult when you don't (which makes it a poor choice for an interview question). Somehow, I achieved to answer it correctly by writing the corresponding code. After getting back home, I decided to retry the problem from the perspective of TDD and was surprised how easier was it to find the algorithm. In this case, TDD really helped splitting the problem in small chunks, and solve it step by step. Let me show you how it works.
I'll start by creating the directory structure:
/example/
validator/
__init__.py
test_validator.py
validator.py
__init__.py
Both __init__.py files are empty. The original contents of the other 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 basic test which could show that our implementation is yet slightly imperfect? What about a valid string?
Test 1: valid string
def test_valid(self):
self.assertTrue(is_valid("([])"))
As a result of running the tests (python3 -m unittest), we get the following error:
AssertionError: None is not true
Great. Let's fix our code:
def is_valid(pattern):
return True
Now, the test passes. What about a second most basic test we could add to show that the code is still not finished?
Test 2: invalid string
def test_invalid(self):
self.assertFalse(is_valid("([])["))
Let's check it. Indeed, it fails:
AssertionError: True is not false
How to fix the code? We could start by imagining our future algorithm which will somehow do the match of the brackets, or we can get really lazy and simply do:
def is_valid(pattern):
return not len(pattern) % 2
The sudden benefit of our TDD approach is that without thinking much about the problem, we figured out one of its possible optimizations: whenever the string contains an odd number of characters, it is invalid. There is no need to check what's inside: we know it cannot be valid independently of the contents. I missed this point entirely during the interview, while it represents an important (and very simple) optimization.
Let's refactor the method to emphasize the edge case of the string containing an odd number of characters:
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 after the refactoring.
What other test could be performed to invalidate the current code? Since strings containing odd number of characters are filtered out, our next test should concern those with the even number of characters; and since for those ones, the method will return true every time, we need to find a string which should be considered invalid.
Test 3: invalid string with an even number of characters
def test_invalid_even(self):
self.assertFalse(is_valid("([[)"))
Running the tests gives the following error for the last one:
AssertionError: True is not false
Fixing the code requires to introduce 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 overly complex. Since all three tests now pass, I'll slightly refactor the method. The first pass consists of moving the newly introduced logic into a separate 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 second pass focuses on the cryptic condition:
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 ('(', '[')
Although the += 1 if x else -1 fragment looks a bit too “clever,” I decide to keep it, since a more explicit variant with two counter operations inside an if/else block will take too much place while having only a slight readability benefit.
What else could be tested? Seems like the newly introduced counter is easy to trick. Since it makes no difference between parenthesis and brackets, let's use it to our advantage.
Test 4: tricking the counter
def test_invalid_type_mismatch(self):
self.assertFalse(is_valid("((]]"))
Seems like we need to add an extra 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 passes, but I don't like the code. Let's refactor it. The keys of the counters, however explicit they are, feel too long. There is a way to shorten them while keeping them explicit 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 introduced constants to replace the four strings, but I don't think it would enhance the readability of the code, while making it quite longer. Another refactoring shortens the _is_* methods:
def _is_opening(bracket):
return bracket in "(["
def _is_parenthesis(bracket):
return bracket in "()"
It looks like we now handled most of the cases, but there is still one which will make our code fail: the one where parenthesis and brackets are intermixed.
Test 5: intermixed brackets
The problem is the following. If parenthesis and brackets are not closed in the inverse order compared to the one in which they were opened, the string should be considered invalid. However, counters we are actually use don't have any notion of order.
def test_invalid_intermixed(self):
self.assertFalse(is_valid("([)]"))
This test fails, because the counters blindly match the closing brackets to the opening ones. Since both counters are equal to zero at the end of the string, the tested method returns True, despite the fact that the string is invalid.
To make this test pass, we may replace the counters 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 refactoring. I don't think having a _get_matching_opening and a separate comparison with the result of stack.pop() makes much sense. Why not moving the comparison 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 notice that I introduced a potential bug. stack.pop()will fail whenever the stack is empty. Let's test this case.
Test 6: closing before opening
def test_invalid_closing(self):
self.assertFalse(is_valid(")("))
gives us a scary:
IndexError: pop from empty list
Wow. An exception. Although the original spec doesn't tell anything about the case where the bracket is closed before being opened, I would assume that the string should be considered invalid.
The case can be handled in two ways: either by explicitly checking the length of the stack before executing stack.pop(), or by handling the corresponding exception. I'll use the first one, since it makes my code simpler:
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 repeated return False looks ugly here. Let's refactor 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 freaking idea what's the elif condition is all about. Seems like a situation where one could introduce 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: opening, but not closing
What else could we add as a test which will fail with the current implementation? If we close a bracket which wasn't opened previously, the code will fail, given the previous change. But what if we open a bracket without closing it?
def test_invalid_closing_missing(self):
self.assertFalse(is_valid("(("))
Indeed, the actual use of the stack fails in this case. A tiny change fixes 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 other refactorings consisting of reordering the methods, changing the names of variables and making len(stack) == 0 explicit leads to the following final 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:
- Finding a solution step by step, without thinking too much about the problem itself,
- Discovering a useful and very easy to implement optimization,
- Writing reliable and readable code.
Therefore, TDD is great. Use it. Seriously.