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 "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.
Oh...I have seen quite a few of these in my life. And the first step is to
clarify the desired result. the question was simple: "what is the result
you expect in this circumstance?" My shock existed...not for the output but
the, I guess you could say, dismissive attitude toward a potential situation
that could inject large scale risk into a real world project. Perhaps I
read too much into a friendly challenge, I apologize if I have overreacted.
>
> What have you studied in school ? Have you ever heard of Dijkstra ?
I graduated from school over twenty years ago...yes I have. But my studies
have very little to do with the actual problems I've faced in the field.
>
> > 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.
Well...we are dealing with the limitations of the written word in more
senses than one. My intent was to clarify the requirements...not to piss
you off.
John
Costin Cozianu
> Costin Cozianu <c_co...@hotmail.com> wrote in message news:<bpe4dp$1nbjt3$1...@ID-152540.news.uni-berlin.de>...
>
>
>>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 problem can take O(n log2 n) in the worst case (with the constant
factor 1). Additional storage required is ideally O(n), I'm willing to
give it a pass with O(n^2) to make it for easier to read OO code, but no
more than that.
>
> 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.
Best,
Costin
Costin Cozianu
>>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?
>
Two correct results are easy to compare: the must have the same length.
What is not easy to test for is that the program(s) found the maximum
length subsequence.
> 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.
>
>
Ok, here's the deal in this hypothetical: the customer is not a real
"don't know anything customer", it is another programmer who wants to
subcontract.
>>
>>I am actually shocked to see a computer professional shocked that a
>>requirement specification may define a non-functional relation between
>>input and output.
>
>
> Oh...I have seen quite a few of these in my life. And the first step is to
> clarify the desired result. the question was simple: "what is the result
> you expect in this circumstance?" My shock existed...not for the output but
> the, I guess you could say, dismissive attitude toward a potential situation
> that could inject large scale risk into a real world project. Perhaps I
> read too much into a friendly challenge, I apologize if I have overreacted.
>
>
To convince you even more, that non-functional relations between input
and output are plausible in the real world, I could have asked you to
generate a strong key for a cryptographic protocol. Or just the random
number generator. We don't want that to be deterministic, do we ?
So yes, we deal with requirements that are non-deterministic. of course,
this makes the doctrine of unit testing and TDD very hard to apply (if
possible at all), but that's a secondary consideration.
Best,
Costin
Robert Oliver
"Costin Cozianu" <c_co...@hotmail.com> presented a problem in
news:bpbu6c$1mf3mg$1...@ID-152540.news.uni-berlin.de...
To paraphrase we are given a (possibly empty) sequence of numbers.
The crux of the problem is to remove the fewest numbers from the sequence
which both preserves the original ordering and produces a new sequence that
is monotonicly increasing. (I know this is not identical to the problem
presented, but it is the part I find interesting.)
How does TDD help with this problem?
* My first test cases were {}, {1}, and {1 2}. These all pass simply by
returning the input sequence.
* Next I tried {2 1}. I solved this case by returning the first element if
the sequence was out of order.
I should have tried {1 1}, but didn't. This would ensure I made the right
choice of < vs <= in my test.
With this little experience out of the way, I started to think about more
general solutions. I observed that if a given sequence is in order, the
task is finished. I simply output the sequence. If the sequence is not in
order, there must be at least one pair of numbers in the sequence for which
the first is greater than the second. At least one of these numbers must be
removed in the final sequence. I generate two new sequences. One with the
first of the pair removed and the other with the second removed. If I am
able to find the longest sequence of each new sequence, the longer of the
two must be the answer. This leads to a simple recursive solution.
The function Longest takes a sequence.
If the sequence is ordered, return it.
Otherwise, find a pair of unordered numbers in the sequence,
generate two new sequences as described above, and
call Longest with each sequence.
Return the longer of the two results.
While implementing this, there were a few implementation specific test cases
for a partition function which split the sequence at an unordered pair.
The remaining test cases were {8 8 8 8} {1 2 3 1 2 3 1 2 3}, and a few
others. In fact, I took a short cut and let the program generate the answer
which I then checked and added to the test.
TDD helped by:
1. Making sure a few of the boundary cases worked, and kept working as the
design evolved.
2. Helped me to understand the problem. In particular, the {2 1} test
case started me thinking about partitioning the sequence.
TDD did not:
1. Provide me with a cookbook solution.
2. Substitute for thought or logic.
3. Prove that my logic was correct or that my algorithm works in any but
the test cases.
Pretty much what I expected.
Regards,
Bob Oliver
Costin Cozianu
[1000,999,998,..., 1] ?
I'm waiting for the results, so please don't hurry, take your time ...
I noticed that you haven't posted your unit tests yet :)
Best,
Costin
Robert Oliver
Thanks for the reply.
"Costin Cozianu" <c_co...@hotmail.com> wrote in message
news:bpg0j7$1o6vka$1...@ID-152540.news.uni-berlin.de...
> Could you run the algorithm for me please with the input of
> [1000,999,998,..., 1] ?
Ultimately the algorithm will retain the rightmost 1, however, it might not
happen before the sun burns out and you may not be willing to wait that long
:)
I'll give the problem a little more thought. In the meantime, a few more
observations.
I find it interesting that you chose to provide me with a test case (albiet,
without the answer) to illustrate the drawback of using my algorithm. This
is something I would hope for in a good XP coach.
I still think the algorithm is correct under the original spec. With only
short data sets, it could be just the ticket. I probably would not try to
optimize a working and understandable piece of code until I had the need.
I don't think this kind of situation is terribly uncommon. Designers and
customers both sometimes don't think things through, make wrong guesses, and
generally provide incomplete requirements. Even when we sit down together,
we overlook stuff. Software needs to be changed. I find that TDD gives me
a better understanding of the effect these changes are having on the system.
>
> I'm waiting for the results, so please don't hurry, take your time ...
>
> I noticed that you haven't posted your unit tests yet :)
All of my unit tests are of the form:
assert LongestSequence (1,2,3,1,2,3,1,2,3) == (1,1,1,2,3)
I know that there are other possible solutions and that changing the
algorithm may cause some tests to fail that should really pass. This is
clearly a drawback.
If I wanted to make my tests insensitive to algorithm changes, I would write
a function that takes the expected length of a sequence and a test sequence.
It would check the length and ensure the sequence was sorted. The results
of this test depend only on the input data, not the algorithm. When it
becomes a problem, this is what I will do.
Regards,
Bob
John Elrick
> John Elrick wrote:
Here's a solution in Ruby (had to pick _some_ language). Built test first,
and follows the plan - return the first longest subsegment
=================
# TestRealToIndex.rb
require 'runit/cui/testrunner'
require 'runit/testsuite'
require 'runit/testcase'
require 'realToIndex'
class Testing_RealToIndexArray < RUNIT::TestCase
def test_new
aRealToIndexArray = RealToIndexArray.new
assert_equal([], aRealToIndexArray.maxSubSegment)
end
def test_single
aRealToIndexArray = RealToIndexArray.new([1])
assert_equal([0], aRealToIndexArray.maxSubSegment)
end
def test_stream
aRealToIndexArray = RealToIndexArray.new([1,2,3])
assert_equal([0,1,2], aRealToIndexArray.maxSubSegment)
end
def test_inside
aRealToIndexArray = RealToIndexArray.new([1,2,3,1,4])
assert_equal([0,1,2,4], aRealToIndexArray.maxSubSegment)
end
def test_duplicates
aRealToIndexArray = RealToIndexArray.new([8,8,8])
assert_equal([0,1,2], aRealToIndexArray.maxSubSegment)
end
end
RUNIT::CUI::TestRunner.run(Testing_RealToIndexArray.suite)
=================
# realToIndex.rb
class RealToIndexArray
class NullIndexItem
def update(aReal, aIndex)
end
def count
0
end
def maxSubSegment
[]
end
end
class IndexItem
def update(aReal, aIndex)
if aReal >= @LastMax
@LastMax = aReal
@ArrayOfIndexes[@ArrayOfIndexes.length] = aIndex
end
end
def initialize(aReal, aIndex)
@ArrayOfIndexes = Array.new
@LastMax = 0
update(aReal, aIndex)
end
def count
@ArrayOfIndexes.length
end
def maxSubSegment
@ArrayOfIndexes
end
end
def update(aReal, aIndex)
@ArrayOfItems.each {|item|
item.update(aReal, aIndex)
}
@ArrayOfItems[@ArrayOfItems.length] = IndexItem.new(aReal, aIndex)
end
def initialize(aArrayOfReals = [])
@ArrayOfItems = Array.new
aArrayOfReals.each_index {|i|
update(aArrayOfReals[i], i)
}
end
def maxSubSegment
max_item = NullIndexItem.new
@ArrayOfItems.each {|item|
if item.count > max_item.count then
max_item = item
end
}
max_item.maxSubSegment
end
end
John Elrick
> John Elrick wrote:
>
> >>Well, it really doesn't matter. The program should output any increasing
> >>sub-sequence that has maximum length.
SNIP
> Two correct results are easy to compare: the must have the same length.
> What is not easy to test for is that the program(s) found the maximum
> length subsequence.
What is also not easy to check is that one of the two is the correct length
by accident. If the algorithm is flawed, it is still possible that it is
returning a "correct length", but not the correct results.
SNIPPING AGREEMENT
> To convince you even more, that non-functional relations between input
> and output are plausible in the real world, I could have asked you to
> generate a strong key for a cryptographic protocol. Or just the random
> number generator. We don't want that to be deterministic, do we ?
Deterministic? Of course...but in a different sense. For a random number
generator we would use statistical analysis on a large run to determine that
the results do exhibit randomness. The strong key would have to survive a
similar test.
John
Uncle Bob (Robert C. Martin)
written this on (or about) Mon, 17 Nov 2003 21:27:31 -0800, :
>> 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])
Actually there are six solutions:
0,1,2,5,8,
0,1,4,5,8,
0,1,4,7,8,
0,3,4,5,8,
0,3,4,7,8,
0,3,6,7,8,
Costin Cozianu
>>What is not easy to test for is that the program(s) found the maximum
>>length subsequence.
>
>
> What is also not easy to check is that one of the two is the correct length
> by accident. If the algorithm is flawed, it is still possible that it is
> returning a "correct length", but not the correct results.
>
But if it is the maximum length and is a correct subsequence, than it is
giving a correct result. A correct result is any of the maximum legnth
sequences. There will be at least one, but there can be more than one
sequence.
If you are to design unit tests (which you didn't) to allow for
algorithm improvements or just refactoring, you cannot assume that the
results will always be the same.
Even if you get a pass in assuming that, going at it the way you did by
enumerating a few samples is not really convincing since you don't
justify that those are the only important test cases (indeed they are not).
>>To convince you even more, that non-functional relations between input
>>and output are plausible in the real world, I could have asked you to
>>generate a strong key for a cryptographic protocol. Or just the random
>>number generator. We don't want that to be deterministic, do we ?
>
>
> Deterministic? Of course...but in a different sense. For a random number
> generator we would use statistical analysis on a large run to determine that
> the results do exhibit randomness. The strong key would have to survive a
> similar test.
>
And you'd have to survive waiting for the results of any conclusive
tests :) But what was the subject, did you want to argue that I have to
give you deterministic or (functional) specification, or else you would
not subcontract with me ?
The spec is what I posted initially, and I stand by it, ok, I admit to
one inaccuracy, I should replace "the longest increasing subsequence"
with "any longest increasing subsequence". Bad English.
>
> John
>
>
Cheers,
Costin
John Elrick
> >>Two correct results are easy to compare: the must have the same length.
> >>What is not easy to test for is that the program(s) found the maximum
> >>length subsequence.
> >
> >
> > What is also not easy to check is that one of the two is the correct
length
> > by accident. If the algorithm is flawed, it is still possible that it
is
> > returning a "correct length", but not the correct results.
> >
>
> But if it is the maximum length and is a correct subsequence, than it is
> giving a correct result. A correct result is any of the maximum legnth
> sequences. There will be at least one, but there can be more than one
> sequence.
The key words here are "correct subsequence"...as RDM pointed out, there
were six additional correct results for that one example. What if the
algorithm produces a result that looks correct, but is not?
>
> If you are to design unit tests (which you didn't) to allow for
> algorithm improvements or just refactoring, you cannot assume that the
> results will always be the same.
Nope...wasn't part of the spec or needed at this time.
>
> Even if you get a pass in assuming that, going at it the way you did by
> enumerating a few samples is not really convincing since you don't
> justify that those are the only important test cases (indeed they are
not).
Care to elaborate?
>
> >>To convince you even more, that non-functional relations between input
> >>and output are plausible in the real world, I could have asked you to
> >>generate a strong key for a cryptographic protocol. Or just the random
> >>number generator. We don't want that to be deterministic, do we ?
> >
> >
> > Deterministic? Of course...but in a different sense. For a random
number
> > generator we would use statistical analysis on a large run to determine
that
> > the results do exhibit randomness. The strong key would have to survive
a
> > similar test.
> >
>
> And you'd have to survive waiting for the results of any conclusive
> tests :) But what was the subject, did you want to argue that I have to
> give you deterministic or (functional) specification, or else you would
> not subcontract with me ?
Not subcontract...I've done the other way too many times...got too much grey
hair from it. It always turns into "but you said...no you said, but I
meant" type arguments that mean I don't get paid what I'm supposed to.
>
> The spec is what I posted initially, and I stand by it, ok, I admit to
> one inaccuracy, I should replace "the longest increasing subsequence"
> with "any longest increasing subsequence". Bad English.
That's cool. I was never criticising the spec, I was attempting to get
clarification on points that, in my opinion, produced risk that the desired
results would not be delivered.
John
John Elrick
"John Elrick" <jel...@adelphia.net> wrote in message
news:X%Oub.2334$_i1.1...@news2.news.adelphia.net...
>
> "Costin Cozianu" <c_co...@hotmail.com> wrote in message
> news:bpfvbg$1o6uin$1...@ID-152540.news.uni-berlin.de...
> > John Elrick wrote:
>
> Here's a solution in Ruby (had to pick _some_ language). Built test
first,
> and follows the plan - return the first longest subsegment
>
> =================
> # TestRealToIndex.rb
>
For laughs, I added this test:
def test_heavyduplicates
aRealToIndexArray = RealToIndexArray.new([1,2,3,1,2,3,1,2,3])
assert_equal([0,1,2,5,8], aRealToIndexArray.maxSubSegment)
end
Passed with flying colors...
John
Costin Cozianu
> Costin Cozianu <c_co...@hotmail.com> might (or might not) have
> written this on (or about) Mon, 17 Nov 2003 21:27:31 -0800, :
>
>
>>> 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])
>
>
> Actually there are six solutions:
> 0,1,2,5,8,
> 0,1,4,5,8,
> 0,1,4,7,8,
> 0,3,4,5,8,
> 0,3,4,7,8,
> 0,3,6,7,8,
>
Of course, I wouldn't even bother to enumerate all of them. The problem
is not about enumerating all solutions.
Added bonus if one can prove the the number of possible solutions is in
the worst case exponential. As such, I'd have to be nuts to bother to
enumerate all solutions for any particular case, those were just
examples I gave to Eric to show that there are more than one possible
solutions.
But I'm curious where the famous TDDers, Unit Tester have all gone ? I'd
have expected for such a trivial problem the tests were ready by now.
Costin
Costin Cozianu
For laughs, do you think you can convince me with yet another test ?
Ok, I think Ruby is a lousy language design (or the way you write code
is lousy), meaning even if I read Ruby code before, it is still not
trivial for me to understand the code.
But let me try it, nevertheless:
You maintain an array of possible solutions, and for each real number
element in the input array, you "update in place" all the existing
possible solutions (by extending them with one element if the element
coming in is >= than the last one ), and you add at the end a new
possible solution of length 1: exactly the new element coming in.
As such your array of possible solutions always grows by 1. At the end,
you scan the array of possible solutions and pick the first one with
maximum length.
If I understood your code correctly, then your algorithm is wrong. I'll
give you flying colors to find a failing test.
Costin
John Elrick
> John Elrick wrote:
SNIP
> Ok, I think Ruby is a lousy language design (or the way you write code
> is lousy