能,跟爱因斯坦的那道题类似,
我以前对那道题用过java实现。
哈,正好派上用场。
不过代码中没有什么模式理论的。import java.util.*;public class Einstein {
public static void main (String [] args) throws ArrayIndexNotFoundException {
test ();
}
static boolean DEBUG = false;
static long count = 0;
static void test () throws ArrayIndexNotFoundException {
long bt = System.currentTimeMillis ();
System.out.println ("Begin time : " + bt);
System.out.println ("Max compare hits : " + " 120^5 = " +
120 * 120 * 120 * 120 * 120);
System.out.println ("Min compare hits : " + " 1 ");
String [] col = new String [] {"red","green","white","yellow","blue"};
String [] cou = new String [] {"gre","bri","dan","rui","nuowei"};
String [] drink = new String [] {"coffee","milk","water","tea","beer"};
String [] anmial = new String [] {"bird","horse","cat","fish","dog"};
String [] cit = new String [] {"dun","mix","pall","print","bluecc"};
List l1 = new ArrayList ();
perm (col, 0, 4, l1);
System.out.println ("-----------------");
print (l1);
List l2 = new ArrayList ();
perm (cou, 0, 4, l2);
List l3 = new ArrayList ();
perm (drink, 0, 4, l3);
List l4 = new ArrayList ();
perm (anmial, 0, 4, l4);
List l5 = new ArrayList ();
perm (cit, 0, 4, l5);
// System.out.println ("l1.size="+l1.size ());
// System.out.println ("l2.size="+l2.size ());
// System.out.println ("l3.size="+l3.size ());
// System.out.println ("l4.size="+l4.size ());
// System.out.println ("l5.size="+l5.size ());
subList1 (l1) ;
subList2 (l2);
subList3 (l1);
// System.out.println ("l1.size="+l1.size ());
// System.out.println ("l2.size="+l2.size ());
// System.out.println ("l3.size="+l3.size ());
// System.out.println ("l4.size="+l4.size ());
// System.out.println ("l5.size="+l5.size ());
System.out.println ("Max compare hits : " +
l1.size () * l2.size () * l3.size () * l4.size () * l5.size ());
System.out.println ("Min compare hits : " + " 1 ");
print (l1);
print (l2);
compare (l1, l2, l3, l4, l5);
System.out.println ("In fact hits : " + count);
long et = System.currentTimeMillis ();
System.out.println ("End time : " + et);
System.out.println ("Elapsed time : " + (et - bt) + " milli secondes!" );
System.out.println ("Elapsed time : " + (et - bt) / 1000.0 / 60 + " minutes!");
}
static void subList3 (List l1) throws ArrayIndexNotFoundException {
//挪威人住在蓝房子旁边
String [] a1 = null;
for (int i = l1.size() - 1;i >= 0;i --) {
a1 = (String []) l1.get (i);
if (getIndex (a1, "blue") != 1) {
l1.remove (i);
}
}
}
static void subList2 (List l2) throws ArrayIndexNotFoundException {
//挪威人住在第一间房子
String [] a2 = null;
for (int i = l2.size() - 1;i >= 0;i --) {
a2 = (String []) l2.get (i);
if (getIndex (a2, "nuowei") != 0) {
l2.remove (i);
}
}
}
我以前对那道题用过java实现。
哈,正好派上用场。
不过代码中没有什么模式理论的。import java.util.*;public class Einstein {
public static void main (String [] args) throws ArrayIndexNotFoundException {
test ();
}
static boolean DEBUG = false;
static long count = 0;
static void test () throws ArrayIndexNotFoundException {
long bt = System.currentTimeMillis ();
System.out.println ("Begin time : " + bt);
System.out.println ("Max compare hits : " + " 120^5 = " +
120 * 120 * 120 * 120 * 120);
System.out.println ("Min compare hits : " + " 1 ");
String [] col = new String [] {"red","green","white","yellow","blue"};
String [] cou = new String [] {"gre","bri","dan","rui","nuowei"};
String [] drink = new String [] {"coffee","milk","water","tea","beer"};
String [] anmial = new String [] {"bird","horse","cat","fish","dog"};
String [] cit = new String [] {"dun","mix","pall","print","bluecc"};
List l1 = new ArrayList ();
perm (col, 0, 4, l1);
System.out.println ("-----------------");
print (l1);
List l2 = new ArrayList ();
perm (cou, 0, 4, l2);
List l3 = new ArrayList ();
perm (drink, 0, 4, l3);
List l4 = new ArrayList ();
perm (anmial, 0, 4, l4);
List l5 = new ArrayList ();
perm (cit, 0, 4, l5);
// System.out.println ("l1.size="+l1.size ());
// System.out.println ("l2.size="+l2.size ());
// System.out.println ("l3.size="+l3.size ());
// System.out.println ("l4.size="+l4.size ());
// System.out.println ("l5.size="+l5.size ());
subList1 (l1) ;
subList2 (l2);
subList3 (l1);
// System.out.println ("l1.size="+l1.size ());
// System.out.println ("l2.size="+l2.size ());
// System.out.println ("l3.size="+l3.size ());
// System.out.println ("l4.size="+l4.size ());
// System.out.println ("l5.size="+l5.size ());
System.out.println ("Max compare hits : " +
l1.size () * l2.size () * l3.size () * l4.size () * l5.size ());
System.out.println ("Min compare hits : " + " 1 ");
print (l1);
print (l2);
compare (l1, l2, l3, l4, l5);
System.out.println ("In fact hits : " + count);
long et = System.currentTimeMillis ();
System.out.println ("End time : " + et);
System.out.println ("Elapsed time : " + (et - bt) + " milli secondes!" );
System.out.println ("Elapsed time : " + (et - bt) / 1000.0 / 60 + " minutes!");
}
static void subList3 (List l1) throws ArrayIndexNotFoundException {
//挪威人住在蓝房子旁边
String [] a1 = null;
for (int i = l1.size() - 1;i >= 0;i --) {
a1 = (String []) l1.get (i);
if (getIndex (a1, "blue") != 1) {
l1.remove (i);
}
}
}
static void subList2 (List l2) throws ArrayIndexNotFoundException {
//挪威人住在第一间房子
String [] a2 = null;
for (int i = l2.size() - 1;i >= 0;i --) {
a2 = (String []) l2.get (i);
if (getIndex (a2, "nuowei") != 0) {
l2.remove (i);
}
}
}
static void subList1 (List l1) throws ArrayIndexNotFoundException {
//绿房子在白房子左边
String [] a1 = null;
for (int i = l1.size() - 1;i >= 0;i --) {
a1 = (String []) l1.get (i);
if (getIndex (a1, "green") != (getIndex (a1, "white") - 1)) {
l1.remove (i);
}
}
}
static void compare (List l1, List l2, List l3, List l4, List l5) throws ArrayIndexNotFoundException{
String [] a1 = null;
String [] a2 = null;
String [] a3 = null;
String [] a4 = null;
String [] a5 = null;
boolean found = false;
outer:
for (int i = 0;i < l1.size ();i ++) {
a1 = (String []) l1.get (i);
for (int j = 0;j < l2.size ();j ++) {
a2 = (String []) l2.get (j);
//1英国人住在红房子里
if (getIndex (a1, "red") == getIndex (a2, "bri")) {
for (int k = 0;k < l3.size ();k ++) {
a3 = (String []) l3.get (k);
//8住在中间那间房子的人喝牛奶
if (getIndex (a3, "milk") == 2) {
//5绿房子主人喝咖啡
if (getIndex (a1, "green") == getIndex (a3, "coffee")) {
//3丹麦人喝茶
if (getIndex (a2, "dan") == getIndex (a3, "tea")) {
for (int l = 0;l < l4.size ();l ++) {
a4 = (String []) l4.get (l);
for (int m = 0;m < l5.size ();m ++) {
a5 = (String []) l5.get (m);
if (condition (a1, a2, a3, a4, a5)) {
found = true;
break outer;
}
}
}
}
}
}
}
}
}
}
if (found) {
for (int i = 0;i < 5;i ++) {
System.out.print (fillSpace (a1 [i]));
System.out.print (" | ");
System.out.print (fillSpace (a2 [i]));
System.out.print (" | ");
System.out.print (fillSpace (a3 [i]));
System.out.print (" | ");
System.out.print (fillSpace (a4 [i]));
System.out.print (" | ");
System.out.print (fillSpace (a5 [i]));
System.out.println ("");
}
}
}
public static String fillSpace (String s) {
while (s.length () < 10) s += " ";
return s;
}
static int getIndex (String [] a, String s)
throws ArrayIndexNotFoundException {
for (int i = 0;i < a.length;i ++) {
if (a [i].equals (s)) {
return i;
}
}
throw new ArrayIndexNotFoundException (s + " is not found!");
}
static boolean condition (String [] a1,
String [] a2,
String [] a3,
String [] a4,
String [] a5 ) {
boolean ret = false;
count ++;
if (count % 1000000 == 0) {
System.out.println ("current count : " + count);
}
try {
// //1英国人住在红房子里
// if (getIndex (a1, "red") != getIndex (a2, "bri"))
// return ret;
//2瑞典人养了一条狗
if (getIndex (a2, "rui") != getIndex (a4, "dog"))
return ret;
// //3丹麦人喝茶
// if (getIndex (a2, "dan") != getIndex (a3, "tea"))
// return ret;
// //4绿房子在白房子左边
// if (getIndex (a1, "green") != (getIndex (a1, "white") - 1))
// return ret;
// //5绿房子主人喝咖啡
// if (getIndex (a1, "green") != getIndex (a3, "coffee"))
// return ret;
//6抽 PALL MALL 烟的人养了一只鸟
if (getIndex (a5, "pall") != getIndex (a4, "bird"))
return ret;
//7黄房子主人抽 DUNHILL 烟
if (getIndex (a1, "yellow") != getIndex (a5, "dun"))
return ret;
// //8住在中间那间房子的人喝牛奶
// if (getIndex (a3, "milk") != 2)
// return ret;
// //9挪威人住在第一间房子
// if (getIndex (a2, "nuowei") != 0)
// return ret;
//10抽混合烟的人住在养猫人的旁边
if ((getIndex (a5, "mix") != (getIndex (a4, "cat") + 1))
&& (getIndex (a5, "mix") != (getIndex (a4, "cat") - 1)))
return ret;
//11养马人住在抽 DUNHILL 烟的人旁边
if ((getIndex (a4, "horse") != (getIndex (a5, "dun") + 1))
&& (getIndex (a4, "horse") != (getIndex (a5, "dun") - 1)))
return ret;
//12抽 BLUE MASTER 烟的人喝啤酒
if (getIndex (a5, "bluecc") != getIndex (a3, "beer"))
return ret;
//13德国人抽 PRINCE 烟
if (getIndex (a2, "gre") != getIndex (a5, "print"))
return ret;
// //14挪威人住在蓝房子旁边
// if ((getIndex (a2, "nuowei") != (getIndex (a1, "blue") - 1))
// && (getIndex (a2, "nuowei") != (getIndex (a1, "blue") + 1)))
// return ret;
//15抽混合烟的人的邻居喝矿泉水
if ((getIndex (a5, "mix") != (getIndex (a3, "water") - 1))
&& (getIndex (a5, "mix") != (getIndex (a3, "water") + 1)))
return ret;
} catch (ArrayIndexNotFoundException e) {
e.printStackTrace ();
return ret;
}
System.out.println ("-----------------------");
ret = true;
return ret;
}
static void print (List l) {
if (! DEBUG) {
return;
}
System.out.println (l.size ());
for (int i = 0 ;i < l.size ();i ++) {
System.out.println (Arrays.asList ((String [])l.get (i)));
}
}
static void perm (String [] c, int k, int m, List l) {
//生成list[k:m]的所有排列方式
if (k == m) { //输出一个排列方式
// System.out.println ("---");
// System.out.println (Arrays.asList (c));
String [] c2 = new String [5];
System.arraycopy (c, 0, c2, 0, 5);
l.add (c2);
}
else {
for (int i = k;i <=m;i ++) {
c = swap (c, k, i);
perm (c, k + 1, m, l);
c = swap (c, k, i);
}
}
}
static String [] swap (String [] c, int i, int j) {
String temp = c [i];
c [i] = c[j];
c [j] = temp;
return c;
}}
class ArrayIndexNotFoundException extends Exception {
public ArrayIndexNotFoundException () {
super ();
}
public ArrayIndexNotFoundException(String s) {
super (s);
}
}