Can TDD help with a gnarly problem?

Here’s a puzzle for you. How do you represent counting numbers — integers starting with 1 and going on indefinitely — using letters, the way a spreadsheet’s columns are labeled? You’d use the letters A through Z, then AA, AB, AC thorough ZZ, AAA, AAB and so on.

Lots of folks think think is trivial when they first hear of it. I did. “That shouldn’t be too hard” is what I said to @kaleidic, when he brought it up. Ha!

I’ll leave it to you to figure out whether it’s trivial for you to solve. But for us, it was challenging. We wanted a functional solution. (Functional-ish, I guess, in the J programming language.) And we weren’t able to create it just by thinking hard.

Not knowing how to do this got me excited. I love the way we humans create new knowledge, and I wanted to try it.

Could we solve it by breaking it down into small pieces. Could we do that and produce something like a functional (denotative) solution? Could we see an algorithm evolve before our eyes through TDD?

[an aside: when I say TDD, I mean finding the smallest bit of success you can specify, and automating that — a unit test or micro test. Then writing the least bit of code to pass that test. Then refactoring the code toward the four rules of simple design. (No duplication, minimal pieces, expressing intent, and passing the tests.) And to watch design emerge from that process.]

So, we’re trying it.

First, Tracy (@kaleidic, that is) wanted to figure it out in his head, and write it down in one chunk, working. But that was taking a while, so we started looking for smaller pieces. We started writing unit tests.

At first, they were too big. We’d move forward a little bit, and then get stuck, and stop and look for a smaller chunk to approach.

We’re not done yet, but we’ve gotten far enough that it’s feeling like we might make it. If you’d like to see our progress, check it out on github. (Idiomatic J sometimes makes strong geeks cry. But this is unusually readable. Still not for the faint of heart.)

So what do you think? Can TDD result in the emergence of an algorithm to solve something like this? Or do we have to wrap our minds around a problem before we can solve it?

