[算法讨论]猜数字游戏 - Bulls and Cows

rubyish

v8:

1. 1       1
   
2. 2       13
   
3. 3       108
   
4. 4       639
   
5. 5       2083
   
6. 6       1900
   
7. 7       293
   
8. 8       3
   
9. ----------------
   
10. COUNT = 26797
    
11. TEST  = 5040
    
12. AVE   = 5.316865
    
13. 
    
14. real    0m6.763s

复制代码

naive: 4.43s

1. 1       1
   
2. 2       13
   
3. 3       108
   
4. 4       596
   
5. 5       1668
   
6. 6       1768
   
7. 7       752
   
8. 8       129
   
9. 9       5
   
10. ----------------
    
11. COUNT = 28024
    
12. TEST  = 5040
    
13. AVE   = 5.560317
    
14. 
    
15. real    0m4.437s

复制代码

code:

1. // gcc -Wall -march=native -Ofast -o bull bull.c
   
2. 
   
3. # include <stdio.h>
   
4. # include <string.h>
   
5. # include <math.h>
   
6. 
   
7. # define OK   0x40
   
8. # define get_a(A)   A >> 4
   
9. # define get_b(A)   0xF & A
   
10. # define copy(A, B) memcpy (A, B, 4)
    
11. # define move1(A)   ((1 << A[0]) | (1 << A[1]) | (1 << A[2]) | (1 << A[3]))
    
12. # define toInt(N)   1000 * N[0] + 100 * N[1] + 10 * N[2] + N[3];
    
13. # define INIT(A)    for (int i = 0; i < 5040; i++) A[i] = i;
    
14. # define AB(A, B)   XAYB[A][B]
    
15. # define TEST 5040
    
16. 
    
17. typedef char kar;
    
18. typedef double dub;
    
19. typedef void voi;
    
20. 
    
21. kar XAYB[5040][5040];
    
22. int A_and_B[961];       // LOOK: sub genB
    
23. kar SPLIT[5040][4];       // SPLIT[0] = [ 0, 1, 2, 3 ]
    
24. int TOTO[5040];
    
25. int MAYBE[5040];        // [ 0 .. 5039 ]
    
26. int INDES[65];          // 4A: 0x40 == 64
    
27. int COUNT[16];          //
    
28. dub INFO[1000];
    
29. int LEN_MAYBE;          // @MAYBE
    
30. 
    
31. voi init (voi);
    
32. voi test (voi);
    
33. voi genTOTO (int);
    
34. voi genIndes (voi);
    
35. voi genB (voi);
    
36. voi genAB (voi);
    
37. voi rehashMaybe (int, int);
    
38. int gimme (int);
    
39. 
    
40. /* ____________________ MAIN ____________________ */
    
41. int main (){
    
42.     init ();
    
43.     test ();
    
44. }
    
45. 
    
46. /* _____________________ SUB _____________________ */
    
47. 
    
48. voi test () {
    
49.     fprintf (stderr, "\rtest ");
    
50.     for (int v = 0; v < TEST; v++) {
    
51.         if (!(v % 100)) fprintf (stderr, "%6d\b\b\b\b\b\b", v);
    
52.         // printf ("%d\n", v + 1);
    
53.         INIT (MAYBE);
    
54.         int ans = v;
    
55.         int gue = 0;
    
56.         LEN_MAYBE = 5040;
    
57.         // printf ("_ [ %04d ]\n", TOTO[ans]);
    
58.         int x;
    
59.         for (x = 1; x < 10; x++) {
    
60.             int ab = AB (ans, gue);
    
61.             // int a  = get_a (ab);
    
62.             // int b  = get_b (ab);
    
63.             // printf ("%d [ %04d ] AB %d %d\n", x, TOTO[gue], a, b);
    
64.             if (ab == OK) break;
    
65.             rehashMaybe (gue, ab);
    
66.             gue = gimme (x);
    
67.             // gue = MAYBE[0]; /* NAIVE: FAST */
    
68. 
    
69.         }
    
70.         COUNT[x]++;
    
71.     }
    
72. 
    
73.     int ave = 0;
    
74.     int tot = 0;
    
75.     puts ("FINISH");
    
76.     for (int i = 1; i < 15; i++) {
    
77.         if (!COUNT[i]) continue;
    
78.         printf ("%d\t%d\n", i, COUNT[i]);
    
79.         ave += i * COUNT[i];
    
80.         tot += COUNT[i];
    
81.     }
    
82. 
    
83.     if (tot != TEST) puts ("ERROR");
    
84.     puts ("----------------");
    
85.     printf ("COUNT = %d\n", ave);
    
86.     printf ("TEST  = %d\n", TEST);
    
87.     printf ("AVE   = %f\n", ave / (dub)TEST);
    
88. } /* test */
    
89. 
    
90. voi init () {
    
91.     fprintf (stderr, "init..");
    
92.     genTOTO (0);
    
93.     genB ();
    
94.     genAB ();
    
95.     genIndes ();
    
96.     for (int i = 0; i < 1000; i++) INFO[i] = i * log (i);
    
97. }
    
98. 
    
99. voi genTOTO (int lev){
    
100.     static kar num[4];
     
101.     static int I = 0;
     
102.     static int has[10];
     
103. 
     
104.     if (lev == 4) {
     
105.         int n = toInt (num);
     
106.         TOTO[I] = n;
     
107.         copy (SPLIT[I], num);
     
108.         I++;
     
109.         return;
     
110.     }
     
111. 
     
112.     for (int i = 0; i <= 9; i++) {
     
113.         if (has[i]) continue;
     
114.         has[i]   = 1;
     
115.         num[lev] = i;
     
116.         genTOTO (lev + 1);
     
117.         has[i] = 0;
     
118.     }
     
119. } /* genTOTO */
     
