By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
448,672 Members | 1,628 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 448,672 IT Pros & Developers. It's quick & easy.

Challenge: Triangles puzzle

P: n/a
I've setup a challenge, mainly for C++, Java and Lisp, but every other
language is welcome:

http://www.frank-buss.de/challenge/index.html

There is nothing to win, but I hope there will be some interesting
solutions at the end, so the win are the results :-)

--
Frank Buß, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Jul 22 '05 #1
Share this Question
Share on Google+
42 Replies


P: n/a
Sorry, but i do not agree with your solution.
You missed many triangles.

E.g., P0 -> P8 -> P5 -> P0 is a triangle of zero area.
but it is not counted in th solution of 27.

-jim

Frank Buss wrote:
I've setup a challenge, mainly for C++, Java and Lisp, but every other
language is welcome:

http://www.frank-buss.de/challenge/index.html

There is nothing to win, but I hope there will be some interesting
solutions at the end, so the win are the results :-)


Jul 22 '05 #2

P: n/a
Jim Newton <ji***@rdrop.com> wrote:
Sorry, but i do not agree with your solution.
You missed many triangles.

E.g., P0 -> P8 -> P5 -> P0 is a triangle of zero area.
but it is not counted in th solution of 27.


you are right, this was not exact enough, I've updated the web page. Only
triangles with area>0 should be counted.

--
Frank Buß, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Jul 22 '05 #3

P: n/a
> Sorry, but i do not agree with your solution.
You missed many triangles.

E.g., P0 -> P8 -> P5 -> P0 is a triangle of zero area.
but it is not counted in th solution of 27.


hmm...

What are you talking about?

A triangle with an area equal to zero doesn't exist. A triangle has three
angles and none of them may be equal to zero, otherwise you just don't have
a triangle.

What you describe with P0 -> P8 -> P5 -> P0 is a segment of a line not a
triangle...

Jul 22 '05 #4

P: n/a
Frank Buss <fb@frank-buss.de> writes:
I've setup a challenge, mainly for C++, Java and Lisp, but every other
language is welcome:

http://www.frank-buss.de/challenge/index.html

There is nothing to win, but I hope there will be some interesting
solutions at the end, so the win are the results :-)


Thanks Frank. Fun way to waste half an hour. :-)
Jul 22 '05 #5

P: n/a
On Sat, 16 Oct 2004 23:29:52 +0200, "Yogo" <n o s p a m> wrote:
Sorry, but i do not agree with your solution.
You missed many triangles.

E.g., P0 -> P8 -> P5 -> P0 is a triangle of zero area.
but it is not counted in th solution of 27.
hmm...

What are you talking about?

A triangle with an area equal to zero doesn't exist.


Not as far as a computer is concerned. Without any form of sanity
checking, the most intuitive (read: quickest for the programmer to
implement) definition of a triangle for a computer is a set of three
points.

The puzzle in question only considers triangles to be formed from a given
set of points, as well requiring a known line connecting between those
points. Although the puzzle didn't define triangle, the webpage now
includes an update that requires these traingle to have an area.
A triangle has three
angles and none of them may be equal to zero, otherwise you just don't have
a triangle.

What you describe with P0 -> P8 -> P5 -> P0 is a segment of a line not a
triangle...


Using the "three angles" definition, the line given is valid. There are
three angles in the shape:

P5 -> P0 -> P8 : 0 degree angle
P0 -> P5 -> P8 : 180 degree angle
P0 -> P8 -> P5 : 0 degree angle.

0 degrees is still an angle, as is 180. These angles are generally
significant as they indicate parallel lines, but can be valid in figures.
Jul 22 '05 #6

P: n/a
Frank Buss <fb@frank-buss.de> wrote in message news:<ck**********@newsreader2.netcologne.de>...
I've setup a challenge, mainly for C++, Java and Lisp, but every other
language is welcome:

http://www.frank-buss.de/challenge/index.html

There is nothing to win, but I hope there will be some interesting
solutions at the end, so the win are the results :-)


Would it be possible for you to have a private mailing list where you
can show us peoples' submissions? I'm too impatient to wait until the
25th. The recipients can be people who already sent you solutions.

It is interesting to see how one programs differently when shipping
time is a factor. After I sent it to you and took a quick look at the
code, I realized I left in parameters named "blah". ;) Which is what I
frequently name things, but I always rename them.
MfG,
Tayssir
Jul 22 '05 #7

