- Mail actions: [ respond to this message ] [ mail a new topic ]
- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Joachim Schimpf <joachim.schimpf_at_...269...>

Date: Mon, 30 May 2011 00:01:37 +1000

Date: Mon, 30 May 2011 00:01:37 +1000

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"). -- JoachimReceived on Sun May 29 2011 - 14:01:44 CEST

*
This archive was generated by hypermail 2.3.0
: Wed Sep 25 2024 - 15:13:20 CEST
*