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), meaning even if I read Ruby code before, it is still not
> trivial for me to understand the code.
Hmmm....YOU don't understand it so either the language sucks or I'm
incompetent...
>
> 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.
Hmmm...nope, I guess I don't get flying colors.
Let's see your failing test.
John
John Elrick
>
> "Costin Cozianu" <c_co...@hotmail.com> wrote in message
> news:bpghrb$1o8cu5$1...@ID-152540.news.uni-berlin.de...
> > John Elrick wrote:
>
> SNIP
> > If I understood your code correctly, then your algorithm is wrong. I'll
> > give you flying colors to find a failing test.
Nope I do get flying colors...as implemented it fails on a negative.
Fixes below:
def test_negatives
aRealToIndexArray = RealToIndexArray.new([-1,0,2])
assert_equal([0,1,2], aRealToIndexArray.maxSubSegment)
end
def initialize(aReal, aIndex)
@ArrayOfIndexes = Array.new
@LastMax = aReal
@ArrayOfIndexes[0] = aIndex
end
John
Shane Mingins
I had a go at doing the Bowling Game example last night with the same design
idea, i.e. Frames and no conditionals.
What I tried to do differently was pass to the Frame being scored the
NextFrame so that the score could be calculated for spares and strike. This
caused me to create an EndFrame (would I be correct in terming this a
NullObject?).
I added a couple of extra tests along the way (a novice's caution).
It is in Java as I do not have access to a C# development environment.
I would appreciate any comments though.
Thanks Shane
package bowlingGame.tests;
import junit.framework.TestCase;
import bowlingGame.BowlingGame;
public class TestBowlingGame extends TestCase
{
BowlingGame game;
protected void setUp() throws Exception
{
game = new BowlingGame();
}
public void testGutterBalls()
{
manyOpenFrames(10, 0, 0);
assertEquals(0, game.getScore());
}
public void testThrees()
{
manyOpenFrames(10, 3, 3);
assertEquals(60, game.getScore());
}
public void testSpareFrame()
{
game.addSpareFrame(4, 6);
game.addOpenFrame(3, 5);
manyOpenFrames(8, 0, 0);
assertEquals(21, game.getScore());
}
public void testSpareFrame2()
{
game.addSpareFrame(4, 6);
game.addOpenFrame(5, 3);
manyOpenFrames(8, 0, 0);
assertEquals(23, game.getScore());
}
public void testSpareFrame3()
{
game.addSpareFrame(4, 6);
game.addSpareFrame(4, 6);
game.addOpenFrame(5, 3);
manyOpenFrames(7, 0, 0);
assertEquals(37, game.getScore());
}
public void testStrike()
{
game.addStrikeFrame();
game.addOpenFrame(5, 3);
manyOpenFrames(8, 0, 0);
assertEquals(26, game.getScore());
}
public void testSpareAndStrike()
{
game.addSpareFrame(4, 6);
game.addSpareFrame(4, 6);
game.addStrikeFrame();
game.addOpenFrame(5, 3);
manyOpenFrames(6, 0, 0);
assertEquals(60, game.getScore());
}
public void testStrikeFinalFrame()
{
manyOpenFrames(9, 0, 0);
game.addStrikeFrame();
game.addBonusRoll(5);
game.addBonusRoll(3);
assertEquals(18, game.getScore());
}
public void testSpareFinalFrame()
{
manyOpenFrames(9, 0, 0);
game.addSpareFrame(4, 6);
game.addBonusRoll(5);
assertEquals(15, game.getScore());
}
public void testPerfectScore()
{
for (int i = 0; i < 10; i++)
game.addStrikeFrame();
game.addBonusRoll(10);
game.addBonusRoll(10);
assertEquals(300, game.getScore());
}
public void testAlternating()
{
for (int i = 0; i < 5; i++)
{
game.addStrikeFrame();
game.addSpareFrame(4, 6);
}
game.addBonusRoll(10);
assertEquals(200, game.getScore());
}
private void manyOpenFrames(int count, int firstBall, int secondBall)
{
for (int frameNumber = 0; frameNumber < count; frameNumber++)
game.addOpenFrame(firstBall, secondBall);
}
}
package bowlingGame;
import java.util.ArrayList;
import java.util.List;
public class BowlingGame
{
private List frames;
public BowlingGame()
{
this.frames = new ArrayList();
}
public void addOpenFrame(int firstBall, int secondBall)
{
this.frames.add(new OpenFrame(firstBall, secondBall));
}
public void addSpareFrame(int firstBall, int secondBall)
{
this.frames.add(new SpareFrame(firstBall, secondBall));
}
public void addStrikeFrame()
{
this.frames.add(new StrikeFrame());
}
public void addBonusRoll(int roll)
{
this.frames.add(new BonusRoll(roll));
}
public int getScore()
{
int score = 0;
for (int i = 0; i < frames.size(); i++)
{
Frame frame = (Frame) frames.get(i);
score += frame.getScore(getNextFrame(i));
}
return score;
}
private Frame getNextFrame(int index)
{
int nextIndex = index + 1;
if (nextIndex == this.frames.size()) return new EndFrame();
return (Frame) this.frames.get(nextIndex);
}
}
package bowlingGame;
abstract public class Frame
{
protected int firstBall;
protected int secondBall;
protected Frame(int firstBall, int secondBall)
{
this.firstBall = firstBall;
this.secondBall = secondBall;
}
abstract int getScore(Frame nextFrame);
public int getFirstBall()
{
return this.firstBall;
}
public int getSimpleTotal()
{
return this.firstBall + this.secondBall;
}
}
package bowlingGame;
public class OpenFrame extends Frame
{
public OpenFrame(int firstBall, int secondBall)
{
super(firstBall, secondBall);
}
public int getScore(Frame nextFrame)
{
return getSimpleTotal();
}
}
package bowlingGame;
public class StrikeFrame extends Frame
{
public StrikeFrame()
{
super(10, 10);
}
public int getScore(Frame nextFrame)
{
return this.firstBall + nextFrame.getSimpleTotal();
}
}
package bowlingGame;
public class SpareFrame extends Frame
{
public SpareFrame(int firstBall, int secondBall)
{
super(firstBall, secondBall);
}
public int getScore(Frame nextFrame)
{
return 10 + nextFrame.getFirstBall();
}
}
package bowlingGame;
public class BonusRoll extends Frame
{
public BonusRoll(int roll)
{
super(roll, 0);
}
public int getScore(Frame nextFrame)
{
return nextFrame.getFirstBall();
}
}
package bowlingGame;
public class EndFrame extends Frame
{
public EndFrame()
{
super(0, 0);
}
public int getScore(Frame nextFrame)
{
return 0;
}
}
--
shanem...@yahoo.com.clothes
remove clothes before replying
"It is not the strongest of the species that survive, nor the most
intelligent, but the one most responsive to change." --- Charles Darwin
Costin Cozianu
John Elrick
> Have you tried with [1,2,1,1] ?
I see your point.
John
Robert Oliver
> 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.
Are you waiting for a set of unit tests that can be used to guarantee a
correct solution to your posted problem? If so I suspect it will take
longer than my first algorithm will take to complete [999,998,...,1].
TDD doesn't work that way. Tests are developed along the way.
How do you go about developing tests for the software you write? I suspect
you try to find ways the software might fail and build test cases around
them. Then if the software does fail, you fix it. Am I even close?
Regards,
Robert Oliver
Ron Jeffries
wrote:
>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.
That's what I'd expect too, though I often gain confidence in the algorithm
which seems to be borne out by later experience with the program.
Universe
> remove clothes before replying
Done! ;- }
> "It is not the strongest of the species that survive, nor the most
> intelligent, but the one most responsive to change." --- Charles
Darwin
I.)
Just a few words, and to begin, I don't really disagree with this.
The essence of Darwin's ideas, considering them as a whole beyond just
the above remark, seems to me, to be that organisms that are able to
adapt to what they face tend to be successful.
Rather than the key being that a species is the "*most* responsive to
change", or some other slightly different formulation, it appears that
species have successfully adapted to contextual changes if their
adaptive response was "at least enuff", i.e. "at least *sufficient*".
II.)
It doesn't seem to be "survival of the fittest", that is salient to a
species ability to survive, but the ability of a species to survive in a
given context. Historically it is evident that it has been the good
fortune of multiple species to simultaneously adapt successfully to an
environment. Some species use the same, or a common genetic trait to
succeed, while other species use other genetic traits.
III.)
Although successful adaptation to contextual change involves having
genetic traits that confer the ability to adapt to the environment, I'm
not so sure this is "directly" true for hominids--especially the later
ones like homo-sapiens.
Genetic mechanisms interacting with the context of experience of
hominids has led to a large brain size. There is no doubt that this
large brain has helped hominids to adapt successfully to many contextual
changes. But it also seems that much of hominids ability to adapt has
come out of a scientific process of learning about the environment and
carrying out practices that enabled hominids to cope with their
environment. In later times this social epistemological process seems
to play a more predominant role in the ability of homo-sapiens to adapt
successfully than does a kind of direct genetic evolution.
Elliott
--
*~* Theory Leads, Practice Verifies *~*
*~* Global Plans + IID (Iterative & Incremental Development) *~*
--
Be bold, be artistically imaginative, yet scientifically grounded -- DO
GREAT OO MODELLING WITH OBJECTS OF ALL TYPES!!
Costin Cozianu
> "Costin Cozianu" <c_co...@hotmail.com> wrote in message
> news:bpgh0g$1ok02n$1...@ID-152540.news.uni-berlin.de...
>
>
>>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.
>
>
> Are you waiting for a set of unit tests that can be used to guarantee a
> correct solution to your posted problem?
For the vast majority of problems in the wild no Unit Test, Integration
Test, Automation Test, XP or non-XP can guarantee a correct solution.
However, some tests are deemed relevant, in the sense that they can
inspire great confidence in the correctness of an implementation. In
other words, given that the program passes a battery of such tests the
likelyhood of the program still having bugs is minimal.
> If so I suspect it will take
> longer than my first algorithm will take to complete [999,998,...,1].
>
> TDD doesn't work that way. Tests are developed along the way.
>
I know how TDD is supposed to work. The mantra is test first, no
functionality added before a test is written. You have to either you
write very irrelevant test cases like John did, or you did or not write
any test at all, because only after you get a grasp of the design of the
solution you are able to write relevant tests.
> How do you go about developing tests for the software you write? I suspect
> you try to find ways the software might fail and build test cases around
> them. Then if the software does fail, you fix it. Am I even close?
>
I very rarely if ever write the tests first. I write them post factum,
and I write them very differently.
I also don't write tests for trivial things. And I have a QA department
to save my ass :) In this case, I'd have a huge amount of random data
with solutions and let your algorithm run overnight. In some cases, I
had extensive tests run over the weekend, and even for a week.
This requires a totally separate engineering effort dedicated to writing
tests, and in any way it cannot be "test first".
> Regards,
> Robert Oliver
>
>
best,
Costin
Costin Cozianu
> For the vast majority of problems in the wild no Unit Test, Integration
> Test, Automation Test, XP or non-XP can guarantee a correct solution.
>
Actually it was meant *cannot* guarantee a correct solution.
Universe
"Universe" <univ...@covad.net> wrote in message:
> ...
> II.)
> It doesn't seem to be "survival of the fittest", that is salient to a
> species ability to survive, but the ability of a species to survive in a
> given context. Historically it is evident that it has been the good
> fortune of multiple species to simultaneously adapt successfully to
*** the same niche(s) in ***
> an environment. Some species use the same, or a common genetic trait to
> succeed, while other species use other genetic traits.
> ...
Elliott
Robert Oliver
<snip>
> > How do you go about developing tests for the software you write? I
suspect
> > you try to find ways the software might fail and build test cases around
> > them. Then if the software does fail, you fix it. Am I even close?
> >
> I very rarely if ever write the tests first. I write them post factum,
> and I write them very differently.
>
> I also don't write tests for trivial things. And I have a QA department
> to save my ass :) In this case, I'd have a huge amount of random data
> with solutions and let your algorithm run overnight. In some cases, I
> had extensive tests run over the weekend, and even for a week.
In this case, where would you find this "huge amount of random data with
solutions"? So much, in fact, that you could reasonably "run overnight"?
> This requires a totally separate engineering effort dedicated to writing
> tests, and in any way it cannot be "test first".
Well, I've spent a fair amount of time testing Radar systems. We were
required to write tests from the specification years before the product was
delivered. Different? Somewhat. But the basic principle was, "if you can't
test the requirement, it's not really required." Many important tests can
be written first.
Regards,
Robert Oliver
Costin Cozianu
Agreed. There are cases and cases. Other tests cannot be written first.
Like in this instance. Having a solution of my own, I can produce tons
of random samples and their solutions, quite easily. But without having
the solution, you can only handpick a few samples, and even that is
error prone.
Many tests can be written first, indeed, starting from requirements
(although Uncle Bob, Phlip et. comp. claimed that requirements *should*
be written as executable tests). Other tests involved individual modules
that do not have a requirements document.
Yet other requirements can be proved to be met. Not that I write any of
these proofs, of course, it is too tedious yet, but it is my
responsibility that I should be able to write the proof should anybody
ask. And trying to render the program provable can lead to very clean
designs, much more than trying to write tests. That's why proof driven
development, what Dijkstra recommended 3 decades ago is better for
evolving a good design than test driven development.
Donald Roby
> 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.
>
"any longest non-decreasing subsequence"
Robert Oliver
> Robert Oliver wrote:
<snip>
> > Well, I've spent a fair amount of time testing Radar systems. We were
> > required to write tests from the specification years before the product
was
> > delivered. Different? Somewhat. But the basic principle was, "if you
can't
> > test the requirement, it's not really required." Many important tests
can
> > be written first.
> >
requirements. Our so-called traceability matrix included methods of
verification like inspection and analysis in addition to testing.
>
> Agreed. There are cases and cases. Other tests cannot be written first.
> Like in this instance. Having a solution of my own, I can produce tons
> of random samples and their solutions, quite easily. But without having
> the solution, you can only handpick a few samples, and even that is
> error prone.
Where did your solution come from?
Who programmed it?
How can you be sure it is correct?
Even if the algorithm it uses is correct, is the implementation correct?
Yes indeed, I do not have the solution yet. I am interested in exploring
how solutions are developed using TDD. I'm trying to pay attention to the
insight I get from following the process and watch the algorithm develop.
Knowing the solution ahead of time is not helpful in this effort. On the
job? Well that's another story...
> Many tests can be written first, indeed, starting from requirements
> (although Uncle Bob, Phlip et. comp. claimed that requirements *should*
> be written as executable tests). Other tests involved individual modules
> that do not have a requirements document.
Do you agree that there is some value in expressing a requirement as an
executable test?
> Yet other requirements can be proved to be met. Not that I write any of
> these proofs, of course, it is too tedious yet, but it is my
> responsibility that I should be able to write the proof should anybody
> ask. And trying to render the program provable can lead to very clean
> designs, much more than trying to write tests. That's why proof driven
> development, what Dijkstra recommended 3 decades ago is better for
> evolving a good design than test driven development.
(Anybody know a good emoticon for "biting ones tongue"?)
The process you seem to be advocating is "too tedious" to use yet, but
better than TDD? It doesn't seem to be much help.
Regards,
Robert Oliver
Costin Cozianu
> "Costin Cozianu" <c_co...@hotmail.com> wrote in message
> news:bphito$1ns1m9$1...@ID-152540.news.uni-berlin.de...
>
>>Robert Oliver wrote:
>
> <snip>
>
>>>Well, I've spent a fair amount of time testing Radar systems. We were
>>>required to write tests from the specification years before the product
>
> was
>
>>>delivered. Different? Somewhat. But the basic principle was, "if you
>
> can't
>
>>>test the requirement, it's not really required." Many important tests
>
> can
>
>>>be written first.
>>>
>
> Let me be clear. We did not insist that "testing" alone verify
> requirements. Our so-called traceability matrix included methods of
> verification like inspection and analysis in addition to testing.
>
Agreed.
>>Agreed. There are cases and cases. Other tests cannot be written first.
>>Like in this instance. Having a solution of my own, I can produce tons
>>of random samples and their solutions, quite easily. But without having
>>the solution, you can only handpick a few samples, and even that is
>>error prone.
>
>
> Where did your solution come from?
From thinking. The exercised came from a book , long time ago, in the
way it was discussed originally, only the maximum length was required.
> Who programmed it?
I did.
> How can you be sure it is correct?
Proof obligation.
> Even if the algorithm it uses is correct, is the implementation correct?
>
Idem.
> Yes indeed, I do not have the solution yet. I am interested in exploring
> how solutions are developed using TDD. I'm trying to pay attention to the
> insight I get from following the process and watch the algorithm develop.
Now the point is that 3 decades ago Dijkstra claimed that in order to
come up with algorithm designs is to search for a proof. He mentions
that in his "memoirs" of OS design: they were trying to solve the mutual
exclusion problem (now we take it for granted from the OS, but they were
writing the OS), and they weren't making much headway, until Dijkstra
unhappy that he had to analyze all kinds of bogus solutions let his
colleagues know that he wouldn't accept any more solutions unless
acompanied by a proof. Then in a few hours one of his coleagues, Dekker
came both with solution and the proof, because he was looking for how to
make thing s provable.
This methodology is later documented in books like "A Discipline of
Programming" Dijkstra 76, "The Science of Programming" Gries 80, "A
Method Of Programming" by Dijkstra, Sterringa and Feijen. And in many
short articles by Dijkstra all on non-trivial programming problems and
all much shorter than our friend Ron Jeffries is spending on trivial things.
People seem to have forgotten these things, or if they are young they
never learnt them.
> Knowing the solution ahead of time is not helpful in this effort. On the
> job? Well that's another story...
>
On the job, I sometimes face non-trivial problems. But most of the times
I can find analogies with something written by somebody esle, someplace
else. Even if you know a solution to a similar problem, TDD is highly
unlikely to get you anywhere for the hard nuts you have to crack.
>
>>Many tests can be written first, indeed, starting from requirements
>>(although Uncle Bob, Phlip et. comp. claimed that requirements *should*
>>be written as executable tests). Other tests involved individual modules
>>that do not have a requirements document.
>
>
> Do you agree that there is some value in expressing a requirement as an
> executable test?
>
I am very doubtful. They'd have to be expressed first as a combination
of unambiguous english and light formalism (equations for example). I'd
be worried that getting your customers to sign off requirements as code
is inviting trouble.
After the reuirements are defined, yes there is value in writing the
executable tests, but I guess not before that.
>
>>Yet other requirements can be proved to be met. Not that I write any of
>>these proofs, of course, it is too tedious yet, but it is my
>>responsibility that I should be able to write the proof should anybody
>>ask. And trying to render the program provable can lead to very clean
>>designs, much more than trying to write tests. That's why proof driven
>>development, what Dijkstra recommended 3 decades ago is better for
>>evolving a good design than test driven development.
>
>
> (Anybody know a good emoticon for "biting ones tongue"?)
>
> The process you seem to be advocating is "too tedious" to use yet, but
> better than TDD? It doesn't seem to be much help.
>
It is too "tedious" to do it formally (using proof tools). But you can
still do it informally. I am hopeful that in maybe 2 decades we'll have
good enough tools to make formality feasible. Trying to do it informally
with pen and paper, still allows you to get to good design faster and
better than with the latest refactoring wizard in Eclipse.
> Regards,
>
> Robert Oliver
>
>
Best,
Costin
Robert Oliver
First, let me apologize for snipping all the preceeding text. My news
reader doesn't send replys with too much original text.
If I understand the thread so far you advocate the development of software
(at least the algorithm) by proof.
Yet, proof is too tedious in many (most?) cases.
Perhaps in two decades the tools will be available for a formal proof, until
then informal proofs can be used.
When you don't have a preexisting solution to the problem and the proof is
too tedious, what do you do? For me, this is what mostly every interesting
program looks like.
I don't have much experience in trying to prove my software correct. Would
it be possible to post your proof for this problem? It would help me better
understand what you are saying.
Finally, it seems to me that TDD and searching for a proof are somewhat
orthogonal. Couldn't a TDD practitioner use proofs and mathematical
techniques to advantage in the same way others do?
Regards,
Robert Oliver
Costin Cozianu" <c_co...@hotmail.com> wrote in message
news:bpimca$1p243i$1...@ID-152540.news.uni-berlin.de...
--
Opportunity is missed by most people because it is dressed in overalls and
looks like work. - T. A. Edison
Steve Haigh
>>"It is not the strongest of the species that survive, nor the most
>>intelligent, but the one most responsive to change." --- Charles
>
> Darwin
>
> I.)
>
> Just a few words, and to begin, I don't really disagree with this.
<snip>
You are responding to someone's .sig???
Firstly, why is it necessary to respond to a comment in a .sig?
Second, with all due respect, why are you telling us your opinion on
Darwin's theories? (interesting though they are, and I was all set to
respond to them until I realised how OT it all is).
Finally, I am sure there are plenty of other groups where this topic is
discussed fervently and where your post would be welcomed (or flamed -
I'm sure there are creationist groups out there too!).
John Elrick
> Have you tried with [1,2,1,1] ?
I'll be back after the holidays...
John
Uncle Bob (Robert C. Martin)
>Uncle Bob (Robert C. Martin) wrote:
>
>> 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.
That's easy. Each digit may be present or not. If there are N digits
there are 2^N possibilities. So at least the search tree is 2**N
>
>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.
It's an interesting problem. I wrote up the test cases in a hotel in
amsterdam; and got the initial 2**N algorithm working one evening
after giving a talk at a trade show. I managed to find a way to prune
the search tree while on a train from Eindhoven to Schipol. I think I
see a few more prunings. The test cases help me to make sure that my
prunings haven't broken anything. I've had a busy weekend (a good
friend died), and I have a class to teach this week, and thanksgiving
to attend, and articles to write and -- well -- it may be another few
weeks before I can take the time. It's not real high on my priority
list. But it is a fun problem!
Costin Cozianu
> Costin Cozianu <c_co...@hotmail.com> might (or might not) have
> written this on (or about) Wed, 19 Nov 2003 11:40:03 -0800, :
>
>
>>Uncle Bob (Robert C. Martin) wrote:
>>
>>
>>>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.
>
>
> That's easy. Each digit may be present or not. If there are N digits
> there are 2^N possibilities. So at least the search tree is 2**N
>
This proves that the space to search with the dummy algorithm is 2**N.
What I was saying is that the space of real solutions can be
exponential. So a program who will output all the solutions possible may
run in exponential time.
Universe
> ... on a train from Eindhoven to Schipol.
Nice airport. Amsterdam is a nice place to "entrez-vous" the Continent. I
like the vibe of Scandanavia and to me the Nederlands is "South
Scandanavia."
A salient feature of Scandanavia to me is how the intellectual
superstructure, not as wedded to the Pragmatist philosophy outlook of
Pierce, Dewey, James, etc., provided the nifty greenhouse fertilization for
maturation of the "world is collaborating objects" world view.
Next of course was the subsequent introduction of that viewpoint into
software engineering by the Norwegian Scandanavians Nygaard & Dahl. At
their web sites they stated that they had reached the limits of conceptually
understanding and then handling use cases that were to assist a Norwegian
shipping firms in routing and scheduling their ships. The system
requirements scope could be said to be "NP++".
It was a good thing Nygaard & Dahl did not base themselves upon what was
popular, or in demand, but upon the objective truth as it was developing in
software engineering at the time.
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) *~*
--
Though types only make sense relative to context, system worthwhile types
are *objectively* significant for the relative context.
--
Tis Season For All Reason, to be Laffing OO the Way!!!!!!! :- }
Ilja Preuß
>> When you have mathematics vs. words you should have trusted the math.
>
> <g>Never...I've worked too long. See below...
I once saw an algebraic specification for a List, which besides other things
(indirectly) specified that true == false. I decided to trust the word
"List" more than the algebraic specification and assumed that there was a
little error in the math part. Possibly I was wrong... ;)
Take care, Ilja
S Perryman
It is quite simple to prove what the lower/upper bounds of the search
space are (where "bound" = length of valid subsequence) for any given
sequence. For example :
1. [123123123] : lower = 5, upper = 7
2. [1211] : lower = 2, upper = 3
3. [1000,999,998, ... , 1, 0] : lower = 1, upper = 1
4. [1000,999,998, ... , 1, 900] : lower = 2, upper = 2
The bounds can be computed with at worst O(2N) comparisons.
If someone can use examples 1 and 2 to derive a corresponding worst case
"big Oh" for an algorithm that searches all combinations within any
given bounds, Santa will no doubt reward you next month (I am too lazy)
... :-)
Regards,
Steven Perryman
Paul Campbell
"Costin Cozianu" <c_co...@hotmail.com> wrote in message news:bph64m$1msum1$1...@ID-152540.news.uni-berlin.de...
> I also don't write tests for trivial things. And I have a QA department
> to save my ass :) In this case, I'd have a huge amount of random data
> with solutions and let your algorithm run overnight.
I find this a very inconsistent standoint - your entire argument upto this point
is predicated on the idea that more direct use of knowledge of the actual solution
itself is better (a proof being the most extreme example of the direct use of
of the solution logic). Yet now you turn around and say that the technique
which involves the *least* knowledge of the actual solution is better than
one that uses more ??.
Paul C.
Costin Cozianu
I'm not saying which one is better, they serve different purposes. It is
always better to have an independent QA department because they will
test including the things that you don't test. It is an indepenedent
verification and independence in itself has a high value.
On the other hand,some of the tests QA department runs are either
written by me or I contributed to them substantially. It works both ways.
But in some case cases such as the problem in discussion a reallistic
test cannot be constructed at all without knowing a good solution.
Costin
Isaac Gouy
> Adventures in C#: The Bowling Game
> Ron Jeffries
> 11/17/2003
>
> When I demonstrate Test-Driven Development using the Bowling Game
Stumbled across "The Bowling Game"
http://www.xprogramming.com/xpmag/acsBowling.htm and happily "The
Story" is long enough that I didn't reach "The Design Idea" before I
decided to look for a solution. A back of the envelope, BUFD solution.
Must have seen bowling sometime in a movie, but I've never played and
didn't know the rules - I wasn't sure if "rolls" and "tries" and
"balls" were the same thing.
1) figure out what the problem is, what a solution would look like...
I scribbled various representations while trying to figure out what
the problem was:
- a list of score pairs [ (2,5) (5,6) (0,0) ...]
but then I noticed that sometimes there was just one roll in a
'strike'
- a list of lists [ [10] [2,5] [5,6] ...]
and noticed that we always had 10 things, so we could also do
- an array of lists { [10] [2,5] [5,6] ... }
and then wondered what we were trying to find out...
Oh - "the *total* score for the game"
- a "sequence of rolls" [10, 2, 5, 5, 6 ...]
can we simply accumulate the score?
2) case analysis
So if we take the "rolls" one at a time can we figure out what should
be added to the total?
loop
total = total + ?
end
if pins = 10 then ...
if pins = 10 then
total = total + pins + next2
OK
else if pins1 + pins2 = 10 then
total = total + pins1 + pins2 + next1
OK
else
total = total + pins1 + pins2
OK, what does that look like for a sequence of rolls?
if p(i) = 10 then
t = t + p(i) + ( p(i+1) + p(i+2) )
else if p(i) + p(i+1) = 10 then
t = t + p(i) + p(i+1) + ( p(i+2) )
else
t = t + p(i) + p(i+1)
OK, do we need to check the index bounds everytime?
Whatever! We do need to increment the index so
if p(i) = 10 then
t = t + p(i) + ( p(i+1) + p(i+2) )
i = i + 1
else if p(i) + p(i+1) = 10 then
t = t + p(i) + p(i+1) + ( p(i+2) )
Oh! we skip over a "roll" - that's the difference between these cases!
else if p(i) + p(i+1) = 10 then
t = t + p(i) + p(i+1) + ( p(i+2) )
i = i + 2
3) iteration
How do we boundary check the index i?
We could use the size of the "sequence of rolls" and check explicitly?
We know that there are always 10 things - should we just count them
and halt after the last thing is processed?
while frames < 10
if p(i) = 10 then
t = t + p(i) + ( p(i+1) + p(i+2) )
i = i + 1
frames = frames + 1
else if p(i) + p(i+1) = 10 then
t = t + p(i) + p(i+1) + ( p(i+2) )
i = i + 2
frames = frames + 1
else
t = t + p(i) + p(i+1)
i = i + 2
frames = frames + 1
Does that work? Need to look at the rules again!
Seems to - the game adds bonus balls so that scoring the tenth frame
is the same as scoring any of the other frames. For "a *valid*
sequence of rolls" we don't need to check the index bounds.
4) code (Nice http://nice.sourceforge.net/index.html )
void main(String[] args){
var frames = 0;
var total = 0;
var i = 0;
let int[] pins = [4,6, 3,5, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0,
0,0];
while (frames<10){
if (pins[i] == 10) {
total += pins[i] + pins[i+1] + pins[i+2];
i++;
}
else if (pins[i] + pins[i+1] == 10) {
total += pins[i] + pins[i+1] + pins[i+2];
i += 2;
}
else {
total += pins[i] + pins[i+1];
i += 2;
}
frames++;
}
println(total);
}
5) test
Silly. Went through testing changing the values in pins[] - must be
late.
Re-write to separate out the test values.
Pity not to have used a Unit test framework ;-)
int score(int[] pins){
var frames = 0;
var total = 0;
var i = 0;
while (frames<10){
if (pins[i] == 10) {
total += pins[i] + pins[i+1] + pins[i+2];
i++;
}
else if (pins[i] + pins[i+1] == 10) {
total += pins[i] + pins[i+1] + pins[i+2];
i += 2;
}
else {
total += pins[i] + pins[i+1];
i += 2;
}
frames++;
}
return total;
}
void main(String[] args){
let int[][] tests = [
[0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0],
[3,3, 3,3, 3,3, 3,3, 3,3, 3,3, 3,3, 3,3, 3,3, 3,3],
[4,6, 3,5, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0],
[4,6, 5,3, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0],
[10, 5,3, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0],
[0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 10, 5,3],
[0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 4,6, 5],
[10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10],
[10, 4,6, 10, 4,6, 10, 4,6, 10, 4,6, 10, 4,6, 10]
];
for(each:tests) println( score(each) );
}
6) observations
#1 #2 #3 #4 an hour, #5 an hour.
We've coded as though "sequence of rolls" is indexed - what would it
be like if we go back to #3 and get rid of the indices?
Representation is everything! Once we see that a bowling game can be
represented as a simple sequence of "the number of pins knocked down"
on each roll, encoding the game rules becomes straightforward. (I
wonder what ye olde JSP design would look like?)
Reducing the cost of testing matters: test framework == good thing
7) conclusions
"But think about it. Less up-front design, and a better result. Could
it be true?"
http://www.xprogramming.com/xpmag/acsBowlingProcedural.htm
The difference isn't "Less up-front design" it's "Less OO design"!
And, of course, it rather depends what we mean by "a better result".
best wishes, Isaac
Isaac Gouy
> Adventures in C#: The Bowling Game
> Ron Jeffries
> 11/17/2003
>
> When I demonstrate Test-Driven Development using the Bowling Game
Following on from BUFD version of the Bowling Game (given that we've
figured out the solution as far as #3) a language with pattern
matching and list functions would allow a recursive solution (compare
to #4) like this:
Start = score [0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 10,
5,3] 0 0
score pins total 10 = total
score [x,y] total frame = total + x + y
score [x,y,z:rest] total frame
| x == 10 = score [y,z:rest] (total+x+y+z) (frame+1)
| x+y == 10 = score [z:rest] (total+x+y+z) (frame+1)
| otherwise = score [z:rest] (total+x+y) (frame+1)
To explain:
- if we've done 10 frames we're finished
- if there are only 2 items we're finished (main clause needs 3 items
to match)
- 3 rules for calculating the score
best wishes, Isaac
John W. Wilkinson
I thought you only added code if a test requires it, and you then refactor
to *reduce* complexity. However, near the start of the example, you have the
code correctly calculating the score for 10*(3,3) frames by a simple summing
algorithm. You then refactor adding the OpenFrame class. This class is added
in anticipation of future need, making the current design more complicated
than the current tests require.
Also there are no tests that solely test the IFrame derived classes. I
imagined that in TDD every class should have their own tests.
John
"Ron Jeffries" <ronje...@REMOVEacm.org> wrote in message
news:l11irvgd06vp6aqup...@4ax.com...
> 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.
Ron Jeffries
>Following on from BUFD version of the Bowling Game
Neat examples, Isaac ... though I don't understand why you called the first one
BUFD ... it seemed like you only designed for a few moments before turning to
code.
Ron Jeffries
<john.wilkinson@spirentcom_removethis.com> wrote:
>The TDD used in the example isn't as rigorous as I thought it would be.
>
>I thought you only added code if a test requires it, and you then refactor
>to *reduce* complexity.
Ideally I would only add code in response to a broken test.
However, we refactor to improve design, not just to reduce complexity. Basically
there are two ways to go, roughly like this:
1. We put in some code that is too complex and then rearrange the code to remove
it. This is my preferred way of working, for some reason having to do with
showing that it is always possible to get out of a hole easily or something like
that.
2. We are about to put in some code, but we see that it will be complex to put
it in. So we refactor to "make a place" to put the code.
Both are "approved practices". I do not know at this time how I decide which one
to do.
>However, near the start of the example, you have the
>code correctly calculating the score for 10*(3,3) frames by a simple summing
>algorithm. You then refactor adding the OpenFrame class. This class is added
>in anticipation of future need, making the current design more complicated
>than the current tests require.
Yes. I have a change in mind, and am making the code have a place for it. That
is definitely anticipatory.
>
>Also there are no tests that solely test the IFrame derived classes. I
>imagined that in TDD every class should have their own tests.
It can be argued that before classes are released into the wild they should have
their own tests. It often turns out, using TDD, that those tests do not
naturally arise. A "better" solution in this case might be to make those classes
private or package protected, so that they never go out on their own and get
into trouble.
Isaac Gouy
> On 24 Nov 2003 13:50:14 -0800, ig...@yahoo.com (Isaac Gouy) wrote:
>
> >Following on from BUFD version of the Bowling Game
>
> Neat examples, Isaac ... though I don't understand why you called the first one
> BUFD ... it seemed like you only designed for a few moments before turning to
> code.
Depends what you mean by "turning to code" ;-)
I spent most of an hour before I wrote in some specific programming
language and tried to get it to compile.
#1 was exploring the problem
#2 was writing down what the game rules were (in subscript notation)
#3 putting the rules into a terminating algorithm
#4 coding the algorithm
1-3 seems to be analysis and design
4 seems to be coding
The second example is BFUD as-well, it just uses the same analysis and
design and implements without using explicit indexing, which gives IMO
a clearer solution.
What do you mean by BFUD?
best wishes, Isaac
Isaac Gouy
> 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
"But think about it. Less up-front design, and a better result. Could
it be true?"
http://www.xprogramming.com/xpmag/acsBowlingProcedural.htm
Seems to me that the difference isn't "Less up-front design" it's "Less OO design"!
Isaac Gouy
> Ron Jeffries <ronje...@REMOVEacm.org> wrote in message news:<l11irvgd06vp6aqup...@4ax.com>...
> > 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.
> Seems to me that the difference isn't "Less up-front design" it's "Less OO design"!
Presuming we wanted an OO solution to the Bowling Game, the only
obvious responsibility is that something has to calculate the total
score for a game, and of the candidate objects the one we definitely
need is a BowlingGame.
The Nice OO solution requires a little more code than the procedural
solution, but not 5 times more code. Seems like the BUFD solution
given in http://www.xprogramming.com/xpmag/acsBowling.htm is a
strawman, loaded with detail that has no relevance to the problem.
(Frames hinder rather than help, because the score for a ball involve
pin-scores from 3 frames.)
class BowlingGame {
int[] balls;
int score(){
var frames = 0;
var total = 0;
var i = 0;
while (frames<10){
if (balls[i] == 10) {
total += balls[i] + balls[i+1] + balls[i+2];
i++;
}
else if (balls[i] + balls[i+1] == 10) {
total += balls[i] + balls[i+1] + balls[i+2];
i += 2;
}
else {
total += balls[i] + balls[i+1];
i += 2;
}
frames++;
}
return total;
}
}
void main(String[] args){
let BowlingGame[] testGames = [
new BowlingGame(
balls: [0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0]),
new BowlingGame(
balls: [3,3, 3,3, 3,3, 3,3, 3,3, 3,3, 3,3, 3,3, 3,3, 3,3]),
new BowlingGame(
balls: [4,6, 3,5, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0]),
new BowlingGame(
balls: [4,6, 5,3, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0]),
new BowlingGame(
balls: [10, 5,3, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0]),
new BowlingGame(
balls: [0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 10,
5,3]),
new BowlingGame(
balls: [0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 4,6,
5]),
new BowlingGame(
balls: [10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10]),
new BowlingGame(
balls: [10, 4,6, 10, 4,6, 10, 4,6, 10, 4,6, 10, 4,6, 10])
];
for(each:testGames) println( each.score() );
}
best wishes, Isaac
Uncle Bob (Robert C. Martin)
(or about) 29 Nov 2003 07:53:02 -0800, :
>ig...@yahoo.com (Isaac Gouy) wrote in message news:<ce7ef1c8.03112...@posting.google.com>...
>> Ron Jeffries <ronje...@REMOVEacm.org> wrote in message news:<l11irvgd06vp6aqup...@4ax.com>...
>> > 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.
>
>> Seems to me that the difference isn't "Less up-front design" it's "Less OO design"!
>
>Presuming we wanted an OO solution to the Bowling Game, the only
>obvious responsibility is that something has to calculate the total
>score for a game, and of the candidate objects the one we definitely
>need is a BowlingGame.
>
>The Nice OO solution requires a little more code than the procedural
>solution, but not 5 times more code.
The solution below doesn't seem to have any OO characteristics. The
fact that you've got some variables and function in a class does not
seem any different than having some variables and functions in a
program without a class.
>Seems like the BUFD solution
>given in http://www.xprogramming.com/xpmag/acsBowling.htm is a
>strawman, loaded with detail that has no relevance to the problem.
I agree with the last clause, but not the strawman. I use this
problem a *lot* when teaching classes; and the vast majority of BUFD
solutions involve frames. Specifically something like this:
+-+ next
| V
|Game|------>|Frame|---------->|Ball|
10 A 1..2 ^ 1
| |
|TenthFrame|----------+
I posted this problem on the net a little over two years ago. Back
then there was an outcry against the solution *because* it did not
contain a Frame class. Indeed, someone posted a frame based program
that was five times larger than the procedural solution and argued
that it was superior.
So, though the frame based solution is clearly inefficient and a poor
match for the problem, it isn't a strawman.
Robert C. Martin | "Uncle Bob"
Isaac Gouy
> ig...@yahoo.com (Isaac Gouy) might (or might not) have written this on
> (or about) 29 Nov 2003 07:53:02 -0800, :
> >The Nice OO solution requires a little more code than the procedural
> >solution, but not 5 times more code.
>
> The solution below doesn't seem to have any OO characteristics. The
> fact that you've got some variables and function in a class does not
> seem any different than having some variables and functions in a
> program without a class.
In the other solutions, the score function could be applied to any
int[] (or in the pure functional implementation any list of Int). In
this solution the score method is sent to a BowlingGame object.
Isn't that a fundamental OO characteristic - structuring behaviour
around objects?
(For encapsulation, we could move the intialization out of the
constructor, initialize to some empty collection and have an instance
method 'balls:' - there's nothing about the solution that requires an
array)
The solution is trivial - how many OO characteristics should we
expect?
> >Seems like the BUFD solution
> >given in http://www.xprogramming.com/xpmag/acsBowling.htm is a
> >strawman, loaded with detail that has no relevance to the problem.
>
> I agree with the last clause, but not the strawman. I use this
> problem a *lot* when teaching classes; and the vast majority of BUFD
> solutions involve frames. Specifically something like this:
>
> +-+ next
> | V
> |Game|------>|Frame|---------->|Ball|
> 10 A 1..2 ^ 1
> | |
> |TenthFrame|----------+
>
> I posted this problem on the net a little over two years ago. Back
> then there was an outcry against the solution *because* it did not
> contain a Frame class. Indeed, someone posted a frame based program
> that was five times larger than the procedural solution and argued
> that it was superior.
Did you agree with them that it was superior ;-)
> So, though the frame based solution is clearly inefficient and a poor
> match for the problem, it isn't a strawman.
When someone in a class comes up with a solution that is clearly
inefficient and a poor match for the problem, we guide them to a
better solution.
When someone who already knows that this is "clearly inefficient and a
poor match for the problem" uses it as an example of BUFD, it's a
strawman.
And in the hope of avoiding misunderstanding: What do you mean by
BUFD?
best wishes, Isaac
Universe
in message
> ig...@yahoo.com (Isaac Gouy) might (or might not) have written this on
> >ig...@yahoo.com (Isaac Gouy) wrote in message
> >> Ron Jeffries <ronje...@REMOVEacm.org> wrote in message
> >> > 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.
> >> Seems to me that the difference isn't "Less up-front design" it's
"Less OO design"!
Right!
> >Seems like the BUFD solution
> >given in http://www.xprogramming.com/xpmag/acsBowling.htm is a
> >strawman, loaded with detail that has no relevance to the problem.
And that is the CHIEF problem with the compare a so-called 'budf'
design against a tdd xp/allie design charades put on by those of
xp/allie persuasion.
These comparisons have no objectively validated, analysis of the domain,
use cases and resources available to the project.
I.e. These comparisons are typically exercises in unscientific xp/allie
wish fulfillment much more than anything else.
Isaac Gouy
> On Mon, 17 Nov 2003 16:31:05 -0600, "Uncle Bob (Robert C. Martin)"
> <u.n.c.l...@objectmentor.com> wrote:
Now that I've looked at the code
http://www.xprogramming.com/xpmag/acsBowling.htm
three 'bad things' stand-out:
1) as Robert C. Martin mentioned
> >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.
The problem description said "given a valid sequence of rolls for one
line of American Ten-Pin Bowling, produces the total score for the
game." The solution given doesn't solve that problem - it requires a
sequence of 'frames'.
There may be "no conditionals in the scoring code" but only because
"the parsing" has been pushed outside the problem scope!
2) From the problem description a game has 10 Frames, and bonus rolls
are part of the 10th frame; in the solution a game may have 12 Frames:
each BonusRoll is implemented as a Frame.
3) Frames share the 'throws' collection with Game (loss of
encapsulation - more code to update when the collection type is
changed)
best wishes, Isaac
Isaac Gouy
> Seems to me that the difference
> isn't "Less up-front design" it's "Less OO design"!
Let me sharpen that: the difference is bad OO analysis and design ;-)
All the way back to the original article, frames get shoved into the
solution without giving any reason why they are necessary or useful to
the solution: "OK, clearly a game object consists of a sequence of ten
frames"
http://www.objectmentor.com/resources/articles/xpepisode.htm
When we look at a bowling game scorecard (Figure 1 or better
http://www.bowling.uklinux.net/bowling/score.php3 ) we can see:
- a sequence of 'frames'
- a sequence of 'throws' (given as 'X' or '/' or the pin score)
So, while it's true that a game consists of a sequence of ten frames,
it's also true that a game consists of a sequence of throws. Why would
we assume that 'frames' will be a better representation than throws?
Here's an alternative OO BUFD
throws
|Game|------------->|Throw|
11..21| pins|
|
A
|
+---------+---------+
| | |
|Strike| |Spare| |Bonus|
Using Nice once more ( http://nice.sourceforge.net/index.html ) we
have a fairly straightforward solution:
class BowlingGame {
Throw[] throws;
int i = 0;
int score(){
var total = 0;
for (i = 0; i < throws.size; i++)
total += throws[i].score + throws[i].bonus(this);
return total;
}
int bonusOne() = throws[i+1].pinCount;
int bonusTwo() = throws[i+2].pinCount;
}
class Throw {
int pins;
int pinCount() = pins;
int score() = pins;
int bonus(BowlingGame game) = 0;
}
class Strike extends Throw {
bonus(BowlingGame game) = game.bonusOne + game.bonusTwo;
}
class Spare extends Throw {
bonus(BowlingGame game) = game.bonusOne;
}
class Bonus extends Throw {
score() = 0;
}
Seems cleaner than the 'frames' based solution doesn't it?
best wishes, Isaac
Like http://www.xprogramming.com/xpmag/acsBowling.htm we could assume
that the input is in-terms of Strike or Bonus throws rather than pin
counts.
Oh, let's do something directly comparable:
void main(String[] args){
let BowlingGame[] testGames = [
new BowlingGame(throws: manyOpenFrames(10,0,0)),
new BowlingGame(throws: manyOpenFrames(10,3,3)),
new BowlingGame(throws:
spareFrame(4,6) +
openFrame(3,5) +
manyOpenFrames(8,0,0)
),
new BowlingGame(throws:
spareFrame(4,6) +
openFrame(5,3) +
manyOpenFrames(8,0,0)
),
new BowlingGame(throws:
strikeFrame() +
openFrame(5,3) +
manyOpenFrames(8,0,0)
),
new BowlingGame(throws:
manyOpenFrames(9,0,0) +
strikeFrame() +
bonusRoll(5) +
bonusRoll(3)
),
new BowlingGame(throws:
manyOpenFrames(9,0,0) +
spareFrame(4,6) +
bonusRoll(5)
),
new BowlingGame(throws:
strikeFrame() + strikeFrame() +
strikeFrame() + strikeFrame() +
strikeFrame() + strikeFrame() +
strikeFrame() + strikeFrame() +
strikeFrame() + strikeFrame() +
bonusRoll(10) +
bonusRoll(10)
),
new BowlingGame(throws:
strikeFrame() + spareFrame(4,6) +
strikeFrame() + spareFrame(4,6) +
strikeFrame() + spareFrame(4,6) +
strikeFrame() + spareFrame(4,6) +
strikeFrame() + spareFrame(4,6) +
bonusRoll(10)
)
];
for(each:testGames) println( each.score() );
}
// utility functions for test cases
Throw[] manyOpenFrames(int count, int firstThrow, int secondThrow)
{
let throwCount = count*2;
Throw[] t = cast(new Throw[throwCount]);
for (int i = 0; i < throwCount; i+=2) {
t[i] = new Throw(pins: firstThrow);
t[i+1] = new Throw(pins: secondThrow);
}
return t;
}
Throw[] openFrame(int firstThrow, int secondThrow) {
return [ new Throw(pins: firstThrow), new Throw(pins:
secondThrow) ];
}
Throw[] spareFrame(int firstThrow, int secondThrow) {
return [ new Throw(pins: firstThrow), new Spare(pins:
secondThrow) ];
}
Throw[] strikeFrame() {
return [ new Strike(pins: 10) ];
}
Throw[] bonusRoll(int roll) {
return [ new Bonus(pins: roll) ];
}
Costin Cozianu
The bonusOne() and bonusTwo() methods depend in a funny way of the "i"
instance variable, and this only make sense in a very particular loop,
creating a nasty sequential dependency, plus you had to take the loop
variable at the instance level because of that. Don't know about your
tastes, but by my taste this is uggggggly.
Now there's a relationship between Game and Throw, however the
information seems to be somehow lost so it is redundantly recovered by
calling :
throws[i].bonus(this);
Which is yet one more ugly and unnecessary dependency. This all makes
the class Throw just a bunch of code chopped out of a loop and promoted
to the status of class. Just about the same as Ron's "OO" solutions
Costin
Isaac Gouy
We can use a similar approach to accumlate the intermediate bowling
scores for a possibly incomplete sequence of valid throws - update the
sequence after each throw and recalculate the scores.
Start = scores [10, 4,6, 10, 4,6, 10, 4,6, 10, 4,6] [] 0 0
scores pins a total 10 = a
scores [] a total count = a
scores [x] a total count = a
scores [x,y] a total count
| x == 10 = a
| x+y == 10 = a
| otherwise = a++[total+x+y]
scores [x,y,z:rest] a total count
| x == 10 = scores [y,z:rest] (a++[total+x+y+z]) (total+x+y+z)
(count+1)
| x+y == 10 = scores [z:rest] (a++[total+x+y+z]) (total+x+y+z)
(count+1)
| otherwise = scores [z:rest] (a++[total+x+y]) (total+x+y)
(count+1)
The answer in this case would be [20,40,60,80,100,120,140] - the 8th
total for the spare cannot be calculated until the next throw.
best wishes, Isaac
Universe
> ig...@yahoo.com (Isaac Gouy) wrote in message
> We can use a similar approach to accumulate the intermediate bowling
> scores for a possibly incomplete sequence of valid throws - update the
> sequence after each throw and recalculate the scores.
Yeah bouyeee!!!!
Just excited, man! I got it! Shweet worked out overall architectural
plan and real, actual proven hooks for then nitty gritty, lower level,
"how" aspect of the design.
[Aside: if a single class with "everything in it" effectively models
essential logical domain role abstractions and collaboration dynamics,
then it does. It would be silly to condemn such an OO design out of
hand, purely on the basis of it using only a single class. Some domains
are logically anchored in only 1 single major abstraction, or a single
abstraction period. Avoid dogmatism.] Check use of lighthearted,
*Logical* OOPL:
class Scorer
{
private:
ref2FrameStructure Frame;
ref2BagO'Frame FrameBag;
bool isFoul;
bool isBonus;
int PinArray
int ThrowCount;
public
Scorer( "init privates"; );
throw(Pins;...)
tally(Pins; ThrowCount; isFoul; FrameBag... )
};
structure Frames
{
private:
int FrameNum;
int mainDigit;
int upperLeftDigit;
int upperRightDigit;
public:
Frames(0, 0, 0, _FrameNum) { FrameNum=_FrameNum; };
};
~ must know specific pins up/down after a throw.
e.g if Pin 1 is standing after a throw( ) it affects the way Frame
score is calculated
~ must know if bowler committed line isFoul
~ must know specific
It seems the "tuned" following code might work as my 'tally( );'
Elliott
> Start = scores [10, 4,6, 10, 4,6, 10, 4,6, 10, 4,6] [] 0 0
>
> scores pins a total 10 = a
> scores [] a total count = a
> scores [x] a total count = a
>
> scores [x,y] a total count
> | x == 10 = a
> | x+y == 10 = a
> | otherwise = a++[total+x+y]
>
> scores [x,y,z:rest] a total count
> | x == 10 = scores [y,z:rest] (a++[total+x+y+z]) (total+x+y+z)
> (count+1)
> | x+y == 10 = scores [z:rest] (a++[total+x+y+z]) (total+x+y+z)
> (count+1)
> | otherwise = scores [z:rest] (a++[total+x+y]) (total+x+y)
> (count+1)
>
>
> The answer in this case would be [20,40,60,80,100,120,140] - the 8th
> total for the spare cannot be calculated until the next throw.
>
> best wishes, Isaac
+
--
Rather than try to make object design as much like procedural design as
possible, I have found that the most effective way of teaching the
idiomatic way
of thinking with objects is to immerse the learner in the "object-ness"
of the
material.
Universe
structure Frame //not Frame"s"
> {
> private:
> int FrameNum;
> int mainDigit;
> int upperLeftDigit;
> int upperRightDigit;
> public:
> Frames(0, 0, 0, _FrameNum) { FrameNum=_FrameNum; };
Elliott
--
Once a fortnight, Audrey and her close companion were driven to
re-experience bathing in the pure sound of shattering panes of glass.
Isaac Gouy
> I'm sorry to say, but your BDUF solution is as clear or as clean as mud.
Don't apologize - justify!
BDUF solution - the Big Dumb Up Front solution? ;-)
> The bonusOne() and bonusTwo() methods depend in a funny way of the "i"
> instance variable, and this only make sense in a very particular loop,
> creating a nasty sequential dependency, plus you had to take the loop
> variable at the instance level because of that. Don't know about your
> tastes, but by my taste this is uggggggly.
I agree!
Using a loop variable outside the scope of the loop is sooo very
error-prone.
-snip-
> This all makes the class Throw just a bunch of code chopped out of a loop
> and promoted to the status of class.
It's just another desperate attempt to somehow push responsibility
into the 'Throw' objects, when fulfilling that responsibility requires
information about other 'Throw' objects. Seems like the responsibility
should be given to some object that "knows" about all the 'Throw'
objects - like BowlingGame.
Once we move that responsibility back to BowlingGame, we're left with
something like this:
class BowlingGame {
Throw[] throws;
int i = 0;
int score(){
var total = 0;
for (i = 0; i < throws.size; i++){
if (throws[i].isStrike) {
total += throws[i].score + throws[i+1].bonus +
throws[i+2].bonus;
}
else if (throws[i].isSpare) {
total += throws[i].score + throws[i+1].bonus;
}
else {
total += throws[i].score;
}
}
return total;
}
}
class Throw {
int pins;
int score() = pins;
int bonus() = pins;
boolean isStrike() = false;
boolean isSpare() = false;
}
class Strike extends Throw {
isStrike() = true;
}
class Spare extends Throw {
isSpare() = true;
}
class Bonus extends Throw {
score() = 0;
}
Perhaps we should conclude that the Throw objects don't do anything
interesting and the OO benefit in-this-case comes from structuring
code around a BowlingGame (like this
http://groups.google.com/groups?dq=&hl=en&lr=&ie=UTF-8&oe=UTF-8&selm=ce7ef1c8.0311290753.6c4cd29a%40posting.google.com
)
best wishes, Isaac
Isaac Gouy
sequence of valid throws, we need to make 2 design changes: 1) we need
to return a sequence of scores; 2) we need to change the loop
invariant.
1) seems easy enough
ArrayList<int> scores(int[] pins){
var frames = 0;
var total = 0;
var i = 0;
let ArrayList<int> knownScores = new ArrayList();
while (frames<10){
if (pins[i] == 10) {
total += pins[i] + pins[i+1] + pins[i+2];
i++;
}
else if (pins[i] + pins[i+1] == 10) {
total += pins[i] + pins[i+1] + pins[i+2];
i += 2;
}
else {
total += pins[i] + pins[i+1];
i += 2;
}
frames++;
knownScores.add(total);
}
return knownScores;
}
which with the previous test cases gives
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 12, 18, 24, 30, 36, 42, 48, 54, 60]
[13, 21, 21, 21, 21, 21, 21, 21, 21, 21]
[15, 23, 23, 23, 23, 23, 23, 23, 23, 23]
[18, 26, 26, 26, 26, 26, 26, 26, 26, 26]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 18]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 15]
[30, 60, 90, 120, 150, 180, 210, 240, 270, 300]
[20, 40, 60, 80, 100, 120, 140, 160, 180, 200]
2) as the sequence of valid throws may be incomplete, we need to check
that there are enough throws in the sequence to calculate the next
score - if not we are finished.
ArrayList<int> scores(int[] pins){
var frames = 0;
var total = 0;
var i = 0;
let ArrayList<int> knownScores = new ArrayList();
var n = 0;
while (frames<10 && (n=pins.size-i)>1){
if (n==2) {
if (pins[i] + pins[i+1] < 10) {
total += pins[i] + pins[i+1];
i++;
}
else break;
}
else if (pins[i] == 10) {
total += pins[i] + pins[i+1] + pins[i+2];
i++;
}
else if (pins[i] + pins[i+1] == 10) {
total += pins[i] + pins[i+1] + pins[i+2];
i += 2;
}
else {
total += pins[i] + pins[i+1];
i += 2;
}
frames++;
knownScores.add(total);
}
return knownScores;
}
void main(String[] args){
let int[][] tests = [
[],
[3],
[3,3],
[3,3, 3],
[4,6],
[4,6, 3],
[4,6, 3,5],
[10],
[10, 5],
[10, 5,3],
[10, 5,3, 0],
[10, 4,6],
[10, 4,6, 10],
[10, 4,6, 10, 4],
[10, 4,6, 10, 4,6],
[0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0],
[3,3, 3,3, 3,3, 3,3, 3,3, 3,3, 3,3, 3,3, 3,3, 3,3],
[4,6, 3,5, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0],
[4,6, 5,3, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0],
[10, 5,3, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0],
[0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 10, 5,3],
[0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 4,6, 5],
[10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10],
[10, 4,6, 10, 4,6, 10, 4,6, 10, 4,6, 10, 4,6, 10]
];
for(each:tests) println( scores(each) );
}
which gives
[]
[]
[6]
[6]
[]
[13]
[13, 21]
[]
[]
[18, 26]
[18, 26]
[20]
[20, 40]
[20, 40]
[20, 40, 60]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 12, 18, 24, 30, 36, 42, 48, 54, 60]
[13, 21, 21, 21, 21, 21, 21, 21, 21, 21]
[15, 23, 23, 23, 23, 23, 23, 23, 23, 23]
[18, 26, 26, 26, 26, 26, 26, 26, 26, 26]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 18]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 15]
[30, 60, 90, 120, 150, 180, 210, 240, 270, 300]
[20, 40, 60, 80, 100, 120, 140, 160, 180, 200]
best wishes, Isaac
Universe
come from" question.
And yes it seems class Scorer might work as class Game. Not sure
thinking about it. Would like to hear peoples pros and cons. IsaacG is
seems to have a very good design and algorithms. I'm thinking the
following might supplement, fill out and possible provide a larger
"setting" for Isaac's designs and algorithms.
I know this is not syntactically correct. I'm mainly getting at overall
logical design solutions.
class Sensor
{
public:
virtual read( *Scorer, Lane ) { ... };
};
... };
class PinSensor : class Sensor
{
private:
int PinState[10];
PinState[10] PinStateArray[15];
public:
PinSensor ( "init privates" ) { ... };
read ( *Scorer, Lane ) { ... }; //get lane pin state
pinVal getPinVal( PinStateNDX ) { return PinState[PinStateNDX]; };
PinStateArrayCopy getPinStateArrayCopy( ) { ... };
};
class LineSensor : class Sensor
{
private:
bool isFoul;
isFoul[10] isFouldArray[15];
public:
LineSensor ( "init privates" ) { ... };
read (*Scorer, Lane ) { ... };
isFoul getisFoulVal( ) { ... };
isFoulArrayCopy( ) { ... };
};
class Scorer
{
private:
FrameStructure Frame;
FrameStructure Frames[15]
int FrameArrayNDX;
bool isFoul;
bool isBonus;
Pins[]* ThrowPins;
PinArray PinStates[10];
int PinArrayNDX;
public
Scorer( "init privates" ) { ... };
throw(ThrowPins, *Sensor, ...) { ... };
tally(ThrowPins, ThrowCount, isFoul; FrameBag, ... ) { ... };
};
structure Frame
{
private:
int FrameNum;
int mainDigit;
int upperLeftDigit;
int upperRightDigit;
public:
Frame( "init privates" ) { ... };
Universe
> class Scorer
> {
> private:
> FrameStructure Frame;
> bool isFoul;
> bool isBonus;
> int PinArrayNDX;
int ThrowCount;
Sensor* ptr2Sensor00
Sensor* ptr2Sensor01
> public
> Scorer( "init privates" ) { ... };
> tally(ptr2Sensor00, ThrowCount, isFoul; Frame, ... ) { ... };
> };
>
> structure Frame
> {
> private:
> int FrameNum;
> int mainDigit;
> int upperLeftDigit;
> int upperRightDigit;
> public:
> Frame( "init privates" ) { ... };
> };
Universe
> This overall design is meant to address the "where does scoring info
> come from" question.
>
> I know this is not syntactically correct. I'm mainly getting at
> overall logical design solutions.
structure ThrowData
{
public:
int Pins[10];
bool isFoul;
};
> class SensorQuery
{
public:
SensorQuery( ) { ... };
ThrowData* getThrowData( *Scorer, Lane ) { ... }; // this querys
pin and Foul line senors
};
class Scorer
{
private:
FrameStructure Frame;
int FrameArrayNDX;
bool isFoul;
bool isBonus;
int* PinArray[]
int PinArrayNDX;
int ThrowCount;
SensorQuery* ptr2SensorQuery;
public
Scorer( "init privates" ) { ... };
throw(ptr2Sensor00, ptr2Sensor01, ...) { ... };
tally(ptr2SensorQuery, ThrowCount, isFoul; Frame, ... ) { ... };
};
structure Frame
{
private:
int FrameNum;
int mainDigit;
int upperLeftDigit;
int upperRightDigit;
public:
Frame( "init privates" ) { ... };
};
Elliott
Isaac Gouy
"What makes this game interesting to score is the lookahead in the
scoring for strike and spare. At the time we throw a strike or spare,
we cannot calculate the frame score: we have to wait one or two frames
to find out what the bonus is."
http://www.xprogramming.com/xpmag/acsBowling.htm
To say it differently, we have to *queue* the individual roll scores
until we can calculate the frame score. Which leads to a solution that
will produce the frame scores as they become available:
class ScoreKeeper {
ArrayList<int> q = new ArrayList(3);
int total = 0;
int frames = 0;
void addScore(int pins){
q.add(pins);
if (q.size==3 && frames<10){
total += q[0]+q[1]+q[2];
frames++;
if (q[0]<10) q.remove(q[1]);
q.remove(q[0]);
totalScore(total);
}
if (q.size==2 && frames<10){
let frameScore = q[0]+q[1];
if (frameScore<10){
total += frameScore;
frames++;
q.clear;
totalScore(total);
}
}
}
}
void totalScore(int score){
print(score); print(" ");
}
void main(String[] args){
let int[][] tests = [
[10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10],
[10, 4,6, 10, 4,6, 10, 4,6, 10, 4,6, 10, 4,6, 10]
];
for(pinScores:tests) {
let sk = new ScoreKeeper();
for(each:pinScores) sk.addScore(each);
print("\n");
}
}
Which gives these results
30 60 90 120 150 180 210 240 270 300
20 40 60 80 100 120 140 160 180 200
Of course, we could configure the ScoreKeeper to not announce the
intermediate frame scores, and instead ask directly for the total
score once a line had been completed.
best wishes, Isaac
Universe
> class Scorer
> {
> private:
> FrameStructure Frame;
> int FrameArrayNDX;
> bool isFoul;
> bool isBonus;
> int* PinArray[]
> int PinArrayNDX;
> int ThrowCount;
> SensorQuery* ptr2SensorQuery;
> public
> Scorer( "init privates" ) { ... };
throw(ptr2SensorQuery* ...) { ... };
> tally(ptr2SensorQuery*, ThrowCount, isFoul; Frame, ... ) {
... };
> };
> structure ThrowData
> {
> public:
> int Pins[10];
> bool isFoul;
> };
>
> > class SensorQuery
> {
> public:
> SensorQuery( ) { ... };
> ThrowData* getThrowData( *Scorer, Lane ) { ... }; // this
querys
> pin and Foul line senors
> };
>
Ron Jeffries
>Scorer::throw() // tweaked
Does it work yet? Does it /compile/ yet?
Universe
"Ron Jeffries" <ronje...@REMOVEacm.org> wrote in message
> On Fri, 5 Dec 2003 21:40:12 -0500, "Universe" <univ...@covad.net>
wrote:
>
> >Scorer::throw() // tweaked
>
> Does it work yet? Does it /compile/ yet?
Why would you doubt that it does?
That's characteristic of XP'ers. Seems to me it's obvious to most the
design is workable. And the best part is that it's deeply rooted in the
domain semantics.
Elliott
Ron Jeffries
> class ScoreKeeper {
> ArrayList<int> q = new ArrayList(3);
> int total = 0;
> int frames = 0;
>
> void addScore(int pins){
> q.add(pins);
> if (q.size==3 && frames<10){
> total += q[0]+q[1]+q[2];
> frames++;
> if (q[0]<10) q.remove(q[1]);
> q.remove(q[0]);
> totalScore(total);
> }
> if (q.size==2 && frames<10){
> let frameScore = q[0]+q[1];
> if (frameScore<10){
> total += frameScore;
> frames++;
> q.clear;
> totalScore(total);
> }
> }
> }
> }
I found that code very hard to understand, though it might just be that I'm dull
or that it is after midnight.
I think it would help if the q.size==2 code was first, rather than the size 3
code, since q size == 2 occurs first in time. Then we can read:
> if (q.size==2 && frames<10){
> let frameScore = q[0]+q[1];
> if (frameScore<10){
> total += frameScore;
> frames++;
> q.clear;
> totalScore(total);
> }
> }
As saying (but not expressing very well IMO), if we have two balls and the frame
score is less than ten (which means it's not a strike and not a spare), then the
total is just the sum of the two balls in the queue, and it's a new frame.
Forget the balls.
The only time this code doesn't clear the queue is if frameScore >= 10. (This is
very odd, since it is calling a strike followed by a 5 a "frame score" of 15,
which is not the score for the frame at all. Nonetheless ...
> if (q.size==3 && frames<10){
> total += q[0]+q[1]+q[2];
> frames++;
> if (q[0]<10) q.remove(q[1]);
> q.remove(q[0]);
> totalScore(total);
> }
Occurs only if it's a strike or spare. The code sums the three balls, which is
either the strike plus its two bonuses, or the spare plus its one bonus.
I occasionally refactor the procedural version into a state like this
one, noting that in the case of a "mark" (strike or spare), the frame score is
the same, namely the sum of three balls starting with the first ball of the
frame. Classes watching this demonstration seem uniformly to agree that this
removal of duplication is not expressive, even though it's correct. Basically
the same trick is being used here. Anyway ...
... we sum the three balls, tick the frame, then we do a curious little
ball-removal thing. We remove the first ball unconditionally (but we have chosen
to do it last). If the first ball is not 10, then we are on a spare, and both
the first and second ball (0 and 1) are used up. So we remove 1 if it's a spare,
and 0 it if's a spike.
I do think this code could be far more clear but it does work. Definitely an
interesting algorithm.
Regards,
Ron Jeffries
>"Ron Jeffries" <ronje...@REMOVEacm.org> wrote in message
>news:tsm2tv4htdolasqmp...@4ax.com...
>> On Fri, 5 Dec 2003 21:40:12 -0500, "Universe" <univ...@covad.net>
>wrote:
>>
>> >Scorer::throw() // tweaked
>>
>> Does it work yet? Does it /compile/ yet?
>
>Why would you doubt that it does?
>
>That's characteristic of XP'ers. Seems to me it's obvious to most the
>design is workable.
Nearly any design is workable, and surely this one is. However, unless the point
of programming is merely to theorize, the program has to compile and run.
If you ever go through the mere formality of making the program actually exist
in statements that computers can compile and execute, it will be interesting to
hear how long it takes, and to observe how many changes need to be made.
>And the best part is that it's deeply rooted in the
>domain semantics.
So are all the examples I've ever seen on this problem. In some cases the
rooting is very obvious, and in some it is not.
Let me ask just one question, since what you've done is "deeply rooted in the
domain semantics": I see above a method "throw" on a class named "Scorer".
Does that suggest that in the domain, the scorer throws the ball, or that the
person who throws the ball does his own scoring? In the game of bowling that I
know, neither is typically the case.
Isaac Gouy
-snip-
> I found that code very hard to understand, though it might just be that I'm
> dull or that it is after midnight.
Not too suprising since you don't seem to have seen this approach
before, and it comes without any explanation.
> I think it would help if the q.size==2 code was first, rather than the size 3
> code, since q size == 2 occurs first in time.
For addScore(10) addScore(5) addScore(3) that would give the
totalScore 18; where it should give the totalScores 18 & 26.
q.size == 3 needs to come first to produce correct results.
> > if (q.size==2 && frames<10){
> > let frameScore = q[0]+q[1];
> > if (frameScore<10){
> > total += frameScore;
> > frames++;
> > q.clear;
> > totalScore(total);
> > }
> > }
>
> As saying (but not expressing very well IMO)
-snip-
> The only time this code doesn't clear the queue is if frameScore >= 10.
> (This is very odd, since it is calling a strike followed by a 5 a "frame
> score" of 15, which is not the score for the frame at all.
Suggestions for improved forms of expression would be more interesting
IMO ;-)
For instance, we could name the temporary variable qTotal or we could
just get rid of it:
if (q.size==2 && frames<10){
if (q[0]+q[1]<10){
total += q[0]+q[1];
frames++;
q.clear;
totalScore(total);
}
> I occasionally refactor the procedural version into a state like this
> one, noting that in the case of a "mark" (strike or spare), the frame score
> is the same, namely the sum of three balls starting with the first ball of
> the frame. Classes watching this demonstration seem uniformly to agree that
> this removal of duplication is not expressive, even though it's correct.
> Basically the same trick is being used here.
No "trick" is being used here.
We're waiting until we can calculate a total - if there are 3 rolls in
the queue we always can, and if there are 2 rolls in the queue we
maybe can. These are conditions basic to the algorithm - there's no
"duplication" to remove.
> We remove the first ball unconditionally (but we have chosen
> to do it last).
If we did it first then we would have changed the value of q[0] before
we tested it in the condition...
> I do think this code could be far more clear but it does work. Definitely an
> interesting algorithm.
I'll post a C# version later, maybe you could refactor that to be more
clear?
best wishes, Isaac
Isaac Gouy
---------
using System;
using System.Collections;
namespace TenPin
{
class ScoreKeeper
{
ArrayList q = new ArrayList(3);
int total = 0;
int frames = 1;
BowlingGame game;
public void AddScore(int pins)
{
q.Add(pins);
if (q.Count==3 && frames<=10)
{
total += (int)q[0]+(int)q[1]+(int)q[2];
frames++;
if ((int)q[0]<10) q.RemoveAt(1);
q.RemoveAt(0);
game.totalScore(total);
}
if (q.Count==2 && frames<=10)
{
if ((int)q[0]+(int)q[1] < 10)
{
total += (int)q[0]+(int)q[1];
frames++;
q.Clear();
game.totalScore(total);
}
}
}
public ScoreKeeper(BowlingGame aGame)
{
game = aGame;
}
}
class BowlingGame
{
public void totalScore(int score)
{
Console.Write(score+" ");
}
static void Main(string[] args)
{
BowlingGame g = new BowlingGame();
foreach(int[] pinScores in tests) {
ScoreKeeper sk = new ScoreKeeper(g);
foreach(int each in pinScores) sk.AddScore(each);
Console.WriteLine();
}
}
static int[][] tests = {
new int[]{0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0},
new int[]{3,3, 3,3, 3,3, 3,3, 3,3, 3,3, 3,3, 3,3, 3,3, 3,3},
new int[]{4,6, 3,5, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0},
new int[]{4,6, 5,3, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0},
new int[]{10, 5,3, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0},
new int[]{0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 10, 5,3},
new int[]{0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 4,6, 5},
new int[]{10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10},
new int[]{10, 4,6, 10, 4,6, 10, 4,6, 10, 4,6, 10, 4,6, 10},
new int[]{},
new int[]{3},
new int[]{3,3},
new int[]{3,3, 3},
new int[]{4,6},
new int[]{4,6, 3},
new int[]{4,6, 3,5},
new int[]{10},
new int[]{10, 5},
new int[]{10, 5,3},
new int[]{10, 5,3, 0},
new int[]{10, 4,6},
new int[]{10, 4,6, 10},
new int[]{10, 4,6, 10, 4},
new int[]{10, 4,6, 10, 4,6},
new int[]{10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10}
};
}
}