P: n/a
Tayssir John Gabbour wrote:
It is interesting to see how one programs differently when shipping
time is a factor. After I sent it to you and took a quick look at the
code, I realized I left in parameters named "blah". ;) Which is what I
frequently name things, but I always rename them.


How very true. I'm also curious to see if anyone comes up with a
"general case" solution to the problem. I'm in the console gaming
industry, where most of the time hard-coding a solution to a specific
problem is preferable -- which is why I did in this case.

Jeff M.
Jul 22 '05 #8

P: n/a

"Raymond Martineau" <bk***@freenet.carleton.ca> wrote in message
news:lo********************************@4ax.com...
On Sat, 16 Oct 2004 23:29:52 +0200, "Yogo" <n o s p a m> wrote:
Sorry, but i do not agree with your solution.
You missed many triangles.

E.g., P0 -> P8 -> P5 -> P0 is a triangle of zero area.
but it is not counted in th solution of 27.
hmm...

What are you talking about?

A triangle with an area equal to zero doesn't exist.


Not as far as a computer is concerned. Without any form of sanity
checking, the most intuitive (read: quickest for the programmer to
implement) definition of a triangle for a computer is a set of three
points.


Which would include um, a three-sided black hole? :-)

The puzzle in question only considers triangles to be formed from a given
set of points, as well requiring a known line connecting between those
points.
If a line intersects three points, those three points do
not represent vertices of the same triangle.
Although the puzzle didn't define triangle, the webpage now
includes an update that requires these traingle to have an area.
A triangle has three
angles and none of them may be equal to zero, otherwise you just don't havea triangle.

What you describe with P0 -> P8 -> P5 -> P0 is a segment of a line not a
triangle...


Using the "three angles" definition, the line given is valid. There are
three angles in the shape:

P5 -> P0 -> P8 : 0 degree angle
P0 -> P5 -> P8 : 180 degree angle
P0 -> P8 -> P5 : 0 degree angle.

0 degrees is still an angle, as is 180. These angles are generally
significant as they indicate parallel lines,


Parellel lines cannot be boundaries of the same triangle.

-Mike
Jul 22 '05 #9

P: n/a

hmm...

What are you talking about?

A triangle with an area equal to zero doesn't exist. A triangle has three
angles and none of them may be equal to zero, otherwise you just don't have
a triangle.

What you describe with P0 -> P8 -> P5 -> P0 is a segment of a line not a
triangle...


no, you are wrong. an angle may have zero degrees, or less than zero
degrees or more than zero degrees.

the sum of the angles in a triangle is 180 degrees. and a 0, 0, 180
triangle is still a triangle.

Jul 22 '05 #10

P: n/a
On Sun, 17 Oct 2004 11:02:55 +0200, Jim Newton wrote:
A triangle with an area equal to zero doesn't exist. A triangle has three
angles and none of them may be equal to zero, otherwise you just don't have
a triangle.

What you describe with P0 -> P8 -> P5 -> P0 is a segment of a line not a
triangle...


no, you are wrong. an angle may have zero degrees, or less than zero
degrees or more than zero degrees.

the sum of the angles in a triangle is 180 degrees. and a 0, 0, 180
triangle is still a triangle.


There are a number of properties that a construct must
posess to be considered a triangle. Amongst them are..

a) Internal angles add to 180 degrees.
b) The length of any two sides exceeds the length of the third.
c) Is a 'three sided polygon'

The case in question fits part a), but neither of parts b)
(true in two cases, but not the third), or c) ('two sides'
joined end to end are a single line, thus form a *single*
side, which, when superimposed over the third side becomes
a *line*, people...)

The 'solution' to this is to define the conditions under
which the shapes are acceptable, and to put at the end,
'we will refer to these as triangles, irrespective of the
exact mathematical definition of a triangle'

--
Andrew Thompson
http://www.PhySci.org/codes/ Web & IT Help
http://www.PhySci.org/ Open-source software suite
http://www.1point1C.org/ Science & Technology
http://www.LensEscapes.com/ Images that escape the mundane
Jul 22 '05 #11

P: n/a
Jim Newton <ji***@rdrop.com> writes:
hmm...
What are you talking about?
A triangle with an area equal to zero doesn't exist. A triangle has
three angles and none of them may be equal to zero, otherwise you
just don't have a triangle.
What you describe with P0 -> P8 -> P5 -> P0 is a segment of a line
not a triangle...


no, you are wrong. an angle may have zero degrees, or less than zero
degrees or more than zero degrees.

the sum of the angles in a triangle is 180 degrees. and a 0, 0, 180
triangle is still a triangle.


You're wrong. The triangle inequality states that the sum of two
triangles sides exceeds the other side. Zero is not a side in any
triangle.
Jul 22 '05 #12

P: n/a
ta*********@yahoo.com (Tayssir John Gabbour) wrote:
http://www.frank-buss.de/challenge/index.html


Would it be possible for you to have a private mailing list where you
can show us peoples' submissions? I'm too impatient to wait until the
25th. The recipients can be people who already sent you solutions.


I've created a private submitters area and I'll send the access information
to every submitter of a working solution.

--
Frank Buß, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Jul 22 '05 #13

P: n/a
no, the triangle inequality says | a + b | >= a + b
equality is allowed in the triangle inequalilty.

-jim
You're wrong. The triangle inequality states that the sum of two
triangles sides exceeds the other side. Zero is not a side in any
triangle.


Jul 22 '05 #14

P: n/a
There are a number of properties that a construct must
posess to be considered a triangle. Amongst them are..

a) Internal angles add to 180 degrees.
b) The length of any two sides exceeds the length of the third.
c) Is a 'three sided polygon'


I do not believe most geometries insist on (b) being the case.
Nothing important is gained by this condition.

a 0/0/180 triangle is a THREE SIDED POLYGON

This sounds like the argument made by the romans when
mathematicians insisited there was a need for a zero
in the number system.

0 is a valid integer
0 miles per hours is a valid speed
0 square meters is a valid area
0 degrees is a valid angle
Jul 22 '05 #15

P: n/a
On Sun, 17 Oct 2004 12:37:33 +0200, Jim Newton wrote:

(A.T.)
b) The length of any two sides exceeds the length of the third.
.... I do not believe most geometries insist on (b) being the case.


Less than 7 minutes ago you were claiming to Mikael ..

"no, the triangle inequality says | a + b | >= a + b
equality is allowed in the triangle inequalilty."

So ..what are your 'beliefs' going to be in another 10 minutes?

--
Andrew Thompson
http://www.PhySci.org/codes/ Web & IT Help
http://www.PhySci.org/ Open-source software suite
http://www.1point1C.org/ Science & Technology
http://www.LensEscapes.com/ Images that escape the mundane
Jul 22 '05 #16

P: n/a
you're right.. my >= was backward.
sorry.

the triangle inequality is

| a + b | <= | a | + | b |

E.g.,

| -1 + 2 | = 1 <= | -1 | + | 2 | = 1 + 2 = 3
1 <= 3

| 1 + 2 | = 3 <= | 1 | + | 2 | = 1 + 2 = 3
3 <= 3

sorry about that (blush).
Andrew Thompson wrote:
On Sun, 17 Oct 2004 12:37:33 +0200, Jim Newton wrote:

(A.T.)
b) The length of any two sides exceeds the length of the third.


...
I do not believe most geometries insist on (b) being the case.

Less than 7 minutes ago you were claiming to Mikael ..

"no, the triangle inequality says | a + b | >= a + b
equality is allowed in the triangle inequalilty."

So ..what are your 'beliefs' going to be in another 10 minutes?


Jul 22 '05 #17

P: n/a
>
a 0/0/180 triangle is a THREE SIDED POLYGON


A polygon is a closed figure (each line segment must intersects exactly two
other line segments). You don't get a closed figure with that.

Besides that, not only the sum of the three angles of a triangle must be
equal to 180, the sum of two angles must also be less than two right angles.

A line segment is just a line segment.

Jul 22 '05 #18

P: n/a
why do you think a 0/0/180 triangle is not closed?

-jim

Yogo wrote:
a 0/0/180 triangle is a THREE SIDED POLYGON

A polygon is a closed figure (each line segment must intersects exactly two
other line segments). You don't get a closed figure with that.

Besides that, not only the sum of the three angles of a triangle must be
equal to 180, the sum of two angles must also be less than two right angles.

A line segment is just a line segment.


Jul 22 '05 #19

P: n/a
in a 0/0/180 triangle each side intersects its two neighboring
sides.

why do you think that the sum of two angles must also be less
than two right angles?

I think you are trying to put a lot of additional requirements
on the definition of a triangle. You are making it harder than
it is.


Yogo wrote:
a 0/0/180 triangle is a THREE SIDED POLYGON

A polygon is a closed figure (each line segment must intersects exactly two
other line segments). You don't get a closed figure with that.

Besides that, not only the sum of the three angles of a triangle must be
equal to 180, the sum of two angles must also be less than two right angles.

A line segment is just a line segment.


Jul 22 '05 #20

P: n/a
Raymond Martineau said...
0 degrees is still an angle, as is 180. These angles are generally
significant as they indicate parallel lines, but can be valid in figures.


The problem is, that parallel lines cannot form a triangle.

Greets,
-Wanja-

--
"Gewisse Schriftsteller sagen von ihren Werken immer: 'Mein Buch, mein
Kommentar, meine Geschichte'. [..] Es wäre besser, wenn sie sagten:
'unser Buch, unser Kommentar, unsere Geschichte'; wenn man bedenkt, dass
das Gute darin mehr von anderen ist als von ihnen." [Blaise Pascal]
Jul 22 '05 #21

P: n/a
Jim Newton said...
in a 0/0/180 triangle each side intersects its two neighboring
sides.


Nope, it intersects in an unlimited number of points, which harms the
definition of a triangle, because there are more than 3 intersections.

If you bring the area of a triangle down to zero, it stops being a
triangle: you get either a point or a line.

Say you would shorten each side of a triamgle to a length of 0, you
would get a single point, which is less than 3, which allows no angle,
no intersections and thus is no triangle at all. Same problem,
basically.

Greets,
-Wanja-

--
"Gewisse Schriftsteller sagen von ihren Werken immer: 'Mein Buch, mein
Kommentar, meine Geschichte'. [..] Es wäre besser, wenn sie sagten:
'unser Buch, unser Kommentar, unsere Geschichte'; wenn man bedenkt, dass
das Gute darin mehr von anderen ist als von ihnen." [Blaise Pascal]
Jul 22 '05 #22

P: n/a
On Sun, 17 Oct 2004 15:17:21 +0200, Wanja Gayk <br********@yahoo.com>
wrote:
Raymond Martineau said...
0 degrees is still an angle, as is 180. These angles are generally
significant as they indicate parallel lines, but can be valid in figures.


The problem is, that parallel lines cannot form a triangle.


They can if they overlap - which is the exact problem one of the posters
was pointing out.

There's also the case with non-euclidian geometry, where a 2D drawing
surface forms a sphere (and nothing is allowed to pass through.) With
something like this, you can draw three individual lines to surround the
equator, and attempt to call it a triangle.

That's why you need definitions on what constitutes as a triangle and what
doesn't. If you don't define things clearly, then you will end up with
confusion and arguments on what really counts as a triangle and what
doesn't.
Jul 22 '05 #23

P: n/a
Hello.

The problem is that the C++ Ansi/Iso standard has not definition of
"trinagle". Then the definition is implementation dependant or undefined
behaviour and seems that you are using different implementatios ;)

--
Salu2
Jul 22 '05 #24

P: n/a
Jim Newton:
the sum of the angles in a triangle is 180 degrees. and a 0, 0, 180
triangle is still a triangle.


I don't know why you are discussing about it. You're talking about a line. A
triangle is an area. If you decide that a triangle may be a line, then a
rectancle can also be a line. A box can be a rectangle and this can be a
line. And a line could be a point.

So a point is a triangle, rectangle, pyramid, and every other geometrical
structure? I think it's wrong if you decide that an area may be a line.

Volume, area, line and point are different worlds. And you can't decide that
a line has an exact area of 0, otherwise the sum of lines would be 0, but
it is an area > 0.
--
<http://www.domaininformation.de/> - Whoisabfrage
Jul 22 '05 #25

P: n/a
On 10/16/2004 at 9:47:02 PM, Raymond Martineau wrote:
On Sat, 16 Oct 2004 23:29:52 +0200, "Yogo" <n o s p a m> wrote:
A triangle with an area equal to zero doesn't exist.


Not as far as a computer is concerned.


That depends on the programming, doesn't it?

Check the dictionary:

tri·an·gle n.

