TDD: how to find the smaller steps when confronted with a big leap

[Alastair Smith]

Hi everyone

I ran an "Introduction to TDD" workshop at work today.  Generally speaking, the feedback has been possible, but made a big mistake in overstretching the participants (and myself) with one of the kata.  The problematic exercise was the Anagrams kata, taken from Jon Jagger's Cyber Dojo:

Write a program to generate all potential 
anagrams of an input string.

 

For example, the potential anagrams of "biro" are

 

biro bior brio broi boir bori
ibro ibor irbo irob iobr iorb
rbio rboi ribo riob roib robi
obir obri oibr oirb orbi orib

Note: I also added the requirement that the input string not be considered an anagram of itself, so in the example above the word "biro" should not be included in the list of potential anagrams.  

The problem that pretty much everyone hit was that after a certain point, the leap required to write the next test or set of tests was too great: there was no "baby step" available.  Most people started off with the degenerate cases of the empty string and the singleton string, both of which return an empty collection, and then moved on to two-letter strings.  This too was fairly simple to tackle, because there is only one valid potential anagram of a two-letter string in this setting, which is its reverse.  

When people started getting to three letters, the number of permutations suddenly leapt, and a recursive solution presented itself as "natural".  As such, some people became very frustrated that they couldn't just write this nice elegant recursive algorithm that they'd come up with.  In order to follow the letter of TDD, they started going down the route of pulling in their favourite mocking framework to check that the recursive step was called the correct number of times which seems unnecessary to me (surely that's testing the wrong thing?), and I think this was a result of the fact that the step to the recursive algorithm was essentially a re-write of what they had already and not a refactoring.  What smaller steps can be made at the three-letter level to allow a solution to emerge through the TDD process?  

I've posted my own (partial) attempt at this kata to GitHub at: https://github.com/alastairs/kata/commits/Anagrams-2012-01-04 (tackled in C#).  I got stuck at a similar point (not helped by my use of yield) and so the code is pretty horrible...  I would hugely appreciate feedback on my approach to the problem as I'm pretty certain this exercise is beyond my current level of TDD expertise (probably evident from the code!).  If you know of a worked example for this exercise, I would also find it invaluable to try to learn from that.

Many thanks in advance!

Alastair

--
Alastair Smith MEng DipABRSM
http://www.alastairsmith.me.uk/

[Simone Busoli]

My personal take on the subject is that TDD is not good for this kind of problems. You need to come up with the algorithm and then just write it down. Applying TDD risks to bring you down a dead end.  https://gist.github.com/1562857 

--
You received this message because you are subscribed to the Google Groups "software_craftsmanship" group.
To post to this group, send email to software_cr...@googlegroups.com.
To unsubscribe from this group, send email to software_craftsma...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/software_craftsmanship?hl=en.

[Ted M. Young [@jitterted]]

Yah, that's why I don't like using algorithmically-based topics for more than basic TDD. I've found it much more interesting (and fun) to do the basics of a dice-based game, such as Monopoly. I guess I should write up how I've done that. :-)

;ted

[Sean Corfield]

On Wed, Jan 4, 2012 at 3:06 PM, Alastair Smith
<alas...@alastairsmith.me.uk> wrote:
> I ran an "Introduction to TDD" workshop at work today.  Generally speaking,
> the feedback has been possible, but made a big mistake in overstretching the
> participants (and myself) with one of the kata.  The problematic exercise
> was the Anagrams kata, taken from Jon Jagger's Cyber Dojo:
>
>> Write a program to generate all potential
>> anagrams of an input string.

I think there are a number of small tests that you can use here:

The result is a sequence.
Each element of the sequence has N characters where N = len( input ).
Each element of the sequence has the same set of characters as the input.
The sequence does not contain the input.
The sequence has K elements = factorial( N ) - 1 where N = len( input ).
Each element of the sequence is unique.

Each test would need a few variants based on inputs ("", "a", "it",
"the", "name" ought to be enough).

That should give you a nice, gentle slope of tests that you can write
the code for a little at a time.

Thoughts?
--
Sean A Corfield -- (904) 302-SEAN
An Architect's View -- http://corfield.org/
World Singles, LLC. -- http://worldsingles.com/

"Perfection is the enemy of the good."
-- Gustave Flaubert, French realist novelist (1821-1880)

[Doug Bradbury]

One of the best kata's that explore this topic is the Word wrap kata.

http://thecleancoder.blogspot.com/2010/10/craftsman-62-dark-path.html

