Test Driven Development Sample
Ron Jeffries
Ron Jeffries
11/17/2003
When I demonstrate Test-Driven Development using the Bowling Game
example, I begin by describing the problem and inviting the attendees to
do a little up front design about what objcts we may need. Then I take a
very simple approach that produces a rather simple single-class solution,
with none of the complexity we anticipated. I've been wondering how to
drive the development to cause the creation of some of the classes that
are anticipated, supposing that we might have some actual need for them.
Here's an example of doing TDD with a bit bigger "design" in mind.
http://www.xprogramming.com/xpmag/acsBowling.htm
Ron Jeffries
www.XProgramming.com
Just because we learned something new today doesn't mean we were
frickin' idiots yesterday. -- Chris Morris, possibly paraphrasing someone.
--
Ronald E Jeffries
http://www.XProgramming.com
http://www.objectmentor.com
I'm giving the best advice I have. You get to decide whether it's true for you.
Uncle Bob (Robert C. Martin)
written this on (or about) Mon, 17 Nov 2003 12:24:34 -0500, :
>Adventures in C#: The Bowling Game
>Ron Jeffries
>11/17/2003
>
> When I demonstrate Test-Driven Development using the Bowling Game
> example, I begin by describing the problem and inviting the attendees to
> do a little up front design about what objcts we may need. Then I take a
> very simple approach that produces a rather simple single-class solution,
> with none of the complexity we anticipated. I've been wondering how to
> drive the development to cause the creation of some of the classes that
> are anticipated, supposing that we might have some actual need for them.
> Here's an example of doing TDD with a bit bigger "design" in mind.
>
> http://www.xprogramming.com/xpmag/acsBowling.htm
I can't say that I like it as much as the traditional solution, but it
is pretty sweet. It's the first reasonable version with frames that
I've seen.
One complaint I have is that the tests are doing the parsing of
whether a frame is Open, Spare, Strike, or Bonus. It seems to me that
this should be in the BowlingGame class itself. The tests shouldn't
know about whether a throw is a strike, spare, open, or bonus. The
tests should just know which balls where thrown IMHO.
Robert C. Martin | "Uncle Bob"
Object Mentor Inc. | unclebob @ objectmentor . com
501 N. Riverside Dr.| Tel: (800) 338-6716
Suite 206 | Fax: (847) 775-8174 | www.objectmentor.com
| | www.XProgramming.com
Gurnee, IL, | Training and Mentoring | www.junit.org
60031 | OO, XP, Agile, C++, Java, C# | http://fitnesse.org
Costin Cozianu
> Adventures in C#: The Bowling Game
> Ron Jeffries
> 11/17/2003
>
> When I demonstrate Test-Driven Development using the Bowling Game
> example, I begin by describing the problem and inviting the attendees to
> do a little up front design about what objcts we may need. Then I take a
> very simple approach that produces a rather simple single-class solution,
> with none of the complexity we anticipated. I've been wondering how to
> drive the development to cause the creation of some of the classes that
> are anticipated, supposing that we might have some actual need for them.
> Here's an example of doing TDD with a bit bigger "design" in mind.
>
> http://www.xprogramming.com/xpmag/acsBowling.htm
>
> Ron Jeffries
> www.XProgramming.com
> Just because we learned something new today doesn't mean we were
> frickin' idiots yesterday. -- Chris Morris, possibly paraphrasing someone.
>
Yet Another Pet Example. Actually, it is a trivial folding in functional
programming, one just has to read the requirements and transform that
into a data structure, that is unless you want to write it as a single
block of code.
The interesting thing missing from the story is if this is a scoring
calculator module to be integrated into another picture what is the
reason behind the interface for this module.
The other interested thing that is missing is how much time and how much
lines of code it took you to come up with the TDD solution, in other
words you can praise TDD all you want, you have to come with some
objective engineering measures.
----
Now forget about bowling frames, take a minimally challenging example.
I added one just for your convenience, it's up to you if you take it or not.
*Longest increasing subsequence.*
Let there be a sequence of real, a subsequence is a sequence obtained
from the original by removing any number of positions while retaining
the ordering for the remaining positions. Find the longest increasing
subsequence.
More formally, givent he input an array of reals (x[0] ..
x[x.length-1]), give the output an array of integer indices: (index[0]
... index[index.length-1]
so that for any k 0<=k< index.length - 1 : 0<=index[k]<x.length
-- index[k] is a valid index in the input array)
and for any 0<=j<k<index.length, we have:
index[j]<index[k]
-- we don't change the ordering
x[index[j]] <= x[index[k]]
-- the corresponding elements are in ascending order
-----
Let's see how TDD fares on this one.
Costin
Ron Jeffries
<u.n.c.l...@objectmentor.com> wrote:
>I can't say that I like it as much as the traditional solution, but it
>is pretty sweet. It's the first reasonable version with frames that
>I've seen.
Yes. I'm going to do my standard procedural one next and compare them. But the
objects are at least semi-sweet.
>
>One complaint I have is that the tests are doing the parsing of
>whether a frame is Open, Spare, Strike, or Bonus. It seems to me that
>this should be in the BowlingGame class itself. The tests shouldn't
>know about whether a throw is a strike, spare, open, or bonus. The
>tests should just know which balls where thrown IMHO.
I think of it as the interface to BowlingGame is coming from the playing of the
game itself. The players know whether they bowled a strike, spare, open frame,
and so on, and they say so.
It would certainly be possible to do the parsing readily enough, but my
intuition said (and I bet you'll agree) that by the time we parse, we might as
well just add up the score rather than create all those cute objects.
It's definitely a different breakout of responsibility, and makes the classes
that use the Game know more. But that was the point, really, try it another way
and see what one gets.
Thanks for the feedback!
Ron Jeffries
wrote:
>*Longest increasing subsequence.*
>
> <description snipped>
>-----
>
>Let's see how TDD fares on this one.
Might be interesting, I'll think about working it. If I understand your
notation, this problem is usually named "Longest increasing SCATTERED
subsequence", is that what you have in mind?
An elementary algorithm is probably fairly simply generated using TDD,
generating all subsequences and comparing them. That will of course have huge
run time and will be seriously sub-optimal.
The problem, if I recall from my college days long ago, is best solved with a
recursive algorithm with memory as to the longest sequence as yet found, over an
increasing sequence length, or something weird like that.
It's the sort of math problem where it takes a kind of creative math insight to
do a really good job, and as such I'd expect it to be unlikely that a TDD
approach would find its way onto the right approach.
So, are there problems that are not amenable to TDD? I think not, because I'd
still use TDD to confine the code to correctness even if I was working on a
specific algorithm. Will TDD, however, just converge on an optimal solution? I
think not. It will converge on a working solutionn but there's no guarantee of
optimality. I know of no approach that guarantees that, but would love to hear
about one.
Ron Jeffries
wrote:
>Let's see how TDD fares on this one.
While we're at it, please show us how your approach, whatever it is, fares on
this one.
John Elrick
"Costin Cozianu" <c_co...@hotmail.com> wrote in message
news:bpbu6c$1mf3mg$1...@ID-152540.news.uni-berlin.de...
> Ron Jeffries wrote:
>
SNIP
> Now forget about bowling frames, take a minimally challenging example.
>
> I added one just for your convenience, it's up to you if you take it or
not.
>
> *Longest increasing subsequence.*
>
> Let there be a sequence of real, a subsequence is a sequence obtained
> from the original by removing any number of positions while retaining
> the ordering for the remaining positions. Find the longest increasing
> subsequence.
>
> More formally, givent he input an array of reals (x[0] ..
> x[x.length-1]), give the output an array of integer indices: (index[0]
> ... index[index.length-1]
>
> so that for any k 0<=k< index.length - 1 : 0<=index[k]<x.length
> -- index[k] is a valid index in the input array)
>
> and for any 0<=j<k<index.length, we have:
>
> index[j]<index[k]
> -- we don't change the ordering
>
> x[index[j]] <= x[index[k]]
> -- the corresponding elements are in ascending order
> -----
>
> Let's see how TDD fares on this one.
I'll bite. Paraphrasing your description, I assume you mean:
f([8,9,1,2,3]) -> [2,3,4]
Assuming a 0 indexed integer array.
Ok...what is the result for this:
f([8,8,8,8]) -> ???
or this:
f([1,2,3,1,2,3,1,2,3]) -> ???
Need all the stories to build the tests...
The tests I would assume would build the function are:
assertEquals([], f([]));
assertEquals([0], f([1]));
assertEquals([1,2], f([1,1,2]));
assertEquals([2,3,4], f([1,2,1,2,3]));
BUT, we need the solutions for the above two ambiguities to finish the
construction.
John
John Elrick
"Ron Jeffries" <ronje...@REMOVEacm.org> wrote in message
news:8h1jrvo142kf4d9ss...@4ax.com...
> On Mon, 17 Nov 2003 17:54:22 -0800, Costin Cozianu <c_co...@hotmail.com>
> wrote:
>
> >*Longest increasing subsequence.*
> >
> > <description snipped>
> >-----
> >
> >Let's see how TDD fares on this one.
>
> Might be interesting, I'll think about working it. If I understand your
> notation, this problem is usually named "Longest increasing SCATTERED
> subsequence", is that what you have in mind?
>
> An elementary algorithm is probably fairly simply generated using TDD,
> generating all subsequences and comparing them. That will of course have
huge
> run time and will be seriously sub-optimal.
IF I'm reading his description correctly (which I may not be), the problem
can be solved with a for loop and five local variables.
And...yes...I'd certainly want to test this particular algorithm<g>
John
Phlip
> On Mon, 17 Nov 2003 17:54:22 -0800, Costin Cozianu <c_co...@hotmail.com>
> wrote:
>
> >*Longest increasing subsequence.*
> >
> > <description snipped>
> >-----
> >
> >Let's see how TDD fares on this one.
>
> Might be interesting, I'll think about working it. If I understand your
> notation, this problem is usually named "Longest increasing SCATTERED
> subsequence", is that what you have in mind?
>
> An elementary algorithm is probably fairly simply generated using TDD,
> generating all subsequences and comparing them. That will of course have
huge
> run time and will be seriously sub-optimal.
Jeeze, Ron - don't you think, if TDD's all it's cracked up to be - can't you
knock off the Traveling Salesman Problem while you are at it?
--
G. Spencer Brown
Costin Cozianu
f([8,8,8,8]) -> [0,1,2,3]
> or this:
>
> f([1,2,3,1,2,3,1,2,3]) -> ?
f([1,2,3,1,2,3,1,2,3]) -> [0,1,4,7,8] ( also [0,1,2,5,8])
>
> Need all the stories to build the tests...
>
You see, that's the problem with your enthusiastic XP/TDD approach. I
gave you enough specification, and now you've mudied the waters with
your "stories" :)
The specification stated quite clearly that x[index[i]]<=x[index[k]]
The specification also did not state that the longest increasing
subsequence is unique, so you shouldn't assume that. Any subsequence
that has maximal length will do.
Therefore your assertEquals() below are restricting the space of
solutions. They are not a faithful encoding of specification.
> The tests I would assume would build the function are:
>
> assertEquals([], f([]));
>
> assertEquals([0], f([1]));
>
> assertEquals([1,2], f([1,1,2]));
>
f([1,1,2]) -> [0,1,2]
> assertEquals([2,3,4], f([1,2,1,2,3]));
f( [1,2,1,2,3]) -> [0,1,3,4] // also [0,2,3,4]
>
> BUT, we need the solutions for the above two ambiguities to finish the
> construction.
>
>
Yes, if you read more carefully the spec you can disambiguate :)
Do they even bother to write Software Requirements Specification these
days in an XP shop ?
Actually if I am to buy into what Uncle Bob claimed yesteryear, I just
couldn't let this piece of software be subcontracted to a XP shop,
because he'd refuse to sign on a specification, he'd only sign off
specific executable tests. And this is, it seems to me just not good
enough, to dillute a specification as a set of tests.
Tests can be a proof that you failed, but never a proof that you
succeeded, so realistically speaking, should we sign a contract over a
spec, or should we sign it over a bunch of "assertEquals" ?
>
> John
>
>
Costin
Costin Cozianu
> On Mon, 17 Nov 2003 17:54:22 -0800, Costin Cozianu <c_co...@hotmail.com>
> wrote:
>
>
>>Let's see how TDD fares on this one.
>
>
> While we're at it, please show us how your approach, whatever it is, fares on
> this one.
>
Actually, I think I've said more than once on this forum that TDD is a
surrogate for the real thing, which is "proof driven development".
Indeed, "test driven" in this example can offer little to no insight
into the nature of the solution, while trying to establish a proof and
having knowledge of established proof techniques both for loops and/or
recursive functions, will offer instantaneous gratification :)
Just try to establish an invariant (for imperative loop) or a relation
when going from a solution of the sequence x[0]..x[k] to a solution of
x[0]..x[k+1]
Costin
Paul Campbell
"Costin Cozianu" <c_co...@hotmail.com> wrote in message news:bpbu6c$1mf3mg$1...@ID-152540.news.uni-berlin.de...
> More formally, givent he input an array of reals (x[0] ..
> x[x.length-1]), give the output an array of integer indices: (index[0]
> ... index[index.length-1]
I'm one of those who uses TDD but I dont expect it to work for everything. However I
have the following observations to make ...
* This sort of algorithm-centric problem is IME very atypical of "day-to-day" software
development unless one is working in a very specialised field such as signal processing.
* Problems such as this almost always have well analysed boiler-plate solutions that I can
just nick and use without having to prove or test it myself.
So even accepting that TDD is all but useless for such a problem I would still conclude
"big deal".
Your other worries about applicability of TDD to concurrent systems (I think this was you)
are much more valid and relevent IMO.
Paul C.
Ron Jeffries
>IF I'm reading his description correctly (which I may not be), the problem
>can be solved with a for loop and five local variables.
It could be, though it seems to me that we have to save sequences, or do some
reasoning about the structure that hasn't come to me yet. I'd love to see your
idea worked out.
>
>And...yes...I'd certainly want to test this particular algorithm<g>
Oh yes!
Ron Jeffries
wrote:
>Actually, I think I've said more than once on this forum that TDD is a
>surrogate for the real thing, which is "proof driven development".
It might be a surrogate for /another/ thing which is "proof driven development".
If all programs had to be proven, there would be a lot fewer programmers in the
world, because most of us aren't up to it.
The longest subsequence problem has a moderately well-known history, and there
are solutions out there -- even some on the Web.
>
>Indeed, "test driven" in this example can offer little to no insight
>into the nature of the solution, while trying to establish a proof and
>having knowledge of established proof techniques both for loops and/or
>recursive functions, will offer instantaneous gratification :)
This might be some new definition of the word "instantaneous" that I wasn't
previously familiar with. Please take us through this experience, preferably
without referencing existing solutions.
>
>Just try to establish an invariant (for imperative loop) or a relation
>when going from a solution of the sequence x[0]..x[k] to a solution of
>x[0]..x[k+1]
Yes, that's what the first thing Google finds recommends. So teach us. I can
help people learn how to do TDD -- let's suppose that's the limit of my
capability. Take us beyond, Costin, show us how to do this thing that you
recommend.
Ron Jeffries
wrote:
>Yes, if you read more carefully the spec you can disambiguate :)
>
>Do they even bother to write Software Requirements Specification these
>days in an XP shop ?
Often they do not. As you have just demonstrated perfectly, talking with the
customer works ever so much better. I shall elaborate:
You presented, as far as I can tell, a perfectly unambiguous description of the
problem. It was without flaw (although the limitations of formatting might make
one wish for better technology).
Yet although the spec was unambiguous, at least one reader who was serious
enough to think about it did not successfully disambiguate. A few words from you
were able to set him straight.
I think there's a deep lesson in that, and it is not "Everyone should learn to
write and read unambiguously".
Ron Jeffries
<p.au.l.ca...@ob.jectvi.sion.c.o.u.k> wrote:
>Your other worries about applicability of TDD to concurrent systems (I think this was you)
>are much more valid and relevent IMO.
Indeed. I have similar concerns. TDD can help me write simple code, which makes
it easier to get correctly-working concurrent systems. But simplicity is often
not enough when it comes to concurrency. Stronger approaches are needed.
And, by the way, that's OK with me. XP and TDD aren't about knowing only one
technique. They offer techniques that are good starting ones, because of their
simplicity and their wide applicability. It's quite valuable -- and in some
cases quite necessary -- to have much more powerful tools in one's bag of
tricks.
Even proof, which seems to be used quite infrequently in practice. Maybe it
should be used more. Some good practical articles, books, and Web postings might
help, if someone was a strong supporter of the idea.
Uncle Bob (Robert C. Martin)
>On Tue, 18 Nov 2003 09:33:58 -0000, "Paul Campbell"
><p.au.l.ca...@ob.jectvi.sion.c.o.u.k> wrote:
>
>>Your other worries about applicability of TDD to concurrent systems (I think this was you)
>>are much more valid and relevent IMO.
>
>Indeed. I have similar concerns. TDD can help me write simple code, which makes
>it easier to get correctly-working concurrent systems. But simplicity is often
>not enough when it comes to concurrency. Stronger approaches are needed.
We've been having some interesting concurrency issues with FitNesse
lately. TDD certainly hasn't prevented them; but we've been able to
build tests cases that demonstrate them. So far we aren't hurting.
The concurrency issues in FitNesse are about to get more interesting.
There are some features we want to implement that will cause some
rather tricky thread juggling. Should be fun.
>
>And, by the way, that's OK with me. XP and TDD aren't about knowing only one
>technique. They offer techniques that are good starting ones, because of their
>simplicity and their wide applicability. It's quite valuable -- and in some
>cases quite necessary -- to have much more powerful tools in one's bag of
>tricks.
You said a mouthful there! Yeah, XP isn't about throwing all your old
tools away, it's about adding some new ones to your kit, and changing
the weighting on your tool selection decision matrix.
>Even proof, which seems to be used quite infrequently in practice. Maybe it
>should be used more.
I can't say I use *formal* proofs; but when diagnosing a concurrency
problem, the steps of logical reasoning are very much like a proof.
Interestingly enough those logical steps are based upon a set of
assumptions that don't always turn out to be true. So experimentation
is also an important part.
Universe
Robert C. Martin wrote in message
> I can't say I use *formal* proofs; but when diagnosing a concurrency
> problem, the steps of logical reasoning are very much like a proof.
> Interestingly enough those logical steps are based upon a set of
> assumptions that don't always turn out to be true.
And whose fault is that?
> So experimentation
> is also an important part.
Elliott
--
Substituting Refactoring For Analysis Modelling and Review
When Facing Major High Level Design Problems
Is Like Drawing a Shade When Totally Dark
--
*~* Theory Leads, Practice Verifies *~*
*~* Global Plans + IID (Iterative & Incremental Development) *~*
Universe
news:e99c3$3fba8f10$3f47e403$23...@msgid.meganewsservers.com...
>
> Robert C. Martin wrote in message
>
> > I can't say I use *formal* proofs; but when diagnosing a concurrency
> > problem, the steps of logical reasoning are very much like a proof.
> > Interestingly enough those logical steps are based upon a set of
> > assumptions that don't always turn out to be true.
> And whose fault is that?
~ For most development questions, issues, matters?
~ For previously tackled kinds of development? - and most kinds have
been
> > So experimentation is also an important part.
*When* the above are not true. And thus for most projects hi-risk
prototyping should be the *lesser* part of development.
You're improperly bowing to spontaneity and thus wasting resources -
time, money, skill, etc - if that is not the case.
Elliott
Costin Cozianu
> On Tue, 18 Nov 2003 02:57:59 GMT, "John Elrick" <jel...@adelphia.net> wrote:
>
>
>>IF I'm reading his description correctly (which I may not be), the problem
>>can be solved with a for loop and five local variables.
>
>
> It could be, though it seems to me that we have to save sequences, or do some
> reasoning about the structure that hasn't come to me yet. I'd love to see your
> idea worked out.
>
>>And...yes...I'd certainly want to test this particular algorithm<g>
>
>
> Oh yes!
>
Before I post a solution, and the mechanism to come up with one, can you
give me a hand and write the unit tests ??
Costin
Ron Jeffries
wrote:
>Before I post a solution, and the mechanism to come up with one, can you
>give me a hand and write the unit tests ??
No, sorry, not at this time. I'm not unwilling, but since I don't have a program
that does the job, and I'm not working on one, creating the tests would be a
fairly long and involved hand process. And I suspect that I would get many of
them wrong through manual errors, which might be confusing.
Costin Cozianu
> On Tue, 18 Nov 2003 13:53:06 -0800, Costin Cozianu <c_co...@hotmail.com>
> wrote:
>
>
>>Before I post a solution, and the mechanism to come up with one, can you
>>give me a hand and write the unit tests ??
>
>
> No, sorry, not at this time. I'm not unwilling, but since I don't have a program
> that does the job, and I'm not working on one, creating the tests would be a
> fairly long and involved hand process. And I suspect that I would get many of
> them wrong through manual errors, which might be confusing.
>
So there is a class of problem where, simply put, tests are much harded
to write if they can be written at all before a solution is written.
John Elrick
> John Elrick wrote:
>
> > "Costin Cozianu" <c_co...@hotmail.com> wrote in message
> > news:bpbu6c$1mf3mg$1...@ID-152540.news.uni-berlin.de...
SNIP
> > f([8,9,1,2,3]) -> [2,3,4]
> >
> > Assuming a 0 indexed integer array.
> >
> > Ok...what is the result for this:
> >
> > f([8,8,8,8]) -> ???
> >
>
> f([8,8,8,8]) -> [0,1,2,3]
This is not an increasing subsequence. Based on your description it can be
one of the following:
-> []
-> [0]
-> [3]
But _not_ all of them:
>>Let there be a sequence of real, a subsequence is a sequence obtained
>>from the original by removing any number of positions while retaining
>>the ordering for the remaining positions. Find the longest increasing
>>subsequence.
For this product to be correct you must reword as follows:
"Find the longest increasing or equal subsequence."
>
> > or this:
> >
> > f([1,2,3,1,2,3,1,2,3]) -> ?
>
> f([1,2,3,1,2,3,1,2,3]) -> [0,1,4,7,8] ( also [0,1,2,5,8])
Nope...this isn't multiple choice and you know it. Which one is correct?
You are specifying the requirements. You must make the decision, not me.
>
> >
> > Need all the stories to build the tests...
> >
>
> You see, that's the problem with your enthusiastic XP/TDD approach. I
> gave you enough specification, and now you've mudied the waters with
> your "stories" :)
No you didn't. You left several ambiguities in the description, as I
already pointed out. I missed one:
f([9,8,7])
What is the longest incresing subsequence?
Note, that based on your description, it can be any of:
-> []
-> [0]
-> [2]
Your call.
John
Costin Cozianu
> "Costin Cozianu" <c_co...@hotmail.com> wrote in message
> news:bpcam3$1mlvei$1...@ID-152540.news.uni-berlin.de...
>
>>John Elrick wrote:
>>
>>
>>>"Costin Cozianu" <c_co...@hotmail.com> wrote in message
>>>news:bpbu6c$1mf3mg$1...@ID-152540.news.uni-berlin.de...
>
>
> SNIP
>
>
>>> f([8,9,1,2,3]) -> [2,3,4]
>>>
>>>Assuming a 0 indexed integer array.
>>>
>>>Ok...what is the result for this:
>>>
>>> f([8,8,8,8]) -> ???
>>>
>>
>>f([8,8,8,8]) -> [0,1,2,3]
>
>
> This is not an increasing subsequence. Based on your description it can be
> one of the following:
>
> -> []
> -> [0]
> -> [3]
>
> But _not_ all of them:
>
Based on my description the condition was x[index[j]] <= x[index[k]] for
any j<k in the given range.
>
>>>Let there be a sequence of real, a subsequence is a sequence obtained
>>
>>>from the original by removing any number of positions while retaining
>>
>>>the ordering for the remaining positions. Find the longest increasing
>>>subsequence.
>
>
> For this product to be correct you must reword as follows:
>
> "Find the longest increasing or equal subsequence."
>
>
Ok, you found a better title.
>
>>>or this:
>>>
>>> f([1,2,3,1,2,3,1,2,3]) -> ?
>>
>>f([1,2,3,1,2,3,1,2,3]) -> [0,1,4,7,8] ( also [0,1,2,5,8])
>
>
> Nope...this isn't multiple choice and you know it.
Why not ?
> Which one is correct?
Any. Both are correct.
> You are specifying the requirements. You must make the decision, not me.
>
>
I can make the decision to take my business elsewhere :)
>>>Need all the stories to build the tests...
>>>
>>
>>You see, that's the problem with your enthusiastic XP/TDD approach. I
>>gave you enough specification, and now you've mudied the waters with
>>your "stories" :)
>
>
> No you didn't. You left several ambiguities in the description, as I
> already pointed out. I missed one:
>
> f([9,8,7])
>
> What is the longest incresing subsequence?
>
> Note, that based on your description, it can be any of:
>
> -> []
> -> [0]
> -> [2]
>
> Your call.
>
Any of [0], [1], [2] but never [] because its lenght is 0.
>
> John
>
>
Any subsequence that meets the specified conditions and has maximum
length will do. I said "longest" because writing in ASCII the formal
clause for maximality is essentially boring, but I guess "longest" is
clear enough what is supposed to mean. Maybe is not "increasing" but
rather non-decreasing" Well, if you replace "<=" with "<" in the
specification, you have essentially the same algorithm.
I don't know where you practice, but customers don't like to be pissed
off responding to obvious questions :)
Cheers,
Costin
John Elrick
"Ron Jeffries" <ronje...@REMOVEacm.org> wrote in message
> On Mon, 17 Nov 2003 21:27:31 -0800, Costin Cozianu <c_co...@hotmail.com>
> wrote:
>
> >Yes, if you read more carefully the spec you can disambiguate :)
> >
> >Do they even bother to write Software Requirements Specification these
> >days in an XP shop ?
>
> Often they do not. As you have just demonstrated perfectly, talking with
the
> customer works ever so much better. I shall elaborate:
>
> You presented, as far as I can tell, a perfectly unambiguous description
of the
> problem. It was without flaw (although the limitations of formatting might
make
> one wish for better technology).
Actually, I found the spec ambiguous and contradictory:
"Find the longest increasing subsequence."
"the corresponding elements are in ascending order"
Then the expression:
"x[index[j]] <= x[index[k]]"
Which contradicts the first two statements. The first requirement
specifically states "increasing", as to eliminate the idea of equality. I
have found through repeated experience that any sign of conflict should be
treated very seriously.
Secondly, there is _nothing_ in the spec that covers the situation of
conflicting cases where there is more than one sequence of the exact same
length. His response "it doesn't matter" indicates to me that he did not
consider this possibility when wording the spec.
I was actually shocked that a computer professional posing a requirement
would dismiss the need to specify the definition of which result should be
considered "correct". If both are "correct", then the defined result is
_not_. It should be an array of arrays, since all are equally correct.
I deal with ambiguous and confusing specifications all the time...we are not
an XP shop, I'm just giving it a fair hearing.
John
Shane Mingins
> I don't know where you practice, but customers don't like to be pissed
> off responding to obvious questions :)
>
I'd have thought they'd get more pissed off if the software doesn't do what
they want ;-)
This thread is very interesting to follow.
Cheers
Shane
John Elrick
> John Elrick wrote:
>
SNIP
> > Nope...this isn't multiple choice and you know it.
>
> Why not ?
>
> > Which one is correct?
>
> Any. Both are correct.
Then the result should be an array of an array of integer indexes,
comprising the longest sequences.
Or we should state in the requirements which is expected.
>
> > You are specifying the requirements. You must make the decision, not
me.
> >
> >
>
> I can make the decision to take my business elsewhere :)
Yes. And any customer who can't make a simple decision like that would be
offered to do so.<vbg - I'm don't want to start a fight>
SNIP
> > -> []
> > -> [0]
> > -> [2]
> >
> > Your call.
> >
>
> Any of [0], [1], [2] but never [] because its lenght is 0.
I included [] as the possiblity that "there is no single longest sequence".
SNIP
> Any subsequence that meets the specified conditions and has maximum
> length will do. I said "longest" because writing in ASCII the formal
> clause for maximality is essentially boring, but I guess "longest" is
> clear enough what is supposed to mean. Maybe is not "increasing" but
Longest is quite clear...my questions dealt with the ambiguous situation of
where there is conflicting answers.
If it doesn't matter, then it would be easy to rewrite:
"The longest non-decreasing, non-sequential subsequence of reals. In the
event there is more than one longest of the same length, return the first
subsequence which satisfies the criterea." Or the last...or the middle
case...whatever.
> rather non-decreasing" Well, if you replace "<=" with "<" in the
> specification, you have essentially the same algorithm.
But not the same results. If I am getting a spec, the customer expects it
to work a certain way. That's what I'm used to having to decipher.
>
> I don't know where you practice, but customers don't like to be pissed
> off responding to obvious questions :)
I practice somewhere where I constantly have to clarify "obvious"
questions...with the Federal Government. You would be surprised how much
trouble you will get into if you don't clarify those issues with them...9
times out of 10 you will deliver the wrong thing thinking you understood
just because you read the formal requirements<g> The other 1 time, it
conflicts because two people have different ideas of what is to happen.
FWIW
John
Costin Cozianu
When you have mathematics vs. words you should have trusted the math.
In any case, it was a friendly challenge, so you could hav
This was a challenge and increasing as well as monotone are by default
taken by mathematician to mean "<=". The relation induced by "<" is
usually called _strict_ : (strictly monotone, strictly increasing).
Here it is:
http://planetmath.org/encyclopedia/StrictlyMonotoneFunction.html
> Secondly, there is _nothing_ in the spec that covers the situation of
> conflicting cases where there is more than one sequence of the exact same
> length. His response "it doesn't matter" indicates to me that he did not
> consider this possibility when wording the spec.
>
Well, it really doesn't matter. The program should output any increasing
sub-sequence that has maximum length.
The customer is happy as long as it is a subsequence, it is increasing
and has maximu length.
> I was actually shocked that a computer professional posing a requirement
> would dismiss the need to specify the definition of which result should be
> considered "correct". If both are "correct", then the defined result is
> _not_. It should be an array of arrays, since all are equally correct.
>
I am actually shocked to see a computer professional shocked that a
requirement specification may define a non-functional relation between
input and output.
What have you studied in school ? Have you ever heard of Dijkstra ?
> I deal with ambiguous and confusing specifications all the time...we are not
> an XP shop, I'm just giving it a fair hearing.
>
>
I don't doubt that you're dealing with confusing specifications -- all
of us do. But pissing off the customer in the process of clarification
is hardly any progress.
>
> John
>
>
Costin
Ron Jeffries
wrote:
>> No, sorry, not at this time. I'm not unwilling, but since I don't have a program
>> that does the job, and I'm not working on one, creating the tests would be a
>> fairly long and involved hand process. And I suspect that I would get many of
>> them wrong through manual errors, which might be confusing.
>>
>
>So there is a class of problem where, simply put, tests are much harded
>to write if they can be written at all before a solution is written.
Certainly. Requirements we don't understand are very hard to write tests for.
The discipline of writing tests, therefore, is one way to discipline ourselves
to come to understand the requirements. Not the only way, surely, but one way.
S Perryman
> Before I post a solution, and the mechanism to come up with one, can you
> give me a hand and write the unit tests ??
Before you post your solution (***) , can you give me the following "big
Oh" numbers (as best you can) :
- Best case
- Average case
- Worst case
The quick skeletal algorithm I devised (about 1hr of thought in total,
near-zero memory requirements etc) has the following :
Best = O(n log2 n)
Average = O(n^2) - O(n^3) [ this is what it appears to be *** ]
Worst = O(2^n) [ditto]
The best/worst seem bad, though I do have the potential for pruning the
candidate space severely based on some basic evaluation of any
candidate subsequence pattern. But as I always operate on the most
pessimistic basis, I cannot be sure the pruning removes the worst case
without actually implementing the algorithm.
*** Note this is primarily to protect myself from the potential disgrace
of a CS101 student coming here and showing something in 10 lines of
of C code and worst case of O(n) . :-)
Regards,
Steven Perryman
BTW, nice formal spec for the problem. Which saved me the first step in
my usual development process.
John Elrick
> John Elrick wrote:
>
> > "Ron Jeffries" <ronje...@REMOVEacm.org> wrote in message
> > news:1p2krvcbb39jhua8m...@4ax.com...
> >
> >>On Mon, 17 Nov 2003 21:27:31 -0800, Costin Cozianu
<c_co...@hotmail.com>
> >>wrote:
> When you have mathematics vs. words you should have trusted the math.
<g>Never...I've worked too long. See below...
> In any case, it was a friendly challenge, so you could hav
True...however, I was only attempting to clarify.
>
> This was a challenge and increasing as well as monotone are by default
> taken by mathematician to mean "<=". The relation induced by "<" is
> usually called _strict_ : (strictly monotone, strictly increasing).
>
> Here it is:
>
> http://planetmath.org/encyclopedia/StrictlyMonotoneFunction.html
Not a mathematician...and even if I was, I'd still ask. One thing I've
learned is to _never_ trust a formula if it contradicts any portion of the
spec. Mind you, I deal with many people who _think_ they can write concise
descriptions of their problem set that do not survive the first set of test
data. Perhaps that experience caused me to react differently than I would
had I started with the assumption that you were a mathematician.
>
> > Secondly, there is _nothing_ in the spec that covers the situation of
> > conflicting cases where there is more than one sequence of the exact
same
> > length. His response "it doesn't matter" indicates to me that he did
not
> > consider this possibility when wording the spec.
> >
>
> Well, it really doesn't matter. The program should output any increasing
> sub-sequence that has maximum length.
>
> The customer is happy as long as it is a subsequence, it is increasing
> and has maximu length.
<vbg>Not mine. Plus, we introduce non-repeatibility. Let's say two people
take two different attacks on the problem, but in the case of duplication
one chooses the first result and the other chooses the last. We feed
through a very large sequence of live data where the results are not known
and are expensive to check by hand. The results from the two programs
differ. Now, is there a problem with one of the algorithms that is causing
it to fail under this circumstance?
Additionally, this particular problem smacks of being a portion of a large
problem. How am I to know that the larger problem will not become skewed
by the results unless I ask.
>
> > I was actually shocked that a computer professional posing a requirement
> > would dismiss the need to specify the definition of which result should
be
> > considered "correct". If both are "corre