1. a. The plane figure formed by connecting three points
not in a straight line by straight line segments;
a three-sided polygon.

http://dictionary.reference.com/search?q=triangle

--
Regards,

John McGrath
Jul 22 '05 #26

P: n/a
Frank Buss <fb@frank-buss.de> wrote in message news:<ck**********@newsreader2.netcologne.de>...
ta*********@yahoo.com (Tayssir John Gabbour) wrote:
http://www.frank-buss.de/challenge/index.html


Would it be possible for you to have a private mailing list where you
can show us peoples' submissions? I'm too impatient to wait until the
25th. The recipients can be people who already sent you solutions.


I've created a private submitters area and I'll send the access information
to every submitter of a working solution.


Thanks. It was interesting to see the differences in thought process.

Since I didn't do a good job of commenting (I just kicked it out),
I've sent you a commentary version that you might put next to my real
submission. It critiques my rough code a little, and gave some of my
background so readers know where I'm at.
MfG,
Tayssir
Jul 22 '05 #27

P: n/a
Mikael Brockman wrote:
Jim Newton <ji***@rdrop.com> writes:
> hmm...
> What are you talking about?
> A triangle with an area equal to zero doesn't exist. A triangle has
> three angles and none of them may be equal to zero, otherwise you
> just don't have a triangle.
> What you describe with P0 -> P8 -> P5 -> P0 is a segment of a line
> not a triangle...
>
no, you are wrong. an angle may have zero degrees, or less than zero
degrees or more than zero degrees.

the sum of the angles in a triangle is 180 degrees. and a 0, 0, 180
triangle is still a triangle.


You're wrong. The triangle inequality states that the sum of two
triangles sides exceeds the other side.


Actually, it is "equals or exceeds". A three-sided polygon with sides 3, 4
and 7 is a degenerate triangle, but it is a triangle.

http://www.fact-index.com/t/tr/triangle_inequality.html

"In mathematics, the triangle inequality is a statement which states roughly
that the distance from A to B to C is never shorter than going directly
from A to C. "

Note that it says "never shorter than ...". Not "always longer than ...".
Zero is not a side in any
triangle.


True, but not the present issue. The problem appears to be the case of
angles of 0,0,180 and nonzero sides a + b = c.

--
Paul Lutus
http://www.arachnoid.com

Jul 22 '05 #28

P: n/a
Frank Buss <fb@frank-buss.de> wrote in message news:<ck**********@newsreader2.netcologne.de>...
ta*********@yahoo.com (Tayssir John Gabbour) wrote:
http://www.frank-buss.de/challenge/index.html


Would it be possible for you to have a private mailing list where you
can show us peoples' submissions? I'm too impatient to wait until the
25th. The recipients can be people who already sent you solutions.


I've created a private submitters area and I'll send the access information
to every submitter of a working solution.


I'm still working on my solution. I have been pondering it for a few
hours on and off, and now I think I've figured it out so I can
actaully write the code. I really had to brush up on geometry. :-)

--
Certum quod factum
Philip Haddad
Jul 22 '05 #29

P: n/a
Frank Buss <fb@frank-buss.de> wrote:
I've setup a challenge, mainly for C++, Java and Lisp, but every other
language is welcome:

http://www.frank-buss.de/challenge/index.html


the challenge is over, thanks to all participants. I've submitted the link
at Slashdot, too, there are always so objective discussions :-)

--
Frank Buß, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Jul 22 '05 #30

P: n/a
Dear Frank,

Frank Buss <fb@frank-buss.de> writes:
http://www.frank-buss.de/challenge/index.html
the challenge is over, thanks to all participants. I've submitted the link
at Slashdot, too, there are always so objective discussions :-)


Did you reach any interesting (or uninteresting) conclusions from the
solutions?

Best,
Chris
Jul 22 '05 #31

P: n/a
ch****@gamow.sci.kun.nl (Chris Dams) wrote:
Did you reach any interesting (or uninteresting) conclusions from the
solutions?


yes, but it is not a new conclusion: The language doesn't matter, if you
have a good idea.

But I don't know, why there are so many Lisp solutions, but this is good,
because I'm still learning Lisp, and now I have many good examples, which I
can compare to see the advantage and disadvantages for this problem.

--
Frank Buß, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Jul 22 '05 #32