120. 
     
121. voi genB (){
     
122. // 0b1111000000 => bit(1): 9876, val = 960
     
123. // 0123:  0b001111
     
124. // 0153:  0b101011
     
125. // A & B: 0b001011 = 0b1011(=11), count(1) = 3, $A[11] = 3
     
126.     for (int i = 0; i < 961; i++) {
     
127.         int count = 0;
     
128. 
     
129.         for (int j = 0; j < 10; j++) {
     
130.             if (i & (1 << j)) count++;
     
131.             if (count > 4) break;
     
132.         }
     
133.         A_and_B[i] = count > 4 ? 0 : count;
     
134.     }
     
135. }
     
136. 
     
137. voi genAB (){
     
138.     for (int i = 0; i < 5040; i++) {
     
139.         kar *cha = SPLIT[i];
     
140.         int C1   = move1 (cha);
     
141. 
     
142.         for (int j = 0; j < 5040; j++) {
     
143.             kar *cha2 = SPLIT[j];
     
144.             int C2    = move1 (cha2);
     
145.             int A     = 0;
     
146.             for (int k = 0; k < 4; k++)
     
147.                 if (cha[k] == cha2[k]) A++;
     
148.             int B = C1 & C2;
     
149.             B          = A_and_B[B] - A;
     
150.             XAYB[i][j] = (A << 4) | B;
     
151.         }
     
152.     }
     
153. }
     
154. 
     
155. inline
     
156. voi rehashMaybe (int gue, int ab){
     
157.     int I = 0;
     
158. 
     
159.     for (int i = 0; i < LEN_MAYBE; i++) {
     
160.         if (AB (MAYBE[i], gue) == ab)
     
161.             MAYBE[I++] = MAYBE[i];
     
162.     }
     
163.     LEN_MAYBE = I;
     
164. }
     
165. 
     
166. inline
     
167. int gimme (int lev){
     
168.     if (LEN_MAYBE == 1 || lev == 1) return MAYBE[0];
     
169.     int best = 0;
     
170.     dub max  = 999999.0; // BIG NUM
     
171. 
     
172.     for (int i = 0; i < LEN_MAYBE; i++) {
     
173.         int test[14] = { 0 };
     
174. 
     
175.         for (int j = 0; j < LEN_MAYBE; j++) {
     
176.             int ab  = AB (MAYBE[i], MAYBE[j]);
     
177.             int pos = INDES[ab];
     
178.             test[pos]++;
     
179.         }
     
180. 
     
181.         dub toto = 0.0;
     
182.         for (int i = 0; i < 14; i++)
     
183.             if (test[i]) toto += INFO[test[i]];
     
184.         if (max > toto) max = toto, best = i;
     
185.     }
     
186.     return MAYBE[best];
     
187. } /* gimme */
     
188. 
     
189. voi genIndes (){
     
190.     int var[] = { 0, 5, 9, 12, 13 };
     
191. 
     
192.     // 0x40 = 4A0B = 64
     
193.     // INDES[64] = var[4] + 0 = 13
     
194.     for (int a = 0; a <= 4; a++) {
     
195.         for (int b = 0; b <= 4; b++) {
     
196.             if (a + b > 4) continue;
     
197.             int ab = (a << 4) | b;
     
198.             int i  = var[a] + b;
     
199.             INDES[ab] = i;
     
200.             // if (a == 3) break;   /* NO 3A1B */
     
201.         }
     
202.     }
     
203. }
     

复制代码

523066680

我写的C的版本，用比较直白的方式写，没有采用优化方案（还是用脚本方便）

包括 5040 次 printf ，耗时差不多1.2秒。

1. times: 28024, average: 5.560317
   
2. Clock: 1185

复制代码

1. // 523066680 2017-08
   
2. 
   
3. #include <stdio.h>
   
4. #include <stdlib.h>
   
5. #include <string.h>
   
6. #include <time.h>
   
7. 
   
8. #define SIZE 10*9*8*7
   
9. #define print_num(s) printf("%c%c%c%c\n", s[0], s[1], s[2], s[3])
   
10. typedef struct { int a, b; } AB;
    
11. 
    
12. int odi = 0;
    
13. int idx;
    
14. char (order[SIZE])[4];
    
15. int oindex[SIZE];
    
16. int temparr[SIZE];
    
17. 
    
18. void permute(char *elements, char *getstr, int len, int lv);
    
19. void guess_s( char *target, char *guess, AB *res );
    
20. void reduce( int *oindex, char *guess, AB *res );
    
21. void printstate( char *guess, AB *res, int n );
    
22. 
    
23. int main(int argc, char *argv[])
    
24. {
    
25.     char elements[] = "0123456789";
    
26.     char getstr[10];
    
27.     AB res;
    
28.    
    
29.     odi = 0;
    
30.     //生成所有组合到 order 数组（全局）
    
31.     permute(elements, getstr, strlen(elements), 0);
    
32. 
    
33.     char nums[4];
    
34.     char guess[4];
    
35.     int times = 0;
    
36. 
    
37.     //遍历所有5040种情况
    
38.     for (int mi = 0; mi < SIZE; mi++)
    
39.     {
    
40.         //初始化、重置索引数组（所有操作都是间接通过索引处理）
    
41.         for (int i = 0; i < SIZE; i++) oindex[i] = i;
    
42. 
    
43.         //nums:目标数字，guess:猜测数字
    
44.         strncpy(nums, order[mi], 4);
    
45.         strncpy(guess, "0123", 4);
    
46.         idx = SIZE;
    
47. 
    
48.         print_num(nums);
    
49. 
    
50.         while ( idx > 0 )
    
51.         {
    
52.             guess_s( nums, guess, &res );
    
53.             //printstate(guess, &res, idx);
    
54. 
    
55.             //筛选出相同反馈的排列
    
56.             reduce( oindex, guess, &res );
    
57.             //从筛选的子集中选第一个
    
58.             strncpy( guess, order[ oindex[0] ], 4 );
    
59. 
    
60.             times++;
    
61.         }
    
62.     }
    
63. 
    
64.     printf("times: %d, average: %f\n", times, (float)times/5040.0);
    
65.     printf("Clock: %d\n", clock() );
    
66.     return 0;
    
67. }
    
