448,672 Members | 1,628 Online
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
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 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 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" 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 threeangles 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 atriangle... 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 wrote in message news:... 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" wrote in message news:lo********************************@4ax.com... On Sat, 16 Oct 2004 23:29:52 +0200, "Yogo" 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 threeangles 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 atriangle... 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 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 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. -- - 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" 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 wrote in message news:... 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 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 wrote in message news:... 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 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 writes: http://www.frank-buss.de/challenge/index.html the challenge is over, thanks to all participants. I've submitted the linkat 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 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 writes:I've setup a challenge, mainly for C++, Java and Lisp, but every otherlanguage is welcome:http://www.frank-buss.de/challenge/index.htmlthe challenge is over, thanks to all participants. I've submitted the linkat 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 wrote: Frank Buss 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 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 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 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 wrote: Yes. In particular, the *very* short solutions all (1) usedassignments within the program as input (though they didn'tcount those assignments as part of the code), (2) used numbers to represent points, which enables various minoralgorithmic 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 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