From: Alexandre Saidi <Alexandre.Saidi_at_ec-lyon.fr>

Date: Tue, 27 Sep 2011 17:38:11 +0200

Date: Tue, 27 Sep 2011 17:38:11 +0200

Hi all, I thought (rapidly) about an algebraic solution but there will be no more use of Eclipse CLP possibilities ! However, below is the modus operandi : Given a grid of M lines and N columns, Given the area A (suppose that M.N >=A), There are W = 2MN+(M+N)(A-1) rectangles with the area A in that grid (except if M=1 or N=1 where we must divide W by 2). For instance, for M=10, N=4 and A=2, there will be 66 rectangles of area 2 in it. And for M=1, N=2, A=1, we get only one rectangle (instead of 2). We can compute (naively) the coordinates of each rectangle. Now, given a rectangle of area A, there are 4 triangles of area A/2 in it (half of them are symmetrical) So, given the grid MN, we can just compute the coordinates of all these rectangles and output 4 triangles for each. Not funny. ! Because we don't use the power of CLP. However, the Sergey solution looks quite nice AND USES Eclipse. That's the point. For the obvious fact about (0,0) , one may translate the center of coordinates from (0,0) to say (x1,y1) and there, the new center is obviously one of the 3 vertices . Hence, translate (x2,y2) and (x3,y3) into that new coordinates. However, this will not reduce the complexity. regards Alex Le 27 sept. 2011 à 08:15, Sergey Dymchenko a écrit : > Hi! > > I've solved a problem from Google Code Jam: Triangle Areas, > https://code.google.com/codejam/contest/dashboard?c=32001#s=p1 > > I think the problem is very suitable for constraint programming > paradigm, and also I wanted to learn how to do simple input parsing, > output formating etc. > My solution work correctly and in reasonable amount of time (6 seconds > for 1000 "large" tests on my computer) for both "small" and "large" > inputs. > > But the speed is OK only when I manually put one point to (0, 0): X1 > #= 0, Y1 #= 0 > Without this "help" to the solver speed is unacceptable on large > inputs. I tried to do symmetry break, but it doesn't help much. > Any ideas hot to speed up program without explicitly putting one point > to (0, 0)? (although I'm OK with this, because it's pretty obvious). > > Also I'd be happy to hear any other comments to my code. > > The solution is about 40 lines long, so I hope it's OK to put it > directly in the email. > > :- lib(ic). > :- lib(util). > > % Triagle area * 2 > area2(X1, Y1, X2, Y2, X3, Y3, A) :- > A #= abs( > X1 * Y2 - X1 * Y3 + > X2 * Y3 - X2 * Y1 + > X3 * Y1 - X3 * Y2 > ). > > model(N, M, A, [X1, Y1, X2, Y2, X3, Y3]) :- > [X1, X2, X3] :: 0..N, > [Y1, Y2, Y3] :: 0..M, > X1 #= 0, Y1 #= 0, % we can safely put one point in (0, 0) > area2(X1, Y1, X2, Y2, X3, Y3, A). > > find(Points) :- > search(Points, 0, input_order, indomain_split, complete, []). > > do_case(Case_num, Case_str) :- > ( > split_string(Case_str, " ", "", [N_str, M_str, A_str]), > number_string(N, N_str), number_string(M, M_str), > number_string(A, A_str), > model(N, M, A, Points), > find(Points), > print_case(Case_num, Points) > ) ; ( > print_case(Case_num, []) > ). > > print_case(Case_num, [X1, Y1, X2, Y2, X3, Y3]) :- > printf("Case #%d: %d %d %d %d %d %d\n", [Case_num, X1, Y1, X2, Y2, X3, Y3]). > print_case(Case_num, []) :- > printf("Case #%d: IMPOSSIBLE\n", [Case_num]). > > do :- > read_line(C_str), > number_string(C, C_str), > ( count(K, 1, C) do > read_line(Case_str), > do_case(K, Case_str) ). > > ------------------------------------------------------------------------------ > All the data continuously generated in your IT infrastructure contains a > definitive record of customers, application performance, security > threats, fraudulent activity and more. Splunk takes this data and makes > sense of it. Business sense. IT sense. Common sense. > http://p.sf.net/sfu/splunk-d2dcopy1 > _______________________________________________ > ECLiPSe-CLP-Users mailing list > ECLiPSe-CLP-Users_at_lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users ------------------------------- Alexandre Saidi Maitre de Conférences Ecole Centrale de Lyon-Dép. MI LIRIS-CNRS UMR 5205 Tél : 0472186530, Fax : 0472186443Received on Tue Sep 27 2011 - 15:36:46 CEST

*
This archive was generated by hypermail 2.2.0
: Thu Feb 02 2012 - 02:31:58 CET
*