I have my apprentices practice this kata including taking the wrong path and backing up.

The basic lesson is that if you have to take too big of a leap, then you've written the wrong test.

Doug

--

[Adam Sroka]

It's worth pointing out that while this type of exercise is great for
practice real TDD is mostly about imagining the API you want to use
and then using that to wrap the algorithm out of the book, or better
yet someone else's well tested library.

[George Dinwiddie]

I also use test-first to help me be sure I'm implementing an algorithm
correctly. I consider test-driving toward a known algorithm distinct
from TDD.

- George

--
----------------------------------------------------------------------
* George Dinwiddie * http://blog.gdinwiddie.com
Software Development http://www.idiacomputing.com
Consultant and Coach http://www.agilemaryland.org
----------------------------------------------------------------------

[Torbjörn Gyllebring]

On Thu, Jan 5, 2012 at 6:57 AM, George Dinwiddie
<li...@idiacomputing.com> wrote:
> I also use test-first to help me be sure I'm implementing an algorithm
> correctly. I consider test-driving toward a known algorithm distinct from
> TDD.

+1 on this.

This is also why I consider the statement "I'll TDD a <well known data
structure>" an oxymoron.
As soon as you name the algorithm or data structure you've already
taken taken a leap of faith w.r.t design and what would constitute a
'sane' design.

[Alastair Smith]

Thanks everyone for your replies!

A few of you mentioned that you thought this wasn't a good problem for TDD, but was still suited to test-first development.  How would you go about tackling this in a test-first manner as distinct to a test-driven manner?  Would you plan out all your tests, write all your tests, and then write the implementation, or would you still take an incremental approach to the test and production code?

Sean, thanks for your ideas for more tests, there were a few in there (particularly the ones about the length of the output strings and the characters contained within them) that I hadn't considered.

I've got a couple of more specific replies, which I'll send through separately...

Alastair

--
Alastair Smith MEng DipABRSM
http://www.alastairsmith.me.uk/

[Alastair Smith]

Hi Ted

On 5 January 2012 01:46, you wrote:

Yah, that's why I don't like using algorithmically-based topics for more than basic TDD.

It seems to me that this algorithm-based exercise doesn't work for basic TDD.  I was intending only to cover basic TDD in yesterday's session, and the simpler exercises like Roman Numerals worked fine for this.

 

I've found it much more interesting (and fun) to do the basics of a dice-based game, such as Monopoly. I guess I should write up how I've done that. :-)

I would be very interested to read about that!

[Alastair Smith]

Hi Adam

On 5 January 2012 05:37, you wrote:

It's worth pointing out that while this type of exercise is great for
practice real TDD is mostly about imagining the API you want to use
and then using that to wrap the algorithm out of the book, or better
yet someone else's well tested library.

That's a really valuable insight, thanks.  For this exercise, TDD in the "design" sense then covers the method definition and the boundary conditions, to create an API that allows the algorithm to be easily tested.  

[Erick Thompson]

