JWorld@TW the best professional Java site in Taiwan
      註冊 | 登入 | 全文檢索 | 排行榜  

» JWorld@TW » Java 程式分享區 » 數獨、猜數字  

按列印兼容模式列印這個話題 列印話題    把這個話題寄給朋友 寄給朋友    訂閱主題
reply to postflat modego to previous topicgo to next topic
本主題所含的標籤
無標籤
作者 [猜數字系列]深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) [精華]
T55555

Java, Ruby, Haskell

版主

發文: 1026
積分: 24
於 2004-02-29 09:49 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
Information about 深綠
http://www.javaworld.com.tw/jute/post/view?bid=35&id=35423&sty=1&tpg=1&age=0

本人在咖啡杯泡了一陣子,因看不慣DeepGreen打遍天下無敵手,決定研發深咖啡. Big Smile

目前DeepCafe 0.1號 CPU 研發成功,馬上挑戰 DeepGreen.
事實證明 DeepCafe 0.1 小勝 DeepGreen !!

目前, DeepCafe 0.1 加了一條規則, 也因為這條規則, 小勝了DeepGreen.

規則:
如果一開始 number of A + number of B == 3 then guess any other 4 numbers no used,
this is try to quickly find the digit missing.

Ex.: "0123" ==> 3A0B
DeepGreen will try to guess
0124, 0125, ..., 0129,
0143, 0153, ..., 0193,
... etc
In worst case, this will eliminate the rest (4 ~ 9) digit by digit.

It is more efficient to do next guess "4567" to eliminate the (8, 9) or (4, 5, 6, 7).

如何證明 DeepCafe 0.1號 優於 DeepGreen 呢?

It is easy, let the DeepGreen guess all possible numbers then take the average.
Which algorithm has better average number will win out.

Below is the code (modified) to test DeepGreen:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
public class TestDeepGreen {
  
  String answerSet[] = new String[10*9*8*7];
  boolean validSet[] = new boolean[10*9*8*7];
  
  void generateAnswerSet() {
    int i = 0;
    for (int a = 0; a < 10; a++) {
      for (int b = 0; b < 10; b++) {
        if (b == a) { continue; }
        for (int c = 0; c < 10; c++) {
          if (c == a || c == b) { continue; }
          for (int d = 0; d < 10; d++) {
            if (d == a || d == b || d == c) { continue; }
            answerSet[i++] = "" + a + b + c + d;
          }
        }
      }
    }
  }
  
  void initValidSet() {
    for (int i = 0; i < validSet.length; i++) {
      validSet[ i ] = true;
    }
  }
  
  int getA(String s1, String s2) {
    int a = 0;
    for (int i = 0; i < 4; i++) {
      if (s1.charAt( i ) == s2.charAt( i )) { a++; }
    }
    return a;
  }
  
  int getB(String s1, String s2) {
    int b = 0;
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
        if (i==j) { continue; }
        if (s1.charAt( i ) == s2.charAt(j)) { b++; }
      }
    }
    return b;
  }
  
  void reduce(String s, int a, int b) {
    for (int i = 0; i < validSet.length; i++) {
      if (!validSet[ i ]) { continue; }
      if ((getA(s, answerSet[ i ]) != a) || (getB(s, answerSet[ i ]) != b)) {
        validSet[ i ] = false;
      }
    }
  }
  
  int guess(String solution) {
    int count = 0;
    for (int i = 0; i < validSet.length; i++) {
      if (!validSet[ i ]) { continue; }
      count++;
      int a = getA(solution, answerSet[ i ]);
      if (a == 4) { break; }
      int b = getB(solution, answerSet[ i ]);
      reduce(answerSet[ i ], a, b);
    }
    return count;
  }
  
  public static void main(String[] args) {
    TestDeepGreen t = new TestDeepGreen();
    t.generateAnswerSet();
  
    int[] guessNb = new int[15];
    for (int i = 0; i < guessNb.length; i++) { guessNb[ i ] = 0; }
  
    for (int i = 0; i < t.answerSet.length; i++) {
      t.initValidSet();
      int guessTimes = t.guess(t.answerSet[ i ]);
      guessNb[guessTimes]++;
    }
    for (int i = 0; i < guessNb.length; i++) {
      System.out.println( i + " => " + guessNb[ i ]);
    }
  
    int sum = 0;
    for (int i = 0; i < guessNb.length; i++) {
      sum += i * guessNb[ i ];
    }
  
    System.out.println(" Average : " +
        sum + " / " + t.answerSet.length + " = " +
        ((double)sum / t.answerSet.length));
  }
}

