免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
1234下一页
最近访问板块 发新帖
查看: 9604 | 回复: 35

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

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

在线猜数字游戏链接:http://www.codetiger.win/extra/

先注册账号,然后通过 post 提交并获取返回的数据,像这样
  1. $res = $ua->post(
  2.        $website,
  3.        [ username=>$user, password =>$pass, number=>$n, send=>'answer' ]
  4. );
复制代码

返回 JSON 格式的参考数据:
{"code":150,"A":0,"B":2,"count":49721,"tokens":"8550662099813553"}

游戏规则和JSON参数说明请见主页(这个网站和竞赛是一个小朋友搞的,后生可畏)

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

---------------------------------------------------------------------------------------

基础的解题方案可以参考上面给出的PDF的后半部分。
服务器随机生成 [0-9] 组成的 4 位不重复数字(可以是0开头)。按照概率知识,可以有 10*9*8*7 = 5040 种情况

假设 服务器生成的谜底数字是 9567 ,我们post过去的数字是 0123, 则返回 A = 0, B = 0
如果提交的数字是 9276,则返回 A = 1, B = 2 表示1个数字位置和内容相同;有两个数字位置不对,但数值相同。

最基本的猜数策略在PDF中有给出,例如 Post 提交的数字是 0123,返回 A = 0,B = 3
我们可以将所有可能的数字集合 5039 种排列(不含0123)和 0123 碰撞,产生14种 AB 值,筛选出 A0B3 的同类排列,暂时称为子集合S,
答案就在S的元素中(因为这些数字和0123碰撞测试,也产生A0B3)。

第二回合从S中取一个数字 t ,POST给服务器,根据返回的AB值,进一步缩小集合(找出和数字t碰撞后反馈同为 AB 的子集)。。。以此类推
直到猜中为止。

猜题者请注意判断服务器返回的 tokens ,如果猜题过程中 tokens 产生变化,说明这一回合的目标已经被别人猜中了。(也可能是自己猜中了~)

当然,这只是基础策略,还有很大优化空间。

论坛徽章:
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-08-09 02:56 |显示全部楼层
KBD?
min MAX, or min average???

论坛徽章:
12
子鼠
日期:2014-10-11 16:46:482016科比退役纪念章
日期:2018-03-16 10:24:0515-16赛季CBA联赛之山东
日期:2017-11-10 14:32:142016科比退役纪念章
日期:2017-09-02 15:42:4715-16赛季CBA联赛之佛山
日期:2017-08-28 17:11:5515-16赛季CBA联赛之浙江
日期:2017-08-24 16:55:1715-16赛季CBA联赛之青岛
日期:2017-08-17 19:55:2415-16赛季CBA联赛之天津
日期:2017-06-29 10:34:4315-16赛季CBA联赛之四川
日期:2017-05-16 16:38:55黑曼巴
日期:2016-07-19 15:03:112015亚冠之萨济拖拉机
日期:2015-05-22 11:38:5315-16赛季CBA联赛之北京
日期:2019-08-13 17:30:53
发表于 2017-08-09 14:51 |显示全部楼层
本帖最后由 523066680 于 2017-08-23 11:52 编辑

回复 2# rubyish

