592 - Island of Logic

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Joan Pi Sarr
New poster
Posts: 4
Joined: Fri Apr 11, 2003 5:29 pm

592 - Island of Logic

I don't know what's wrong with my program It works fine with the sample input given with the problem.
What follows is a sample input and corresponding output
of my program with all the cases I could think of:

*************************************************************************************
6
A: B is human.
A: B is evil.
B: A is human.
C: A is not lying.
B: C is not human.
D: E is not lying.
4
A: I am human.
A: It is night.
B: I am human.
B: It is day.
3
A: I am human.
B: I am human.
A: B is lying.
3
A: I am divine.
B: A is not lying.
A: B is lying.
3
A: I am divine.
B: A is lying.
A: B is lying.
5
A: B is human.
A: B is evil.
B: A is evil.
C: A is not lying.
B: It is day.
5
C: A is not lying.
A: B is human.
A: B is evil.
B: A is evil.
B: It is day.
1
A: A is not lying.
1
A: A is lying.
2
E: E is evil.
E: E is divine.
7
A: It is night.
B: It is day.
C: I am human.
E: C is human.
C: E is divine.
A: B is lying.
B: C is evil.
0

*********************************************************************************

Conversation #1
A is human.
B is divine.
C is evil.
D is divine.
It is night.

Conversation #2
A is evil.
B is human.
It is day.

Conversation #3
It is day.

Conversation #4
This is impossible.

Conversation #5
No facts are deducible.

Conversation #6
A is evil.
B is divine.
C is evil.
It is day.

Conversation #7
A is evil.
B is divine.
It is day.

Conversation #8
No facts are deducible.

Conversation #9
This is impossible.

Conversation #10
E is human.
It is night.

Conversation #11
A is evil.
C is evil.
E is evil.
It is day.

********************************************************************************

Any idea about what may I be doing wrong? Thanks a lot.

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
Your output for input #1 and #7 is wrong.

In the first case you can't say D is divine., while in the seventh you omitted C is evil.

At least my ACed program says that. (Of course I didn't prove incorrectness of your output myself - or I'll should be considered to be evil ).

Good luck!
Andrey.

Joan Pi Sarr
New poster
Posts: 4
Joined: Fri Apr 11, 2003 5:29 pm
Two questions induced from the last answer:

1) In the first case of my input my program says that D is divine because
what D says is true (E is not lying because she didn't say nor will say
anything), and it's night.

Must sentences about people who do not speak be ignored?

2) In the seventh case of my input my program does not say that C is evil
because it considers C to say the truth. Indeed, when C speaks, A (which
turns out to be evil) has not spoken yet, so she has not lied yet.

So the order of sentences must be ignored too?

Thanks for your help Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
Yes, ignore both cases.