68. 
    
69. void reduce( int *oindex, char *guess, AB *res )
    
70. {
    
71.     AB t;
    
72.     int ai = 0;
    
73. 
    
74.     for (int i = 0; i < idx; i++)
    
75.     {
    
76.         guess_s( guess, order[ oindex[i] ], &t );
    
77.         if ( (t.a == res->a) &&
    
78.              (t.b == res->b) &&
    
79.             (strncmp(guess, order[ oindex[i] ], 4) != 0 ) )  //不全等
    
80.         {
    
81.             temparr[ai] = oindex[i];
    
82.             ai++;
    
83.         }
    
84.     }
    
85. 
    
86.     idx = ai;
    
87.     for (int i = 0; i < idx; i++) oindex[i] = temparr[i];
    
88. }
    
89. 
    
90. void permute(char *elements, char *getstr, int len, int lv)
    
91. {
    
92.     char *tempele = (char *)malloc( len * sizeof(char) );
    
93. 
    
94.     for ( int i = 0; i < len; i++)
    
95.     {
    
96.         strcpy( tempele, elements );
    
97.         getstr[lv] = elements[i];
    
98. 
    
99.         for (int j = i; j < (len-1); j++)  //popup one char
    
100.             tempele[j] = elements[j+1];
     
101. 
     
102.         if ( lv < 4 )
     
103.             permute( tempele, getstr, len-1, lv+1 );
     
104.         else
     
105.         {
     
106.             strncpy( order[odi++], getstr, 4 );
     
107.             break;
     
108.         }
     
109.     }
     
110. }
     
111. 
     
112. void guess_s( char target[4], char guess[4], AB *res )
     
113. {
     
114.     char idx, in;
     
115.     res->a = 0;
     
116.     res->b = 0;
     
117. 
     
118.     for ( idx = 0; idx < 4; idx++ )
     
119.     {
     
120.         if ( target[idx] == guess[idx] )
     
121.             res->a++;
     
122.         else
     
123.             if ( strchr(target, guess[idx]) != 0 )
     
124.             {
     
125.                 res->b++;
     
126.             }
     
127.     }
     
128. }
     
129. 
     
130. void printstate( char *guess, AB *res, int n )
     
131. {   
     
132.     char s[5];
     
133.     strncpy(s, guess, 4 );
     
134.     s[4] = 0;
     
135.     printf("%s [%d%d] %d\n", s, res->a, res->b, n);
     
136. }
     

复制代码

rubyish

回复 22# 523066680

Run le jici, faxian AVE jingran hui biandong?
average:

1. 6.275794
   
2. 9.411508
   
3. 2.425794

复制代码

Xiugaile sub guess_s:

1. void guess_s (char target[4], char guess[4], AB *res){
   
2.     static char TAGRET0[5];  // END = 0, for strchr
   
3. 
   
4.     memcpy (TAGRET0, target, 4);
   
5.     res->a = 0;
   
6.     res->b = 0;
   
7. 
   
8.     for (int i = 0; i < 4; i++) {
   
9.         if (target[i] == guess[i]) res->a++;
   
10.         else if (strchr (TAGRET0, guess[i])) res->b++;
    
11.     }
    
12. }

复制代码

compile:
gcc -Wall -march=native -Ofast

time: 3.401s

1. times: 28024, average: 5.560317
   
2. Clock: 3398914
   
3. 
   
4. real    0m3.401s

复制代码

Meiyou OPT de code jingrang hai kuaile OPT 1 miao!!
Zhe rang wo qile yixin, OPT shifou yijing useless le?

rubyish

v9:
# add POWER

time: 0.7s

1. 1       1
   
2. 2       13
   
3. 3       108
   
4. 4       596
   
5. 5       1668
   
6. 6       1768
   
7. 7       752
   
8. 8       129
   
9. 9       5
   
10. ----------------
    
11. COUNT = 28024
    
12. TEST  = 5040
    
13. AVE   = 5.560317
    
14. 
    
15. real    0m0.736s

复制代码

1. 1       1
   
2. 2       13
   
3. 3       108
   
4. 4       639
   
5. 5       2083
   
6. 6       1900
   
7. 7       293
   
8. 8       3
   
9. ----------------
   
10. COUNT = 26797
    
11. TEST  = 5040
    
12. AVE   = 5.316865
    
13. 
    
14. real    0m4.433s

复制代码

bull.c

1. // gcc -Wall -march=native -Ofast -o bull bull.c -lm
   
2. 
   
3. # include <stdio.h>
   
4. # include <string.h>
   
5. # include <math.h>
   
6. 
   
7. # define OK 0x40
   
8. # define get_a(A)   A >> 4
   
9. # define get_b(A)   0xF & A
   
10. # define copy(A, B) memcpy (A, B, 4)
    
11. # define move1(A)   ((1 << A[0]) | (1 << A[1]) | (1 << A[2]) | (1 << A[3]))
    
12. # define INIT(A)    for (int i = 0; i < 5040; i++) A[i] = i;
    
13. # define AB(A, B)   (A < B ? XAYB[A][B] : XAYB[B][A])
    
