[算法讨论]猜数字游戏 - Bulls and Cows

523066680

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

复制代码

现在我放出最后的资料/参考网站：
这个网站给出了两种优化方案的搜索树，可以在线浏览
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，时间消耗非常大，实现也相当费脑，等以后再尝试。

523066680

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

rubyish

回复 31# 523066680

avgBullsCows 方案平均回合数 5.213 次

yinxiangzhong haoxiang zuixin de shijie jilu shi 5.1X?

# (X keneng shi 6)

rubyish

回复 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. 
   
7. int USEFUL = sizeof(Node) - 13 * sizeof(Node *);
   
8. 
   
9. void dump (Node *node, FILE *file) {
   
10.     fwrite (node, USEFUL, 1, file);
    
11.     ...
    
12.    
    
13. void load (Node *node, FILE *file) {
    
14.     fread (node, USEFUL, 1, file);
    
15.     ...

复制代码

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

523066680

回复 34# rubyish

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

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

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

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

rubyish

回复 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. 
   
4. use 5.016;    # >= 5.016
   
5. sub NUMBER() { 0 }
   
6. sub AGAIN()  { 1 }
   
7. sub OK()     { 13 }
   
8. 
   
9. __INIT__:
   
10. print STDERR 'INIT...';
    
11. my @NUMBER = collect();
    
12. my $GUESS  = guess();
    
13. 
    
14. __TEST__:
    
15. print STDERR "\rTEST  ";
    
16. my $TEST = 5040;
    
17. my @COUNT;
    
18. 
    
19. =IF_WANT_PRINT
    
20. my @AB = (
    
21.     0x00, 0x01, 0x02, 0x03, 0x04, 0x10, 0x11,
    
22.     0x12, 0x13, 0x20, 0x21, 0x22, 0x30, 0x40,
    
23. );
    
24. =cut
    
25. 
    
26. for my $ans ( 0 .. $TEST - 1 ) {
    
27.     my $guess = $GUESS;
    
28. 
    
29.     #say "\nA [@{$NUMBER[$ans]}] TEST ", $ans + 1;
    
30.     for ( my $telle = 1 ; ; $telle++ ) {
    
31.         my $num = $guess->[NUMBER];
    
32.         my $that = AB( $ans, $num );
    
33. 
    
34.         #printf "$telle [@{$NUMBER[$num]}] AB %02x\n", $AB[$that];
    
35.         $COUNT[$telle]++, last if $that == OK;
    
36.         $guess = $guess->[AGAIN][$that];
    
37.     }
    
38. }
    
39. 
    
40. print STDERR "\rFINISH\n";
    
41. my $TOTO;
    
42. 
    
43. for my $i ( 1 .. $#COUNT ) {
    
44.     next unless $COUNT[$i];
    
45.     say "$i\t$COUNT[$i]";
    
46.     $TOTO += $i * $COUNT[$i];
    
47. }
    
48. 
    
49. say "\nTEST\t= $TEST";
    
50. say "GUESS\t= $TOTO ";
    
51. printf "AVE\t= %.3f\n", $TOTO / $TEST;
    
52. 
    
53. # ____________________SUB____________________
    
54. sub guess {
    
55.     my $guess = [];
    
56.     my $fun   = sub {
    
57.         my ( $guess, $maybe ) = @_;
    
58.         my $num = $maybe->[0];
    
59.         $guess->[NUMBER] = $num;
    
60.         my @next;
    
61.         for my $may (@$maybe) {
    
62.             my $ab = AB( $num, $may );
    
63.             push @{ $next[$ab] }, $may;
    
64.         }
    
65.         for my $ab ( 0 .. 12 ) {
    
66.             next unless $next[$ab];
    
67.             __SUB__->( $guess->[AGAIN][$ab] = [], $next[$ab] );
    
68.         }
    
69.     };
    
70.     $fun->( $guess, [ 0 .. 5040 - 1 ] );
    
71.     return $guess;
    
72. }
    
73. 
    
74. sub AB {
    
75.     state $val = [ 0, 5, 9, 12, 13 ];
    
76.     my ( $N1, $N2 ) = @NUMBER[@_];
    
77.     my ( $A, $B ) = ( 0, 0 );
    
78. 
    
79.     for my $i ( 0 .. 3 ) {
    
80.         $A++, next if $N1->[$i] == $N2->[$i];
    
81.         for my $j ( 0 .. 3 ) {
    
82.             $B++, last if $N1->[$i] == $N2->[$j];
    
83.         }
    
84.     }
    
85.     $val->[$A] + $B;
    
86. }
    
87. 
    
88. sub collect {
    
89.     sub {
    
90.         my ( $a, $b ) = @_;
    
91.         return $b if @$b == 4;
    
92.         map __SUB__->( [ @$a[ 0 .. $_ - 1, $_ + 1 .. $#$a ] ],
    
93.             [ @$b, $a->[$_] ] ), 0 .. $#$a;
    
94.       } ->( [ 0 .. 9 ], [] );
    
95. }
    
96. 
    
97. __DATA__
    
98. $_
    

复制代码