Compiler and Run, here is the result:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0 => 0
1 => 1
2 => 13
3 => 108
4 => 596
5 => 1668
6 => 1768
7 => 752
8 => 129
9 => 5
10 => 0
11 => 0
12 => 0
13 => 0
14 => 0
 Average : 28024 / 5040 = 5.56031746031746


Which means: 108 numbers, DeepGreen guesses only on 3 times to get it right.
596 numbers, DeepGreen guesses on 4 times to get it right.
... etc

(5040 == total possible numbers; 28024 == 1*1 + 2*13 + 3*108 + ... + 9*5)

Which means DeepGreen by average will guesses your number correctly on 5.560317 times.


BTW:
"5293" "9204" "9214" "9241" "9431" 是DeepGreen 的五大死穴!
要九次才猜中!


Now, let's see the DeepCafe test code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
public class TestDeepCafe {
  
    String answerSet[] = new String[10*9*8*7];
    boolean validSet[] = new boolean[10*9*8*7];
  
    void generateAnswerSet() {
        int i = 0;
        for (int a = 0; a < 10; a++) {
            for (int b = 0; b < 10; b++) {
                if (b == a) { continue; }
                for (int c = 0; c < 10; c++) {
                    if (c == a || c == b) { continue; }
                    for (int d = 0; d < 10; d++) {
                        if (d == a || d == b || d == c) { continue; }
                        answerSet[i++] = "" + a + b + c + d;
                    }
                }
            }
        }
    }
  
    void initValidSet() {
        for (int i = 0; i < validSet.length; i++) {
            validSet[ i ] = true;
        }
    }
  
    int getA(String s1, String s2) {
        int a = 0;
        for (int i = 0; i < 4; i++) {
            if (s1.charAt( i ) == s2.charAt( i )) { a++; }
        }
        return a;
    }
  
    int getB(String s1, String s2) {
        int b = 0;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (i==j) { continue; }
                if (s1.charAt( i ) == s2.charAt(j)) { b++; }
            }
        }
        return b;
    }
  
    void reduce(String s, int a, int b) {
        for (int i = 0; i < validSet.length; i++) {
            if (!validSet[ i ]) { continue; }
            if ((getA(s, answerSet[ i ]) != a) || (getB(s, answerSet[ i ]) != b)) {
                validSet[ i ] = false;
            }
        }
    }
  
    int guess(String solution) {
        int count = 1;
  
        int a1 = getA(solution, answerSet[ 0 ]);
        if (a1 == 4) { return count; }
        int b1 = getB(solution, answerSet[ 0 ]);
        reduce(answerSet[ 0 ], a1, b1);
  
        // rule #1 :
        if (a1+b1 == 3) {
            count++;
            int a2 = getA(solution, "4567"); // pick any 4 digit not in answerSet[ 0 ]
            if (a2 == 4) { return count; }
            int b2 = getB(solution, "4567");
            reduce("4567", a2, b2);
        }
          
        for (int i = 1; i < validSet.length; i++) { // we start from 1 instead of 0 because we already check the answerSet[ 0 ]
            if (!validSet[ i ]) { continue; }
            count++;
            int a = getA(solution, answerSet[ i ]);
            if (a == 4) { break; }
            int b = getB(solution, answerSet[ i ]);
            reduce(answerSet[ i ], a, b);
        }
        return count;
    }
  
    public static void main(String[] args) {        
        TestDeepCafe t = new TestDeepCafe();
        t.generateAnswerSet();
  
        int[] nb = new int[15];
        for (int i = 0; i < nb.length; i++) { nb[ i ] = 0; }        
  
        for (int i = 0; i < t.answerSet.length; i++) {
             t.initValidSet();
             int guessNumber = t.guess(t.answerSet[ i ]);
             nb[guessNumber]++;
        }          
        for (int i = 0; i < nb.length; i++) { 
            System.out.println( i + " => " + nb[ i ]);
        }
  
        int sum = 0;
        for (int i = 0; i < nb.length; i++) { 
            sum += i * nb[ i ];
        }
        System.out.println(" Average : " + 
                           sum + " / " + t.answerSet.length + " = " + 
                           ((double)sum / t.answerSet.length));
    }
  
}

Compiler and Run, here is the result:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0 => 0
1 => 1
2 => 9
3 => 89
4 => 556
5 => 1746
6 => 1839
7 => 692
8 => 103
9 => 5
10 => 0
11 => 0
12 => 0
13 => 0
14 => 0
 Average : 27987 / 5040 = 5.5529761904761905


As you can see, the average to guess your number correctly, DeepCafe need 5.552976 times

