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

523066680

生成搜索树（没有估值，从每个子集中选第一项作为下一层的猜测数），内联C

1. =info
   
2.     Code By 523066680, 2017-08-10
   
3.    
   
4.     选择第一项
   
5.     $k = shift @keyset;
   
6. 
   
7.     选择中间项
   
8.     $k = splice @keyset, int(($#keyset+1)/2), 1;
   
9. =cut
   
10. 
    
11. use Inline C;
    
12. use IO::Handle;
    
13. use Data::Dumper;
    
14. use File::Slurp;
    
15. STDOUT->autoflush(1);
    
16. $Data::Dumper::Indent = 1;
    
17. $Data::Dumper::Sortkeys = 1;
    
18. 
    
19. #生成所有排列
    
20. my @orders;
    
21. permute( [0 .. 9] , [], 4, \@orders);
    
22. 
    
23. print "Step 1, make tree\n";
    
24. my $tree;
    
25. #树的起点固定为 - "0123"，首层的可选排列有5040种
    
26. $tree = { "0123" => {} };
    
27. maketree( $tree, \@orders, 0 );
    
28. 
    
29. #生成 Perl 树结构，以及 JSON 树结构
    
30. print "Step 2, dump tree\n";
    
31. write_file("./Tree.txt", Dumper $tree);
    
32. 
    
33. sub maketree
    
34. {
    
35.         my ($ref, $arr, $lv) = @_;
    
36.         my $AB = "00";
    
37.     my $k;
    
38.     my @keyset;
    
39.    
    
40.     #将所有项按字符排序
    
41.     @keyset = sort { $a cmp $b } keys %$ref;
    
42. 
    
43.     #选择第一项
    
44.     $k = shift @keyset;
    
45. 
    
46.     #生成反馈节点 {$AB}，以及每个反馈下的数字集合 {$e}
    
47.         for my $e ( @$arr )
    
48.         {
    
49.                 bullcow( $k, $e, $AB );
    
50.                 if ($AB ne "40")
    
51.                 {
    
52.             $ref->{$k}{$AB}{$e} = {};
    
53.                 }
    
54.         }
    
55. 
    
56.     #从首层(相对地)节点中删除 $k 以外的项
    
57.     grep { delete $ref->{$_} } @keyset;
    
58. 
    
59.     #对于每一个反馈，递归筛选新的数字集合、生成子节点
    
60.     for my $ab ( keys %{ $ref->{ $k } } )
    
61.     {
    
62.         maketree( $ref->{$k}{$ab}, [ keys %{$ref->{$k}{$ab}} ], $lv+1 );
    
63.     }
    
64. }
    
65. 
    
66. sub permute
    
67. {
    
68.     my ( $a, $b, $n, $aref ) = @_;
    
69.     my $last = $#$a;
    
70. 
    
71.     if ( $#$b >= ($n-1) )
    
72.     {
    
73.         push @$aref, join("", @$b);
    
74.         return;
    
75.     }
    
76. 
    
77.     for my $idx ( 0 .. $last )
    
78.     {
    
79.         permute( [ @$a[0 .. $idx-1, $idx+1 .. $last] ], [ @$b, $a->[$idx] ], $n, $aref );
    
80.     }
    
81. }
    
82. 
    
83. __END__
    
84. __C__
    
85. void bullcow(char *stra, char *strb, char *AB)
    
86. {
    
87.     int idx;
    
88.     char a = '0';
    
89.     char b = '0';
    
90. 
    
91.     for ( idx = 0; idx < 4; idx++ )
    
92.     {
    
93.         if ( stra[idx] == strb[idx] )
    
94.             a++;
    
95.         else
    
96.             if ( strchr(stra, strb[idx]) != 0 )
    
97.             {
    
98.                 b++;
    
99.             }
    
100.     }
     
101. 
     
102.     AB[0] = a;
     
103.     AB[1] = b;
     
104. }

复制代码

rubyish

回复 10# 523066680

是AB反馈函数耗时最多，这个函数改为内联C函数处理就快多了

Ni shi duide. 3Q~~
Delete zhege sub AB zhihou. Sudu queshi biankuaile.

time:

1. 23m15.507s -> 5m49.733s

复制代码

naive: 7.14s

1. -----------------
   
2. 1       1
   
3. 2       13
   
4. 3       108
   
5. 4       596
   
6. 5       1668
   
7. 6       1768
   
8. 7       752
   
9. 8       129
   
10. 9       5
    
11. AVE = 5.560317
    
12. 
    
13. real    0m7.145s

复制代码

1. -----------------
   
2. 1       1
   
3. 2       11
   
4. 3       80
   
5. 4       535
   
6. 5       2222
   
7. 6       1990
   
8. 7       199
   
9. 8       2
   
10. AVE = 5.329762
    
11. real    5m32.530s

复制代码

1. 1        1
   
2. 2        9
   
3. 3        44
   
4. 4        344
   
5. 5        1831
   
6. 6        2480
   
7. 7        331
   
8. AVE = 5.531548
   
9. 
   
10. real        5m45.675s

复制代码

1. # include <stdio.h>
   
2. # include <string.h>
   
3. 
   
4. # define OK   0x40
   
5. # define get_a(A)   A >> 4
   
6. # define get_b(A)   0xF & A
   
7. # define copy(A, B) memcpy (A, B, 4)
   
8. # define COPY(A, B) memcpy (A, B, 20160)
   
9. // 20160 == 5040 * 4
   
10. # define C2I(A)     ((1 << A[0]) | (1 << A[1]) | (1 << A[2]) | (1 << A[3]))
    
11. # define AB(A, B)   TABAB[A][B]
    
12. # define TEST 5040
    
13. 
    
14. typedef char kar;
    
15. 
    
16. kar TABAB[9877][9877];
    
17. int TABB[961];
    
18. kar KAR[9877][4];
    
19. int TOTO[5040];
    
20. int MAYBE[5040];
    
21. int TABI[65];
    
22. int COUNT[15];
    
23. int LEN;
    
24. 
    
25. 
    
26. void init (void);
    
27. void make (int);
    
28. int gimme (void);
    
29. void grep (int, int);
    
30. void test (void);
    
31. void gen_i (void);
    
32. void gen_b (void);
    
33. void gen_ab (void);
    
34. /* ____________________ MAIN ____________________ */
    
35. int main (){
    
36.     init ();
    
37.     //getchar();
    
38.     test ();
    
39. }
    
40. 
    
41. /* _____________________ SUB _____________________ */
    
42. 
    
43. void test () {
    
44.     for (int v = 0; v < TEST; v++) {
    
45.         printf ("%d\n", v + 1);
    
46.         COPY (MAYBE, TOTO);
    
47.         int ans = TOTO[v];
    
48.         int gue = TOTO[0];
    
49.         LEN = 5040;
    
50.         // printf ("ANS = [ %04d ]\n", ans);
    
51.         int x;
    
52.         for (x = 1; x < 15; x++) {
    
53.             int ab = AB (ans, gue);
    
54.             // int a  = get_a (ab);
    
55.             // int b  = get_b (ab);
    
56.             // printf ("%d [ %04d ] AB %d %d\n", x, gue, a, b);
    
57.             if (ab == OK) break;
    
58.             grep (gue, ab);
    
59.             // gue = gimme ();  /* SLOW: MAX = 7 */
    
60.             gue = MAYBE[0]; /* FAST: MAX = 9 */
    
61. 
    
62.         }
    
63.         COUNT[x]++;
    
64.     }
    
65.     puts ("-----------------");
    
66.     int ave = 0;
    
67.     for (int i = 1; i < 15; i++) {
    
68.         printf ("%d\t%d\n", i, COUNT[i]);
    
69.         ave += i * COUNT[i];
    
70.     }
    
71.     printf ("AVE = %f\n", ave / (double)TEST);
    
72. } /* test */
    
73. 
    
74. void init () {
    
75.     puts ("init..");
    
76.     make (0);
    
77.     gen_b ();
    
78.     gen_ab ();
    
79.     gen_i ();
    
80. }
    
81. 
    
82. void make (int lev){
    
83.     static kar num[4];
    
84.     static int I = 0;
    
85.     static int has[10];
    
86. 
    
87.     if (lev == 4) {
    
88.         int n = 1000 * num[0] + 100 * num[1] + 10 * num[2] + num[3];
    
89.         TOTO[I] = n;
    
90.         copy (KAR[n], num);
    
91.         I++;
    
92.         return;
    
93.     }
    
94. 
    
95.     for (int i = 0; i <= 9; i++) {
    
96.         if (has[i]) continue;
    
97.         has[i]   = 1;
    
98.         num[lev] = i;
    
99.         make (lev + 1);
    
100.         has[i] = 0;
     
101.     }
     
102. } /* make */
     
103. 
     
104. void gen_b (){
     
105.     for (int i = 0; i < 961; i++) {
     
106.         int count = 0;
     
107.         for (int j = 0; j < 10; j++) {
     
108.             if (i & (1 << j)) count++;
     
109.             if (count > 4) break;
     
110.         }
     
111.         TABB[i] = count > 4 ? 0 : count;
     
112.     }
     
113. }
     
114. 
     
115. void gen_ab (){
     
116.     for (int i = 0; i < 5040; i++) {
     
117.         int indes = TOTO[i];
     
118.         kar *cha  = KAR[indes];
     
119.         int C1    = C2I (cha);
     
120.         for (int j = 0; j < 5040; j++) {
     
121.             int indes2 = TOTO[j];
     
122.             kar *cha2  = KAR[indes2];
     
123.             int C2     = C2I (cha2);
     
124.             int same   = 0;
     
125.             for (int k = 0; k < 4; k++)
     
126.                 if (cha[k] == cha2[k]) same++;
     
127.             int B = C1 & C2;
     
128.             B                    = TABB[B] - same;
     
129.             TABAB[indes][indes2] = (same << 4) | B;
     
130.         }
     
131.     }
     
132. }
     
133. 
     
134. 
     
135. 
     
136. inline void grep (int gue, int ab){
     
137.     int I = 0;
     
138. 
     
139.     for (int i = 0; i < LEN; i++) {
     
140.         int ab2 = AB (MAYBE[i], gue);
     
141.         if (ab2 == ab)
     
142.             MAYBE[I++] = MAYBE[i];
     
143.     }
     
144.     LEN = I;
     
145. }
     
146. 
     
147. int gimme (){
     
148. 
     
149.     if (LEN == 1) return MAYBE[0];
     
150.     int best = 0;
     
151.     int max  = 0;
     
152.     for (int i = 0; i < 5040; i++) {
     
153.         int test[15] = { 0 };
     
154.         for (int j = 0; j < LEN; j++) {
     
155.             int ab = AB (TOTO[i], MAYBE[j]);
     
156.             int I  = TABI[ab];
     
157.             test[I] = test[I] ? : 1;
     
158.         }
     
159.         int toto = 0;
     
160.         for (int i = 0; i < 15; i++)
     
161.             if (test[i]) toto++;
     
162.         if (toto > max) {
     
163.             max  = toto;
     
164.             best = i;
     
165.         }
     
166.     }
     
167.     return TOTO[best];
     
168. } /* gimme */
     
169. 
     
170. void gen_i (){
     
171.     int var[] = { 0, 5, 9, 12, 14 };
     
172. 
     
173.     for (int i = 0; i <= 4; i++) {
     
174.         for (int j = 0; j <= 4; j++) {
     
175.             if (i + j > 4) continue;
     
176.             int k = (i << 4) | j;
     
177.             int v = var[i] + j;
     
178.             TABI[k] = v;
     
179.         }
     
180.     }
     
181. }
     

复制代码

rubyish

回复 11# 523066680

Ruhe shiyong zhege Tree.txt?
Jugelizi? You example ma?
3Q~~

523066680

回复 13# rubyish

其实就是把搜索的过程以及可能遇到的情况都保存到结构树里，实际测试的时候顺着树节点跑就是了（省去了反复筛选的过程）。

1. =info
   
2.     523066680 2017-08
   
3. =cut
   
4. 
   
5. use IO::Handle;
   
6. use File::Slurp;
   
7. STDOUT->autoflush(1);
   
8. 
   
9. #加载树结构
   
10. my $tree = eval read_file("tree.txt");
    
11. my $ref = $tree;
    
12. 
    
13. my $AB;
    
14. my $guess;
    
15. my $secret = "9876";
    
16. print "Target Number: $secret\n";
    
17. ($guess) = keys %$ref;
    
18. 
    
19. while (1)
    
20. {
    
21.     $AB = guess( $secret, $guess );
    
22.     print "[$AB] $guess\n";
    
23. 
    
24.     last if ( $AB eq "40" );
    
25. 
    
26.     #迭代树节点，提取下一节点的猜数
    
27.     if ( exists $ref->{$guess}{$AB} )
    
28.     {
    
29.         $ref = $ref->{$guess}{$AB};
    
30.         ($guess) = keys %{$ref};
    
31.     }
    
32.     else
    
33.     {
    
34.         die "Something wrong\n";
    
35.     }
    
36. }
    
37. 
    
38. sub guess
    
39. {
    
40.     my ($secret, $guess) = @_;
    
41.     my ($A, $B) = (0, 0);
    
42.     my $t;
    
43. 
    
44.     for my $i ( 0 .. 3 )
    
45.     {
    
46.         if ( substr($secret, $i, 1) eq substr($guess, $i, 1) )
    
47.         {
    
48.             $A++;
    
49.         }
    
50.         else
    
51.         {
    
52.             $t = substr($guess, $i, 1);
    
53.             $B++ if ( $secret =~/$t/ );
    
54.         }
    
55.         $i++;
    
56.     }
    
57. 
    
58.     return $A . $B;
    
59. }
    

复制代码

最大反馈指标的搜索树，以及普通搜索树
http://523066680.ys168.com/
目录 Perl/猜数字游戏bullscows

rubyish

回复 14# 523066680

顺着树节点跑就是了（省去了反复筛选的过程）。

3Q ~~

rubyish

v6:

1. -----------------
   
2. 1       1
   
3. 2       13
   
4. 3       73
   
5. 4       561
   
6. 5       2224
   
7. 6       1992
   
8. 7       176
   
9. TEST = 5040
   
10. AVE  = 5.316270
    
11. 
    
12. real    2m37.176s

复制代码

523066680

回复 16# rubyish

用结构树猜数字，遍历5040种情况，可以秒出结果（print 消耗不计入内）

其他预期估值公式汇总
http://www.pepsplace.org.uk/Trivia/Moo/Moo.pdf

举几个例子，
Minimise the square of the variance - 最小化平方差估值
对于某一层得到的反馈，将每个反馈下的可能集合（子集合）的数量分别统计为 t1 t2 t3 .. tn
对这些t值分别平方、求和，再除以反馈数量n， (t1^2+t2^2+ ... tn^2)/n，值越小，就能越快缩小范围。
（本质就是在追求最大反馈量的同时，确保各反馈下子集合数量的均衡，不会相差太大。）

公式末尾有个函数 -f(1)，如果该最小值属于5040种排列但不属于当前子集合，返回0；如果属于当前子集合，返回1
也就是：如果子集合种也包含最小估值，则优先选择子集合种的元素。

Square root - 平方根估值
(t1*sqrt(t1) + t2*sqrt(t2) .... tn*sqrt(tn) )/n - f(1)

Information content - Dr J. Larmouth 给出的算法。
sum( t1*log(t1) ... tn*log(tn) )  / n - f(2*log(2)) , f() 函数参考前面的说明，猜数字属于子集合时返回 2*log(2)，否则返回0
平均回合数为 5.239

经过 rubyish 提醒，Larmouth 的算法应该为
sum( t1*log(t1) ... tn*log(tn) ) - f(2*log(2)) ，当时习惯性地加了 /n，Sorry。

rubyish

回复 17# 523066680

3Q ~~ this is very good!!
EQ:

1. # use MAGIC
   
2. # use TURBO
   
3. # add POWER

复制代码

USE: Information content
TIME: 0m8.377s

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        0m8.377s

复制代码

Jicide changshi zhihou....
Hai wufa dadao AVE = 5.2X.

523066680

回复 18# rubyish

用C实现比较繁琐，你的C代码我也没有仔细看，结果不一致可能是实现细节有差别。
我把完整的生成树和遍历测试的代码发到网盘了，你对比下。

http://ys-h.ys168.com/205774914/ ... %96%B9%E6%A1%88.zip

http://523066680.ys168.com/
perl/猜数字游戏/Larmouth方案.zip

rubyish

回复 19# 523066680

3Q ~~
Bidui zhihou faxian zhiyou yichu chayi
sum( t1*log(t1) ... tn*log(tn) ) / n - f(2*log(2))

1. grep { $amount += $_ * log($_) } values %hash;
   
2. if ( exists $ref->{$e} ) { $amount -= 2 * log(2) }

复制代码

gaicheng zhege zhihou keyi dadao AVE = 5.2X

1. sum( t1*log(t1) ... tn*log(tn) )  - f(2*log(2))

复制代码

AVE: 5.27

1. 1       1
   
2. 2       13
   
3. 3       60
   
4. 4       548
   
5. 5       2440
   
6. 6       1871
   
7. 7       106
   
8. 8       1
   
9. ----------------
   
10. COUNT = 26575
    
11. TEST  = 5040
    
12. AVE   = 5.272817
    
13. 
    
14. real    1m24.631s

复制代码

AVE: 5.23

1. 1       1
   
2. 2       7
   
3. 3       70
   
4. 4       611
   
5. 5       2468
   
6. 6       1782
   
7. 7       100
   
8. 8       1
   
9. ----------------
   
10. COUNT = 26409
    
11. TEST  = 5040
    
12. AVE   = 5.239881
    
13. 
    
14. real    4m36.666s

复制代码

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

复制代码