Re: [eclipse-clp-users] Triangle Areas: code review request

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 : 0472186443