From: Sergey Dymchenko <kit1980_at_...6...>

Date: Sat, 28 May 2011 01:18:12 +0300

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.2.0
: Mon Jul 09 2018 - 02:05:29 CEST
*