PakTC

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

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

codegay

回复 70# PakTC


    最大的时间消耗应该都是网络IO上，直觉用什么语言差异都不大。算法和方法才有影响。

523066680

前面是个误会，链接的问题实在不应该，我们反复问楼主群号，他反复回答是在主题蓝色的链接里，
而楼主发的网站链接恰恰没有打上 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，有空继续优化。

Scallop    77453 + 38    226.2/min
vic3       20333 + 13    77.4/min
bbaa         238 + 0     0.0/min
TJUGERKFER    21 + 0     0.0/min
 
Scallop    77453 + 79    235.5/min
vic3       20333 + 19    56.6/min
bbaa         238 + 0     0.0/min
TJUGERKFER    21 + 0     0.0/minCOPY

其他优化

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

是否还考虑多线程？

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

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

Edit by 523066680

[Finished in 0.2s]

avgBullsCows

我想试试这棵树

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

这棵树的生成脚本

http://slovesnov.users.sourceforge.net/scripts/bullscows.js

整个脚本文件 1000+ 行, 就不贴了COPY

523066680

回复 73# avgBullsCows

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

更新一下现在的情况，还是 JAVA 对 PERL

Scallop    208598 + 1351  172.0/min
vic3       45021 + 722   91.9/min
bbaa         238 + 0     0.0/min
TJUGERKFER    55 + 0     0.0/min
adad          27 + 0     0.0/minCOPY

差不多是2:1

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

avgBullsCows

回复 74# 523066680

An secret number for bulls-cows game can be four-place decimal with different
digits from 0 to 9. Total amount of secret numbers is 10!/6! = 5040. For
mastermind secret number is four-place digital with digits from 0 to 5. Digits
can repeat. So total amount of secret numbers is 6^4 = 1296. In common case
such games have three parameters - number of positions, number of different
digits and repeatability (1 - yes, 0 -no). From this point of view bulls-cows game
has parameters (4, 10, 0), mastermind has parameters (4, 6, 1). Optimization
of two game types has two directions.COPY

我的理解是 bulls-cows 游戏是 参数描述(4, 10, 0) 4个位置, 10个符号, 符号不可重复
mastermind 参数描述(4, 6, 1) 4个位置, 6个符号, 符号可重复

不论哪种游戏, 算法优化有两个目标方向

 The goal is to find algorithm which minimizes amount of secret numbers which algorithm can guess ...COPY

crush 算法的优化目标, 搜索树空间回合总数最小化

 The second criterion is minimize average amount of turns for guess arbitrary secret number - minimal average game lengthCOPY

avg 算法的优化目标, 平均搜索回合数(平均游戏长度)最小化

523066680

观察比赛各玩家猜题速度的脚本。

=info
    Auth: 523066680
    Date: 2017-07
=cut
 
use JSON;
use Encode;
use Data::Dumper;
use Try::Tiny;
use Time::HiRes qw/time sleep/;
use IO::Handle;
STDOUT->autoflush(1);
 
use LWP::Simple;
use LWP::UserAgent;
 
our $user = "vic3";
our $pass = "tempcode";
our $website = 'http://www.codetiger.win/extra/score.json';
our $ua = LWP::UserAgent->new(  agent => 'Mozilla/5.0', timeout => 3 );
 
my %ever;
my %current;
getData( \%ever );
 
my $count = 0;
my $delta;
my $speed;
my $time_a = time();
 
while (1)
{
    getData(\%current);
 
    $count = 0;
    for my $k (reverse sort { $ever{$a} <=> $ever{$b} } keys %ever)
    {
        $delta = $current{$k} - $ever{$k};
        $speed = $delta / (time() - $time_a) * 60.0;
 
        printf "%-10s %5d + %-5d %.1f/min\n", 
            encode('gbk',  $k), 
            $ever{$k}, 
            $delta,
            $speed
            ;
 
        last if ($count++ > 5);
    }
    print "\n";
 
    sleep 10.0;
}
 
sub getData
{
    my $href = shift;
    my $res;
    my $data;
 
    while (1)
    {
        $res = $ua->get( $website );
        try { $data = decode_json( $res->content ); last; }
        catch { sleep 2.0; printf "repeat\n" }
    }
 
    for my $name ( keys %$data )
    {
        $href->{$name} = $data->{$name};
    }
}COPY

523066680

回复 64# avgBullsCows

    感谢neo提供的最优搜索树，省去了筛选+处理数组的过程，本地效率大大提升。（后来我发现这个问题即使运行时效率提高了，网络不熟悉的话还是要吃大亏啊）
读取 JSON 进行刷题的 Perl 代码：

=info
523066680 2017-08
=cut
 
use JSON;
use IO::Handle;
use File::Slurp;
use LWP::UserAgent;
use Data::Dumper;
use Time::HiRes qw/sleep/;
STDOUT->autoflush(1);
 
our $user = "vic3";
our $pass = "tempcode";
our $website = 'http://www.codetiger.win/extra/API.php';
our $ua = LWP::UserAgent->new(  keep_alive=>1, agent => 'Mozilla/5.0', timeout => 0.2 );
 
my $json;
my $tree;
$json = read_file("crushBullsCows.json");
$json=~s/\'/\"/g;
$tree = decode_json($json);
 
AGAIN:
my $ref = $tree;
my $guess = $ref->{'xx'};
my $AB;
my ($curr, $prev) = (undef, undef);
 
while (1)
{
	($AB, $curr) = post_num( $guess );
    print " [$AB] [ $guess ] $curr\n";
 
    if ( $AB eq "40" ) {
        print "Success $guess\n\n";
        last;
    }
 
    if (defined $prev and ($curr ne $prev) ) 
    { 
        print "Tokens changed\n [$AB] [ @$guess ] $curr\n";
        goto AGAIN;
    }
 
    #update guess number, and $ref 
	for my $e ( @{$ref->{'c'}})
	{
		if ( exists $e->{$AB} )
		{
			#print $e->{$AB};
			$guess = $e->{$AB};
			$ref = $e;
			last;
		} 
	}
    $prev = $curr;
}
 
goto AGAIN;
 
sub post_num
{
    our($ua, $website, $user, $pass);
    my $n = shift;
    my $res;
    my $data;
    my $text;
 
    while (1)
    {
        $res = 
            $ua->post( 
                $website,
                [ username=>$user, password =>$pass, number=>$n, send=>'answer' ]
            );
        $text = $res->content();
        if ( $text =~/"A":\d,"B":\d/ ) { last }
        print ".";
        sleep 0.01;
    }
 
    #print $res->content(), " - $n\n";
    $data = decode_json( $res->content() );
    return $data->{A} . $data->{B}, $data->{tokens};
}COPY