P: n/a
Frank Buss wrote:
ch****@gamow.sci.kun.nl (Chris Dams) wrote:
Did you reach any interesting (or uninteresting) conclusions from
the solutions?


yes, but it is not a new conclusion: The language doesn't matter,
if you have a good idea.


The useful thing was though, that I didn't have any conscious idea of
what I was doing. Usually with my previous languages, I always made my
thoughts explicit (for example, on things like paper). Being in
control. After being inspired by the video, I am now experimenting with
trying other extreme, which is like falling backwards in the
expectation that I can actually levitate. Maybe I'm just weakly and
slowly groping around, but I liked the moment when I thought, "Hmm, so
that's what I'm doing."

For example, if there were something tricky about it, I might have
signalled a warning and left restarts for later. Meat & potatoes stuff
which has nothing to do with what Lisp is hyped for (and didn't appear
in the code), but quietly takes away intellectual issues so you can do
as you wish.

I certainly don't want my code to be any representative example of
Lisp, in the eyes of the public, but I thought it was fun and
edumacational. I kind of hope no one tries drawing any lessons from
what I did. ;)

On the other hand, I liked that Literate Haskell answer. Sort of the
opposite approach.
MfG,
Tayssir

Jul 22 '05 #33

P: n/a
Frank Buss <fb@frank-buss.de> writes:
I've setup a challenge, mainly for C++, Java and Lisp, but every other
language is welcome:

http://www.frank-buss.de/challenge/index.html


the challenge is over, thanks to all participants. I've submitted the link
at Slashdot, too, there are always so objective discussions :-)


I've put a little plot of the results at
http://homepage.ntlworld.com/g.mccau...e/tri-times.ps
http://homepage.ntlworld.com/g.mccau.../tri-times.pdf

which should be reasonably self-explanatory. The letters above and
to the right of the main plot show the marginal distributions.
The ones below the main plot are those with no time specified in
Frank's table.

All the numbers depicted should be taken with a grain of salt;
in particular, I haven't made a very serious attempt to correct
for the fact that some people will have reported non-blank non-comment
line counts and others will have included everything. (Where the
distinction was made, I chose the non-blank non-comment figure,
or the nearest thing thereto.) Likewise, those who gave times
may have meant different things by them.

There may be interesting conclusions to draw, but I am not going
to draw them. :-)

--
Gareth McCaughan
..sig under construc
Jul 22 '05 #34

P: n/a
Gareth McCaughan wrote:
Frank Buss <fb@frank-buss.de> writes:

I've setup a challenge, mainly for C++, Java and Lisp, but every other
language is welcome:

http://www.frank-buss.de/challenge/index.html


the challenge is over, thanks to all participants. I've submitted the link
at Slashdot, too, there are always so objective discussions :-)

I've put a little plot of the results at
http://homepage.ntlworld.com/g.mccau...e/tri-times.ps
http://homepage.ntlworld.com/g.mccau.../tri-times.pdf

which should be reasonably self-explanatory. The letters above and
to the right of the main plot show the marginal distributions.
The ones below the main plot are those with no time specified in
Frank's table.

All the numbers depicted should be taken with a grain of salt;
in particular, I haven't made a very serious attempt to correct
for the fact that some people will have reported non-blank non-comment
line counts and others will have included everything. (Where the
distinction was made, I chose the non-blank non-comment figure,
or the nearest thing thereto.) Likewise, those who gave times
may have meant different things by them.

There may be interesting conclusions to draw, but I am not going
to draw them. :-)


What do the Python, Java, Lisp, and Ruby entries with times less than 0
mean? Has time travel already been invented?

-- MJF
Jul 22 '05 #35

P: n/a
Gareth McCaughan <ga**************@pobox.com> wrote:
Frank Buss <fb@frank-buss.de> writes:
the challenge is over, thanks to all participants. I've submitted the link
at Slashdot, too, there are always so objective discussions :-)

I've put a little plot of the results at
http://homepage.ntlworld.com/g.mccau...e/tri-times.ps
http://homepage.ntlworld.com/g.mccau.../tri-times.pdf

which should be reasonably self-explanatory. The letters above and
to the right of the main plot show the marginal distributions.
The ones below the main plot are those with no time specified in
Frank's table.

