523066680

回复 16# a2002

   其实这并不妨碍我们线下测试和比较计算机的运算能力。
当然，还是线上更吸引人，更有去写算法的动力，bbaa完全可以在原有的网站基础上搞起。

523066680

回复 57# a2002


    这就尴尬了。

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/min
复制代码

其他优化

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

是否还考虑多线程？

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

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

Edit by 523066680

[Finished in 0.2s]

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/min
复制代码

差不多是2:1

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

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};
    }
}
复制代码

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};
}
复制代码