[新手上路]批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动[批处理精品]CMD命令50条不能说的秘密[在线下载]第三方命令行工具[在线帮助]VBScript / JScript 在线参考
返回列表 发帖
本帖最后由 PakTC 于 2017-7-28 23:30 编辑

提供一点资料
www.cs.nccu.edu.tw/~chaolin/papers/science3203.pdf
这个文档是中文的,讲了两个数字游戏,关于这次的游戏的分析和解法在后半部分。

另外给准备做这道题但是还未实践的小伙伴提一些建议:
服务器响应蛮快的,不要让程序在运算和筛选上面过多耗时,
尽量使用速度更快的语言,如果一定要用脚本,空间换时间吧。
1

评分人数

Press Any Key To Continue...

TOP

回复 70# PakTC


    最大的时间消耗应该都是网络IO上,直觉用什么语言差异都不大。算法和方法才有影响。
去学去写去用才有进步。安装python3代码存为xx.py 双击运行或右键用IDLE打开按F5运行

TOP

一点分析

本帖最后由 523066680 于 2017-7-29 08:55 编辑

前面是个误会,链接的问题实在不应该,我们反复问楼主群号,他反复回答是在主题蓝色的链接里,
而楼主发的网站链接恰恰没有打上 url 标签,所以不是蓝色的,只有百度百科是蓝色的。
大写的懵(每一次看回复都是黑人问号脸)!

知道链接后就去试了,游戏规则之一是,post 4位不重复的数字测试结果。数字少了不行。
试了一阵子发现可以用字母做占位符,这个时候还不知道筛选法。

多线程?

      第一个思路,跑10个线程,"0ABC","1ABC","2ABC" ... "9ABC",等10个线程返回,
      会得到1个 A1B0 和 3个A0B1 。也就是这10个里必然有一个位置正确,3个数字正确但位置不正确。
      将3个B1取出,可以排6种情况,A1在开头,6个线程出去就有结果了。

      优化空间

          如果提前得到1个A1 和3个B1,线程可以提前kill掉。
          第二轮6个排列出去,如果提前出现A4B0,可以提前kill线程,进入下个回合。

      结果

          刚开始 Scallop 没在跑,这方法大概是20/min的抢答速度。当他的程序跑起来的时候,
          线程严重阻塞,10个线程都返回的时候 tokens 变了 3 到 4 次

筛选法

      后面才搞清楚百科提到的筛选法,比较固执没去看,多亏happy66r指教。

      先派出"0123"去试探,假设返回是A0B1,用5040个排列情况去和这个0123做比较,找出也是 A0B1 的排列,
      这个时候缩小到 1440 种排列(可参考PAKTC提供的文档),答案就在这里面。
      从1440中挑选一个去试探,假设是3987, 返回A0B2;再用1439个元素(去掉了3987)和 3987碰撞,筛选出
      结果为A0B2的组合,这个有多少就交给程序了~
      重复这个过程,备用组合不断缩小,最后得到A4B0。

      这种方法需要自己写一个测试函数,返回AB数值。
      试过所有情况,平均5.5次猜中一次,有优化空间,参考百度。

      效率

          用的Perl脚本,反复的数组操作和测试函数的调用消耗较大。假设post来回0.1秒,第一轮5040个测试
          跑了0.3秒,别人已经三个post来回了。做了一些修改,

          目前 Scallop 和 vic3 的猜题速度大概是 4:1 到 5:1,有空继续优化。
          1. Scallop    77453 + 38    226.2/min
          2. vic3       20333 + 13    77.4/min
          3. bbaa         238 + 0     0.0/min
          4. TJUGERKFER    21 + 0     0.0/min
          5. Scallop    77453 + 79    235.5/min
          6. vic3       20333 + 19    56.6/min
          7. bbaa         238 + 0     0.0/min
          8. TJUGERKFER    21 + 0     0.0/min
          复制代码
      其他优化

          tokens 变化的时候,可以用当前反馈的数据更新筛选数组,接着跑;重置的话基本错过一个回合。

是否还考虑多线程?

      由于现在服务端的处理机制(据说现在是文本存数据),我发现排队发送阻塞还少一点,多线程阻塞严重。
      如果一定要多线程,参考前面提到的,单线程平均5.x次就能猜中一个。所以多线程不要超过5。假设是5线程,
      第二回合你就该算出结果,不要超过两回合,别人已经刷了几个答案了。

      当然了,如果服务端改了方案,多线程的利弊会有所改变。

Edit by 523066680
    [Finished in 0.2s]

    TOP

    本帖最后由 avgBullsCows 于 2017-7-29 10:33 编辑

    我想试试这棵树

    http://slovesnov.users.sourceforge.net/index.php?bullscows_tree,english,avgBullsCows

    这棵树的生成脚本

    http://slovesnov.users.sourceforge.net/scripts/bullscows.js
    1. 整个脚本文件 1000+ 行, 就不贴了
    复制代码
    1

    评分人数

    TOP

    本帖最后由 523066680 于 2017-7-29 14:33 编辑

    回复 73# avgBullsCows

    avgBullsCows 好像是跑可重复数字的,平均速度4.x, crusBullsCows 是不可重复4位数字的,平均速率 5.25 和百度提到的一样
        http://slovesnov.users.sourcefor ... lish,crushBullsCows

    更新一下现在的情况,还是 JAVA 对 PERL
    1. Scallop    208598 + 1351  172.0/min
    2. vic3       45021 + 722   91.9/min
    3. bbaa         238 + 0     0.0/min
    4. TJUGERKFER    55 + 0     0.0/min
    5. adad          27 + 0     0.0/min
    复制代码
    差不多是2:1

    另一个对比,分别 POST 网站 1000次,java 耗时大约52秒,perl 耗时大约64秒。

    TOP

    回复 74# 523066680
    1. An secret number for bulls-cows game can be four-place decimal with different
    2. digits from 0 to 9. Total amount of secret numbers is 10!/6! = 5040. For
    3. mastermind secret number is four-place digital with digits from 0 to 5. Digits
    4. can repeat. So total amount of secret numbers is 6^4 = 1296. In common case
    5. such games have three parameters - number of positions, number of different
    6. digits and repeatability (1 - yes, 0 -no). From this point of view bulls-cows game
    7. has parameters (4, 10, 0), mastermind has parameters (4, 6, 1). Optimization
    8. of two game types has two directions.
    复制代码
    我的理解是 bulls-cows 游戏是 参数描述(4, 10, 0) 4个位置, 10个符号, 符号不可重复
    mastermind 参数描述(4, 6, 1) 4个位置, 6个符号, 符号可重复

    不论哪种游戏, 算法优化有两个目标方向
    1. The goal is to find algorithm which minimizes amount of secret numbers which algorithm can guess ...
    复制代码
    crush 算法的优化目标, 搜索树空间回合总数最小化
    1. The second criterion is minimize average amount of turns for guess arbitrary secret number - minimal average game length
    复制代码
    avg 算法的优化目标, 平均搜索回合数(平均游戏长度)最小化
    1

    评分人数

      • 523066680: 感谢你提供的搜索树,帮大忙了PB + 12

    TOP

    观察比赛各玩家猜题速度的脚本。
    1. =info
    2.     Auth: 523066680
    3.     Date: 2017-07
    4. =cut
    5. use JSON;
    6. use Encode;
    7. use Data::Dumper;
    8. use Try::Tiny;
    9. use Time::HiRes qw/time sleep/;
    10. use IO::Handle;
    11. STDOUT->autoflush(1);
    12. use LWP::Simple;
    13. use LWP::UserAgent;
    14. our $user = "vic3";
    15. our $pass = "tempcode";
    16. our $website = 'http://www.codetiger.win/extra/score.json';
    17. our $ua = LWP::UserAgent->new(  agent => 'Mozilla/5.0', timeout => 3 );
    18. my %ever;
    19. my %current;
    20. getData( \%ever );
    21. my $count = 0;
    22. my $delta;
    23. my $speed;
    24. my $time_a = time();
    25. while (1)
    26. {
    27.     getData(\%current);
    28.     $count = 0;
    29.     for my $k (reverse sort { $ever{$a} <=> $ever{$b} } keys %ever)
    30.     {
    31.         $delta = $current{$k} - $ever{$k};
    32.         $speed = $delta / (time() - $time_a) * 60.0;
    33.         printf "%-10s %5d + %-5d %.1f/min\n",
    34.             encode('gbk',  $k),
    35.             $ever{$k},
    36.             $delta,
    37.             $speed
    38.             ;
    39.         last if ($count++ > 5);
    40.     }
    41.     print "\n";
    42.     sleep 10.0;
    43. }
    44. sub getData
    45. {
    46.     my $href = shift;
    47.     my $res;
    48.     my $data;
    49.     while (1)
    50.     {
    51.         $res = $ua->get( $website );
    52.         try { $data = decode_json( $res->content ); last; }
    53.         catch { sleep 2.0; printf "repeat\n" }
    54.     }
    55.     for my $name ( keys %$data )
    56.     {
    57.         $href->{$name} = $data->{$name};
    58.     }
    59. }
    复制代码

    TOP

    本帖最后由 523066680 于 2017-8-4 22:30 编辑

    回复 64# avgBullsCows

        感谢neo提供的最优搜索树,省去了筛选+处理数组的过程,本地效率大大提升。(后来我发现这个问题即使运行时效率提高了,网络不熟悉的话还是要吃大亏啊)
    读取 JSON 进行刷题的 Perl 代码:
    1. =info
    2. 523066680 2017-08
    3. =cut
    4. use JSON;
    5. use IO::Handle;
    6. use File::Slurp;
    7. use LWP::UserAgent;
    8. use Data::Dumper;
    9. use Time::HiRes qw/sleep/;
    10. STDOUT->autoflush(1);
    11. our $user = "vic3";
    12. our $pass = "tempcode";
    13. our $website = 'http://www.codetiger.win/extra/API.php';
    14. our $ua = LWP::UserAgent->new(  keep_alive=>1, agent => 'Mozilla/5.0', timeout => 0.2 );
    15. my $json;
    16. my $tree;
    17. $json = read_file("crushBullsCows.json");
    18. $json=~s/\'/\"/g;
    19. $tree = decode_json($json);
    20. AGAIN:
    21. my $ref = $tree;
    22. my $guess = $ref->{'xx'};
    23. my $AB;
    24. my ($curr, $prev) = (undef, undef);
    25. while (1)
    26. {
    27. ($AB, $curr) = post_num( $guess );
    28.     print " [$AB] [ $guess ] $curr\n";
    29.     if ( $AB eq "40" ) {
    30.         print "Success $guess\n\n";
    31.         last;
    32.     }
    33.     if (defined $prev and ($curr ne $prev) )
    34.     {
    35.         print "Tokens changed\n [$AB] [ @$guess ] $curr\n";
    36.         goto AGAIN;
    37.     }
    38.     #update guess number, and $ref
    39. for my $e ( @{$ref->{'c'}})
    40. {
    41. if ( exists $e->{$AB} )
    42. {
    43. #print $e->{$AB};
    44. $guess = $e->{$AB};
    45. $ref = $e;
    46. last;
    47. }
    48. }
    49.     $prev = $curr;
    50. }
    51. goto AGAIN;
    52. sub post_num
    53. {
    54.     our($ua, $website, $user, $pass);
    55.     my $n = shift;
    56.     my $res;
    57.     my $data;
    58.     my $text;
    59.     while (1)
    60.     {
    61.         $res =
    62.             $ua->post(
    63.                 $website,
    64.                 [ username=>$user, password =>$pass, number=>$n, send=>'answer' ]
    65.             );
    66.         $text = $res->content();
    67.         if ( $text =~/"A":\d,"B":\d/ ) { last }
    68.         print ".";
    69.         sleep 0.01;
    70.     }
    71.     #print $res->content(), " - $n\n";
    72.     $data = decode_json( $res->content() );
    73.     return $data->{A} . $data->{B}, $data->{tokens};
    74. }
    复制代码

    TOP

    返回列表