Finally, Redundancy in TDD

It took me a while, but I finally remember a case of true redundancy in a test case. I was at the Codemash pre-compiler learning Ruby from Jim Weirich. I had just finished a 1/2 day Ruby Koans session and was hot to try out my new skills, so I plopped down on a couch with a few others and we started banging away on a problem. We decided as a group to each build the same application in different languages and see what the differences were. I'm not going to name names here, but I'll say we had Ruby, Python, Perl, Grails, and Scala all rolling in the same small space for a little while. Our problem was Sudoku Solver if I remember correctly.

I was having a wonderful time banging away on this problem. First off, I love puzzles, second I love automating their solutions. We were working our way through test cases on the board and the topic came up about checking for duplicates in a row. If you aren't familiar with Sudoku, using the numbers 1-9 you populate an 81 cell board such that no number appears twice in the same row or column and each sub-grid contains only the numbers 1-9 without duplicates. Therefore, you could test each column, row, and sub-grid for these conditions and if all of these things are true you've solved the puzzle. 

But think about this in terms of your code and the abstractions of the playing board. Does your row checker need to check every row? Does your column checker need to check each column? I think a conscientious design suggests not. What you need is a Nine-Unique-Numbers checker. So in my test suite there are a couple tests for 'row has digit' and 'column has digit' but by no means did I check every single column. You can check out my code here. 

Just to be clear, I'm not holding my solver up as the bastion of awesome, I'm just using the example. After rereading that code for this post I'm thinking its a little embarrassing and I should rewrite it ;-).

So all of this lead to some discussion. How thorough do you need to be in order to ensure proper behavior of your solver? On of the other people at the table had very thoroughly written explicit tests for each row, column, and grid (subsection) of the board and tested each case to ensure that he has 100% coverage. I think he went to far. I'd call it 1000% coverage. I say that because after the first few proofs, those others are redundant. Unless you have an impossibly flawed design, the conditions don't vary much from column to column or row to row. Looking at my code you will see I isolated the get_col, get_row, and get_section code. To check for numbers in those structures I flatten the content into an array and check to see if the number is present (see row_has_digit, col_has_digit, and section_has_digit) [oops, I just found a damp spot in that code, do you see it?]

My point is, once I have row_has_digit isolated from get_row I can test each independently and in total isolation. I minimize the number of tests while maximizing the clarity of what I'm doing as an expression in tests. 

My cohort had rather brutally tested every possible combination regardless of it being redundant. He used parameterized tests and loops (two things I distain in a test) and ensured that there was no way his code would ever get it wrong. Now if I'm launching a Mars Lander I *might* take it that far, but for Sudoku no way. To be honest, I couldn't justify it for a Mars Lander either. 

What we know about boolean logic (and others) is that there are only so many conditions that can be tested across an operator. There are a finite (because bits) number of numbers below, equal, and above any other number in a computer. So if we have a condition like '< 5' we can use 2 tests for complete proof our logic goes the right way. Testing the other numbers is wasteful and redundant. [I made this mistake in 2002 when I was just getting into unit tests, my test ran across a 256-bit number, every single combination of bits, and took 13 hours to complete on my clunker IBM Thinkpad, better solution would have been about 16 cases].

So, it took me a while to think of some cases of true redundancy, and to try to answer (at least in part) Tim's question, if you are like the guy in that group, writing a test for every conceivable case, rather than the minimum number of logical cases possible, then yes, you are being redundant and you should stop.

Hopefully I can provide a cogent explanation of how to unwind redundancy. I'll start thinking about that next.