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

From: Sergey Dymchenko <kit1980_at_gmail.com>
Date: Tue, 27 Sep 2011 09:15:31 +0300
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) ).
Received on Tue Sep 27 2011 - 06:15:38 CEST

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