Follow Slashdot stories on Twitter

 


Forgot your password?
Close
typodupeerror
×
Programming Technology

Programming Challenge: Triangles Puzzle 40

Posted by michael 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."
This discussion has been archived. No new comments can be posted.

Programming Challenge: Triangles Puzzle More

Programming Challenge: Triangles Puzzle

Comments Filter:

  • lots of Lisp people out there. (Score:3, Interesting)

    by sgant ( 178166 ) on Tuesday October 26, 2004 @12:57PM (#10632810) Homepage Journal
    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?

    • Re:lots of Lisp people out there. (Score:4, Informative)

      by evilmousse ( 798341 ) on Tuesday October 26, 2004 @01:21PM (#10633079) Journal

      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.

  • Looky... (Score:5, Funny)

    by maunleon ( 172815 ) on Tuesday October 26, 2004 @12:59PM (#10632821)
    Shhh... I see dead languages.

    • There's only one thing dead about APL, and I'm sad about that.

      It's more of a Mark Twain language: reports are greatly exaggerated.

  • Only one solution (Score:2, Interesting)

    by Anonymous Coward
    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).

    • Re:Only one solution (Score:2, Interesting)

      by erykjj ( 213892 )
      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.

    • Re:Only one solution (Score:4, Interesting)

      by Evil Pete ( 73279 ) on Tuesday October 26, 2004 @06:32PM (#10636728) Homepage

      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.

  • I wonder... (Score:3, Interesting)

    by Sheetrock ( 152993 ) on Tuesday October 26, 2004 @01:26PM (#10633131) Homepage Journal
    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).

  • More simple solution (Score:2, Informative)

    by eric2hill ( 33085 )
    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.
    • What if I add a line between P8 and P9? Your solution no longer works.
      • 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)

    • Re:More simple solution (Score:3, Interesting)

      by Photar ( 5491 )
      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

  • Why not Prolog? (Score:5, Interesting)

    by ameoba ( 173803 ) on Tuesday October 26, 2004 @07:09PM (#10637080)
    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.
    • ...and not a single comment.
    • ...it's definately simpler than any of the other solutions.

      Have you looked at the Haskell solution? It is very similar to yours. But with that said, your Prolog solution does seem to be just a bit clearer than the Haskell solution. Although Haskells lists and list comprehensions do a good job of modelling the problem, the use of lists is an implementation detail that is explicitly coded into the solution. The Prolog solution looks like a pure specification for the problem.

    • Are the two '>' predicates needed in tri()?

      Note, I've never even _seen_ any prolog before, I'm trying to work out how it might work (prolog, that is) from your code.

      It just that you have those conditions in edge(), so it looks like they're redundant in tri()

      FP.

  • Need more challenges (Score:5, Interesting)

    by miyako ( 632510 ) <miyako.gmail@com> on Wednesday October 27, 2004 @05:55AM (#10640187) Homepage Journal
    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
  • 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?
    • Find the angle from pt1 to pt4 to pt2 (+ve if clockwise, -ve if not). Find the angle from pt2 to pt4 to pt3. And again from pt3 to pt4 to pt 1.

      If the angles sum to 360 degrees, p4 is within the triangle. If they sum to 0, it is not.

    • Re:One problem I've always wanted to solve... (Score:1, Insightful)

      by Anonymous Coward
      The three points (call them p1, p2, p3) form three lines - any two of the points describe a line on the plain. Now determine, with respect to each of those lines, if p4 is on the same side of the line as the third point. So, if p4 is on the same side of p1-p2 as p3, and on the same side of p1-p3 as p2, and on the same side of p2-p3 as p1 - then it is in the triangle.
  • For Lisp you could use ACL2 [utexas.edu]. For Java you could use JML [iastate.edu] , together with Krakatoa [krakatoa.lri.fr], Why [why.lri.fr] (which could also be used to program the solution) and Coq [inria.fr]. For all the other languages that appear in the solutions list I think you're on your own.

  • The problem is to create a function that takes NO input and produces 27.

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

Slashdot Top Deals

Disc space -- the final frontier!

Close