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];
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
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[5] = 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);
ma.add(i);
mb.add(j);
mc.add(k);
md.add(l);
me.add(e);
mf.add(val);
}
// 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[0] ) {
System.out.println("A is "+G(ma)+".");
++cnt;
}
if ( mb.size() == 1 && present[1] ) {
System.out.println("B is "+G(mb)+".");
++cnt;
}
if ( mc.size() == 1 && present[2] ) {
System.out.println("C is "+G(mc)+".");
++cnt;
}
if ( md.size() == 1 && present[3] ) {
System.out.println("D is "+G(md)+".");
++cnt;
}
if ( me.size() == 1 && present[4] ) {
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("");
}
}
};
).