Extreme Enthusiasm

Know your stuff

A while ago we had a fun evening at the Milano XPUG writing a Sudoku solver. I blogged about my solution. I’m not particularly proud of it, in retrospect. The code and the tests are not obvious. I can’t read any of it and be certain that it works. It does not speak.

It is true that solving puzzles like Sudoku is quite different from what application programmers do everyday at work. Why is it that? The problems that we solve in business applications do not have that mathematical crispness that puzzles have. Perhaps it’s because we’re not good enough at analyzing them and expressing them abstractly. That would explain why business code is so long, convoluted and expensive.

Anyway, the point I want to make is that it is not satisfying to use the tests in TDD as a crutch for constructing hapazard code that, with a kick here and a few hammer blows there seem to work. The point of TDD is to *design* code; and a good design shows how and why a solution works.

I often see people doing katas that involve problems with well-known solutions. We usually disregard, forget, or ignore the well-known solution! And we keep writing tests and production code until we rig together something that passes the tests. It’s painful. I know. I too did some of that.

TDD does not work well when we don’t know what we’re doing. Some high-profile XPers failed to ship when TDDing their way with unfamiliar APIs or disregarding known solutions. TDD is no substitute for analyzing a problem, and finding abstractions that make it easy to solve. TDD without thinking and analyzing and abstracting is not fun!.

It’s for this reason that there is the XP practice of “spiking solutions”, that is, take time to learn how to do something, make experiments, then apply what you learned. If you know how to do things, you will not spend hours discussing with your pair; you and your pair will grab the keyboard from each other, as Francesco Cirillo often says.

A better way

Consider Sudoku again. Peter Norvig solves it in two different ways by using known techniques. The first solution is depth-first search, which is gueranteed to terminate as the graph of Sudoku states is acyclic. The other is by constraint propagation. If I were to do the exercise again, I would try to make the analysis apparent from the code.

Say we want to solve it by depth-first search. That entails two sub-problems:

• a) writing a depth-first algorithm
• b) writing something that enumerates legal moves in a given Sudoku board

I would start by testing the depth-first search algorithm. I would drive it with an abstract “tree” implementation. This means I could concentrate on the search algorithm without being distracted by the complex details of the Sudoku rules.

Then I would test-drive the generation of next-moves from a Sudoku position. That could also be done incrementally. Can we imagine a simplified Sudoku board? The full Sudoku is too complex for the first test! A year ago I would have started by defining a 9 by 9 array of numbers, but now the sheer boredom of defining it would stop me. Is there a better way?

Relax. Think. Dream.

Think about the game terminology. As Norvig says, the game is about units (either a row, a column or a box). A unit with no empty spaces has no descendant moves. A unit where a number is missing has the full unit as a descendant move. A unit where two numbers are missing… You get the point.

Then work out how to combine descendant moves of two units that share a square. Think a row and a column. If the common square is empty, than valid solutions for that square must be valid for both units…

The point is to work the problem incrementally. Try smaller scales first. Try 2×2 boards. Make the size of units and the board parametric. Add the constraint rules one by one, so that you can test them separately.

Conclusions

One important principle to apply is “separation of concerns”. Enumerating moves is a problem, and search strategy is another. By solving them separately, our tests become more clear and to the point. We gain confidence that we know how and why our code works.

Another way to see this is to decompose a problem in smaller problems; prove with tests that you can solve the subproblems, then prove with tests that you can solve the composition of the subproblems.

When you have a problem that is of fixed size 42, turn that constant into a parameter and solve the problem for N=1, N=2, … Imagine if the Sudoku board was 100×100 instead of 9×9; would you define a 100×100 matrix in your tests? Turning these constants into parameters make your code more general, your tests more clear, while making the problem *easier* to solve!

To summarize, what I think is important is

• Learn data structures, algorithms, known solutions, the proper way of doing things.
• Apply separation of concerns.
• Solving a slightly more general problem sometimes is much easier than solving the actual problem
• It’s more fun to work when you know what you’re doing!

Update

Charlie Poole recently posted this on the TDD mailing list (Emphasis is mine):

I’ve written elsewhere that I believe attempting to get TDD to “drive” the invention of a new algorithm reflects an incorrect understanding of what TDD is for.

TDD allows us to express intent (i.e. design) in a testable manner and to move from intention to implementation very smoothly – I know of no better way.

OTOH, you have to start out with an intent. In this context, I think that means you need to have some idea of the algorithm you want to implement. TDD will help you implement it and even refine the details of the idea. Writing tests may also inspire you to have further ideas, to deepen the ones you started with or to abandon ideas that are not working out.

Vlad Levin blogs thoughtfully:

one of the first rules I teach my students when I am doing a TDD workshop or teaching a course is precisely that TDD is not an algorithm generator! Solving sudoku is just the kind of problem you want to find an algorithm for first, then implement that algorithm

[…]

So what is the purpose of TDD then? One goal of TDD is to reduce the need to determine ahead of time which classes and methods you’re going to implement for an entire story. There’s a large body of shared experience in the developer community that trying to anticipate such things tends to lead to paralysis where nothing useful gets done and/or produces bloated, over-designed code. Instead, you can develop one aspect of the story at a time, using each test to keep yourself moving forward and refactoring the design as you go along

This entry was posted on 29 June 2010 at 13:26 and is filed under Agile, Essay, Expressive Code. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.