Programming Challenge: Triangles Puzzle 40
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."
lots of Lisp people out there. (Score:3, Interesting)
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)
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)
Re:Looky... (Score:1)
It's more of a Mark Twain language: reports are greatly exaggerated.
Only one solution (Score:2, Interesting)
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)
Re:Only one solution (Score:1)
Re:Only one solution (Score:4, 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.
I wonder... (Score:3, Interesting)
Re:I wonder... (Score:3, Interesting)
Quote fromYoda not Spock!! (Score:2)
More simple solution (Score:2, Informative)
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.
Re:More simple solution (Score:1)
Re:More simple solution (Score:2, Informative)
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)
((x*y)*(x+y))/2
x = left side divisions
y = right side divisions
Why not Prolog? (Score:5, Interesting)
% 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.
Re:Why not Prolog? (Score:1)
Re:Why not Prolog? (Score:1)
If you think you can get away with no comments in lisp or prolog, then you haven't written very large lisp or prolog programs.
Re:Why not Prolog? (Score:1)
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.
Re:Why not Prolog? (Score:1)
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)
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
Re:Need more challenges (Score:2)
Re:Need more challenges (Score:2, Informative)
Re:Need more challenges (Score:3, Informative)
One problem I've always wanted to solve... (Score:1)
Re:One problem I've always wanted to solve... (Score: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)
Challenge 1b: Provably Correct Solutions (Score:1)
Problem statement is flawed. (Score:2)
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.
Good performance from Java (Score:1)