From: Sergey Dymchenko <kit1980_at_gmail.com>

Date: Sun, 29 May 2011 18:32:06 +0300

Date: Sun, 29 May 2011 18:32:06 +0300

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_monash.edu> 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 >Received on Sun May 29 2011 - 15:32:12 CEST

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