14. # define DATA(a)    TOTO[a][0], TOTO[a][1], TOTO[a][2], TOTO[a][3]
    
15. 
    
16. # define TEST 5040
    
17. 
    
18. typedef char kar;
    
19. typedef double dub;
    
20. typedef void voi;
    
21. 
    
22. kar XAYB[5040][5040];
    
23. int A_and_B[961];       // LOOK: sub genB
    
24. kar TOTO[5040][4];       // TOTO[0] = [ 0, 1, 2, 3 ]
    
25. int MAYBE[5040];        // [ 0 .. 5039 ]
    
26. int INDES[65];          // 4A: 0x40 == 64
    
27. int COUNT[16];          //
    
28. dub INFO[1000];
    
29. int LEN_MAYBE;          // @MAYBE
    
30. 
    
31. voi init (voi);
    
32. voi test (voi);
    
33. voi genTOTO (int);
    
34. voi genIndes (voi);
    
35. voi genB (voi);
    
36. voi genAB (voi);
    
37. voi rehashMaybe (int, int);
    
38. int gimme (int);
    
39. 
    
40. /* ____________________ MAIN ____________________ */
    
41. int main (){
    
42.     init ();
    
43.     test ();
    
44. }
    
45. 
    
46. /* _____________________ SUB _____________________ */
    
47. 
    
48. voi test () {
    
49.     fprintf (stderr, "\rtest ");
    
50.     for (int v = 0; v < TEST; v++) {
    
51.         if (!(v % 100)) fprintf (stderr, "%6d\b\b\b\b\b\b", v);
    
52.         // printf ("%d\n", v + 1);
    
53.         INIT (MAYBE);
    
54.         int ans = v;
    
55.         int gue = 0;
    
56.         LEN_MAYBE = 5040;
    
57.         // printf ("_ [ %d%d%d%d ]\n", DATA (ans));
    
58.         int x;
    
59.         for (x = 1; x < 15; x++) {
    
60.             int ab = AB (ans, gue);
    
61.             // int a  = get_a (ab);
    
62.             // int b  = get_b (ab);
    
63.             // printf ("%d [ %d%d%d%d ] AB %d %d\n", x, DATA (gue), a, b);
    
64.             if (ab == OK) break;
    
65.             rehashMaybe (gue, ab);
    
66.             // gue = gimme (x);
    
67.             gue = MAYBE[0]; /* NAIVE: FAST */
    
68. 
    
69.         }
    
70.         COUNT[x]++;
    
71.     }
    
72. 
    
73.     int ave = 0;
    
74.     int tot = 0;
    
75.     puts ("FINISH");
    
76. 
    
77.     for (int i = 1; i < 15; i++) {
    
78.         if (!COUNT[i]) continue;
    
79.         printf ("%d\t%d\n", i, COUNT[i]);
    
80.         ave += i * COUNT[i];
    
81.         tot += COUNT[i];
    
82.     }
    
83. 
    
84.     if (tot != TEST) puts ("ERROR");
    
85.     puts ("----------------");
    
86.     printf ("COUNT = %d\n", ave);
    
87.     printf ("TEST  = %d\n", TEST);
    
88.     printf ("AVE   = %f\n", ave / (dub)TEST);
    
89. } /* test */
    
90. 
    
91. voi init () {
    
92.     fprintf (stderr, "init...");
    
93.     genTOTO (0);
    
94.     genB ();
    
95.     genAB ();
    
96.     genIndes ();
    
97.     for (int i = 0; i < 1000; i++) INFO[i] = i * log (i);
    
98. }
    
99. 
    
100. voi genTOTO (int lev){
     
101.     static kar num[4];
     
102.     static int I = 0;
     
103.     static int has[10];
     
104. 
     
105.     if (lev == 4) {
     
106.         copy (TOTO[I], num);
     
107.         I++;
     
108.         return;
     
109.     }
     
110. 
     
111.     for (int i = 0; i <= 9; i++) {
     
112.         if (has[i]) continue;
     
113.         has[i]   = 1;
     
114.         num[lev] = i;
     
115.         genTOTO (lev + 1);
     
116.         has[i] = 0;
     
117.     }
     
118. } /* genTOTO */
     
119. 
     
120. voi genB (){
     
121. // 0b1111000000 => bit(1): 9876, val = 960
     
122. // 0123:  0b001111
     
123. // 0153:  0b101011
     
124. // A & B: 0b001011 = 0b1011(=11), count(1) = 3, $A[11] = 3
     
125.     for (int i = 0; i < 961; i++) {
     
126.         int count = 0;
     
127. 
     
128.         for (int j = 0; j < 10; j++) {
     
129.             if (i & (1 << j)) count++;
     
130.             if (count > 4) break;
     
131.         }
     
132.         A_and_B[i] = count > 4 ? 0 : count;
     
133.     }
     
134. }
     
135. 
     
136. voi genAB (){
     
137.     for (int i = 0; i < 5040; i++) {
     
138.         kar *cha = TOTO[i];
     
139.         int C1   = move1 (cha);
     
140. 
     
141.         for (int j = i; j < 5040; j++) {
     
142.             kar *cha2 = TOTO[j];
     
143.             int C2    = move1 (cha2);
     
144.             int A     = 0;
     
145.             for (int k = 0; k < 4; k++)
     
146.                 if (cha[k] == cha2[k]) A++;
     
147.             int B = C1 & C2;
     
148.             B          = A_and_B[B] - A;
     
149.             XAYB[i][j] = (A << 4) | B;
     
150.         }
     
151.     }
     
152. }
     
153. 
     
154. inline
     