All the numbers depicted should be taken with a grain of salt;
in particular, I haven't made a very serious attempt to correct
for the fact that some people will have reported non-blank non-comment
line counts and others will have included everything. (Where the
distinction was made, I chose the non-blank non-comment figure,
or the nearest thing thereto.) Likewise, those who gave times
may have meant different things by them. There may be interesting conclusions to draw, but I am not going
to draw them. :-)


One thing that was interesting for me in the graph: If you just look
at the Lisp entries alone (which are numerous enough), you can see on
the one hand a linear relationship between lines of code/time needed
(a diagonal line), and on the other hand and vertical line (a nearly
constant relationship) on the left hand side. Both effects are not so
surprising: It takes longer to write more lines of code on the other
hand, and to get a short and simple solution, you have to invest some
time thinking about it, but no matter how it long takes you, the
"simplest" solution will have roughly the same number of lines.

I didn't expect those effects to be so visible so prominently, however.

(And I agree with Frank: In the end, what counts is the idea behind
the algorithm, no matter what language you use to describe it in.)

- Dirk

Jul 22 '05 #36

P: n/a
Gareth McCaughan <ga**************@pobox.com> wrote in message news:<87************@g.mccaughan.ntlworld.com>...
I've put a little plot of the results at
http://homepage.ntlworld.com/g.mccau...e/tri-times.ps
http://homepage.ntlworld.com/g.mccau.../tri-times.pdf
[snip]
All the numbers depicted should be taken with a grain of salt;
in particular, I haven't made a very serious attempt to correct
for the fact that some people will have reported non-blank non-comment
line counts and others will have included everything. (Where the
distinction was made, I chose the non-blank non-comment figure,
or the nearest thing thereto.) Likewise, those who gave times
may have meant different things by them.


Also, people chose different definitions of the problem--of what it
means to input points and lines.
Jul 22 '05 #37

P: n/a
M Jared Finder wrote:

[I said:]
I've put a little plot of the results at
http://homepage.ntlworld.com/g.mccau...e/tri-times.ps
http://homepage.ntlworld.com/g.mccau.../tri-times.pdf
which should be reasonably self-explanatory. The letters above and
to the right of the main plot show the marginal distributions.
The ones below the main plot are those with no time specified in
Frank's table.
All the numbers depicted should be taken with a grain of salt;
in particular, I haven't made a very serious attempt to correct
for the fact that some people will have reported non-blank non-comment
line counts and others will have included everything. (Where the
distinction was made, I chose the non-blank non-comment figure,
or the nearest thing thereto.) Likewise, those who gave times
may have meant different things by them.
There may be interesting conclusions to draw, but I am not going
to draw them. :-)


What do the Python, Java, Lisp, and Ruby entries with times less than
0 mean? Has time travel already been invented?


As I said ...
The ones below the main plot are those with no time specified in
Frank's table.


--
Gareth McCaughan
..sig under construc
Jul 22 '05 #38

P: n/a
mm*************@yahoo.com (Mark McConnell) writes:
Gareth McCaughan <ga**************@pobox.com> wrote in message news:<87************@g.mccaughan.ntlworld.com>...
I've put a little plot of the results at
http://homepage.ntlworld.com/g.mccau...e/tri-times.ps
http://homepage.ntlworld.com/g.mccau.../tri-times.pdf
[snip]
All the numbers depicted should be taken with a grain of salt;
in particular, I haven't made a very serious attempt to correct
for the fact that some people will have reported non-blank non-comment
line counts and others will have included everything. (Where the
distinction was made, I chose the non-blank non-comment figure,
or the nearest thing thereto.) Likewise, those who gave times
may have meant different things by them.


Also, people chose different definitions of the problem--of what it
means to input points and lines.


Yes. In particular, the *very* short solutions all (1) used
assignments within the program as input (though they didn't
count those assignments as part of the code), thus requiring
0 lines for handling input, and (2) used numbers to represent
points, which enables various minor algorithmic simplifications.

Whether you think of that as cheating or as intelligent use
of the language's facilities is up to you. :-)

--
Gareth McCaughan
..sig under construc
Jul 22 '05 #39

P: n/a
Gareth McCaughan <ga**************@pobox.com> wrote:
Yes. In particular, the *very* short solutions all (1) used
assignments within the program as input (though they didn't
count those assignments as part of the code),
No, at least one short solution did count those assignments (3 lines
of assignments out of 6 total lines of code).