A lot of algorithms have a natural testing approach built in, even if not TDD friendly. In the cited case, you can use some basic probability approaches to figure out the boundary of the problem (how many results are possible), and other edge cases (e.g., only allow these characters in the string, length must be 4, etc). I would personally start with the general tests (# of results), and start writing the code. 

[George Dinwiddie]

Hi, Alastair,

On 1/5/12 5:26 AM, Alastair Smith wrote:
> Thanks everyone for your replies!
>
> A few of you mentioned that you thought this wasn't a good problem for
> TDD, but was still suited to test-first development. How would you go
> about tackling this in a test-first manner as distinct to a test-driven
> manner? Would you plan out all your tests, write all your tests, and
> then write the implementation, or would you still take an incremental
> approach to the test and production code?

I would still take an incremental approach. The distinction is that I'm
not letting the needs of the client's usage drive the design. Instead,
I'm expressing the requirements of the algorithm in tests.

In your example, I would likely start with the 0-character, 1-character,
and 2-character cases, as you mentioned. When I got to the 3-character
case, I would implement it using the design I had in mind (the recursive
algorithm) rather than trying to tease out the design as forced by the
tests.

- George

[RonJeffries]

Hi George,

On Jan 6, 2012, at 10:43 PM, George Dinwiddie wrote:

On 1/5/12 5:26 AM, Alastair Smith wrote:

Thanks everyone for your replies!

A few of you mentioned that you thought this wasn't a good problem for

TDD, but was still suited to test-first development.  How would you go

about tackling this in a test-first manner as distinct to a test-driven

manner?  Would you plan out all your tests, write all your tests, and

then write the implementation, or would you still take an incremental

approach to the test and production code?

I would still take an incremental approach. The distinction is that I'm not letting the needs of the client's usage drive the design. Instead, I'm expressing the requirements of the algorithm in tests.

In your example, I would likely start with the 0-character, 1-character, and 2-character cases, as you mentioned. When I got to the 3-character case, I would implement it using the design I had in mind (the recursive algorithm) rather than trying to tease out the design as forced by the tests.

I'm not understanding the distinction you're making re using the design you have in mind rather than trying to tease it out.

Seems to me I only do things that I have in mind, and it's a question of how much I do in one bite. Sounds like you have more of a distinction in mind(!) here?

Ron Jeffries

www.XProgramming.com

If it is more than you need, it is waste. -- Andy Seidl

[Aviv Ben-Yosef]

Hey Ron,

I'm not in George's mind, but I've actually thought about something
similar often. Often when confronted with a problem like this one an
algorithm pops to my mind. Were I not TDDing, I would just go ahead
and write it. But, because I want the tests to drive my design I start
implementing one test at a time, trying to ignore the way I've already
envisioned and see if the tests are telling me I should use a
different way to solve the problem. Sometimes I do get a better
realization, and sometimes the tests just nudge me towards the same
thing I had in mind from the first place (maybe because I get
developer-myopia once I think of a solution).

>
> Ron Jeffrieswww.XProgramming.com

> If it is more than you need, it is waste. -- Andy Seidl

Aviv Ben-Yosef @avivby http://codelord.net

[RonJeffries]

Hi Aviv,

On Jan 8, 2012, at 10:38 AM, Aviv Ben-Yosef wrote:

I'm not in George's mind, but I've actually thought about something
similar often. Often when confronted with a problem like this one an
algorithm pops to my mind. Were I not TDDing, I would just go ahead
and write it. But, because I want the tests to drive my design I start
implementing one test at a time, trying to ignore the way I've already
envisioned and see if the tests are telling me I should use a
different way to solve the problem. Sometimes I do get a better
realization, and sometimes the tests just nudge me towards the same
thing I had in mind from the first place (maybe because I get
developer-myopia once I think of a solution).

Yes. It seems sometimes the tests push us in a notably different direction, sometimes the same direction with little improvements. Seems to me that at some point we say "recursion" and that one work shapes the program a lot.

I'm just wondering if George has something different in mind ...

Ron Jeffries

www.XProgramming.com

Everything that needs to be said has already been said.

But since no one was listening, everything must be said again. -- Andre Gide

[George Dinwiddie]

Hi, Ron,

I guess the question is "does what I have in mind relate to the external
view of this bit of code or the internal view?" For this particular
problem, working only from the external view might take some steps
bigger than I want, so I might work from an internal view--knowing the
algorithm I want.

In less algorithmic cases, I often (now) don't think too much about the
implementation until I've written the test asking for the behavior.

Does that make more sense? I've not found a good way to describe this.

[RonJeffries]

Hi George,

On Jan 8, 2012, at 2:37 PM, George Dinwiddie wrote:

I guess the question is "does what I have in mind relate to the external view of this bit of code or the internal view?"  For this particular problem, working only from the external view might take some steps bigger than I want, so I might work from an internal view--knowing the algorithm I want.

In less algorithmic cases, I often (now) don't think too much about the implementation until I've written the test asking for the behavior.

Does that make more sense? I've not found a good way to describe this.

Dunno. I like to think that I'm thinking all the time ... but I don't have a sense of switching from external to internal that I'm aware of ... not sure if that's good or bad. :)

Ron Jeffries

www.XProgramming.com

I'm not bad, I'm just drawn that way.  -- Jessica Rabbit

[Alastair Smith]

Hi George

On Saturday, 7 January 2012, George Dinwiddie <li...@idiacomputing.com> wrote:
> I would still take an incremental approach. The distinction is that I'm not letting the needs of the client's usage drive the design. Instead, I'm expressing the requirements of the algorithm in tests.
>
> In your example, I would likely start with the 0-character, 1-character, and 2-character cases, as you mentioned. When I got to the 3-character case, I would implement it using the design I had in mind (the recursive algorithm) rather than trying to tease out the design as forced by the tests.

This is an interesting approach, thank you.  I suspect using some of the ideas for tests that Sean posted earlier in the thread, combined with some of the enlightenment from Uncle Bob's post would guide me down the path of teasing out the design via the tests.  