155. voi rehashMaybe (int gue, int ab){
     
156.     int I = 0;
     
157. 
     
158.     for (int i = 0; i < LEN_MAYBE; i++) {
     
159.         if (AB (MAYBE[i], gue) == ab)
     
160.             MAYBE[I++] = MAYBE[i];
     
161.     }
     
162.     LEN_MAYBE = I;
     
163. }
     
164. 
     
165. inline
     
166. int gimme (int lev){
     
167.     if (LEN_MAYBE == 1 || lev == 1) return MAYBE[0];
     
168.     int best = 0;
     
169.     dub min  = 999999.0; // BIG NUM
     
170. 
     
171.     for (int i = 0; i < LEN_MAYBE; i++) {
     
172.         int test[14] = { 0 };
     
173. 
     
174.         for (int j = 0; j < LEN_MAYBE; j++) {
     
175.             int ab  = AB (MAYBE[i], MAYBE[j]);
     
176.             int pos = INDES[ab];
     
177.             test[pos]++;
     
178.         }
     
179. 
     
180.         dub toto = 0.0;
     
181.         for (int i = 0; i < 14; i++)
     
182.             if (test[i]) toto += INFO[test[i]];
     
183.         if (min > toto) min = toto, best = i;
     
184.     }
     
185.     return MAYBE[best];
     
186. } /* gimme */
     
187. 
     
188. voi genIndes (){
     
189.     int var[] = { 0, 5, 9, 12, 13 };
     
190. 
     
191.     // 0x40 = 4A0B = 64
     
192.     // INDES[64] = var[4] + 0 = 13
     
193.     for (int a = 0; a <= 4; a++) {
     
194.         for (int b = 0; b <= 4; b++) {
     
195.             if (a + b > 4) continue;
     
196.             int ab = (a << 4) | b;
     
197.             int i  = var[a] + b;
     
198.             INDES[ab] = i;
     
199.             // if (a == 3) break;   /* NO 3A1B */
     
200.         }
     
201.     }
     
202. }
     

复制代码

523066680

回复 23# rubyish

关于未优化比优化快一秒的问题，采用估值算法的程序增加了运算量，所以消耗可能更多。
要提高效率只有先生成结构树。可惜用C语言实现比较麻烦，所以用了perl

试了一下 Perl 内联C，跑完 5040种情况，0.087 秒（不含 print 耗时）
不使用内联C代码：0.4秒 （不含 print 耗时）

523066680

回复 24# rubyish

链表的版本来了（我已经把C忘光了，折腾了一整天……
写的很凌乱，加载和导出没有做详细的错误判断处理。

机制：
如果没有结构文件，会执行 maketree() 建立链表树，然后dump到 F:/struct.dat
如果找到结构文件会直接加载。

效率（CPU: i7-4790K）：
print 不计入内，从文件加载，遍历所有情况，耗时 0.006秒
print 不计入内，重新建造树，遍历所有情况，耗时 0.050秒

1. // Game - Bulls and Cows
   
2. // Code By 523066680@163.com
   
3. // zhuanlan.zhihu.com/PerlExample
   
4. // 2017-09
   
5. 
   
6. #include <stdio.h>
   
7. #include <stdlib.h>
   
8. #include <string.h>
   
9. #include <time.h>
   
10. 
    
11. #define SIZE 10*9*8*7
    
12. #define print_num(s) printf("%c%c%c%c\n", s[0], s[1], s[2], s[3])
    
13. typedef struct { int a, b; } AB;
    
14. 
    
15. int odi = 0;
    
16. int idx;
    
17. char (order[SIZE])[4];
    
18. int oindex[SIZE];
    
19. int temparr[SIZE];
    
20. 
    
21. void permute(char *elements, char *getstr, int len, int lv);
    
22. void bullscows( char target[4], char guess[4], AB *res );
    
23. int reduce( int *oindex, char *guess, AB *res, int *subset, int osize );
    
24. void printstate( char *guess, AB *res, int n );
    
25. 
    
26. FILE* fp;
    
27. 
    
28. struct node
    
29. {
    
30.     char guess[5];
    
31.     struct node *res[13];
    
32.     int count;
    
33. };
    
34. 
    
35. int mapindex[4][5] = {
    
36.     {0,  1, 2, 3, 4,},
    
37.     {5,  6, 7, 8,-1,},
    
38.     {9, 10,11,-1,-1,},
    
39.     {12,-1,-1,-1,-1}
    
40. };
    
41. 
    
42. AB alltypes[13] =
    
43. {
    
44.     {0,0},{0,1},{0,2},{0,3},{0,4},
    
45.     {1,0},{1,1},{1,2},{1,3},
    
46.     {2,0},{2,1},{2,2},
    
47.     {3,0}
    
48. };
    
49. 
    
50. 
    
51. // ----------------  about Tree node ------------------ //
    
52. 
    
53. void node_value(struct node *pt, char *str)
    
54. {
    
55.     strncpy( pt->guess, str, 4 );
    
56.     pt->count = 0;
    
57. }
    
58. 
    
59. void node_alloc(struct node *pt)
    
60. {
    
61.     for (int i = 0; i < 13; i++)
    
62.     {
    
63.         pt->res[i] = (struct node *) malloc( sizeof( struct node ) );
    
64.         strcpy(pt->res[i]->guess, "\0\0\0\0");
    
65.         pt->res[i]->count = 0;
    
66.         for (int j = 0; j < 13; j++)
    
67.         {
    
68.             pt->res[i]->res[j] = NULL;
    
69.         }
    
70.     }
    
71. }
    
72. 
    
73. void load_tree( struct node *pt, FILE *fp, int lv )
    
74. {
    
75.     fread(pt, sizeof(struct node), 1, fp);
    
76. 
    
77.     if ( pt->count > 0 && (! feof(fp) ) )
    
78.     {
    
79.         node_alloc( pt );
    
80.         for (int i = 0; i < 13; i++)
    
81.         {
    
82.             load_tree( pt->res[i], fp, lv+1 );
    
83.         }
    
84.     }
    
85. }
    
