[eclipse-clp-users] Request for code review

From: Sergey Dymchenko <kit1980_at_...6...>
Date: Sat, 28 May 2011 01:18:12 +0300
Hi!

I'm very new (several days) to Prolog and ECLIPSe.

To learn ECLIPSe I decided to solve simple problem from
www.topcoder.com/stat?c=problem_statement&pm=11414&rd=14524 :

"""
There is a group of N people numbered from 0 to N-1. Each of them is
either an honest person or a liar. You wish to know how many liars are
in the group. To do this, you have asked the same question to every
person in the group: "What is the number of liars in this group?". The
people in the group themselves know the exact number of liars, but
since you are a foreigner in the group, they have not told it to you
exactly. Instead, the i-th person answered you as follows: "There are
at least claim[i] liars in the group." It is known that statements by
honest persons are always true. However, statements by liars are
always false. So, if a liar claims that there are at least X liars in
the group, then in fact there are less than X liars.

Now, given a int[] claim containing the N answers that you received,
you would like to determine the number of liars in the group.
Unfortunately, there's another twist that makes this problem more
complicated. The people in the group speak a different language than
you, so you might have misunderstood some of their answers. The
answers in claim are how you understood them, but they might not match
what the people actually told you. If you definitely misunderstood at
least one of the answers, return -1. Otherwise, assuming that you
understood all answers correctly, return the minimum number of liars
that could be in the group.

-	claim will contain between 2 and 50 elements, inclusive.
-	Each element of claim will be between 0 and 100, inclusive.
"""

This problem is aimed to be solved in C++ or Java (and it's very easy
problem), but I want to solve it in declarative way.

My code:


:- lib(ic).

solve(Claims) :-
    dim(Claims, [N]),

    dim(Liars, [N]),
    Liars[1..N] :: [0, 1],

    ( for(I, 1, N), param(Claims, Liars, N) do

        % if a liar claims that there are at least X liars in the
        % group, then in fact there are less than X liars
        (Liars[I] #= 1, sum(Liars[1..N]) #< Claims[I]) ;

            % statements by honest persons are always true
            (Liars[I] #= 0, sum(Liars[1..N]) #>= Claims[I])),

    (
        labeling(Liars),
        R is sum(Liars[1..N]),
        writeln(R),
        fail
    ).


I tested the code and I found it works.
For example

: solve([](7, 8, 1)).
2

: solve([](4, 9, 1, 12, 21, 8, 1, 23, 3, 6, 5, 6, 21, 20, 0, 8, 7, 9, 4, 27)).
8

:solve([](1, 2, 3, 4, 5)).
 - empty -

Please review my code and suggest improvements or other (declarative)
ways to solve the problem.
Should I use lists instead of arrays?

How to speed up the program? For large inputs with no answer it thinks
for half of a minute...

How to writeln "-1" in case the is no solution?
Received on Fri May 27 2011 - 22:18:19 CEST

This archive was generated by hypermail 2.3.0 : Thu Feb 22 2024 - 18:13:20 CET