wrong
New poster
Posts: 4
Joined: Wed Nov 22, 2006 8:14 pm
I have considered all the cases mentioned above, but I`m still getting WA for this problem..

could anybody post other inputs and outputs, or suggest what to be aware of in this problem apart from things already mentioned in this topic?

wrong
New poster
Posts: 4
Joined: Wed Nov 22, 2006 8:14 pm
i have AC finally, thanks anyway

nghiank
New poster
Posts: 31
Joined: Wed Nov 20, 2002 3:10 pm
Contact:

Re: 592

Any tricky input for this problem? I still get WA.

red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

Re: 592 - Island of Logic

Is JavaScript engine allowed on UVa? I'm getting RTEs with the following:

Code: Select all

/*
* 592. Island of Logic
* TOPIC:
* status:
*/
import java.io.*;
import java.util.*;
import java.util.regex.*;
import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;

class Main {

Pattern pa = Pattern.compile("\\(A=(\\d)\\)");
Pattern pb = Pattern.compile("\\(B=(\\d)\\)");
Pattern pc = Pattern.compile("\\(C=(\\d)\\)");
Pattern pd = Pattern.compile("\\(D=(\\d)\\)");
Pattern pe = Pattern.compile("\\(E=(\\d)\\)");
Pattern pf = Pattern.compile("\\(F=(\\d)\\)");

final int DIVINE = 0, EVIL = 1, HUMAN = 2, LYING = 3, DAY = 0, NIGHT = 1, A = 0, BE = 0, CE = 0, DE = 0, E = 0, TAIM = 5;
int n,pos,cnt;
int []var = new int[0x40];
String BRACKETS( String t ) { return "("+t+")"; }
String T;
char []txt;

class F {
int var_name,val;
F( int vname, int val ) { this.var_name = vname; this.val = val; }
String toStr() { return BRACKETS(Character.toString((char)(this.var_name+'A'))+"="+Integer.toString(this.val)); }
};

int getCode( String s ) {
if ( s.equals("divine") ) return DIVINE;
if ( s.equals("evil") ) return EVIL;
if ( s.equals("human") ) return HUMAN;
if ( s.equals("lying") ) return LYING;
if ( s.equals("day") ) return DAY;
return NIGHT;
}

String conj( F a, F b ) { return a.toStr()+"&&"+b.toStr(); }
String disj( F a, F b ) { return BRACKETS(a.toStr()+"||"+b.toStr()); }
String TRUTHFUL( int k ) { return BRACKETS((new F(k,DIVINE)).toStr()+"||"+conj(new F(k,HUMAN),new F(TAIM,DAY))); }
String LIE( int k ) { return BRACKETS((new F(k,EVIL)).toStr()+"||"+conj(new F(k,HUMAN),new F(TAIM,NIGHT))); }

String ANYTHING_BUT( int k, int val ) {
if ( k == TAIM )
return (new F(k,val^1)).toStr();
if ( val == DIVINE )
return disj(new F(k,HUMAN),new F(k,EVIL));
if ( val == HUMAN )
return disj(new F(k,EVIL),new F(k,DIVINE));
if ( val == EVIL )
return disj(new F(k,HUMAN),new F(k,DIVINE));
return "";
}

String replaceOll( String s, int a, int b, int c, int d, int e, int f ) {
Matcher m;
String t = s;
TreeMap<String,String> h = new TreeMap<String,String>();
Set set;
Iterator it;

h.clear();
m = pa.matcher(s);
while ( m.find() )
if ( Integer.parseInt(m.group(1)) != a )
h.put(m.group(0),"false");
else
h.put(m.group(0),"true");
set = h.entrySet();
it = set.iterator();
while ( it.hasNext() ) {
Map.Entry me = (Map.Entry)it.next();
// System.out.println("Replacing "+(String)me.getKey()+" with "+(String)me.getValue());
s = s.replaceAll((String)me.getKey(),(String)me.getValue());
}

h.clear();
m = pb.matcher(s);
while ( m.find() ) {
if ( Integer.parseInt(m.group(1)) != b )
h.put(m.group(0),"false");
else
h.put(m.group(0),"true");
}
set = h.entrySet();
it = set.iterator();
while ( it.hasNext() ) {
Map.Entry me = (Map.Entry)it.next();
s = s.replaceAll((String)me.getKey(),(String)me.getValue());
}

h.clear();
m = pc.matcher(s);
while ( m.find() ) {
if ( Integer.parseInt(m.group(1)) != c )
h.put(m.group(0),"false");
else
h.put(m.group(0),"true");
}
set = h.entrySet();
it = set.iterator();
while ( it.hasNext() ) {
Map.Entry me = (Map.Entry)it.next();
s = s.replaceAll((String)me.getKey(),(String)me.getValue());
}

h.clear();
m = pd.matcher(s);
while ( m.find() ) {
if ( Integer.parseInt(m.group(1)) != d )
h.put(m.group(0),"false");
else
h.put(m.group(0),"true");
}
set = h.entrySet();
it = set.iterator();
while ( it.hasNext() ) {
Map.Entry me = (Map.Entry)it.next();
s = s.replaceAll((String)me.getKey(),(String)me.getValue());
}

h.clear();
m = pe.matcher(s);
while ( m.find() ) {
if ( Integer.parseInt(m.group(1)) != e )
h.put(m.group(0),"false");
else
h.put(m.group(0),"true");
}
set = h.entrySet();
it = set.iterator();
while ( it.hasNext() ) {
Map.Entry me = (Map.Entry)it.next();
s = s.replaceAll((String)me.getKey(),(String)me.getValue());
}

h.clear();
m = pf.matcher(s);
while ( m.find() ) {
if ( Integer.parseInt(m.group(1)) != f )
h.put(m.group(0),"false");
else
h.put(m.group(0),"true");
}
set = h.entrySet();
it = set.iterator();
while ( it.hasNext() ) {
Map.Entry me = (Map.Entry)it.next();
s = s.replaceAll((String)me.getKey(),(String)me.getValue());
}
return "true"+s;
}

public static void main( String [] args ) throws Exception { new Main().go(); }

String G( TreeSet<Integer> t ) {
Iterator<Integer> it = t.iterator();
switch ( it.next() ) {
case 0:   return "divine";
case 1:   return "evil";
case 2:   return "human";
default:  return "";
}
}

String H( TreeSet<Integer> t ) {
Iterator<Integer> it = t.iterator();
switch ( it.next() ) {
case 0:   return "day";
case 1:   return "night";
default:  return "";
}
}

boolean []present = new boolean[0x40];
int U( int k ) {
if ( k == 5 ) {
if ( present[k] )
return NIGHT;
return DAY;
}
if ( present[k] )
return HUMAN;
return DIVINE;
}

void go() throws Exception {
int i,j,k,val,cs = 0,e = 0,l;
boolean ok;
String nn;
Pattern p1 = Pattern.compile("I\\s+am\\s+(not )?\\s*(divine|human|evil|lying)");
Pattern p2 = Pattern.compile("([A-Z])\\s+is\\s+(not )?\\s*(divine|human|evil|lying)");
Pattern p3 = Pattern.compile("It\\s+is\\s+(day|night)");
Pattern p4 = Pattern.compile("([A-Z])");
while ( (nn=br.readLine())!=null && (n=Integer.parseInt(new StringTokenizer(nn).nextToken()))!=0 ) {
T = "";
System.out.println("Conversation #"+(++cs));
ok = true;
for ( i = 0; i <= 5; ++i ) present[i] = false;
for ( i = 0; i < n; ++i ) {
String t = br.readLine();
if ( !ok ) { T = ""; continue ; }
if ( t.indexOf("It") != -1 )
present = true;
for ( char c: t.toCharArray() )
if ( 'A' <= c && c <= 'Z' )
present[c-'A'] = true;
Matcher m1 = p1.matcher(t.substring(t.indexOf(":")));
Matcher m2 = p2.matcher(t.substring(t.indexOf(":")));
Matcher m3 = p3.matcher(t.substring(t.indexOf(":")));
Matcher m4 = p4.matcher(t);
m4.find();
k = m4.group(1).charAt(0)-'A';
if ( m1.find() ) {
e = getCode(m1.group(2));
if ( m1.group(1) != null ) {
// m1.group(1).equals("not");
if ( e == LYING ) T += "&&"+BRACKETS(TRUTHFUL(k)+"||"+(new F(k,EVIL)).toStr());
else if ( e == DIVINE ) T += "&&"+conj(new F(TAIM,DAY),new F(k,HUMAN));
else if ( e == HUMAN ) T += "&&"+BRACKETS((new F(k,DIVINE)).toStr()+"||"+conj(new F(TAIM,NIGHT),new F(k,HUMAN)));
else T += "&&"+BRACKETS((new F(k,DIVINE)).toStr()+"||"+conj(new F(TAIM,DAY),new F(k,HUMAN))+(new F(k,EVIL)).toStr());
}
else {
if ( e == LYING ) ok = false;
else if ( e == DIVINE ) T += "&&"+BRACKETS((new F(k,DIVINE)).toStr()+"||"+LIE(k));
else if ( e == HUMAN ) T += "&&"+BRACKETS(conj(new F(k,HUMAN),new F(TAIM,DAY))+"||"+(new F(k,EVIL)).toStr());
else T += "&&"+conj(new F(k,HUMAN),new F(TAIM,NIGHT));
}
}
else if ( m2.find() ) {
j = m2.group(1).charAt(0)-'A';
e = getCode(m2.group(3));
if ( m2.group(2) != null ) {
// m2.group(2).equals("not");
if ( e == LYING ) T += "&&"+BRACKETS(BRACKETS(TRUTHFUL(k)+"&&"+TRUTHFUL(j))+"||"+BRACKETS(LIE(k)+"&&"+LIE(j)));
else if ( e == DIVINE )
T += "&&"+BRACKETS(BRACKETS(LIE(k)+"&&"+(new F(j,DIVINE)).toStr())+"||"+BRACKETS(TRUTHFUL(k)+"&&"+ANYTHING_BUT(j,DIVINE)));
else if ( e == HUMAN )
T += "&&"+BRACKETS(BRACKETS(LIE(k)+"&&"+(new F(j,HUMAN)).toStr())+"||"+BRACKETS(TRUTHFUL(k)+"&&"+ANYTHING_BUT(j,HUMAN)));
else
T += "&&"+BRACKETS(BRACKETS(LIE(k)+"&&"+(new F(j,EVIL)).toStr())+"||"+BRACKETS(TRUTHFUL(k)+"&&"+ANYTHING_BUT(j,EVIL)));
}
else {
if ( e == LYING ) T += "&&"+BRACKETS(BRACKETS(TRUTHFUL(k)+"&&"+LIE(j))+"||"+BRACKETS(LIE(k)+"&&"+TRUTHFUL(j)));
else if ( e == DIVINE )
T += "&&"+BRACKETS(BRACKETS(TRUTHFUL(k)+"&&"+(new F(j,DIVINE)).toStr())+"||"+BRACKETS(LIE(k)+"&&"+ANYTHING_BUT(j,DIVINE)));
else if ( e == HUMAN )
T += "&&"+BRACKETS(BRACKETS(TRUTHFUL(k)+"&&"+(new F(j,HUMAN)).toStr())+"||"+BRACKETS(LIE(k)+"&&"+ANYTHING_BUT(j,HUMAN)));
else
T += "&&"+BRACKETS(BRACKETS(TRUTHFUL(k)+"&&"+(new F(j,EVIL)).toStr())+"||"+BRACKETS(LIE(k)+"&&"+ANYTHING_BUT(j,EVIL)));
}
}
else if ( m3.find() ) {
val = getCode(m3.group(1));
T += "&&"+BRACKETS(BRACKETS(TRUTHFUL(k)+"&&"+(new F(TAIM,val)).toStr())+"||"+BRACKETS(LIE(k)+"&&"+(new F(TAIM,val^1)).toStr()));
}
}
if ( !ok || T.equals("") ) {
System.out.println("This is impossible.\n");
continue ;
}
// System.out.println(T);
TreeSet<Integer> ma = new TreeSet<Integer>();
TreeSet<Integer> mb = new TreeSet<Integer>();
TreeSet<Integer> mc = new TreeSet<Integer>();
TreeSet<Integer> md = new TreeSet<Integer>();
TreeSet<Integer> me = new TreeSet<Integer>();
TreeSet<Integer> mf = new TreeSet<Integer>();
for ( i = DIVINE; i <= U(0); ++i )
for ( j = DIVINE; j <= U(1); ++j )
for ( k = DIVINE; k <= U(2); ++k )
for ( l = DIVINE; l <= U(3); ++l )
for ( e = DIVINE; e <= U(4); ++e )
for ( val = DAY; val <= NIGHT; ++val ) {
String S = T; S = replaceOll(S,i,j,k,l,e,val);
// System.out.println(S);
ScriptEngineManager sem = new ScriptEngineManager();
ScriptEngine se = sem.getEngineByName("JavaScript");
if ( ((boolean)se.eval(S)) ) {
// System.out.println(T+" "+S);
}
// System.out.println(S);
}
if ( ma.size() == 0 && mb.size() == 0 && mc.size() == 0 && md.size() == 00 && me.size() == 0 && mf.size() == 0 ) {
System.out.println("This is impossible.\n");
continue ;
}
cnt = 0;
if ( ma.size() == 1 && present ) {
System.out.println("A is "+G(ma)+".");
++cnt;
}
if ( mb.size() == 1 && present ) {
System.out.println("B is "+G(mb)+".");
++cnt;
}
if ( mc.size() == 1 && present ) {
System.out.println("C is "+G(mc)+".");
++cnt;
}
if ( md.size() == 1 && present ) {
System.out.println("D is "+G(md)+".");
++cnt;
}
if ( me.size() == 1 && present ) {
System.out.println("E is "+G(me)+".");
++cnt;
}
if ( mf.size() == 1 ) {
System.out.println("It is "+H(mf)+".");
++cnt;
}
if ( cnt == 0 )
System.out.println("No facts are deducible.");
System.out.println("");
}
}
};