Slashdot Mirror

← Back to Stories (view on slashdot.org)

Programming Challenge: Triangles Puzzle

Posted by michael on from the idle-hands-do-the-devil's-work dept.

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."

15 of 40 comments (clear)

  1. lots of Lisp people out there. by sgant · · Score: 2, Interesting

    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
    1. Re:lots of Lisp people out there. by evilmousse · · Score: 4, Informative


      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.

  2. Looky... by maunleon · · Score: 4, Funny

    Shhh... I see dead languages.

  3. Only one solution by Anonymous Coward · · Score: 2, Interesting

    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).

    1. Re:Only one solution by erykjj · · Score: 2, Interesting

      The point is to have the computer figure it out, rather than providing a formula that a human being came up with. I guess there is always going to be a fine line as to how much "human" logic goes into a program, hence the variety of solutions.

    2. Re:Only one solution by Evil+Pete · · Score: 3, Interesting

      What's more it is in a language ('J') that is derived from APL ! He gets high geek points for even understanding anything derived from APL much less writing quick solutions in it.

      --
      Bitter and proud of it.
  4. I wonder... by Sheetrock · · Score: 2, Interesting

    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.




    1. Re:I wonder... by TwistedSquare · · Score: 2, Interesting

      By the time you've used EP on the problem, I think quicker would be out of the window ;) I gather from other comments than manual rearranging is possible (I didn't read the problem too closely admittedly).

  5. More simple solution by eric2hill · · Score: 2, Informative

    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
    1. Re:More simple solution by Photar · · Score: 3, Interesting

      Except if the number of divisions isn't the same on both sides. In which case its
      ((x*y)*(x+y))/2
      x = left side divisions
      y = right side divisions

      --
      He who knows not and knows he knows not is a wise man. He who knows not and knows not he knows not is a fool.
    2. Re:More simple solution by blankman · · Score: 2, Informative

      What if I add a line between P8 and P9? Your solution no longer works.

      Notice that all the additional lines in the problem intersect either P0 or P1. Adding a line between P8 and P9 significantly changes the problem.

      You are correct though, in saying that x^y is not the solution. A few of the solutions did work out general formulae, the simplest I saw being (1/2)*(m*n)*(m+n)

  6. Why not Prolog? by ameoba · · Score: 4, Interesting

    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.

    --
    my sig's at the bottom of the page.
  7. Need more challenges by miyako · · Score: 4, Interesting

    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"
    1. Re:Need more challenges by Anonymous Coward · · Score: 2, Informative

      http://online-judge.uva.es/problemset/ //Jesper Miller

    2. Re:Need more challenges by meme_police · · Score: 2, Informative

      Pedant mode: it's piqued, meaning aroused, not peaked.

      --

      The meme police, They live inside of my head