Programming Challenge: Triangles Puzzle

Frank Buss writes "Last week was a challenge to write a program, which solves a simple geometric problem. There was nothing to win, only the solutions at the end are the win for all readers, but nevertheless the response was great (some thousands of web-hits) and there are some nice solutions."

Comments

Looky...

[maunleon]

Shhh... I see dead languages.

Re:lots of Lisp people out there.

[evilmousse]

No, I'm pretty sure mathematica would work fine.
It does indeed have it's own language, and plenty of permutation/combination logistics.
I'm guessing it'd be more useful to someone seeking a mathematical proof/theorem regarding the problem, listing complex genral-case equations at each step.
The more common programming languages are likely more productive, being concerned more with just the result than the theory at each step. tho I do know many math majors that would have an easier time programming it in mathematica, just because that's what they're used to.
Lisp is the logical language choice for this or any other heavily-combinational/AI task, though you'll never catch me programming in it.

Why not Prolog?

[ameoba]

Lots of Lisp, why no Prolog? Looks like a textbook problem for an intro prolog class.


% ameoba@girl:~/triangle$ gprolog
% GNU Prolog 1.2.18
% By Daniel Diaz
% Copyright (C) 1999-2004 Daniel Diaz
% | ?- consult('tri.pl').
% compiling /home/ameoba/triangle/tri.pl for byte code...
% /home/ameoba/triangle/tri.pl compiled, 33 lines read - 4628 bytes written, 10 ms
%
% yes
% | ?- numtri(X).
%
% X = 27
%
% yes
% | ?-

line([0,5,8,10]).
line([0,1]).
line([1,6,9,10] ).
line([0,3,7,9]).
line([0,2,4,6]).
line([1,2, 3,5]).
line([1,4,7,8]).

edge(X,Y) :-
line(L),
member(X,L),
member(Y,L),
X > Y.

colinear(X,Y,Z) :-
line(L),
member(X,L),
member(Y,L),
member(Z,L).

tri(X,Y,Z) :-
edge(X,Y),
edge(X,Z),
edge(Y,Z),
X > Y,
Y > Z,
\+ colinear(X,Y,Z).

numtri(X) :-
setof([X,Y,Z], tri(X,Y,Z), Tris),
length(Tris,X).


35 lines of code in about 45min (mostly remembering syntax & predicates) and it's definately simpler than any of the other solutions.

Need more challenges

[miyako]

We need more challenges like this. I remember seeing this when it was posted on usenet a while ago, and my interest was peaked. Not sure if it was my math or programming skills that were lacking, but I wasn't able to immediately see a solution, and ended up forgetting to go back to the problem, but I would love to see more challenges like this.
I remember there was a time when I would spend days coding, now it seems like I spend days trying to think of something interesting to try to code, and usually end up getting distracted by something else.
I guess it could probably be laziness on my part, but I would like to see more challenges like this (perhaps a website that posts a monthly programming challenge, maybe cycling through different types of challenges like math, text procesing, optimization, etc) for people to take on. Does something like this already exist?
Somewhat off topic, but I would also like to see a site that every couple of weeks or something posts a different open source project that looks promising and needs help getting something specific to work.
As a matter of fact, the above two problems sound like something that would make a good and interesting website, maybe even offering a chance at doing some overly complex and unnessecary PHP programming.
If anyone is interested in working on a website like this, send me an email at:miyako at gmail dot com