I'll have another stab at it in a couple of days.

Cheers

Alastair

>  - George
>
> --
>  ----------------------------------------------------------------------
>  * George Dinwiddie *                      http://blog.gdinwiddie.com
>  Software Development                    http://www.idiacomputing.com
>  Consultant and Coach                    http://www.agilemaryland.org
>  ----------------------------------------------------------------------
>

[Peter Gfader]

I had similar experiences with TDD+algorithms.

 

I get into this "brute force coding" mode, where I don't think too much, but I just want to get the test to green.

--> It would be better to spend more time thinking about the problem on paper and then go back to coding...

My 2c

   .peter.gfader. (current mood = perfectly happy)

   http://blog.gfader.com

--

  .peter.gfader. (current mood = happy!) 

  Check this before you go live

  http://blog.gfader.com/2011/07/website-check-list-part-1-aspnet-4.html

[Grégory Salvan]

Hi everyone,
I've small experience, but my approach is different and I'm curious to
know yours opinions, about it.

What I found interesting here, is that TDD shows that the problem must
be correctly defined before start.
It's most often the case when steps are big and, when a definition
needs an example, it more often smells that the problem statement must
be refactored.

so, I tried to give a new definition :
- the anagram of an empty string or a single char is itself.
- a word (a string with more than 1 char) B is an anagram of a word A:
* if B have exactely the same letters than word A in a different order
AND
* if all anagrams of A are identicals of the anagrams of B

The definition can also be recursive (I have in mind the vision of the
arithmetic definition of addition for natural numbers) :
- the anagram of an empty string or a single char is itself. (same but
important because it's the exit of recursion and firsts things we
tests)
- anagrams of a word are each letter of the word prepended to the
anagrams of the word without the letter.

I would start by tests and implements the first property (empty and
char) wich is the exit of recursion.
Then based on news definitions I would successively iterate over these
tests :
- 'ab' anagrams are itself and 'ba' (just return 'ba' in method
'anagrams')
- anagrams of 'abc' contains only letters 'a', 'b', and 'c' (return a
list with the word and the reverse of the word due to previous tests)
- 'a' prepended to the anagrams of 'bc' return words with letters 'a',
'b', and 'c' only
(I create a new method 'prependAnagrams' that retrieve anagrams of the
second arguments 'bc' and append them to the first argument 'a')
- 'abc' anagrams contains 'a' prepended to the anagrams of 'bc' (make
the method anagrams call prependAnagrams with the first letter of the
word if word length >2 )
- 'abc' anagrams contains 'b' prepended to the anagrams of 'ca' (make
the method anagrams call prependAnagrams with the first and the second
letter of the word if word length >2 )
- 'abc' anagrams contains 'c' prepended to the anagrams of 'ab' (make
the method anagrams call prependAnagrams with all letters of the word)
...
(you can continue with 'returned elements are uniques', 'anagrams
don't contains the given word')

This guide to the recursive solution certainly because I know it
before, but steps appears smaller.
Hope I'm not wrong,
Gregory

On 9 jan, 17:12, Peter Gfader <pe...@gfader.com> wrote:
> I had similar experiences with TDD+algorithms.
>
> I get into this "brute force coding" mode, where I don't think too much,
> but I just want to get the test to green.
> --> It would be better to spend more time thinking about the problem on
> paper and then go back to coding...
>
> My 2c
>    .peter.gfader. (current mood = perfectly happy)
>    http://blog.gfader.com
>

> On Mon, Jan 9, 2012 at 4:00 PM, Alastair Smith <alast...@alastairsmith.me.uk

[Kay A Pentecost]

Hi, Everybody,

 

I’m not clear on the difference between test-first and test-driven here.  Sorry if this has already been covered earlier… I just started reading this list.

 

Thanks,

 

Kay Pentecost

 

---

[Wouter Lagerweij]

Hi Kay,

How I understand it, test-first is simply that: writing a test before writing production code. The test could be quite large, and so could the amount of production code written in one go.

Test-driven would refer to the full TDD design process, red-green-refactor, part of which is writing the test first, but it has additional rules such as writing a very small test, doing the simplest thing that could possibly work, refactor to remove duplication, etc.

Wouter

Wouter Lagerweij         | wou...@lagerweij.com

http://www.lagerweij.com | @wouterla

[Steve Tooke]

J.B Rainsberger has a good description in this article: http://www.jbrains.ca/permalink/how-test-driven-development-works-and-more

Steve

/tooky