You could replace those 3 lines by 1 line to read the contents of a file,
1 line to parse it and to call the algorithm, 1 line to calculate the
missing part of the input definition, and 1 line to print the result.
Maybe an additional line to get the filename from the commandline arguments.
So instead of 3, you have 4-5 lines. I didn't bother, because then you have
to edit 2 files instead of 1 for testing.
(2) used numbers to represent points, which enables various minor
algorithmic simplifications.


Nope. Anything that's comparable will do for the simple solution,
and with two additional lines, you can use anything that only admits equality.
If you just want the number of solutions, and not the solutions themselves
without "duplicates" by permutation, then you can do even without that
(just divide the length of the list of solutions by 6).

BTW, one more important difference is that some algorithms just counted,
while some actually computed all solutions. Some algorithms restricted
themselves to two "fans" of lines, while some allowed an arbitrary
geometry. And so on, and so on.

- Dirk
Jul 22 '05 #40

P: n/a
Dirk Thierbach wrote:
Gareth McCaughan <ga**************@pobox.com> wrote:

Yes. In particular, the *very* short solutions all (1) used
assignments within the program as input (though they didn't
count those assignments as part of the code), (2) used numbers to represent points, which enables various minor
algorithmic simplifications.



Nope. Anything that's comparable will do for the simple solution,
and with two additional lines, you can use anything that only admits equality.
If you just want the number of solutions, and not the solutions themselves
without "duplicates" by permutation, then you can do even without that
(just divide the length of the list of solutions by 6).

BTW, one more important difference is that some algorithms just counted,
while some actually computed all solutions. Some algorithms restricted
themselves to two "fans" of lines, while some allowed an arbitrary
geometry. And so on, and so on.


It is also interesting to look at the various time complexities for
the algorithms used. The programs that generate all tree-tuples of points
and then filter for triangles and remove duplicates will be slower than
programs that generate the triangles in way that doesn't generate non-triangles
nor duplicates, when we run the programs for large n and m.

--
Jens Axel Søgaard
Jul 22 '05 #41

P: n/a
Dirk Thierbach wrote:

[I said:]
Yes. In particular, the *very* short solutions all (1) used
assignments within the program as input (though they didn't
count those assignments as part of the code),
No, at least one short solution did count those assignments (3 lines
of assignments out of 6 total lines of code).


I beg your pardon; I misremembered.
You could replace those 3 lines by 1 line to read the contents of a file,
1 line to parse it and to call the algorithm, 1 line to calculate the
missing part of the input definition, and 1 line to print the result.
Maybe an additional line to get the filename from the commandline arguments.
So instead of 3, you have 4-5 lines. I didn't bother, because then you have
to edit 2 files instead of 1 for testing.
Sure.
(2) used numbers to represent points, which enables various minor
algorithmic simplifications.


Nope. Anything that's comparable will do for the simple solution,
and with two additional lines, you can use anything that only admits equality.


I'm not sure how we're in disagreement here...
If you just want the number of solutions, and not the solutions themselves
without "duplicates" by permutation, then you can do even without that
(just divide the length of the list of solutions by 6).
Indeed. (Though you may, in some implementations, need a little
extra code to avoid repeated points.)
BTW, one more important difference is that some algorithms just counted,
while some actually computed all solutions. Some algorithms restricted
themselves to two "fans" of lines, while some allowed an arbitrary
geometry. And so on, and so on.


Indeed. The solution that was a 3-character program in J
(or whatever it was) was particularly notable in this respect :-).

(I get the impression that you think I think it was cheating
to avoid using a separate file for the data. I don't.)

--
Gareth McCaughan
..sig under construc
Jul 22 '05 #42

P: n/a
Gareth McCaughan <ga**************@pobox.com> wrote:
BTW, one more important difference is that some algorithms just counted,
while some actually computed all solutions. Some algorithms restricted
themselves to two "fans" of lines, while some allowed an arbitrary
geometry. And so on, and so on.
Indeed. The solution that was a 3-character program in J
(or whatever it was) was particularly notable in this respect :-).
Yes. J (and APL, and K) can be very terse, but also somewhat hard to
read (at least for me).
(I get the impression that you think I think it was cheating
to avoid using a separate file for the data.


No. I guess the point was that other differences are much more important.

- Dirk
Jul 22 '05 #43

This discussion thread is closed

Replies have been disabled for this discussion.