10 thoughts on “Can TDD help with a gnarly problem?

  1. Tracy Harms

    Whether TDD works for developing algorithms is a particularly interesting question to me. It’s part of what I’m exploring through working on this with you.

    I found a blog post where it’s said that TDD is not suitable as a way to conceptualize an algorithm: http://matteo.vaccari.name/blog/archives/416

    I’ve seen Bob Martin write something similar. Since I tend to see programming as nothing but algorithms, I get the sense that I’m still missing a key idea.

    Reply
    1. xpmatteo

      Hi Tracy,

      The point I wanted to make in that post is that even if I get something working that passes all my test cases, I’m still not done if the resulting algorithm is not *crystal clear*. I mean, sometimes I start with TDD and end up hammering the code until it seems to work. This is not good :-)

      How do we get to code that is crystal clear? One way is to invent a way to break the problem into bits that can be solved separately. For instance, if you want to do a Sudoku solver, you can TDD a depth-first search algorithm, and then a sudoku-next-position generator. Both bits are doable and interesting and they happen to solve the Sudoku problem.

      Once you have those bits to play with, you may use them to ask more questions about the *problem domain*. For instance: does this Sudoku puzzle have a single solution? How many legal moves are there from this position? Etc. etc.

      The point of TDD is, to quote Kent Beck, “to move from unknown to known”. For me, TDD is successful if I manage to get knowledge about the problem domain and if I manage to embed this knowledge in the code.

      Knowledge of algorithms is of course useful for doing algorithms work, wether you use TDD or not. Even if the problem is not one that is covered in any algorithm book, knowledge of algorithms helps you to formalize the problem, so that you can find the “bits” I was talking about earlier.

      Disclaimer: I’m still learning :-)

      Reply
  2. Sean McMillan

    Hello,

    Tracy, I see some discussion there about the Sudoku Solver wars. I think http://ravimohan.blogspot.com/2007/04/learning-from-sudoku-solvers.html is a better link, because it actually links to the Ron Jeffries articles. Unfortunately, it seems like this is the root of the whole diuscussion, with no further examples. Just lots of internet chat about Ron and Peter and their code, approach, relative worth, and personal hygiene.

    I’d love to hear more about what happens.

    Reply
  3. Ron Jeffries

    If we look at the TDD cycle, it is

    1. Devise the next test, picking something we think we could do.
    2. Make the test pass.
    2a. If we can’t make the test pass, go back to #1 and pick a simpler tests.
    3. Refactor, then go to #1 and pick a new test.

    In the Sudoku exercise, the whole POINT was to see what can be done with a problem where one does not know the “classical” solutions. A more typical case, we hope, is one where there is no published solution.

    The good news with the Sudoku example, despite the *ssh*ls, is that a fair amount of progress was made, resulting in some steps toward a solution, AND it became clear that the progress was not good enough. What more can we ask of ourselves than that we can make progress and know when we’re in trouble.

    In response to the question here, can we TDD without knowing the algorithm, the answer is surely yes. Can we TDD without having an IDEA about what might work? Maybe, but it’s going to be hard to select the test, since we’ll try and fail. However, creating a simpler test may put us back on the path.

    Might we go down a wrong path? Sure. The effect of TDD in that case is that we have a growing number of tests as we advanced down the wrong path, and we can step back in time to whatever place we think, in retrospect, was the first wrong step. This is usually not the very first step, for any “interesting” program.

    So, what are we doing when we do TDD, if we fill in more of the micro steps? Something like this:

    0.0 Talk about the problem. Try to understand it.
    0.1 Talk about how we might solve it. Draw pictures, wave arms, whatever.
    0.2 Pick an approach to try. Talk briefly about it. Think briefly about it.
    1.0 Write a test you think you can pass, in the direction of your approach.
    2.0 Make the test pass.
    2.5 If we can’t make it pass, go back to 1.0 or even earlier
    3.0 Refactor, then go back to 1.0 or even earlier.

    One is thinking, designing, adapting, all the time.

    Reply
  4. rdm

    I see http://matteo.vaccari.name/blog/archives/416 saying that you also need to know what you are doing.

    I would add that learning is a part of the job description, if you are a programmer.

    I would also add that having learned a lot is also a part of the job description, if you are a programmer.

    Put differently, the best programmers are probably the savvy ignorant types that understand a great deal and yet are cheerfully willing to learn everything afresh where it’s called for.

    Anyways, for this task… the problem is that it’s a mix of base 27 and base 26, where a leading space means something special. (Or maybe: where the absence of a leading space means something special?)

    So… test cases are probably something like this:

    A: 1
    Z: 26
    AA: 27
    AZ: 52
    BA: 53
    BZ: 78
    ZZ: 702

    I’m a bit uncertain about that last one, but I think ZZ must be 27 + 25 + (26 * 25):

    If I am right, it breaks down like this:

    AA: 27
    (AZ-AA): 25
    (ZZ-ZA): 26*25

    As an aside, the problem here is rather similar to the problem involved with dealing with arithmetic using roman numerals: There is no way to represent zero in this notation.

    Anyways, if my above tests are right, it’s relatively simple to go from encoded to unencoded:

    ABC=: u: 65+i.26

    decode=: 26 #. ABC&i. + # # 1:

    Or, in english: it’s base 26, but you get an extra +1 in the digit position every time you introduce a new digit.

    This gives us a new test: (-: decode@encode)

    As an aside, I am amused that so many tests in J begin with a smiley…

    So.. going the other way, we need to know how many digits we need to represent the result. The thresholds look something like this: 1 27 703 18279 …

    Or, as J expressions:

    1
    1+26
    1+26*1+26
    1+26*1+26*1+26

    In other words, something like this would give you the thresholds for a given number:

    ((1 + 26 * ])^:>^:a:&1) 1000
    1 27 703 18279

    (Here, the number I used was 1000). And, yes, that expression might be considered “cheating”… but I think that the solutions should be clear from here?

    26&#.@#&1″0 i. 9
    0 1 27 703 18279 475255 12356631 321272407 8353082583

    (Except, no zero…)

    Reply
  5. Patrick Kelly

    Interesting problem. Per your suggestion Angela – tried it functionally and it was lots of fun.

    This seems like a classic straightforward computer task on the surface but then you realize it’s not as simple as breaking down a number by place values – the stuff just doesn’t come out right.

    rdm’s comment “There is no way to represent zero in this notation” was a key observation – if you are dividing 6 by 3, and can’t have a remainder of 0 (because there’s no “letter” that means 0) then you have to find some “legal” way to express it – so in a 3-letter alphabet 6 / 3 becomes 1 with a remainder of 3 (or “A” with a remainder of “C”).

    I like the functional approach because it allows you to unit test with a small, comprehensible subset of the universe (like a 3-letter alphabet), and then rely on the rules of functional composition to know that if correctness is demonstrated in the small, easily understood case, it will hold true for larger cases.

    I found the algorithm didn’t quite “invent itself” with TDD – although a TDD helped to decompose small pieces each time a piece of the solution, or a direction to head, became clear.

    Here is some F# code and tests
    Code
    Tests

    Reply
  6. Matt

    I think I agree with the premise that emergence can find the answers to hard problems. But in the past I have notice pairing takes a different format than normal. One that might be somewhat in-compatible with TDD.

    The only change is that instead of both people sitting at a terminal, we are in front of a whiteboard. State charts and sequence diagrams abound. Talking over the approach to the problem instead of the implementation. In this problem I start with paper and pencil, working though the math of converting numerical bases. This makes writing test harder, but in going over your approach you can and probably will touch on how to prove that it works.

    Now you may, can, or probably will actually write test first so this may be TDD still, but it might bend the spirit of TDD a little by doing the architecture first.

    I have yet to come across a question in the domain of CS that doesn’t end with ‘It depends.’ So my final answer is generally yes.

    p.s. I’m not an expert in TDD or Agile, so my apologies if misunderstood, misconstrued, or step on the more exact definitions of TDD

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>