86. 
    
87. void dump_tree( struct node *pt, FILE *fp, int lv )
    
88. {
    
89.     fwrite( pt, sizeof(struct node), 1, fp );
    
90. 
    
91.     if ( pt->count > 0 )
    
92.     {
    
93.         for (int i = 0; i < 13; i++)
    
94.         {
    
95.             dump_tree( pt->res[i], fp, lv+1 );
    
96.         }
    
97.     }
    
98. }
    
99. 
    
100. void node_print(struct node *pt, int lv)
     
101. {
     
102.     for (int i = 0; i < 13 ; i++)
     
103.     {
     
104.         printf("[%d%d] %s\n", alltypes[i].a,alltypes[i].b,
     
105.             pt->res[i]->guess);
     
106.     }
     
107. }
     
108. 
     
109. void tree_print(struct node *pt, int lv)
     
110. {
     
111.     if ( pt->guess[0] != '\0' )
     
112.     {
     
113.         for (int i = 0; i < lv; i++)
     
114.             printf("  ");
     
115.         printf("%s %d %d\n", pt->guess, pt->count, lv);
     
116.     }
     
117. 
     
118.     if ( pt->count > 0 )
     
119.     {
     
120.         for (int i = 0; i < 13 ; i++)
     
121.         {
     
122.             //printf("[%d%d]\n", alltypes[i].a, alltypes[i].b );
     
123.             tree_print( pt->res[i], lv+1 );   
     
124.         }
     
125.     }
     
126. }
     
127. 
     
128. void maketree( int *oindex, int osize, int lv, struct node *pt )
     
129. {
     
130.     char guess[5];
     
131. 
     
132.     int subset[SIZE];
     
133.     int nsize;    //new_size
     
134. 
     
135.     node_alloc(pt);
     
136.     strncpy(guess, order[oindex[0]], 4);
     
137. 
     
138.     for (int ti = 0; ti < 13; ti++)
     
139.     {
     
140.         //筛选出相同反馈的排列
     
141.         memset(subset, 0, SIZE);
     
142.         nsize = reduce( oindex, guess, &alltypes[ti], subset, osize );
     
143. 
     
144.         if (nsize > 0)
     
145.         {
     
146.             node_value( pt->res[ti], order[subset[0]] ) ;
     
147.             maketree( subset, nsize, lv+1, pt->res[ti] );
     
148.             pt->count++;
     
149.         }
     
150.     }
     
151. }
     
152. 
     
153. // ----------------  end Tree node ------------------ //
     
154. 
     
155. int main(int argc, char *argv[] )
     
156. {
     
157.     char elements[] = "0123456789";
     
158.     char getstr[10]; //临时缓冲区
     
159.     //生成所有组合到 order 数组（全局）
     
160.     permute(elements, getstr, strlen(elements), 0);
     
161. 
     
162.     //初始化、重置索引数组（筛选函数间接通过索引处理）
     
163.     for (int i = 0; i < SIZE; i++) oindex[i] = i;
     
164. 
     
165.     struct node tree;
     
166.     FILE *fp;
     
167.     fp = fopen("F:/sturct.dat", "rb");
     
168.         if (fp)
     
169.         {
     
170.             load_tree( &tree, fp, 0 );
     
171.         }
     
172.         else
     
173.         {
     
174.             fp = fopen("F:/sturct.dat", "wb");
     
175.             node_value( &tree, (char *)"0123");
     
176.             maketree( oindex, SIZE, 0, &tree ); //index, size, level, pt
     
177.             dump_tree( &tree, fp, 0 );
     
178.         }
     
179.     fclose( fp );
     
180. 
     
181.     AB ab;
     
182.     struct node *pt;
     
183.     char target[4];
     
184.     int count = 0;
     
185. 
     
186.     for (int m = 0; m < SIZE; m++ )
     
187.     {
     
188.         pt = &tree;
     
189.         strncpy(target, order[m], 4);
     
190.         //print_num( target );  //显示目标数字
     
191. 
     
192.         while ( 1 )
     
193.         {
     
194.             bullscows( target, pt->guess, &ab );
     
195.             //printf("%s [%d%d]\n", pt->guess, ab.a, ab.b );  //显示当前情况
     
196.             count++;
     
197.             if (ab.a == 4) break;
     
198. 
     
199.             pt = pt->res[ mapindex[ab.a][ab.b] ];
     
200.             if ( pt->guess[0] == '\0' )
     
201.             {
     
202.                 printf("Something wrong!");
     
203.                 break;
     
204.             }
     
205.         }
     
206.         //printf("\n");
     
207.     }
     
208. 
     
209.     printf("Clock:%ld, count: %d, avg: %.3f\n",
     
210.             clock(), count, (float)count/((float)SIZE)
     
211.         );
     
212.     return 0;
     
213. 
     
214. }
     
215. 
     
216. int reduce( int *oindex, char *guess, AB *res, int *subset, int osize )
     
217. {
     
218.     AB t;
     
219.     int idx = 0;
     
220. 
     
221.     for (int i = 0; i < osize; i++)
     
222.     {
     
223.         bullscows( guess, order[ oindex[i] ], &t );
     
224.         if ( (t.a == res->a) &&
     
225.              (t.b == res->b) &&
     
226.             (strncmp(guess, order[ oindex[i] ], 4) != 0 ) )  //不全等
     
227.         {
     
228.             subset[idx] = oindex[i];
     
229.             idx++;
     
230.         }
     
231.     }
     
232. 
     
233.     return idx;
     
234. }
     
