忘记密码   免费注册 查看新帖 | 论坛精华区

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT HPC论坛 徽章 文库 沙龙 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
最近访问板块 发新帖
楼主: 523066680

[算法讨论]猜数字游戏 - Bulls and Cows [复制链接]

论坛徽章:
9
子鼠
日期:2014-10-11 16:46:482015亚冠之萨济拖拉机
日期:2015-05-22 11:38:53黑曼巴
日期:2016-07-19 15:03:1115-16赛季CBA联赛之四川
日期:2017-05-16 16:38:5515-16赛季CBA联赛之天津
日期:2017-06-29 10:34:4315-16赛季CBA联赛之青岛
日期:2017-08-17 19:55:2415-16赛季CBA联赛之浙江
日期:2017-08-24 16:55:1715-16赛季CBA联赛之佛山
日期:2017-08-28 17:11:552016科比退役纪念章
日期:2017-09-02 15:42:47
发表于 2017-08-31 09:10 |显示全部楼层
本帖最后由 523066680 于 2017-08-31 20:03 编辑

生成搜索树(没有估值,从每个子集中选第一项作为下一层的猜测数),内联C
  1. =info
  2.     Code By 523066680, 2017-08-10
  3.    
  4.     选择第一项
  5.     $k = shift @keyset;

  6.     选择中间项
  7.     $k = splice @keyset, int(($#keyset+1)/2), 1;
  8. =cut

  9. use Inline C;
  10. use IO::Handle;
  11. use Data::Dumper;
  12. use File::Slurp;
  13. STDOUT->autoflush(1);
  14. $Data::Dumper::Indent = 1;
  15. $Data::Dumper::Sortkeys = 1;

  16. #生成所有排列
  17. my @orders;
  18. permute( [0 .. 9] , [], 4, \@orders);

  19. print "Step 1, make tree\n";
  20. my $tree;
  21. #树的起点固定为 - "0123",首层的可选排列有5040种
  22. $tree = { "0123" => {} };
  23. maketree( $tree, \@orders, 0 );

  24. #生成 Perl 树结构,以及 JSON 树结构
  25. print "Step 2, dump tree\n";
  26. write_file("./Tree.txt", Dumper $tree);

  27. sub maketree
  28. {
  29.         my ($ref, $arr, $lv) = @_;
  30.         my $AB = "00";
  31.     my $k;
  32.     my @keyset;
  33.    
  34.     #将所有项按字符排序
  35.     @keyset = sort { $a cmp $b } keys %$ref;

  36.     #选择第一项
  37.     $k = shift @keyset;

  38.     #生成反馈节点 {$AB},以及每个反馈下的数字集合 {$e}
  39.         for my $e ( @$arr )
  40.         {
  41.                 bullcow( $k, $e, $AB );
  42.                 if ($AB ne "40")
  43.                 {
  44.             $ref->{$k}{$AB}{$e} = {};
  45.                 }
  46.         }

  47.     #从首层(相对地)节点中删除 $k 以外的项
  48.     grep { delete $ref->{$_} } @keyset;

  49.     #对于每一个反馈,递归筛选新的数字集合、生成子节点
  50.     for my $ab ( keys %{ $ref->{ $k } } )
  51.     {
  52.         maketree( $ref->{$k}{$ab}, [ keys %{$ref->{$k}{$ab}} ], $lv+1 );
  53.     }
  54. }

  55. sub permute
  56. {
  57.     my ( $a, $b, $n, $aref ) = @_;
  58.     my $last = $#$a;

  59.     if ( $#$b >= ($n-1) )
  60.     {
  61.         push @$aref, join("", @$b);
  62.         return;
  63.     }

  64.     for my $idx ( 0 .. $last )
  65.     {
  66.         permute( [ @$a[0 .. $idx-1, $idx+1 .. $last] ], [ @$b, $a->[$idx] ], $n, $aref );
  67.     }
  68. }

  69. __END__
  70. __C__
  71. void bullcow(char *stra, char *strb, char *AB)
  72. {
  73.     int idx;
  74.     char a = '0';
  75.     char b = '0';

  76.     for ( idx = 0; idx < 4; idx++ )
  77.     {
  78.         if ( stra[idx] == strb[idx] )
  79.             a++;
  80.         else
  81.             if ( strchr(stra, strb[idx]) != 0 )
  82.             {
  83.                 b++;
  84.             }
  85.     }

  86.     AB[0] = a;
  87.     AB[1] = b;
  88. }
复制代码

论坛徽章:
7
戌狗
日期:2013-12-15 20:43:38技术图书徽章
日期:2014-03-05 01:33:12技术图书徽章
日期:2014-03-15 20:31:17未羊
日期:2014-03-25 23:48:20丑牛
日期:2014-04-07 22:37:44巳蛇
日期:2014-04-11 21:58:0915-16赛季CBA联赛之青岛
日期:2016-03-17 20:36:13
发表于 2017-09-01 02:54 |显示全部楼层
回复 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. 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. real        5m45.675s
复制代码
  1. # include <stdio.h>
  2. # include <string.h>

  3. # define OK   0x40
  4. # define get_a(A)   A >> 4
  5. # define get_b(A)   0xF & A
  6. # define copy(A, B) memcpy (A, B, 4)
  7. # define COPY(A, B) memcpy (A, B, 20160)
  8. // 20160 == 5040 * 4
  9. # define C2I(A)     ((1 << A[0]) | (1 << A[1]) | (1 << A[2]) | (1 << A[3]))
  10. # define AB(A, B)   TABAB[A][B]
  11. # define TEST 5040

  12. typedef char kar;

  13. kar TABAB[9877][9877];
  14. int TABB[961];
  15. kar KAR[9877][4];
  16. int TOTO[5040];
  17. int MAYBE[5040];
  18. int TABI[65];
  19. int COUNT[15];
  20. int LEN;


  21. void init (void);
  22. void make (int);
  23. int gimme (void);
  24. void grep (int, int);
  25. void test (void);
  26. void gen_i (void);
  27. void gen_b (void);
  28. void gen_ab (void);
  29. /* ____________________ MAIN ____________________ */
  30. int main (){
  31.     init ();
  32.     //getchar();
  33.     test ();
  34. }

  35. /* _____________________ SUB _____________________ */

  36. void test () {
  37.     for (int v = 0; v < TEST; v++) {
  38.         printf ("%d\n", v + 1);
  39.         COPY (MAYBE, TOTO);
  40.         int ans = TOTO[v];
  41.         int gue = TOTO[0];
  42.         LEN = 5040;
  43.         // printf ("ANS = [ %04d ]\n", ans);
  44.         int x;
  45.         for (x = 1; x < 15; x++) {
  46.             int ab = AB (ans, gue);
  47.             // int a  = get_a (ab);
  48.             // int b  = get_b (ab);
  49.             // printf ("%d [ %04d ] AB %d %d\n", x, gue, a, b);
  50.             if (ab == OK) break;
  51.             grep (gue, ab);
  52.             // gue = gimme ();  /* SLOW: MAX = 7 */
  53.             gue = MAYBE[0]; /* FAST: MAX = 9 */

  54.         }
  55.         COUNT[x]++;
  56.     }
  57.     puts ("-----------------");
  58.     int ave = 0;
  59.     for (int i = 1; i < 15; i++) {
  60.         printf ("%d\t%d\n", i, COUNT[i]);
  61.         ave += i * COUNT[i];
  62.     }
  63.     printf ("AVE = %f\n", ave / (double)TEST);
  64. } /* test */

  65. void init () {
  66.     puts ("init..");
  67.     make (0);
  68.     gen_b ();
  69.     gen_ab ();
  70.     gen_i ();
  71. }

  72. void make (int lev){
  73.     static kar num[4];
  74.     static int I = 0;
  75.     static int has[10];

  76.     if (lev == 4) {
  77.         int n = 1000 * num[0] + 100 * num[1] + 10 * num[2] + num[3];
  78.         TOTO[I] = n;
  79.         copy (KAR[n], num);
  80.         I++;
  81.         return;
  82.     }

  83.     for (int i = 0; i <= 9; i++) {
  84.         if (has[i]) continue;
  85.         has[i]   = 1;
  86.         num[lev] = i;
  87.         make (lev + 1);
  88.         has[i] = 0;
  89.     }
  90. } /* make */

  91. void gen_b (){
  92.     for (int i = 0; i < 961; i++) {
  93.         int count = 0;
  94.         for (int j = 0; j < 10; j++) {
  95.             if (i & (1 << j)) count++;
  96.             if (count > 4) break;
  97.         }
  98.         TABB[i] = count > 4 ? 0 : count;
  99.     }
  100. }

  101. void gen_ab (){
  102.     for (int i = 0; i < 5040; i++) {
  103.         int indes = TOTO[i];
  104.         kar *cha  = KAR[indes];
  105.         int C1    = C2I (cha);
  106.         for (int j = 0; j < 5040; j++) {
  107.             int indes2 = TOTO[j];
  108.             kar *cha2  = KAR[indes2];
  109.             int C2     = C2I (cha2);
  110.             int same   = 0;
  111.             for (int k = 0; k < 4; k++)
  112.                 if (cha[k] == cha2[k]) same++;
  113.             int B = C1 & C2;
  114.             B                    = TABB[B] - same;
  115.             TABAB[indes][indes2] = (same << 4) | B;
  116.         }
  117.     }
  118. }



  119. inline void grep (int gue, int ab){
  120.     int I = 0;

  121.     for (int i = 0; i < LEN; i++) {
  122.         int ab2 = AB (MAYBE[i], gue);
  123.         if (ab2 == ab)
  124.             MAYBE[I++] = MAYBE[i];
  125.     }
  126.     LEN = I;
  127. }

  128. int gimme (){

  129.     if (LEN == 1) return MAYBE[0];
  130.     int best = 0;
  131.     int max  = 0;
  132.     for (int i = 0; i < 5040; i++) {
  133.         int test[15] = { 0 };
  134.         for (int j = 0; j < LEN; j++) {
  135.             int ab = AB (TOTO[i], MAYBE[j]);
  136.             int I  = TABI[ab];
  137.             test[I] = test[I] ? : 1;
  138.         }
  139.         int toto = 0;
  140.         for (int i = 0; i < 15; i++)
  141.             if (test[i]) toto++;
  142.         if (toto > max) {
  143.             max  = toto;
  144.             best = i;
  145.         }
  146.     }
  147.     return TOTO[best];
  148. } /* gimme */

  149. void gen_i (){
  150.     int var[] = { 0, 5, 9, 12, 14 };

  151.     for (int i = 0; i <= 4; i++) {
  152.         for (int j = 0; j <= 4; j++) {
  153.             if (i + j > 4) continue;
  154.             int k = (i << 4) | j;
  155.             int v = var[i] + j;
  156.             TABI[k] = v;
  157.         }
  158.     }
  159. }
复制代码

论坛徽章:
7
戌狗
日期:2013-12-15 20:43:38技术图书徽章
日期:2014-03-05 01:33:12技术图书徽章
日期:2014-03-15 20:31:17未羊
日期:2014-03-25 23:48:20丑牛
日期:2014-04-07 22:37:44巳蛇
日期:2014-04-11 21:58:0915-16赛季CBA联赛之青岛
日期:2016-03-17 20:36:13
发表于 2017-09-01 03:04 |显示全部楼层
回复 11# 523066680

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

论坛徽章:
9
子鼠
日期:2014-10-11 16:46:482015亚冠之萨济拖拉机
日期:2015-05-22 11:38:53黑曼巴
日期:2016-07-19 15:03:1115-16赛季CBA联赛之四川
日期:2017-05-16 16:38:5515-16赛季CBA联赛之天津
日期:2017-06-29 10:34:4315-16赛季CBA联赛之青岛
日期:2017-08-17 19:55:2415-16赛季CBA联赛之浙江
日期:2017-08-24 16:55:1715-16赛季CBA联赛之佛山
日期:2017-08-28 17:11:552016科比退役纪念章
日期:2017-09-02 15:42:47
发表于 2017-09-01 09:11 |显示全部楼层
本帖最后由 523066680 于 2017-09-01 09:29 编辑

回复 13# rubyish

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

  1. =info
  2.     523066680 2017-08
  3. =cut

  4. use IO::Handle;
  5. use File::Slurp;
  6. STDOUT->autoflush(1);

  7. #加载树结构
  8. my $tree = eval read_file("tree.txt");
  9. my $ref = $tree;

  10. my $AB;
  11. my $guess;
  12. my $secret = "9876";
  13. print "Target Number: $secret\n";
  14. ($guess) = keys %$ref;

  15. while (1)
  16. {
  17.     $AB = guess( $secret, $guess );
  18.     print "[$AB] $guess\n";

  19.     last if ( $AB eq "40" );

  20.     #迭代树节点,提取下一节点的猜数
  21.     if ( exists $ref->{$guess}{$AB} )
  22.     {
  23.         $ref = $ref->{$guess}{$AB};
  24.         ($guess) = keys %{$ref};
  25.     }
  26.     else
  27.     {
  28.         die "Something wrong\n";
  29.     }
  30. }

  31. sub guess
  32. {
  33.     my ($secret, $guess) = @_;
  34.     my ($A, $B) = (0, 0);
  35.     my $t;

  36.     for my $i ( 0 .. 3 )
  37.     {
  38.         if ( substr($secret, $i, 1) eq substr($guess, $i, 1) )
  39.         {
  40.             $A++;
  41.         }
  42.         else
  43.         {
  44.             $t = substr($guess, $i, 1);
  45.             $B++ if ( $secret =~/$t/ );
  46.         }
  47.         $i++;
  48.     }

  49.     return $A . $B;
  50. }
复制代码

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

论坛徽章:
7
戌狗
日期:2013-12-15 20:43:38技术图书徽章
日期:2014-03-05 01:33:12技术图书徽章
日期:2014-03-15 20:31:17未羊
日期:2014-03-25 23:48:20丑牛
日期:2014-04-07 22:37:44巳蛇
日期:2014-04-11 21:58:0915-16赛季CBA联赛之青岛
日期:2016-03-17 20:36:13
发表于 2017-09-02 02:07 |显示全部楼层
回复 14# 523066680

顺着树节点跑就是了(省去了反复筛选的过程)。
3Q ~~

论坛徽章:
7
戌狗
日期:2013-12-15 20:43:38技术图书徽章
日期:2014-03-05 01:33:12技术图书徽章
日期:2014-03-15 20:31:17未羊
日期:2014-03-25 23:48:20丑牛
日期:2014-04-07 22:37:44巳蛇
日期:2014-04-11 21:58:0915-16赛季CBA联赛之青岛
日期:2016-03-17 20:36:13
发表于 2017-09-02 02:27 |显示全部楼层
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. real    2m37.176s
复制代码

论坛徽章:
9
子鼠
日期:2014-10-11 16:46:482015亚冠之萨济拖拉机
日期:2015-05-22 11:38:53黑曼巴
日期:2016-07-19 15:03:1115-16赛季CBA联赛之四川
日期:2017-05-16 16:38:5515-16赛季CBA联赛之天津
日期:2017-06-29 10:34:4315-16赛季CBA联赛之青岛
日期:2017-08-17 19:55:2415-16赛季CBA联赛之浙江
日期:2017-08-24 16:55:1715-16赛季CBA联赛之佛山
日期:2017-08-28 17:11:552016科比退役纪念章
日期:2017-09-02 15:42:47
发表于 2017-09-02 08:57 |显示全部楼层
本帖最后由 523066680 于 2017-09-06 08:12 编辑

回复 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。

评分

参与人数 1信誉积分 +10 收起 理由
rubyish + 10 # add POWER

查看全部评分

论坛徽章:
7
戌狗
日期:2013-12-15 20:43:38技术图书徽章
日期:2014-03-05 01:33:12技术图书徽章
日期:2014-03-15 20:31:17未羊
日期:2014-03-25 23:48:20丑牛
日期:2014-04-07 22:37:44巳蛇
日期:2014-04-11 21:58:0915-16赛季CBA联赛之青岛
日期:2016-03-17 20:36:13
发表于 2017-09-05 02:25 |显示全部楼层
本帖最后由 rubyish 于 2017-09-04 22:29 编辑

回复 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. real        0m8.377s
复制代码




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

论坛徽章:
9
子鼠
日期:2014-10-11 16:46:482015亚冠之萨济拖拉机
日期:2015-05-22 11:38:53黑曼巴
日期:2016-07-19 15:03:1115-16赛季CBA联赛之四川
日期:2017-05-16 16:38:5515-16赛季CBA联赛之天津
日期:2017-06-29 10:34:4315-16赛季CBA联赛之青岛
日期:2017-08-17 19:55:2415-16赛季CBA联赛之浙江
日期:2017-08-24 16:55:1715-16赛季CBA联赛之佛山
日期:2017-08-28 17:11:552016科比退役纪念章
日期:2017-09-02 15:42:47
发表于 2017-09-05 12:43 |显示全部楼层
回复 18# rubyish

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

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

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

论坛徽章:
7
戌狗
日期:2013-12-15 20:43:38技术图书徽章
日期:2014-03-05 01:33:12技术图书徽章
日期:2014-03-15 20:31:17未羊
日期:2014-03-25 23:48:20丑牛
日期:2014-04-07 22:37:44巳蛇
日期:2014-04-11 21:58:0915-16赛季CBA联赛之青岛
日期:2016-03-17 20:36:13
发表于 2017-09-06 03:44 |显示全部楼层
本帖最后由 rubyish 于 2017-09-06 00:36 编辑

回复 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. 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. real    4m36.666s
复制代码



  1. // gcc -Wall -march=native -Ofast -o bull bull.c

  2. # include <stdio.h>
  3. # include <string.h>
  4. # include <math.h>

  5. # define OK     0x40
  6. # define get_a(A)   A >> 4
  7. # define get_b(A)   0xF & A
  8. # define copy(A, B) memcpy (A, B, 4)
  9. # define move1(A)   ((1 << A[0]) | (1 << A[1]) | (1 << A[2]) | (1 << A[3]))
  10. # define toInt(N)   1000 * N[0] + 100 * N[1] + 10 * N[2] + N[3];
  11. # define INIT(A, B) for (int i = 0; i < 5040; i++) { A[i] = i; B[i] = 1; }
  12. # define AB(A, B)   XAYB[A][B]
  13. # define F2log2 1.38629436111989
  14. # define TEST   5040

  15. typedef char kar;
  16. typedef double dub;
  17. typedef void voi;

  18. kar XAYB[5040][5040];
  19. int A_and_B[961];       // LOOK: sub genB
  20. kar SPLIT[5040][4];       // SPLIT[0] = [ 0, 1, 2, 3 ]
  21. int TOTO[5040];
  22. int MAYBE[5040];        // [ 0 .. 5039 ]
  23. int hasMAYBE[5040];
  24. int INDES[65];          // 4A: 0x40 == 64
  25. int COUNT[16];          //
  26. dub INFO[2000];
  27. int LEN_MAYBE;          // @MAYBE

  28. voi init (voi);
  29. voi test (voi);
  30. voi genTOTO (int);
  31. voi genIndes (voi);
  32. voi genB (voi);
  33. voi genAB (voi);
  34. voi rehashMaybe (int, int);
  35. int gimme (int);

  36. /* ____________________ MAIN ____________________ */
  37. int main (){
  38.     init ();
  39.     test ();
  40. }

  41. /* _____________________ SUB _____________________ */

  42. voi test () {
  43.     fprintf (stderr, "\rtest ");
  44.     for (int v = 0; v < TEST; v++) {
  45.         if (!(v % 100)) fprintf (stderr, "%6d\b\b\b\b\b\b", v);
  46.         // printf ("%d\n", v + 1);
  47.         INIT (MAYBE, hasMAYBE);

  48.         int ans = v;
  49.         int gue = 0;
  50.         LEN_MAYBE = 5040;
  51.         // printf ("_ [ %04d ]\n", TOTO[ans]);
  52.         int x;
  53.         for (x = 1; x < 9; x++) {
  54.             int ab = AB (ans, gue);
  55.             // int a  = get_a (ab);
  56.             // int b  = get_b (ab);
  57.             // printf ("%d [ %04d ] AB %d %d\n", x, TOTO[gue], a, b);
  58.             if (ab == OK) break;
  59.             rehashMaybe (gue, ab);
  60.             gue = gimme (x);
  61.             // gue = MAYBE[0]; /* NAIVE: FAST */

  62.         }
  63.         COUNT[x]++;
  64.     }

  65.     int ave = 0;
  66.     int tot = 0;
  67.     puts ("FINISH");
  68.     for (int i = 1; i < 15; i++) {
  69.         if (!COUNT[i]) continue;
  70.         printf ("%d\t%d\n", i, COUNT[i]);
  71.         ave += i * COUNT[i];
  72.         tot += COUNT[i];
  73.     }

  74.     if (tot != TEST) puts ("ERROR");
  75.     puts ("----------------");
  76.     printf ("COUNT = %d\n", ave);
  77.     printf ("TEST  = %d\n", TEST);
  78.     printf ("AVE   = %f\n", ave / (dub)TEST);
  79. } /* test */

  80. voi init () {
  81.     fprintf (stderr, "init..");
  82.     genTOTO (0);
  83.     genB ();
  84.     genAB ();
  85.     genIndes ();
  86.     for (int i = 0; i < 2000; i++) INFO[i] = i * log (i);
  87. }

  88. voi genTOTO (int lev){
  89.     static kar num[4];
  90.     static int I = 0;
  91.     static int has[10];

  92.     if (lev == 4) {
  93.         int n = toInt (num);
  94.         TOTO[I] = n;
  95.         copy (SPLIT[I], num);
  96.         I++;
  97.         return;
  98.     }

  99.     for (int i = 0; i <= 9; i++) {
  100.         if (has[i]) continue;
  101.         has[i]   = 1;
  102.         num[lev] = i;
  103.         genTOTO (lev + 1);
  104.         has[i] = 0;
  105.     }
  106. } /* genTOTO */

  107. voi genB (){
  108. // 0b1111000000 => bit(1): 9876, val = 960
  109. // 0123:  0b001111
  110. // 0153:  0b101011
  111. // A & B: 0b001011 = 0b1011(=11), count(1) = 3, $A[11] = 3
  112.     for (int i = 0; i < 961; i++) {
  113.         int count = 0;

  114.         for (int j = 0; j < 10; j++) {
  115.             if (i & (1 << j)) count++;
  116.             if (count > 4) break;
  117.         }
  118.         A_and_B[i] = count > 4 ? 0 : count;
  119.     }
  120. }

  121. voi genAB (){
  122.     for (int i = 0; i < 5040; i++) {
  123.         kar *cha = SPLIT[i];
  124.         int C1   = move1 (cha);

  125.         for (int j = 0; j < 5040; j++) {
  126.             kar *cha2 = SPLIT[j];
  127.             int C2    = move1 (cha2);
  128.             int A     = 0;
  129.             for (int k = 0; k < 4; k++)
  130.                 if (cha[k] == cha2[k]) A++;
  131.             int B = C1 & C2;
  132.             B          = A_and_B[B] - A;
  133.             XAYB[i][j] = (A << 4) | B;
  134.         }
  135.     }
  136. }

  137. inline
  138. voi rehashMaybe (int gue, int ab){
  139.     int I = 0;

  140.     for (int i = 0; i < LEN_MAYBE; i++) {
  141.         if (AB (MAYBE[i], gue) == ab)
  142.             MAYBE[I++] = MAYBE[i];
  143.         else hasMAYBE[MAYBE[i]] = 0;
  144.     }
  145.     LEN_MAYBE = I;
  146. }

  147. inline
  148. int gimme (int lev){
  149.     if (LEN_MAYBE == 1) return MAYBE[0];
  150.     int best = 0;
  151.     dub max  = 999999999.0; // BIG NUM

  152.     for (int i = 0; i < 5040; i++) {
  153.         int test[14] = { 0 };

  154.         for (int j = 0; j < LEN_MAYBE; j++) {
  155.             int ab  = AB (i, MAYBE[j]);
  156.             int pos = INDES[ab];
  157.             test[pos]++;
  158.         }

  159.         dub toto = 0.0;
  160.         for (int i = 0; i < 14; i++)
  161.             if (test[i]) toto += INFO[test[i]];
  162.         if (hasMAYBE[i]) toto -= F2log2;
  163.         if (max > toto) max = toto, best = i;
  164.     }
  165.     return best;
  166. } /* gimme */

  167. voi genIndes (){
  168.     int var[] = { 0, 5, 9, 12, 13 };

  169.     // 0x40 = 4A0B = 64
  170.     // INDES[64] = var[4] + 0 = 13
  171.     for (int a = 0; a <= 4; a++) {
  172.         for (int b = 0; b <= 4; b++) {
  173.             if (a + b > 4) continue;
  174.             int ab = (a << 4) | b;
  175.             int i  = var[a] + b;
  176.             INDES[ab] = i;
  177.             // if (a == 3) break;   /* NO 3A1B */
  178.         }
  179.     }
  180. }
复制代码

您需要登录后才可以回帖 登录 | 注册

本版积分规则

SACC2017购票8.8折优惠进行时

2017中国系统架构师大会(SACC2017)将于10月19-21日在北京新云南皇冠假日酒店震撼来袭。今年,大会以“云智未来”为主题,云集国内外顶级专家,围绕云计算、人工智能、大数据、移动互联网、产业应用等热点领域展开技术探讨与交流。本届大会共设置2大主会场,18个技术专场;邀请来自互联网、金融、制造业、电商等多个领域,100余位技术专家及行业领袖来分享他们的经验;并将吸引4000+人次的系统运维、架构师及IT决策人士参会,为他们提供最具价值的交流平台。
----------------------------------------
优惠时间:2017年8月2日前

活动链接>>
  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP