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

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT HPC论坛 徽章 文库 沙龙 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
1234
最近访问板块 发新帖
楼主: 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-09-08 09:42 |显示全部楼层
本帖最后由 523066680 于 2017-09-08 22:45 编辑

回复 30# rubyish

是一样的。
在用指针数组/数组指针的时候有 char (*str)[4]  和 char *(str[4]) 之分,有时记不住,
习惯每次都加上括号试一下看看。对于明确的二维数组,并没有这样的用法区别,还是不要加的好。

速度变快的原因是搜索树省去了冗余的筛选过程。
bullscows函数和之前的guess_s函数是一样的,strchr我用的不妥,可以改成这样,效率无明显变化:
  1. void bullscows( char target[4], char guess[4], AB *res )
  2. {
  3.     static int idx;
  4.     static int chr;
  5.     res->a = 0;
  6.     res->b = 0;

  7.     for ( idx = 0; idx < 4; idx++ )
  8.     {
  9.         if ( guess[idx] == target[idx] )
  10.             res->a++;
  11.         else
  12.             for ( chr = 0; chr < 4; chr++ )
  13.                 if ( guess[idx] == target[chr] )
  14.                 {
  15.                     res->b++;
  16.                     break;
  17.                 }
  18.     }
  19. }
复制代码

现在我放出最后的资料/参考网站:
这个网站给出了两种优化方案的搜索树,可以在线浏览
crushBullsCows
http://slovesnov.users.sourceforge.net/index.php?bullscows_tree,english,crushBullsCows
avgBullsCows
http://slovesnov.users.sourceforge.net/index.php?bullscows_tree,english,avgBullsCows

avgBullsCows 方案平均回合数 5.213 次
文档
http://slovesnov.users.sourceforge.net/bullscows/bullscows.pdf
源码
bcAll28mar2013ver201.zip

这个实现就相当折腾了,里面好几个方案混合切换着用,特别是3.1节提到的 exact algorithm,时间消耗非常大,实现也相当费脑,等以后再尝试。

论坛徽章:
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-08 10:41 |显示全部楼层
本帖最后由 523066680 于 2017-09-08 22:41 编辑

bcAll28mar2013ver201.zip - bcw/treeAvg5.txt 搜索树转Perl结构 以及 遍历测试
http://ys-i.ys168.com/205774990/p4J4U5J368NI5VUSMhV/treeAvg5_to_PerlStruct.zip

http://523066680.ys168.com/
位置:Perl/猜数字游戏BullsCows/treeAvg5_to_PerlStruct.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-09 03:23 |显示全部楼层
回复 31# 523066680

avgBullsCows 方案平均回合数 5.213 次
yinxiangzhong haoxiang zuixin de shijie jilu shi 5.1X?

# (X keneng shi 6)

论坛徽章:
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-09 03:42 |显示全部楼层
回复 32# 523066680

yanjiu le 1 tian, shouhuo bushao. 3Q ~~

faxian 1 chu:
memset(subset, 0, SIZE);
=> memset(subset, 0, SIZE * sizeof(int));