235. 
     
236. void bullscows( char target[4], char guess[4], AB *res )
     
237. {
     
238.     int idx;
     
239.     res->a = 0;
     
240.     res->b = 0;
     
241. 
     
242.     for ( idx = 0; idx < 4; idx++ )
     
243.     {
     
244.         if ( target[idx] == guess[idx] )
     
245.             res->a++;
     
246.         else
     
247.             if ( strchr(target, guess[idx]) != 0 )
     
248.             {
     
249.                 res->b++;
     
250.             }
     
251.     }
     
252. }
     
253. 
     
254. void permute(char *elements, char *getstr, int len, int lv)
     
255. {
     
256.     char *tempele = (char *)malloc( len * sizeof(char) );
     
257. 
     
258.     for ( int i = 0; i < len; i++)
     
259.     {
     
260.         strcpy( tempele, elements );
     
261.         getstr[lv] = elements[i];
     
262. 
     
263.         for (int j = i; j < (len-1); j++)  //popup one char
     
264.             tempele[j] = elements[j+1];
     
265. 
     
266.         if ( lv < 4 )
     
267.             permute( tempele, getstr, len-1, lv+1 );
     
268.         else
     
269.         {
     
270.             strncpy( order[odi++], getstr, 4 );
     
271.             break;
     
272.         }
     
273.     }
     
274. }
     
275. 
     

复制代码

rubyish

回复 26# 523066680

v10: final version

time: 0.5s

1. 1    1
   
2. 2    13
   
3. 3    108
   
4. 4    596
   
5. 5    1668
   
6. 6    1768
   
7. 7    752
   
8. 8    129
   
9. 9    5
   
10. ----------------
    
11. COUNT = 28024
    
12. TEST  = 5040
    
13. AVE   = 5.560317
    
14. 
    
15. real    0m0.515s

复制代码

1. // gcc -Wall -march=native -Ofast -o bull bull.c -lm
   
2. 
   
3. # include <stdio.h>
   
4. # include <string.h>
   
5. # include <math.h>
   
6. 
   
7. # define OK 0x40
   
8. # define get_a(A)   A >> 4
   
9. # define get_b(A)   0xF & A
   
10. # define copy(A, B) memcpy (A, B, 4)
    
11. # define move1(A)   ((1 << A[0]) | (1 << A[1]) | (1 << A[2]) | (1 << A[3]))
    
12. # define INIT(A)    for (int i = 0; i < 5040; i++) A[i] = i;
    
13. # define AB(A, B)   (A < B ? XAYB[A][B] : XAYB[B][A])
    
14. # define DATA(a)    TOTO[a][0], TOTO[a][1], TOTO[a][2], TOTO[a][3]
    
15. 
    
16. # define TEST 5040
    
17. 
    
18. typedef char kar;
    
19. typedef double dub;
    
20. typedef void voi;
    
21. 
    
22. kar XAYB[5040][5040];
    
23. int A_and_B[961];       // LOOK: sub genB
    
24. kar TOTO[5040][4];       // TOTO[0] = [ 0, 1, 2, 3 ]
    
25. int MAYBE[5040];        // [ 0 .. 5039 ]
    
26. int INDES[65];          // 4A: 0x40 == 64
    
27. int COUNT[16];          //
    
28. dub INFO[1500];
    
29. int MOVE[5040];
    
30. int LEN_MAYBE;          // @MAYBE
    
31. 
    
32. voi init (voi);
    
33. voi test (voi);
    
34. voi genTOTO (int);
    
35. voi genIndes (voi);
    
36. voi genB (voi);
    
37. voi genAB (voi);
    
38. voi rehashMaybe (int, int);
    
39. int gimme (int);
    
40. 
    
41. /* ____________________ MAIN ____________________ */
    
42. int main (){
    
43.     init ();
    
44.     test ();
    
45. }
    
46. 
    
47. /* _____________________ SUB _____________________ */
    
48. 
    
49. voi test () {
    
50.     fprintf (stderr, "\rtest ");
    
51.     for (int v = 0; v < TEST; v++) {
    
52.         if (!(v % 100)) fprintf (stderr, "%6d\b\b\b\b\b\b", v);
    
53.         // printf ("%d\n", v + 1);
    
54.         INIT (MAYBE);
    
55.         int ans = v;
    
56.         int gue = 0;
    
57.         LEN_MAYBE = 5040;
    
58.         // printf ("_ [ %d%d%d%d ]\n", DATA (ans));
    
59.         int x;
    
60.         for (x = 1; x < 10; x++) {
    
61.             int ab = AB (ans, gue);
    
62.             // int a  = get_a (ab);
    
63.             // int b  = get_b (ab);
    
64.             // printf ("%d [ %d%d%d%d ] AB %d %d\n", x, DATA (gue), a, b);
    
65.             if (ab == OK) break;
    
66.             rehashMaybe (gue, ab);
    
67.             // gue = gimme (x);
    
68.             gue = MAYBE[0]; /* NAIVE: FAST */
    
69. 
    
70.         }
    
71.         COUNT[x]++;
    
72.     }
    
73. 
    
74.     int ave = 0;
    
75.     int tot = 0;
    
76.     puts ("FINISH");
    
77. 
    
78.     for (int i = 1; i < 15; i++) {
    
79.         if (!COUNT[i]) continue;
    
80.         printf ("%d\t%d\n", i, COUNT[i]);
    
81.         ave += i * COUNT[i];
    
82.         tot += COUNT[i];
    
83.     }
    
84. 
    
85.     if (tot != TEST) puts ("ERROR");
    
86.     puts ("----------------");
    
87.     printf ("COUNT = %d\n", ave);
    
88.     printf ("TEST  = %d\n", TEST);
    
89.     printf ("AVE   = %f\n", ave / (dub)TEST);
    
90. } /* test */
    
91. 
    
92. voi init () {
    
93.     fprintf (stderr, "init...");
    
94.     genTOTO (0);
    
95.     genB ();
    
96.     genAB ();
    
97.     genIndes ();
    
98.     for (int i = 0; i < 1500; i++) INFO[i] = i * log (i);
    
99. }
    
100. 
     
101. voi genTOTO (int lev){
     
102.     static kar num[4];
     
103.     static int I = 0;
     
104.     static int has[10];
     
105. 
     
106.     if (lev == 4) {
     
107.         copy (TOTO[I], num);
     
108.         MOVE[I] = move1 (num);
     
109.         I++;
     
110.         return;
     
111.     }
     
112. 
     
113.     for (int i = 0; i <= 9; i++) {
     
114.         if (has[i]) continue;
     
115.         has[i]   = 1;
     
116.         num[lev] = i;
     
117.         genTOTO (lev + 1);
     
118.         has[i] = 0;
     
119.     }
     
120. } /* genTOTO */
     
121. 
     
122. voi genB (){
     
123.     for (int i = 0; i < 961; i++) {
     
124.         int count = 0;
     
125. 
     
126.         for (int j = 0; j < 10; j++) {
     
127.             if (i & (1 << j)) count++;
     
128.             if (count > 4) break;
     
129.         }
     
130.         A_and_B[i] = count > 4 ? 0 : count;
     
131.     }
     
132. }
     
133. 
     
134. voi genAB (){
     
135.     for (int i = 0; i < 5040; i++) {
     
136.         kar *cha = TOTO[i];
     
137.         int C1   = MOVE[i];
     
138.         for (int j = i; j < 5040; j++) {
     
139.             kar *cha2 = TOTO[j];
     
140.             int C2    = MOVE[j];
     
141.             int A     = 0;
     
142.             for (int k = 0; k < 4; k++)
     
143.                 if (cha[k] == cha2[k]) A++;
     
144.             int B = A_and_B[C1 & C2] - A;
     
145.             XAYB[i][j] = (A << 4) | B;
     
146.         }
     
147.     }
     
148. }
     
149. 
     
150. inline
     
151. voi rehashMaybe (int gue, int ab){
     
152.     int I = 0;
     
153. 
     
154.     for (int i = 0; i < LEN_MAYBE; i++) {
     
155.         if (AB (MAYBE[i], gue) == ab)
     
156.             MAYBE[I++] = MAYBE[i];
     
157.     }
     
158.     LEN_MAYBE = I;
     
159. }
     
160. 
     
161. inline
     
162. int gimme (int lev){
     
163.     if (LEN_MAYBE == 1 || lev == 1) return MAYBE[0];
     
164.     int best = 0;
     
165.     dub max  = 999999.0; // BIG NUM
     
166. 
     
167.     for (int i = 0; i < LEN_MAYBE; i++) {
     
168.         int test[14] = { 0 };
     
169. 
     
170.         for (int j = 0; j < LEN_MAYBE; j++) {
     
171.             int ab  = AB (MAYBE[i], MAYBE[j]);
     
172.             int pos = INDES[ab];
     
173.             test[pos]++;
     
174.         }
     
175. 
     
176.         dub toto = 0.0;
     
177.         for (int i = 0; i < 14; i++)
     
178.             if (test[i]) toto += INFO[test[i]];
     
179.         if (max > toto) max = toto, best = i;
     
180.     }
     
181.     return MAYBE[best];
     
182. } /* gimme */
     
183. 
     
184. voi genIndes (){
     
185.     int var[] = { 0, 5, 9, 12, 13 };
     
186. 
     
187.     for (int a = 0; a <= 4; a++) {
     
188.         for (int b = 0; b <= 4; b++) {
     
189.             if (a + b > 4) continue;
     
190.             int ab = (a << 4) | b;
     
191.             int i  = var[a] + b;
     
192.             INDES[ab] = i;
     
193.         }
     
194.     }
     
195. }
     

复制代码

rubyish

回复 26# 523066680

run de jieguo shi:

bash: line 1:  3567 Segmentation fault      (core dumped)


Zhege banben youyisi. Keyi xuexi ruhe maketree.
3Q~~

rubyish

回复 26# 523066680


Intel(R) Atom(TM) CPU N280   @ 1.66GHz
make tree: 0.16s

1. Clock:162568, count: 28024, avg: 5.560
   
2. 
   
3. real    0m0.166s

复制代码

load tree: 0.03s

1. Clock:36215, count: 28024, avg: 5.560
   
2. 
   
3. real    0m0.039s

复制代码

Very very fast!! kanlai wode final haibuneng final.

Zhege code wo bixu zixide yuedu.
Tansuo ta ruci shensu de aomi.
3Q ~~


Zhe shi xiugai bullscows hanshu zhihou de jieguo.

Jiu wo de lijie?

1. void bullscows (char target[4], char guess[4], AB *res){
   
2. ...
   
3.     if (strchr (target, guess[idx]) != 0) {

复制代码

Zhelide strchr shi cuowude shiyong.
strchr de diyige canshu bixu shi string. yejiushi yi '\0' jiewei de char array.

You yige example:
http://clc-wiki.net/wiki/strchr
In standard C, this can be implemented as:

1. char *strchr(const char *s, int c)
   
2. {
   
3.     while (*s != (char)c)
   
4.         if (!*s++) return 0;
   
5.     return (char *)s;
   
6. }

复制代码

Huoshi windows de strchr butongyu C biaozhun?

rubyish

What is this?

1. char (order[SIZE])[4];

复制代码

youhe butong?

1. char order[SIZE][4];

复制代码