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

Joachim, thanks for your review, it's really helpful!

Also recently I read about shelves.  The tutorial says: "A typical
application is counting of solutions...".
So I think using shelf object to writeln "-1" in case there is no
solution is a good idea. Am I right?


On Sun, May 29, 2011 at 5:01 PM, Joachim Schimpf
<joachim.schimpf_at_...269...> wrote:
> 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
>