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

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

按列印兼容模式列印這個話題 列印話題    把這個話題寄給朋友 寄給朋友    訂閱主題
reply to postflat modego to previous topicgo to next topic
本主題所含的標籤
無標籤
作者 [猜數字系列]深咖啡 0.2 研發成功 !!
T55555

Java, Ruby, Haskell

版主

發文: 1026
積分: 24
於 2004-03-02 00:24 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
在看 深咖啡 0.2 之前, 您首先必須完全 了解深咖啡 0.1
More information about DeepCafe 0.1 can find it on:
http://www.javaworld.com.tw/jute/post/view?bid=35&id=35572&sty=1&tpg=1&age=0

(Note: below DeepGreen means: the "initial" (first version) of DeepGreen)

worookie 指出 DeepCafe is not always win DeepGreen exactly 37 times.
At beginning, I think that it should be always 37, but I am wrong.
This make me think about the second set number.
You could choice better second set number to make it even better!

As on version 0.1, we know that the answerSet is in ascending order.
like "0123", "0124" ..."0129", "0132", "0134" ... "9867"

In case first guess #A+#B == 3, DeepCafe try to use "special second set" number ( at version 0.1 this special number could any 4 digit not in the first guess number ).

Since we know DeepCafe will fallow DeepGreen in its ascending answerSet order guessing. It make sence if we choice the second set close to the "end" of answerSet ascending order, and make this second set in reverse order.

Like, for example: the first guess number is "0123"
instead of choic "4567", I think (*probability*) it may be good to pick the "6789" ( the close end ).
For even close to the end it maybe good to pick the *last* four digits in reverse order, which means "9876" !!

If we pick the right second special guessing number, we imporve the DeepCafe 0.1

That's what happend for the DeepCafe 0.2 ==> It try to win not only 37 times. This time, it try to win 50 times.

To prove my concept is right, I quickly develop the test code.

It tests all second special possible number to prove my concept :
"Take the 4 digit not in first guess AND closest to the *end* of answerSet's for better second special guessing number"


(Again, You must first understand the DeepCafe 0.1 before see this 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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
 
// Warning: this program, depend on your machine, may take 5 to 10 minutes to execute ...
 
public class DeepCafeResearch {
 
    String answerSet[] = new String[10*9*8*7];
    boolean validSet[] = new boolean[10*9*8*7];
    String specialGuessNumberSet[] = new String[6*5*4*3];
    String specialGuessNumber;
 
    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;
        }
    }
 
    void initSpecialGuessNumberSet() {
        // Since we fix the answerSet[0] = "0123"
        // Here we try to find out all combination possible for 4 digit of "456789"
        int i = 0;
        for (int a = 4; a < 10; a++) {
            for (int b = 4; b < 10; b++) {
                if (b == a) { continue; }
                for (int c = 4; c < 10; c++) {
                    if (c == a || c == b) { continue; }
                    for (int d = 4; d < 10; d++) {
                        if (d == a || d == b || d == c) { continue; }
                        specialGuessNumberSet[i++] = "" + a + b + c + d;
                    }
                }
            }
        }
    }
 
    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;
            }
        }
    }
 
    // guess the <code> solution </code> and return number of time to get it right.
    int deepCafeGuess(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);
 
        count++;
        int a2 = getA(solution, specialGuessNumber);
        if (a2 == 4) { return count; }
        int b2 = getB(solution, specialGuessNumber);
        reduce(specialGuessNumber , a2, b2);
 
        for (int i = 1; i < validSet.length; i++) { // i start form 1 instead of 0, because we already guess 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) {
 
        DeepCafeResearch t = new DeepCafeResearch();
        t.generateAnswerSet();
        t.initSpecialGuessNumberSet();
        Hash hash = new Hash();
 
        for (int specialNbIndex = 0; specialNbIndex < t.specialGuessNumberSet.length; specialNbIndex++) {
            t.specialGuessNumber = t.specialGuessNumberSet[ specialNbIndex ];
            int totalGuess = 0;
            for (int i = 0; i < t.answerSet.length; i++) {
                t.initValidSet();
                int a = t.getA(t.answerSet[ i ], t.answerSet[ 0 ]);
                int b = t.getB(t.answerSet[ i ], t.answerSet[ 0 ]);
                if (a + b != 3) { continue; } // we only interest the value which first guess the #A+#B == 3
                totalGuess += t.deepCafeGuess(t.answerSet[ i ]);
            }
 
            // if (totalGuess == 3023) { System.out.println(t.specialGuessNumber); }
            hash.addOneMoreTimeFor(totalGuess);
        }
        hash.dump();
    }
 
}
 
/** Hash: Help class, try to count the totGuessCount appear how many times in total of 6*5*4*3 possible combination tests*/
class Hash {
 
    // we know the total number, for the first guess #A+#B==3, equals 576.
    // let's fixed the table size == 50, and growing later if we got out index exception.
    int TABLE_SIZE = 50;
 
    /** this groups the possible total guess count, like: 3036 times, 3038 times, ... etc */
    int[] totGuessCount = new int[TABLE_SIZE];
 
    /** this, with respect index order to the totGuessCount, represents that totGuessCount happend how many times. */
    int[] totTimes = new int[TABLE_SIZE];
 
    int tableSize = 0;
 
    public void addOneMoreTimeFor(int guessCount) {
 
        // first test the guessCount exist in the totGuessCount table or not,
        // if exist, then increment the totTimes correspond to guessCount by 1
        // if not, then add guessCount in totGuessCount table.
        for (int i = 0; i < tableSize; i++) {
            if (totGuessCount[ i ] == guessCount ) {
                totTimes[ i ]++;
                return;
            }
        }
 
        // exit the for, and no return yet, which means guessCount not exist in the totGuessCount ==> add it.
        if (tableSize >= TABLE_SIZE) {
            System.out.println("Need more room for table, grow it and test again...");
            System.exit(1);
        }
 
        totGuessCount[tableSize] = guessCount;
        totTimes[tableSize] = 1;
        tableSize++;
    }
 
    public void dump() {
        for (int i = 0; i < tableSize; i++) {
            System.out.println(totGuessCount[i] + " ==> " + totTimes[i]);
        }
    }
}
 
/*
By using this test program, you could find:
 
3036 ==> 60
3038 ==> 15
3034 ==> 60
3037 ==> 45
3030 ==> 15
3029 ==> 75
3031 ==> 15
3028 ==> 30
3026 ==> 15
3025 ==> 15
3023 ==> 15
 
60 + 15 + 60 + 45 + 15 + 75 + 15 + 30 + 15 + 15 + 15 == 360 ( == 6 * 5 * 4 * 3 )
 
possible count number: (3023, 3025, 3026, 3028, 3029, 3030, 3031, 3034, 3036, 3037, 3038)
The "inital" deepGreen will always take 3073 times
possible win times: (50, 48, 47, 45, 44, 43, 42, 39, 37, 36, 35)
==> minimum win times == 3073 - 3038 = 35 times
==> maximun win times == 3073 - 3023 = 50 times
 
the special second guess number for total guess == 3023 :
7654
8654
8754
8764
8765
9654
9754
9764
9765
9854
9864
9865
9874
9875
9876 <== my concept is good !! ( Why the other 14 are good too ?? and it seems these numbers are close to the *end* of answerSet )
*/


caterpillar edited on 2005-12-26 00:36
reply to postreply to post
話題樹型展開
人氣 標題 作者 字數 發文時間
9227 [猜數字系列]深咖啡 0.2 研發成功 !! T55555 8965 2004-03-02 00:24
7714 Re:深咖啡 0.2 研發成功 !! sungo 26 2004-03-02 03:04
7694 Re:深咖啡 0.2 研發成功 !! T55555 17 2004-03-02 03:21
8087 Re:深咖啡 0.2 研發成功 !! sungo 65 2004-03-02 03:27
» 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