Re: [eclipse-clp-users] Request for code review

Sergey Dymchenko wrote:
...
> :- 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
>     ).
...
> Please review my code and suggest improvements or other (declarative)
> ways to solve the problem.

This is really good for a first attempt.  A couple of improvements:

If you use ECLiPSe for constraint programming, you should separate
your code into:  model (logic), search, and i/o.

The model should not contain any nondeterminism (i.e. no alternatives
expressed as disjunction ";" or alternative clauses).  Instead, model
allcalternatives as different values for decision variables.

The ";" in your model is actually not necessary, you can simply write

         Liars[I] #= (sum(Liars[1..N]) #< Claims[I])

which has exactly the meaning you intended, i.e. when Liars[I] is 1,
then the inequation is true, else the opposite is true.

So I would write:

:- lib(ic).

model(Claims, Liars) :-
     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.
         % if honest, the opposite is true, i.e. at least X liars
         Liars[I] #= (sum(Liars[1..N]) #< Claims[I])
     ).

solve(Claims, Liars) :-
     model(Claims, Liars),
     labeling(Liars).


You can run this directly:

?- solve([](4, 9, 1, 12, 21, 8, 1, 23, 3, 6, 5, 6, 21, 20, 0, 8, 7, 9, 4, 27), L).
L = [](0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1)
Yes (0.00s cpu, solution 1, maybe more)
No (0.00s cpu)

?- solve([](1, 2, 3, 4, 5)).
No (0.00s cpu)


> Should I use lists instead of arrays?

You could, but no advantage.


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

Removing the unnecessary disjunction fixed that already.
The principle is to set up all constraints first, and then
do the nondeterministic search/labeling (which will then be
pruned by constraint propagation).


> How to writeln "-1" in case the is no solution?

To add your original output printing, plus the required -1:

all(Claims) :-
	solve(Claims,Liars),
	R is sum(Liars),
	writeln(R),
	fail.
all(_) :-
	writeln(-1).

This will print all solutions (0, 1, or several), and then -1.

If you insist of having the -1 only printed when there are no solutions,
it gets a bit more complicated, e.g.

all(Claims) :-
     findall(x, (solve(Claims,Liars), R is sum(Liars), writeln(R)), Sols),
     ( Sols==[] -> writeln(-1) ; true ).


On last point about bracketing:  DON'T put parentheses around
conjunctions (sequences of comma-separated goals).
DO put parentheses around disjunctions and do-loops (because
the comma binds more strongly than ";" and "do").


-- Joachim