and this:

  1. typedef struct node {
  2.     char ges[5];
  3.     int count;
  4.     struct node *ab[13];    // move it to END
  5. } Node;

  6. int USEFUL = sizeof(Node) - 13 * sizeof(Node *);

  7. void dump (Node *node, FILE *file) {
  8.     fwrite (node, USEFUL, 1, file);
  9.     ...
  10.    
  11. void load (Node *node, FILE *file) {
  12.     fread (node, USEFUL, 1, file);
  13.     ...
复制代码


tree.dat de size keyi you 1.X M suoxiao dao 342 K

论坛徽章:
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-09 08:41 |显示全部楼层
本帖最后由 523066680 于 2017-09-09 18:44 编辑

回复 34# rubyish

看明白了,省去了指针数据的导出。

那句 memset 可以去掉,因为nsize和子集合是由递归层重新赋值的。

//LinkedList
struct node
{
    char guess[5];
    char count;
    struct node *res[13];
};

count 取值范围 0-13,改用 char 可以把体积缩小到 171kb

论坛徽章:
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-11 00:48 |显示全部楼层
本帖最后由 rubyish 于 2017-09-11 22:26 编辑

回复 35# 523066680

Zai xuehuile maketree de jiqiao zhihou
Shishi perl:

ganxie 523066680. zhidao!! 3Q ~~

update 0m1.166s


final version:

bull.pl

  1. #!/usr/bin/perl
  2. # version 26, subversion 0 (v5.26.0)

  3. use 5.016;    # >= 5.016
  4. sub NUMBER() { 0 }
  5. sub AGAIN()  { 1 }
  6. sub OK()     { 13 }

  7. __INIT__:
  8. print STDERR 'INIT...';
  9. my @NUMBER = collect();
  10. my $GUESS  = guess();

  11. __TEST__:
  12. print STDERR "\rTEST  ";
  13. my $TEST = 5040;
  14. my @COUNT;

  15. =IF_WANT_PRINT
  16. my @AB = (
  17.     0x00, 0x01, 0x02, 0x03, 0x04, 0x10, 0x11,
  18.     0x12, 0x13, 0x20, 0x21, 0x22, 0x30, 0x40,
  19. );
  20. =cut

  21. for my $ans ( 0 .. $TEST - 1 ) {
  22.     my $guess = $GUESS;

  23.     #say "\nA [@{$NUMBER[$ans]}] TEST ", $ans + 1;
  24.     for ( my $telle = 1 ; ; $telle++ ) {
  25.         my $num = $guess->[NUMBER];
  26.         my $that = AB( $ans, $num );

  27.         #printf "$telle [@{$NUMBER[$num]}] AB %02x\n", $AB[$that];
  28.         $COUNT[$telle]++, last if $that == OK;
  29.         $guess = $guess->[AGAIN][$that];
  30.     }
  31. }

  32. print STDERR "\rFINISH\n";
  33. my $TOTO;

  34. for my $i ( 1 .. $#COUNT ) {
  35.     next unless $COUNT[$i];
  36.     say "$i\t$COUNT[$i]";
  37.     $TOTO += $i * $COUNT[$i];
  38. }

  39. say "\nTEST\t= $TEST";
  40. say "GUESS\t= $TOTO ";
  41. printf "AVE\t= %.3f\n", $TOTO / $TEST;

  42. # ____________________SUB____________________
  43. sub guess {
  44.     my $guess = [];
  45.     my $fun   = sub {
  46.         my ( $guess, $maybe ) = @_;
  47.         my $num = $maybe->[0];
  48.         $guess->[NUMBER] = $num;
  49.         my @next;
  50.         for my $may (@$maybe) {
  51.             my $ab = AB( $num, $may );
  52.             push @{ $next[$ab] }, $may;
  53.         }
  54.         for my $ab ( 0 .. 12 ) {
  55.             next unless $next[$ab];
  56.             __SUB__->( $guess->[AGAIN][$ab] = [], $next[$ab] );
  57.         }
  58.     };
  59.     $fun->( $guess, [ 0 .. 5040 - 1 ] );
  60.     return $guess;
  61. }

  62. sub AB {
  63.     state $val = [ 0, 5, 9, 12, 13 ];
  64.     my ( $N1, $N2 ) = @NUMBER[@_];
  65.     my ( $A, $B ) = ( 0, 0 );

  66.     for my $i ( 0 .. 3 ) {
  67.         $A++, next if $N1->[$i] == $N2->[$i];
  68.         for my $j ( 0 .. 3 ) {
  69.             $B++, last if $N1->[$i] == $N2->[$j];
  70.         }
  71.     }
  72.     $val->[$A] + $B;
  73. }

  74. sub collect {
  75.     sub {
  76.         my ( $a, $b ) = @_;
  77.         return $b if @$b == 4;
  78.         map __SUB__->( [ @$a[ 0 .. $_ - 1, $_ + 1 .. $#$a ] ],
  79.             [ @$b, $a->[$_] ] ), 0 .. $#$a;
  80.       } ->( [ 0 .. 9 ], [] );
  81. }

  82. __DATA__
  83. $_
复制代码


评分

参与人数 1信誉积分 +8 收起 理由
523066680 + 8 效率好高!

查看全部评分

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

本版积分规则

10张SACC2017门票等你来拿~

在数字化转型时代,云已成为万物智能的数字化大脑。而随着大数据应用、人工智能、移动互联网等技术的飞速发展,“智慧 +” 的概念正在深入到各行各业,提升企业效率,释放商业潜能,创造全新机遇。作为国内顶级技术盛会之一,2017 中国系统架构师大会(SACC2017)将于 10 月 19-21 日在北京新云南皇冠假日酒店震撼来袭。今年,大会以 “云智未来” 为主题,云集国内外顶级专家,围绕云计算、人工智能、大数据、移动互联网、产业应用等热点领域展开技术探讨与交流。本届大会共设置 2 大主会场,18 个技术专场;邀请来自互联网、金融、制造业、电商等多个领域,100 余位技术专家及行业领袖来分享他们的经验;并将吸引 4000 + 人次的系统运维、架构师及 IT 决策人士参会,为他们提供最具价值的交流平台。
----------------------------------------
优惠时间:2017年10月19日前

活动链接>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP