Slashdot Mirror
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."
Interesting contest. I was wondering though, (as I have no experience or knowledge of programming and my math is laughed at by my 11 year old) wouldn't a program like Mathematica or Maple be able to handle something like this with ease? Don't they have programming interfaces?
Or is the problem so simple that it's kinda overkill for them? Or is it just plain easier to do it with Lisp or Python?
"Leo Fender was in a 'state of grace' when he designed the Stratocaster." -- Paul Reed Smith
Shhh... I see dead languages.
Most of the entries are complex programs that calculate the answer. I only saw one person that solved the problem purely at the mathematical level.
That is the "J" entry, and in fact that same solution would work in all the other languages in 1 line of code (for the most part).
If the fastest way to compute this is really the mathematical method, or if a technique like evolutionary programming might expose a quicker means of arriving at the result (i.e. a simpler mathematical method).
Try not. Do or do not, there is no try.
-- Dr. Spock, stardate 2822-3.
Using any handheld calculator with an "x^y" key...
Take the number of divisions coming from a base vertex of the triangle and raise it to the power of the number of divisions coming from the opposite vertex. In the case given, 3 divisons to the power of 3 divisons = 27.
LOAD "SIG",8,1
LOADING...
READY.
RUN
open4free ©
Lots of Lisp, why no Prolog? Looks like a textbook problem for an intro prolog class.
/home/ameoba/triangle/tri.pl for byte code... /home/ameoba/triangle/tri.pl compiled, 33 lines read - 4628 bytes written, 10 ms
] )., 3,5]).
:-
:-
:-
:-
% ameoba@girl:~/triangle$ gprolog
% GNU Prolog 1.2.18
% By Daniel Diaz
% Copyright (C) 1999-2004 Daniel Diaz
% | ?- consult('tri.pl').
% compiling
%
%
% 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
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.
my sig's at the bottom of the page.
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
Famous Last Words: "hmm...wikipedia says it's edible"
I thought that quote in the sig was from Yoda not from Spock.
If you have a triangle on a plain with three points x1, y1 x2, y2 and x3, y3 and you select a point on the plane x4, y4, how do you prove the point is in the triangle or not?
Mumia Abu-Jamal is *laughably guilty*. Check the evidence.
For Lisp you could use ACL2. For Java you could use JML , together with Krakatoa, Why (which could also be used to program the solution) and Coq. For all the other languages that appear in the solutions list I think you're on your own.
Music: a super-stimulus for the perception of musicality. Musicality: a perceived aspect of speech.
The problem is to create a function that takes NO input and produces 27.
There's some hand-waving about making the program general-purpose, but it's too imprecise to be of any use. You need inputs.
I was quite supried to see how small in terms of line count the Java solution was. I was expecting to see a much higher disparity between the lisp like solutions and more standard languages.
There are four sorts of people in the world: fools, lunatics, idiots and morons. - Umberto Eco, Foucaut's pendulum.
Was the one written in SQL. A very innovative use of a database language.