==> DeepCafe win out!!


Note About Program:
(1) 目前偏重 CPU AI 部份, 暫時不做 Performance turning.
If you allow user to continue play the game...
DeepGreen will create more than 5040 String objects each time (and Garbage Collection)
This is why the Test code reuse directly 5040 string objects (instead of create them on each game)
The better way is hard coded, create a big String object contents "5040*4 bytes", and using offset to simulate the answerSet. This will save memory and construct objects time.
And it maybe can usnig swap table element, instead of always perform the loop from beginning of the table for checking... etc

(2) 目前是Algorithm 較量, 不加運氣成份.
In final product, it may use Random function, but add Random in test code will just make the test complexe and incorrect.

(3) 人機界面就留給新手練習吧.

歡迎 深紫, 深紅 等等雜七雜八挑戰霸主地位. Big Smile (Be Careful, DeepCafe 0.2 may coming out soon...)


caterpillar edited on 2005-12-26 00:36
reply to postreply to post
話題樹型展開
人氣 標題 作者 字數 發文時間
27478 [精華] [猜數字系列]深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 8882 2004-02-29 09:49
23983 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 257 2004-02-29 11:58
23932 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 405 2004-02-29 12:14
23920 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 406 2004-02-29 12:23
23944 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 367 2004-02-29 12:31
23928 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 623 2004-02-29 14:33
23845 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 292 2004-02-29 12:48
23845 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) jini 19 2004-02-29 12:53
23845 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1153 2004-02-29 12:57
23782 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 1143 2004-02-29 13:36
23817 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) Yoshi 374 2004-02-29 14:05
23487 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) JiaYun 233 2004-03-01 21:19
23415 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) Duncan 745 2004-03-01 23:09
23590 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1384 2004-03-02 00:42
23189 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 874 2004-03-02 01:18
23419 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) JiaYun 692 2004-03-02 01:33
23371 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 155 2004-03-02 01:43
23284 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 834 2004-03-02 02:09
23294 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1966 2004-03-02 02:50
23249 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 2225 2004-03-02 03:03
23120 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 781 2004-03-02 03:14
24603 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 773 2004-03-02 03:19
23264 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 314 2004-03-02 01:55
23302 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) JiaYun 112 2004-03-02 01:58
23362 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) koji 130 2004-03-02 02:02
23833 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) Yoshi 227 2004-02-29 13:33
23727 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 870 2004-02-29 22:43
23746 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) Yoshi 348 2004-02-29 23:39
23711 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 1267 2004-03-01 01:26
23715 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) TAHO 347 2004-03-01 01:59
23612 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) Yoshi 477 2004-03-01 02:12
23565 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 568 2004-03-01 02:13
23549 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) TAHO 858 2004-03-01 02:46
23796 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 998 2004-03-01 04:07
23730 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1042 2004-03-01 04:23
23639 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 0 2004-03-01 04:28
23630 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 402 2004-03-01 05:14
23588 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 447 2004-03-01 05:41
23662 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 292 2004-03-01 05:08
23596 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 399 2004-03-01 05:50
23655 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 180 2004-03-01 05:57
23584 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 294 2004-03-01 09:15
23494 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1446 2004-03-01 06:27
23465 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 1295 2004-03-01 07:25
23532 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1234 2004-03-01 09:12
23517 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 1631 2004-03-01 10:02
23495 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 146 2004-03-01 16:36
23682 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 595 2004-03-01 03:39
23816 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 718 2004-03-01 03:34
23565 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 252 2004-03-01 04:20
23564 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 6047 2004-03-01 05:01
23461 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) TAHO 297 2004-03-01 12:34
23430 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 637 2004-03-01 16:40
23464 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 137 2004-03-01 16:45
23363 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 236 2004-03-01 17:31
23386 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 756 2004-03-01 17:04
23387 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 971 2004-03-01 18:35
23500 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) ramb 753 2004-03-01 18:01
23254 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) T55555 1046 2004-03-02 01:11
23341 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) TAHO 716 2004-03-01 18:23
23431 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) worookie 847 2004-03-01 18:44
23448 Re:深咖啡 0.1 挑戰 深綠 (DeepCafe 0.1 vs DeepGreen) TAHO 12 2004-03-01 18:48
» JWorld@TW »  Java 程式分享區 » 數獨、猜數字

reply to postflat modego to previous topicgo to next topic
  已讀文章
  新的文章
  被刪除的文章
Jump to the top of page

JWorld@TW 本站商標資訊

Powered by Powerful JuteForum® Version Jute 1.5.8