我先举一个本地猜数字的例子(包含一个测试盒子,guess 函数),写的比较粗糙:

  1. use IO::Handle;
  2. STDOUT->autoflush(1);

  3. our @nums;
  4. our $nums;
  5. generate(\@nums);                       #初始化随机4位数
  6. $nums = join("", @nums);

  7. our @orders;
  8. permute( [0 .. 9] , [], 4, \@orders);   #0-9取4个数的所有组合

  9. print "Rand Number: $nums\n";

  10. my $AB;
  11. my $guess = "0123";

  12. while (1)
  13. {
  14.     $AB = guess( $nums, $guess );
  15.     print "$guess - $AB\n";
  16.     last if ( $AB eq "40" );

  17.     reduce( \@orders, $guess, $AB );    #缩小可选数组的范围
  18.     $guess = shift @orders;
  19. }

  20. =function
  21.     reduce   根据反馈的AB值,缩小集合范围
  22.     guess    测试盒,给出两个数字,返回 AB 值
  23.     generate 生成4位不重复的随机数
  24.     permute  生成 0-9 排成 4位数(不重复)的所有组合
  25. =cut

  26. sub reduce
  27. {
  28.     my ($oref, $guess, $AB) = @_;
  29.     my @temparr;
  30.     my $TAB;
  31.     my $idx = 0;

  32.     for my $e ( @$oref )
  33.     {
  34.         $TAB = guess( $e, $guess );
  35.         push @temparr, $e if ( $TAB eq $AB );
  36.     }

  37.     @$oref = @temparr;
  38. }

  39. sub guess
  40. {
  41.     my ($nums, $guess) = @_;

  42.     my @nums = split("", $nums);
  43.     my @guess = split("", $guess);

  44.     my ($A, $B) = (0, 0);

  45.     for my $i ( 0 .. $#guess )
  46.     {
  47.         if ( $guess[$i] == $nums[$i] )
  48.         {
  49.             $A++;
  50.         }
  51.         else
  52.         {
  53.             $B++ if ( $nums =~/$guess[$i]/ );
  54.         }
  55.     }

  56.     return $A . $B;
  57. }

  58. sub generate
  59. {
  60.     #从10个数字中随机挑选出4个
  61.     my $aref = shift;
  62.     my $len = 4;
  63.     my [url=home.php?mod=space&uid=17981]@ele[/url] = (0..9);
  64.     my $range = 10;
  65.     my $get;

  66.     for ( 1 .. $len )
  67.     {
  68.         $get = int(rand($range));
  69.         push @$aref, $ele[$get];
  70.         splice(@ele, $get, 1);
  71.         $range--;
  72.     }
  73. }

  74. sub permute
  75. {
  76.     my ( $a, $b, $n, $aref ) = @_;
  77.     my $last = $#$a;

  78.     if ( $#$b >= ($n-1) )
  79.     {
  80.         push @$aref, join("", @$b);
  81.         return;
  82.     }

  83.     for my $idx ( 0 .. $last )
  84.     {
  85.         permute( [ @$a[0 .. $idx-1, $idx+1 .. $last] ], [ @$b, $a->[$idx] ], $n, $aref );
  86.     }
  87. }
复制代码

输出样板
Rand Number: 0954
0123 - 10
0456 - 21
0467 - 11
0586 - 11
0954 - 40

评分

参与人数 1信誉积分 +10 收起 理由
rubyish + 10 3Q~~ XXle

查看全部评分

论坛徽章:
12
子鼠
日期:2014-10-11 16:46:482016科比退役纪念章
日期:2018-03-16 10:24:0515-16赛季CBA联赛之山东
日期:2017-11-10 14:32:142016科比退役纪念章
日期:2017-09-02 15:42:4715-16赛季CBA联赛之佛山
日期:2017-08-28 17:11:5515-16赛季CBA联赛之浙江
日期:2017-08-24 16:55:1715-16赛季CBA联赛之青岛
日期:2017-08-17 19:55:2415-16赛季CBA联赛之天津
日期:2017-06-29 10:34:4315-16赛季CBA联赛之四川
日期:2017-05-16 16:38:55黑曼巴
日期:2016-07-19 15:03:112015亚冠之萨济拖拉机
日期:2015-05-22 11:38:5315-16赛季CBA联赛之北京
日期:2019-08-13 17:30:53
发表于 2017-08-17 10:41 |显示全部楼层

反馈指标

本帖最后由 523066680 于 2017-08-23 11:54 编辑

遍历测试:
  1. Times: 26751, average: 5.307738
  2. 1, 1
  3. 2, 11
  4. 3, 80
  5. 4, 556
  6. 5, 2277
  7. 6, 1929
  8. 7, 183
  9. 8, 3
复制代码

论坛徽章:
0
发表于 2017-08-24 13:03 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽

论坛徽章:
12
子鼠
日期:2014-10-11 16:46:482016科比退役纪念章
日期:2018-03-16 10:24:0515-16赛季CBA联赛之山东
日期:2017-11-10 14:32:142016科比退役纪念章
日期:2017-09-02 15:42:4715-16赛季CBA联赛之佛山
日期:2017-08-28 17:11:5515-16赛季CBA联赛之浙江
日期:2017-08-24 16:55:1715-16赛季CBA联赛之青岛
日期:2017-08-17 19:55:2415-16赛季CBA联赛之天津
日期:2017-06-29 10:34:4315-16赛季CBA联赛之四川
日期:2017-05-16 16:38:55黑曼巴
日期:2016-07-19 15:03:112015亚冠之萨济拖拉机
日期:2015-05-22 11:38:5315-16赛季CBA联赛之北京
日期:2019-08-13 17:30:53
发表于 2017-08-24 16:15 |显示全部楼层
本帖最后由 523066680 于 2017-08-24 18:36 编辑

回复 5# 本友会机友会摄友会

哈哈哈,怂了吧,真碰到题目还是不敢来了,算法固定的?优化算法去查了没有?
敢不敢实现一个先跑起来?最坏情况指标、平均情况指标、反馈个数指标 这些都懂?
踢馆要是只有这种水平,就不要出来丢 powershell 的脸了

比赛方式;
比猜题速率,线下各自使用程序统计不同的用户每分钟猜中多少次。设定一个截止日期结束比赛,参加者可以在结束前不断优化算法以提高猜题速率。

Get 这个地址可以获得当前时间每个用户的猜中次数,从而统计猜题速度
http://www.codetiger.win/extra/score.json
{"adad":194301,"vic3":160852,"BatchScript":89139,"coadsa":850,"robot":397,"llsd":139,"sdafasdf":75,"sfwfssf":0,"1111111111":0}


关于公平性:
网站是一个深圳中学生建的,我这里 ping 该网站的返回结果是(体现了网络响应速度):
正在 Ping www.codetiger.win [43.251.105.212] 具有 32 字节的数据:
来自 43.251.105.212 的回复: 字节=32 时间=13ms TTL=54
来自 43.251.105.212 的回复: 字节=32 时间=12ms TTL=54
来自 43.251.105.212 的回复: 字节=32 时间=14ms TTL=54
来自 43.251.105.212 的回复: 字节=32 时间=15ms TTL=54

即使不敢应战,起码跑个本地的让我们瞧瞧 powershell 的强大?


论坛徽章:
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-08-30 03:00 |显示全部楼层
回复 6# 523066680

根据计算机测算,如果采用严谨的猜测策略,任何数字最多7次就可猜出(即达到 4A0B)。

Caiyong Pusude xiefa: Faxian you gaoda 8, 9 ci de

  1. my @new = grep { ... } @old;
复制代码

7 ci shi ruhe dacheng de?


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

回复 7# rubyish

估值。
普通的筛选法,是在每一层,在可选元素中选第一个,没有任何优化。
这种方案测完5040种情况的统计结果大致如下,平均需要猜 5.56 次:
  1. Times: 28024, average: 5.560317
  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
复制代码

如果在每一层,我们在可选数字中,做一些判断,把判断为较好的数字选为下次测试的数字,最大回合数/平均回合数就能减少。
比如百度百科提到的最大反馈指标:用子集合中的每一个元素去碰撞集合,看哪一个数字碰撞时得到更多的反馈类型
举个例子,当前缩小集合是 S = (1032,1230,1302,2031,2301,2310,3012,3201,3210)
用这些元素分别碰撞整个数组,得到不同的反馈,反馈越多的,说明下一层子集合的平均量越小。(当前总数/反馈数)
1032 - 04,22,40
1230 - 04,22,13,40
1302 - 04,13,22,40
2031 - 13,04,40,22
2301 - 04,22,40
2310 - 22,13,04,40
3012 - 04,22,13,40
3201 - 04,13,22,40
3210 - 04,22,40

按这种方案,可以选 1230,1302,2310,3012,3201 中的一个。当然,还可以进一步优化,做更准确的的评估。
以及碰撞的集合不一定是在 S集合内,可以是整个5040种排列和 S集合碰撞

使用最大反馈估值(在较高估值的结果中选第一项),测试结果是:
  1. Times: 27139, average: 5.384722
  2. 1, 1
  3. 2, 3
  4. 3, 44
  5. 4, 515
  6. 5, 2124
  7. 6, 2151
  8. 7, 202
复制代码



论坛徽章:
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-08-31 03:21 |显示全部楼层
本帖最后由 rubyish 于 2017-08-31 00:58 编辑

回复 8# 523066680


1 1
2 9
3 44
4 344
5 1831
6 2480
7 331

AVE = 5.531548

real    23m15.507s
user    23m13.891s
sys        0m0.697s


Queshi zai 7 ci zhinei
Wode ave shi 5.53
Nide shi 5.38

Question:
1: Ruhe dadao 5.38 de ave?
2: 23m, taimanle, ruhe OPT?

3Q~~

  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 show(a)    printf ("[ %d%d%d%d ]", a[0], a[1], a[2], a[3]);
  7. # define copy(A, B) memcpy (A, B, 4)
  8. # define COPY(A, B) memcpy (A, B, 20160)
  9. // 20160 == 5040 * 4
  10. # define TEST 5040

  11. typedef char kar;

  12. kar TOTO[5040][4];
  13. kar MAYBE[5040][4];
  14. int COUNT[15];
  15. int LEN;


  16. int AB (kar*, kar*);
  17. void make (int);
  18. kar* gimme (void);
  19. void grep (kar*, int);
  20. void test (void);

  21. /* ____________________ MAIN ____________________ */
  22. int main (){
  23.     make (0);
  24.     test ();
  25. }

  26. /* _____________________ SUB _____________________ */
  27. void test () {
  28.     for (int v = 0; v < TEST; v++) {
  29.         printf ("%d\n", v + 1);
  30.         COPY (MAYBE, TOTO);
  31.         kar *ans = TOTO[v];
  32.         kar *gue = TOTO[0];
  33.         LEN = 5040;
  34.         // show (ans);
  35.         // puts ("");
  36.         int x;
  37.         for (x = 1; x < 15; x++) {
  38.             // show (gue);
  39.             int ab = AB (ans, gue);
  40.             // int a  = get_a (ab);
  41.             // int b  = get_b (ab);
  42.             // printf (" %d AB = %d %d\n", x, a, b);
  43.             if (ab == OK) break;
  44.             grep (gue, ab);
  45.             gue = gimme ();
  46.         }
  47.         COUNT[x]++;
  48.     }
  49.     puts ("-----------------");
  50.     int ave = 0;
  51.     for (int i = 1; i < 15; i++) {
  52.         printf ("%d\t%d\n", i, COUNT[i]);
  53.         ave += i * COUNT[i];
  54.     }
  55.     printf ("AVE = %f\n", ave / (double)TEST);
  56. }

  57. void grep (kar *gue, int ab){
  58.     int I = 0;

  59.     for (int i = 0; i < LEN; i++) {
  60.         int ab2 = AB (MAYBE[i], gue);
  61.         if (ab2 == ab)
  62.             copy (MAYBE[I++], MAYBE[i]);
  63.     }
  64.     LEN = I;
  65. }

  66. kar* gimme (){
  67.     static int var[] = { 0, 5, 9, 12, 14 };

  68.     if (LEN == 1) return MAYBE[0];
  69.     int best = 0;
  70.     int max  = 0;
  71.     for (int i = 0; i < 5040; i++) {
  72.         int test[15] = { 0 };
  73.         for (int j = 0; j < LEN; j++) {
  74.             int ab = AB (TOTO[i], MAYBE[j]);
  75.             int a  = get_a (ab);
  76.             int b  = get_b (ab);
  77.             int I  = var[a] + b;
  78.             test[I]++;
  79.         }
  80.         int toto = 0;
  81.         for (int i = 0; i < 15; i++)
  82.             if (test[i]) toto++;

  83.         if (toto > max) {
  84.             max  = toto;
  85.             best = i;
  86.         }
  87.     }
  88.     return TOTO[best];
  89. }

  90. int AB (kar *ans, kar *gue){
  91.     int ab[2] = { 0 };

  92.     for (int i = 0; i < 4; i++) {
  93.         if (ans[i] == gue[i]) ab[0]++;
  94.         else
  95.             for (int j = 0; j < 4; j++)
  96.                 if (ans[i] == gue[j]) ab[1]++;
  97.     }
  98.     return (ab[0] << 4) | ab[1];
  99. }

  100. void make (int lev){
  101.     static kar num[4];
  102.     static int I = 0;
  103.     static int has[10];

  104.     if (lev == 4) {
  105.         copy (TOTO[I++], num);
  106.         return;
  107.     }

  108.     for (int i = 0; i <= 9; i++) {
  109.         if (has[i]) continue;
  110.         has[i]   = 1;
  111.         num[lev] = i;
  112.         make (lev + 1);
  113.         has[i] = 0;
  114.     }
  115. }

复制代码

论坛徽章:
12
子鼠
日期:2014-10-11 16:46:482016科比退役纪念章
日期:2018-03-16 10:24:0515-16赛季CBA联赛之山东
日期:2017-11-10 14:32:142016科比退役纪念章
日期:2017-09-02 15:42:4715-16赛季CBA联赛之佛山
日期:2017-08-28 17:11:5515-16赛季CBA联赛之浙江
日期:2017-08-24 16:55:1715-16赛季CBA联赛之青岛
日期:2017-08-17 19:55:2415-16赛季CBA联赛之天津
日期:2017-06-29 10:34:4315-16赛季CBA联赛之四川
日期:2017-05-16 16:38:55黑曼巴
日期:2016-07-19 15:03:112015亚冠之萨济拖拉机
日期:2015-05-22 11:38:5315-16赛季CBA联赛之北京
日期:2019-08-13 17:30:53
发表于 2017-08-31 08:50 |显示全部楼层
本帖最后由 523066680 于 2017-08-31 08:59 编辑

回复 9# rubyish

关于效率,我用 NTYProf 分析自己代码的时候发现 是AB反馈函数耗时最多,这个函数改为内联C函数处理就快多了

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

  4. use Inline C;

  5. my $AB = "00";
  6. bullcow("0123", "5280", $AB);
  7. print $AB;

  8. __END__
  9. __C__
  10. void bullcow(char *stra, char *strb, char *AB)
  11. {
  12.     int idx;
  13.     char a = '0';
  14.     char b = '0';

  15.     for ( idx = 0; idx < 4; idx++ )
  16.     {
  17.         if ( stra[idx] == strb[idx] )
  18.             a++;
  19.         else
  20.             if ( strchr(stra, strb[idx]) != 0 )
  21.             {
  22.                 b++;
  23.             }
  24.     }

  25.     AB[0] = a;
  26.     AB[1] = b;
  27. }
复制代码

原来四五十秒的大批量测试,用内联C可能不到1秒完成。

我才发现你整个程序都用C实现的,这个涉及到树分支的筛选和构造,我觉得用完全C太累了,还是脚本操作方便

===============================================================

进一步优化,如果要用某个优化指标的方案去测试5040个数字,最好的方法是把优化指标的搜索顺序生成结构树。
比如 $tree->{0123} = { '01' => {子集合以及下一级反馈}, '02' => {子集合以及下一级反馈} .....  '30'=>{子集合以及下一级反馈} }
将树导出,需要用的时候加载使用,这样就不用每次都进行筛选,循着树的分支选取下一个数字。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP