忘记密码   免费注册 查看新帖 | 论坛精华区

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT HPC论坛 徽章 文库 沙龙 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
最近访问板块 发新帖
楼主: 523066680

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

论坛徽章:
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-09-06 04:01 |显示全部楼层
v8:
  1. 1       1
  2. 2       13
  3. 3       108
  4. 4       639
  5. 5       2083
  6. 6       1900
  7. 7       293
  8. 8       3
  9. ----------------
  10. COUNT = 26797
  11. TEST  = 5040
  12. AVE   = 5.316865

  13. real    0m6.763s
复制代码


naive: 4.43s
  1. 1       1
  2. 2       13
  3. 3       108
  4. 4       596
  5. 5       1668
  6. 6       1768
  7. 7       752
  8. 8       129
  9. 9       5
  10. ----------------
  11. COUNT = 28024
  12. TEST  = 5040
  13. AVE   = 5.560317

  14. real    0m4.437s
复制代码



code:
  1. // gcc -Wall -march=native -Ofast -o bull bull.c

  2. # include <stdio.h>
  3. # include <string.h>
  4. # include <math.h>

  5. # define OK   0x40
  6. # define get_a(A)   A >> 4
  7. # define get_b(A)   0xF & A
  8. # define copy(A, B) memcpy (A, B, 4)
  9. # define move1(A)   ((1 << A[0]) | (1 << A[1]) | (1 << A[2]) | (1 << A[3]))
  10. # define toInt(N)   1000 * N[0] + 100 * N[1] + 10 * N[2] + N[3];
  11. # define INIT(A)    for (int i = 0; i < 5040; i++) A[i] = i;
  12. # define AB(A, B)   XAYB[A][B]
  13. # define TEST 5040

  14. typedef char kar;
  15. typedef double dub;
  16. typedef void voi;

  17. kar XAYB[5040][5040];
  18. int A_and_B[961];       // LOOK: sub genB
  19. kar SPLIT[5040][4];       // SPLIT[0] = [ 0, 1, 2, 3 ]
  20. int TOTO[5040];
  21. int MAYBE[5040];        // [ 0 .. 5039 ]
  22. int INDES[65];          // 4A: 0x40 == 64
  23. int COUNT[16];          //
  24. dub INFO[1000];
  25. int LEN_MAYBE;          // @MAYBE

  26. voi init (voi);
  27. voi test (voi);
  28. voi genTOTO (int);
  29. voi genIndes (voi);
  30. voi genB (voi);
  31. voi genAB (voi);
  32. voi rehashMaybe (int, int);
  33. int gimme (int);

  34. /* ____________________ MAIN ____________________ */
  35. int main (){
  36.     init ();
  37.     test ();
  38. }

  39. /* _____________________ SUB _____________________ */

  40. voi test () {
  41.     fprintf (stderr, "\rtest ");
  42.     for (int v = 0; v < TEST; v++) {
  43.         if (!(v % 100)) fprintf (stderr, "%6d\b\b\b\b\b\b", v);
  44.         // printf ("%d\n", v + 1);
  45.         INIT (MAYBE);
  46.         int ans = v;
  47.         int gue = 0;
  48.         LEN_MAYBE = 5040;
  49.         // printf ("_ [ %04d ]\n", TOTO[ans]);
  50.         int x;
  51.         for (x = 1; x < 10; x++) {
  52.             int ab = AB (ans, gue);
  53.             // int a  = get_a (ab);
  54.             // int b  = get_b (ab);
  55.             // printf ("%d [ %04d ] AB %d %d\n", x, TOTO[gue], a, b);
  56.             if (ab == OK) break;
  57.             rehashMaybe (gue, ab);
  58.             gue = gimme (x);
  59.             // gue = MAYBE[0]; /* NAIVE: FAST */

  60.         }
  61.         COUNT[x]++;
  62.     }

  63.     int ave = 0;
  64.     int tot = 0;
  65.     puts ("FINISH");
  66.     for (int i = 1; i < 15; i++) {
  67.         if (!COUNT[i]) continue;
  68.         printf ("%d\t%d\n", i, COUNT[i]);
  69.         ave += i * COUNT[i];
  70.         tot += COUNT[i];
  71.     }

  72.     if (tot != TEST) puts ("ERROR");
  73.     puts ("----------------");
  74.     printf ("COUNT = %d\n", ave);
  75.     printf ("TEST  = %d\n", TEST);
  76.     printf ("AVE   = %f\n", ave / (dub)TEST);
  77. } /* test */

  78. voi init () {
  79.     fprintf (stderr, "init..");
  80.     genTOTO (0);
  81.     genB ();
  82.     genAB ();
  83.     genIndes ();
  84.     for (int i = 0; i < 1000; i++) INFO[i] = i * log (i);
  85. }

  86. voi genTOTO (int lev){
  87.     static kar num[4];
  88.     static int I = 0;
  89.     static int has[10];

  90.     if (lev == 4) {
  91.         int n = toInt (num);
  92.         TOTO[I] = n;
  93.         copy (SPLIT[I], num);
  94.         I++;
  95.         return;
  96.     }

  97.     for (int i = 0; i <= 9; i++) {
  98.         if (has[i]) continue;
  99.         has[i]   = 1;
  100.         num[lev] = i;
  101.         genTOTO (lev + 1);
  102.         has[i] = 0;
  103.     }
  104. } /* genTOTO */

  105. voi genB (){
  106. // 0b1111000000 => bit(1): 9876, val = 960
  107. // 0123:  0b001111
  108. // 0153:  0b101011
  109. // A & B: 0b001011 = 0b1011(=11), count(1) = 3, $A[11] = 3
  110.     for (int i = 0; i < 961; i++) {
  111.         int count = 0;

  112.         for (int j = 0; j < 10; j++) {
  113.             if (i & (1 << j)) count++;
  114.             if (count > 4) break;
  115.         }
  116.         A_and_B[i] = count > 4 ? 0 : count;
  117.     }
  118. }

  119. voi genAB (){
  120.     for (int i = 0; i < 5040; i++) {
  121.         kar *cha = SPLIT[i];
  122.         int C1   = move1 (cha);

  123.         for (int j = 0; j < 5040; j++) {
  124.             kar *cha2 = SPLIT[j];
  125.             int C2    = move1 (cha2);
  126.             int A     = 0;
  127.             for (int k = 0; k < 4; k++)
  128.                 if (cha[k] == cha2[k]) A++;
  129.             int B = C1 & C2;
  130.             B          = A_and_B[B] - A;
  131.             XAYB[i][j] = (A << 4) | B;
  132.         }
  133.     }
  134. }

  135. inline
  136. voi rehashMaybe (int gue, int ab){
  137.     int I = 0;

  138.     for (int i = 0; i < LEN_MAYBE; i++) {
  139.         if (AB (MAYBE[i], gue) == ab)
  140.             MAYBE[I++] = MAYBE[i];
  141.     }
  142.     LEN_MAYBE = I;
  143. }

  144. inline
  145. int gimme (int lev){
  146.     if (LEN_MAYBE == 1 || lev == 1) return MAYBE[0];
  147.     int best = 0;
  148.     dub max  = 999999.0; // BIG NUM

  149.     for (int i = 0; i < LEN_MAYBE; i++) {
  150.         int test[14] = { 0 };

  151.         for (int j = 0; j < LEN_MAYBE; j++) {
  152.             int ab  = AB (MAYBE[i], MAYBE[j]);
  153.             int pos = INDES[ab];
  154.             test[pos]++;
  155.         }

  156.         dub toto = 0.0;
  157.         for (int i = 0; i < 14; i++)
  158.             if (test[i]) toto += INFO[test[i]];
  159.         if (max > toto) max = toto, best = i;
  160.     }
  161.     return MAYBE[best];
  162. } /* gimme */

  163. voi genIndes (){
  164.     int var[] = { 0, 5, 9, 12, 13 };

  165.     // 0x40 = 4A0B = 64
  166.     // INDES[64] = var[4] + 0 = 13
  167.     for (int a = 0; a <= 4; a++) {
  168.         for (int b = 0; b <= 4; b++) {
  169.             if (a + b > 4) continue;
  170.             int ab = (a << 4) | b;
  171.             int i  = var[a] + b;
  172.             INDES[ab] = i;
  173.             // if (a == 3) break;   /* NO 3A1B */
  174.         }
  175.     }
  176. }
复制代码



论坛徽章:
10
子鼠
日期:2014-10-11 16:46:482016科比退役纪念章
日期: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联赛之山东
日期:2017-11-10 14:32:14
发表于 2017-09-06 14:22 |显示全部楼层
本帖最后由 523066680 于 2017-09-06 14:27 编辑

我写的C的版本,用比较直白的方式写,没有采用优化方案(还是用脚本方便)

包括 5040 次 printf ,耗时差不多1.2秒。
  1. times: 28024, average: 5.560317
  2. Clock: 1185
复制代码
  1. // 523066680 2017-08

  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <time.h>

  6. #define SIZE 10*9*8*7
  7. #define print_num(s) printf("%c%c%c%c\n", s[0], s[1], s[2], s[3])
  8. typedef struct { int a, b; } AB;

  9. int odi = 0;
  10. int idx;
  11. char (order[SIZE])[4];
  12. int oindex[SIZE];
  13. int temparr[SIZE];

  14. void permute(char *elements, char *getstr, int len, int lv);
  15. void guess_s( char *target, char *guess, AB *res );
  16. void reduce( int *oindex, char *guess, AB *res );
  17. void printstate( char *guess, AB *res, int n );

  18. int main(int argc, char *argv[])
  19. {
  20.     char elements[] = "0123456789";
  21.     char getstr[10];
  22.     AB res;
  23.    
  24.     odi = 0;
  25.     //生成所有组合到 order 数组(全局)
  26.     permute(elements, getstr, strlen(elements), 0);

  27.     char nums[4];
  28.     char guess[4];
  29.     int times = 0;

  30.     //遍历所有5040种情况
  31.     for (int mi = 0; mi < SIZE; mi++)
  32.     {
  33.         //初始化、重置索引数组(所有操作都是间接通过索引处理)
  34.         for (int i = 0; i < SIZE; i++) oindex[i] = i;

  35.         //nums:目标数字,guess:猜测数字
  36.         strncpy(nums, order[mi], 4);
  37.         strncpy(guess, "0123", 4);
  38.         idx = SIZE;

  39.         print_num(nums);

  40.         while ( idx > 0 )
  41.         {
  42.             guess_s( nums, guess, &res );
  43.             //printstate(guess, &res, idx);

  44.             //筛选出相同反馈的排列
  45.             reduce( oindex, guess, &res );
  46.             //从筛选的子集中选第一个
  47.             strncpy( guess, order[ oindex[0] ], 4 );

  48.             times++;
  49.         }
  50.     }

  51.     printf("times: %d, average: %f\n", times, (float)times/5040.0);
  52.     printf("Clock: %d\n", clock() );
  53.     return 0;
  54. }

  55. void reduce( int *oindex, char *guess, AB *res )
  56. {
  57.     AB t;
  58.     int ai = 0;

  59.     for (int i = 0; i < idx; i++)
  60.     {
  61.         guess_s( guess, order[ oindex[i] ], &t );
  62.         if ( (t.a == res->a) &&
  63.              (t.b == res->b) &&
  64.             (strncmp(guess, order[ oindex[i] ], 4) != 0 ) )  //不全等
  65.         {
  66.             temparr[ai] = oindex[i];
  67.             ai++;
  68.         }
  69.     }

  70.     idx = ai;
  71.     for (int i = 0; i < idx; i++) oindex[i] = temparr[i];
  72. }

  73. void permute(char *elements, char *getstr, int len, int lv)
  74. {
  75.     char *tempele = (char *)malloc( len * sizeof(char) );

  76.     for ( int i = 0; i < len; i++)
  77.     {
  78.         strcpy( tempele, elements );
  79.         getstr[lv] = elements[i];

  80.         for (int j = i; j < (len-1); j++)  //popup one char
  81.             tempele[j] = elements[j+1];

  82.         if ( lv < 4 )
  83.             permute( tempele, getstr, len-1, lv+1 );
  84.         else
  85.         {
  86.             strncpy( order[odi++], getstr, 4 );
  87.             break;
  88.         }
  89.     }
  90. }

  91. void guess_s( char target[4], char guess[4], AB *res )
  92. {
  93.     char idx, in;
  94.     res->a = 0;
  95.     res->b = 0;

  96.     for ( idx = 0; idx < 4; idx++ )
  97.     {
  98.         if ( target[idx] == guess[idx] )
  99.             res->a++;
  100.         else
  101.             if ( strchr(target, guess[idx]) != 0 )
  102.             {
  103.                 res->b++;
  104.             }
  105.     }
  106. }

  107. void printstate( char *guess, AB *res, int n )
  108. {   
  109.     char s[5];
  110.     strncpy(s, guess, 4 );
  111.     s[4] = 0;
  112.     printf("%s [%d%d] %d\n", s, res->a, res->b, n);
  113. }
复制代码

论坛徽章:
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-09-06 23:17 |显示全部楼层
本帖最后由 rubyish 于 2017-09-06 19:19 编辑

回复 22# 523066680

Run le jici, faxian AVE jingran hui biandong?
average:
  1. 6.275794
  2. 9.411508
  3. 2.425794
复制代码


Xiugaile sub guess_s:

  1. void guess_s (char target[4], char guess[4], AB *res){
  2.     static char TAGRET0[5];  // END = 0, for strchr

  3.     memcpy (TAGRET0, target, 4);
  4.     res->a = 0;
  5.     res->b = 0;

  6.     for (int i = 0; i < 4; i++) {
  7.         if (target[i] == guess[i]) res->a++;
  8.         else if (strchr (TAGRET0, guess[i])) res->b++;
  9.     }
  10. }
复制代码


compile:
gcc -Wall -march=native -Ofast

time: 3.401s
  1. times: 28024, average: 5.560317
  2. Clock: 3398914

  3. real    0m3.401s
复制代码



Meiyou OPT de code jingrang hai kuaile OPT 1 miao!!
Zhe rang wo qile yixin, OPT shifou yijing useless le?

论坛徽章:
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-09-07 00:36 |显示全部楼层
v9:
# add POWER

time: 0.7s
  1. 1       1
  2. 2       13
  3. 3       108
  4. 4       596
  5. 5       1668
  6. 6       1768
  7. 7       752
  8. 8       129
  9. 9       5
  10. ----------------
  11. COUNT = 28024
  12. TEST  = 5040
  13. AVE   = 5.560317

  14. real    0m0.736s
复制代码


  1. 1       1
  2. 2       13
  3. 3       108
  4. 4       639
  5. 5       2083
  6. 6       1900
  7. 7       293
  8. 8       3
  9. ----------------
  10. COUNT = 26797
  11. TEST  = 5040
  12. AVE   = 5.316865

  13. real    0m4.433s
复制代码


bull.c
  1. // gcc -Wall -march=native -Ofast -o bull bull.c -lm

  2. # include <stdio.h>
  3. # include <string.h>
  4. # include <math.h>

  5. # define OK 0x40
  6. # define get_a(A)   A >> 4
  7. # define get_b(A)   0xF & A
  8. # define copy(A, B) memcpy (A, B, 4)
  9. # define move1(A)   ((1 << A[0]) | (1 << A[1]) | (1 << A[2]) | (1 << A[3]))
  10. # define INIT(A)    for (int i = 0; i < 5040; i++) A[i] = i;
  11. # define AB(A, B)   (A < B ? XAYB[A][B] : XAYB[B][A])
  12. # define DATA(a)    TOTO[a][0], TOTO[a][1], TOTO[a][2], TOTO[a][3]

  13. # define TEST 5040

  14. typedef char kar;
  15. typedef double dub;
  16. typedef void voi;

  17. kar XAYB[5040][5040];
  18. int A_and_B[961];       // LOOK: sub genB
  19. kar TOTO[5040][4];       // TOTO[0] = [ 0, 1, 2, 3 ]
  20. int MAYBE[5040];        // [ 0 .. 5039 ]
  21. int INDES[65];          // 4A: 0x40 == 64
  22. int COUNT[16];          //
  23. dub INFO[1000];
  24. int LEN_MAYBE;          // @MAYBE

  25. voi init (voi);
  26. voi test (voi);
  27. voi genTOTO (int);
  28. voi genIndes (voi);
  29. voi genB (voi);
  30. voi genAB (voi);
  31. voi rehashMaybe (int, int);
  32. int gimme (int);

  33. /* ____________________ MAIN ____________________ */
  34. int main (){
  35.     init ();
  36.     test ();
  37. }

  38. /* _____________________ SUB _____________________ */

  39. voi test () {
  40.     fprintf (stderr, "\rtest ");
  41.     for (int v = 0; v < TEST; v++) {
  42.         if (!(v % 100)) fprintf (stderr, "%6d\b\b\b\b\b\b", v);
  43.         // printf ("%d\n", v + 1);
  44.         INIT (MAYBE);
  45.         int ans = v;
  46.         int gue = 0;
  47.         LEN_MAYBE = 5040;
  48.         // printf ("_ [ %d%d%d%d ]\n", DATA (ans));
  49.         int x;
  50.         for (x = 1; x < 15; x++) {
  51.             int ab = AB (ans, gue);
  52.             // int a  = get_a (ab);
  53.             // int b  = get_b (ab);
  54.             // printf ("%d [ %d%d%d%d ] AB %d %d\n", x, DATA (gue), a, b);
  55.             if (ab == OK) break;
  56.             rehashMaybe (gue, ab);
  57.             // gue = gimme (x);
  58.             gue = MAYBE[0]; /* NAIVE: FAST */

  59.         }
  60.         COUNT[x]++;
  61.     }

  62.     int ave = 0;
  63.     int tot = 0;
  64.     puts ("FINISH");

  65.     for (int i = 1; i < 15; i++) {
  66.         if (!COUNT[i]) continue;
  67.         printf ("%d\t%d\n", i, COUNT[i]);
  68.         ave += i * COUNT[i];
  69.         tot += COUNT[i];
  70.     }

  71.     if (tot != TEST) puts ("ERROR");
  72.     puts ("----------------");
  73.     printf ("COUNT = %d\n", ave);
  74.     printf ("TEST  = %d\n", TEST);
  75.     printf ("AVE   = %f\n", ave / (dub)TEST);
  76. } /* test */

  77. voi init () {
  78.     fprintf (stderr, "init...");
  79.     genTOTO (0);
  80.     genB ();
  81.     genAB ();
  82.     genIndes ();
  83.     for (int i = 0; i < 1000; i++) INFO[i] = i * log (i);
  84. }

  85. voi genTOTO (int lev){
  86.     static kar num[4];
  87.     static int I = 0;
  88.     static int has[10];

  89.     if (lev == 4) {
  90.         copy (TOTO[I], num);
  91.         I++;
  92.         return;
  93.     }

  94.     for (int i = 0; i <= 9; i++) {
  95.         if (has[i]) continue;
  96.         has[i]   = 1;
  97.         num[lev] = i;
  98.         genTOTO (lev + 1);
  99.         has[i] = 0;
  100.     }
  101. } /* genTOTO */

  102. voi genB (){
  103. // 0b1111000000 => bit(1): 9876, val = 960
  104. // 0123:  0b001111
  105. // 0153:  0b101011
  106. // A & B: 0b001011 = 0b1011(=11), count(1) = 3, $A[11] = 3
  107.     for (int i = 0; i < 961; i++) {
  108.         int count = 0;

  109.         for (int j = 0; j < 10; j++) {
  110.             if (i & (1 << j)) count++;
  111.             if (count > 4) break;
  112.         }
  113.         A_and_B[i] = count > 4 ? 0 : count;
  114.     }
  115. }

  116. voi genAB (){
  117.     for (int i = 0; i < 5040; i++) {
  118.         kar *cha = TOTO[i];
  119.         int C1   = move1 (cha);

  120.         for (int j = i; j < 5040; j++) {
  121.             kar *cha2 = TOTO[j];
  122.             int C2    = move1 (cha2);
  123.             int A     = 0;
  124.             for (int k = 0; k < 4; k++)
  125.                 if (cha[k] == cha2[k]) A++;
  126.             int B = C1 & C2;
  127.             B          = A_and_B[B] - A;
  128.             XAYB[i][j] = (A << 4) | B;
  129.         }
  130.     }
  131. }

  132. inline
  133. voi rehashMaybe (int gue, int ab){
  134.     int I = 0;

  135.     for (int i = 0; i < LEN_MAYBE; i++) {
  136.         if (AB (MAYBE[i], gue) == ab)
  137.             MAYBE[I++] = MAYBE[i];
  138.     }
  139.     LEN_MAYBE = I;
  140. }

  141. inline
  142. int gimme (int lev){
  143.     if (LEN_MAYBE == 1 || lev == 1) return MAYBE[0];
  144.     int best = 0;
  145.     dub min  = 999999.0; // BIG NUM

  146.     for (int i = 0; i < LEN_MAYBE; i++) {
  147.         int test[14] = { 0 };

  148.         for (int j = 0; j < LEN_MAYBE; j++) {
  149.             int ab  = AB (MAYBE[i], MAYBE[j]);
  150.             int pos = INDES[ab];
  151.             test[pos]++;
  152.         }

  153.         dub toto = 0.0;
  154.         for (int i = 0; i < 14; i++)
  155.             if (test[i]) toto += INFO[test[i]];
  156.         if (min > toto) min = toto, best = i;
  157.     }
  158.     return MAYBE[best];
  159. } /* gimme */

  160. voi genIndes (){
  161.     int var[] = { 0, 5, 9, 12, 13 };

  162.     // 0x40 = 4A0B = 64
  163.     // INDES[64] = var[4] + 0 = 13
  164.     for (int a = 0; a <= 4; a++) {
  165.         for (int b = 0; b <= 4; b++) {
  166.             if (a + b > 4) continue;
  167.             int ab = (a << 4) | b;
  168.             int i  = var[a] + b;
  169.             INDES[ab] = i;
  170.             // if (a == 3) break;   /* NO 3A1B */
  171.         }
  172.     }
  173. }
复制代码




评分

参与人数 1信誉积分 +5 收起 理由
523066680 + 5 厉害

查看全部评分

论坛徽章:
10
子鼠
日期:2014-10-11 16:46:482016科比退役纪念章
日期: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联赛之山东
日期:2017-11-10 14:32:14
发表于 2017-09-07 08:02 |显示全部楼层
本帖最后由 523066680 于 2017-09-07 17:57 编辑

回复 23# rubyish

关于未优化比优化快一秒的问题,采用估值算法的程序增加了运算量,所以消耗可能更多。
要提高效率只有先生成结构树。可惜用C语言实现比较麻烦,所以用了perl

试了一下 Perl 内联C,跑完 5040种情况,0.087 秒(不含 print 耗时)
不使用内联C代码:0.4秒 (不含 print 耗时)

论坛徽章:
10
子鼠
日期:2014-10-11 16:46:482016科比退役纪念章
日期: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联赛之山东
日期:2017-11-10 14:32:14
发表于 2017-09-08 00:09 |显示全部楼层
回复 24# rubyish

链表的版本来了(我已经把C忘光了,折腾了一整天……
写的很凌乱,加载和导出没有做详细的错误判断处理。

机制:
如果没有结构文件,会执行 maketree() 建立链表树,然后dump到 F:/struct.dat
如果找到结构文件会直接加载。

效率(CPU: i7-4790K):
print 不计入内,从文件加载,遍历所有情况,耗时 0.006秒
print 不计入内,重新建造树,遍历所有情况,耗时 0.050秒

  1. // Game - Bulls and Cows
  2. // Code By 523066680@163.com
  3. // zhuanlan.zhihu.com/PerlExample
  4. // 2017-09

  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <string.h>
  8. #include <time.h>

  9. #define SIZE 10*9*8*7
  10. #define print_num(s) printf("%c%c%c%c\n", s[0], s[1], s[2], s[3])
  11. typedef struct { int a, b; } AB;

  12. int odi = 0;
  13. int idx;
  14. char (order[SIZE])[4];
  15. int oindex[SIZE];
  16. int temparr[SIZE];

  17. void permute(char *elements, char *getstr, int len, int lv);
  18. void bullscows( char target[4], char guess[4], AB *res );
  19. int reduce( int *oindex, char *guess, AB *res, int *subset, int osize );
  20. void printstate( char *guess, AB *res, int n );

  21. FILE* fp;

  22. struct node
  23. {
  24.     char guess[5];
  25.     struct node *res[13];
  26.     int count;
  27. };

  28. int mapindex[4][5] = {
  29.     {0,  1, 2, 3, 4,},
  30.     {5,  6, 7, 8,-1,},
  31.     {9, 10,11,-1,-1,},
  32.     {12,-1,-1,-1,-1}
  33. };

  34. AB alltypes[13] =
  35. {
  36.     {0,0},{0,1},{0,2},{0,3},{0,4},
  37.     {1,0},{1,1},{1,2},{1,3},
  38.     {2,0},{2,1},{2,2},
  39.     {3,0}
  40. };


  41. // ----------------  about Tree node ------------------ //

  42. void node_value(struct node *pt, char *str)
  43. {
  44.     strncpy( pt->guess, str, 4 );
  45.     pt->count = 0;
  46. }

  47. void node_alloc(struct node *pt)
  48. {
  49.     for (int i = 0; i < 13; i++)
  50.     {
  51.         pt->res[i] = (struct node *) malloc( sizeof( struct node ) );
  52.         strcpy(pt->res[i]->guess, "\0\0\0\0");
  53.         pt->res[i]->count = 0;
  54.         for (int j = 0; j < 13; j++)
  55.         {
  56.             pt->res[i]->res[j] = NULL;
  57.         }
  58.     }
  59. }

  60. void load_tree( struct node *pt, FILE *fp, int lv )
  61. {
  62.     fread(pt, sizeof(struct node), 1, fp);

  63.     if ( pt->count > 0 && (! feof(fp) ) )
  64.     {
  65.         node_alloc( pt );
  66.         for (int i = 0; i < 13; i++)
  67.         {
  68.             load_tree( pt->res[i], fp, lv+1 );
  69.         }
  70.     }
  71. }

  72. void dump_tree( struct node *pt, FILE *fp, int lv )
  73. {
  74.     fwrite( pt, sizeof(struct node), 1, fp );

  75.     if ( pt->count > 0 )
  76.     {
  77.         for (int i = 0; i < 13; i++)
  78.         {
  79.             dump_tree( pt->res[i], fp, lv+1 );
  80.         }
  81.     }
  82. }

  83. void node_print(struct node *pt, int lv)
  84. {
  85.     for (int i = 0; i < 13 ; i++)
  86.     {
  87.         printf("[%d%d] %s\n", alltypes[i].a,alltypes[i].b,
  88.             pt->res[i]->guess);
  89.     }
  90. }

  91. void tree_print(struct node *pt, int lv)
  92. {
  93.     if ( pt->guess[0] != '\0' )
  94.     {
  95.         for (int i = 0; i < lv; i++)
  96.             printf("  ");
  97.         printf("%s %d %d\n", pt->guess, pt->count, lv);
  98.     }

  99.     if ( pt->count > 0 )
  100.     {
  101.         for (int i = 0; i < 13 ; i++)
  102.         {
  103.             //printf("[%d%d]\n", alltypes[i].a, alltypes[i].b );
  104.             tree_print( pt->res[i], lv+1 );   
  105.         }
  106.     }
  107. }

  108. void maketree( int *oindex, int osize, int lv, struct node *pt )
  109. {
  110.     char guess[5];

  111.     int subset[SIZE];
  112.     int nsize;    //new_size

  113.     node_alloc(pt);
  114.     strncpy(guess, order[oindex[0]], 4);

  115.     for (int ti = 0; ti < 13; ti++)
  116.     {
  117.         //筛选出相同反馈的排列
  118.         memset(subset, 0, SIZE);
  119.         nsize = reduce( oindex, guess, &alltypes[ti], subset, osize );

  120.         if (nsize > 0)
  121.         {
  122.             node_value( pt->res[ti], order[subset[0]] ) ;
  123.             maketree( subset, nsize, lv+1, pt->res[ti] );
  124.             pt->count++;
  125.         }
  126.     }
  127. }

  128. // ----------------  end Tree node ------------------ //

  129. int main(int argc, char *argv[] )
  130. {
  131.     char elements[] = "0123456789";
  132.     char getstr[10]; //临时缓冲区
  133.     //生成所有组合到 order 数组(全局)
  134.     permute(elements, getstr, strlen(elements), 0);

  135.     //初始化、重置索引数组(筛选函数间接通过索引处理)
  136.     for (int i = 0; i < SIZE; i++) oindex[i] = i;

  137.     struct node tree;
  138.     FILE *fp;
  139.     fp = fopen("F:/sturct.dat", "rb");
  140.         if (fp)
  141.         {
  142.             load_tree( &tree, fp, 0 );
  143.         }
  144.         else
  145.         {
  146.             fp = fopen("F:/sturct.dat", "wb");
  147.             node_value( &tree, (char *)"0123");
  148.             maketree( oindex, SIZE, 0, &tree ); //index, size, level, pt
  149.             dump_tree( &tree, fp, 0 );
  150.         }
  151.     fclose( fp );

  152.     AB ab;
  153.     struct node *pt;
  154.     char target[4];
  155.     int count = 0;

  156.     for (int m = 0; m < SIZE; m++ )
  157.     {
  158.         pt = &tree;
  159.         strncpy(target, order[m], 4);
  160.         //print_num( target );  //显示目标数字

  161.         while ( 1 )
  162.         {
  163.             bullscows( target, pt->guess, &ab );
  164.             //printf("%s [%d%d]\n", pt->guess, ab.a, ab.b );  //显示当前情况
  165.             count++;
  166.             if (ab.a == 4) break;

  167.             pt = pt->res[ mapindex[ab.a][ab.b] ];
  168.             if ( pt->guess[0] == '\0' )
  169.             {
  170.                 printf("Something wrong!");
  171.                 break;
  172.             }
  173.         }
  174.         //printf("\n");
  175.     }

  176.     printf("Clock:%ld, count: %d, avg: %.3f\n",
  177.             clock(), count, (float)count/((float)SIZE)
  178.         );
  179.     return 0;

  180. }

  181. int reduce( int *oindex, char *guess, AB *res, int *subset, int osize )
  182. {
  183.     AB t;
  184.     int idx = 0;

  185.     for (int i = 0; i < osize; i++)
  186.     {
  187.         bullscows( guess, order[ oindex[i] ], &t );
  188.         if ( (t.a == res->a) &&
  189.              (t.b == res->b) &&
  190.             (strncmp(guess, order[ oindex[i] ], 4) != 0 ) )  //不全等
  191.         {
  192.             subset[idx] = oindex[i];
  193.             idx++;
  194.         }
  195.     }

  196.     return idx;
  197. }

  198. void bullscows( char target[4], char guess[4], AB *res )
  199. {
  200.     int idx;
  201.     res->a = 0;
  202.     res->b = 0;

  203.     for ( idx = 0; idx < 4; idx++ )
  204.     {
  205.         if ( target[idx] == guess[idx] )
  206.             res->a++;
  207.         else
  208.             if ( strchr(target, guess[idx]) != 0 )
  209.             {
  210.                 res->b++;
  211.             }
  212.     }
  213. }

  214. void permute(char *elements, char *getstr, int len, int lv)
  215. {
  216.     char *tempele = (char *)malloc( len * sizeof(char) );

  217.     for ( int i = 0; i < len; i++)
  218.     {
  219.         strcpy( tempele, elements );
  220.         getstr[lv] = elements[i];

  221.         for (int j = i; j < (len-1); j++)  //popup one char
  222.             tempele[j] = elements[j+1];

  223.         if ( lv < 4 )
  224.             permute( tempele, getstr, len-1, lv+1 );
  225.         else
  226.         {
  227.             strncpy( order[odi++], getstr, 4 );
  228.             break;
  229.         }
  230.     }
  231. }

复制代码

评分

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

查看全部评分

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

v10: final version

time: 0.5s
  1. 1    1
  2. 2    13
  3. 3    108
  4. 4    596
  5. 5    1668
  6. 6    1768
  7. 7    752
  8. 8    129
  9. 9    5
  10. ----------------
  11. COUNT = 28024
  12. TEST  = 5040
  13. AVE   = 5.560317

  14. real    0m0.515s
复制代码


  1. // gcc -Wall -march=native -Ofast -o bull bull.c -lm

  2. # include <stdio.h>
  3. # include <string.h>
  4. # include <math.h>

  5. # define OK 0x40
  6. # define get_a(A)   A >> 4
  7. # define get_b(A)   0xF & A
  8. # define copy(A, B) memcpy (A, B, 4)
  9. # define move1(A)   ((1 << A[0]) | (1 << A[1]) | (1 << A[2]) | (1 << A[3]))
  10. # define INIT(A)    for (int i = 0; i < 5040; i++) A[i] = i;
  11. # define AB(A, B)   (A < B ? XAYB[A][B] : XAYB[B][A])
  12. # define DATA(a)    TOTO[a][0], TOTO[a][1], TOTO[a][2], TOTO[a][3]

  13. # define TEST 5040

  14. typedef char kar;
  15. typedef double dub;
  16. typedef void voi;

  17. kar XAYB[5040][5040];
  18. int A_and_B[961];       // LOOK: sub genB
  19. kar TOTO[5040][4];       // TOTO[0] = [ 0, 1, 2, 3 ]
  20. int MAYBE[5040];        // [ 0 .. 5039 ]
  21. int INDES[65];          // 4A: 0x40 == 64
  22. int COUNT[16];          //
  23. dub INFO[1500];
  24. int MOVE[5040];
  25. int LEN_MAYBE;          // @MAYBE

  26. voi init (voi);
  27. voi test (voi);
  28. voi genTOTO (int);
  29. voi genIndes (voi);
  30. voi genB (voi);
  31. voi genAB (voi);
  32. voi rehashMaybe (int, int);
  33. int gimme (int);

  34. /* ____________________ MAIN ____________________ */
  35. int main (){
  36.     init ();
  37.     test ();
  38. }

  39. /* _____________________ SUB _____________________ */

  40. voi test () {
  41.     fprintf (stderr, "\rtest ");
  42.     for (int v = 0; v < TEST; v++) {
  43.         if (!(v % 100)) fprintf (stderr, "%6d\b\b\b\b\b\b", v);
  44.         // printf ("%d\n", v + 1);
  45.         INIT (MAYBE);
  46.         int ans = v;
  47.         int gue = 0;
  48.         LEN_MAYBE = 5040;
  49.         // printf ("_ [ %d%d%d%d ]\n", DATA (ans));
  50.         int x;
  51.         for (x = 1; x < 10; x++) {
  52.             int ab = AB (ans, gue);
  53.             // int a  = get_a (ab);
  54.             // int b  = get_b (ab);
  55.             // printf ("%d [ %d%d%d%d ] AB %d %d\n", x, DATA (gue), a, b);
  56.             if (ab == OK) break;
  57.             rehashMaybe (gue, ab);
  58.             // gue = gimme (x);
  59.             gue = MAYBE[0]; /* NAIVE: FAST */

  60.         }
  61.         COUNT[x]++;
  62.     }

  63.     int ave = 0;
  64.     int tot = 0;
  65.     puts ("FINISH");

  66.     for (int i = 1; i < 15; i++) {
  67.         if (!COUNT[i]) continue;
  68.         printf ("%d\t%d\n", i, COUNT[i]);
  69.         ave += i * COUNT[i];
  70.         tot += COUNT[i];
  71.     }

  72.     if (tot != TEST) puts ("ERROR");
  73.     puts ("----------------");
  74.     printf ("COUNT = %d\n", ave);
  75.     printf ("TEST  = %d\n", TEST);
  76.     printf ("AVE   = %f\n", ave / (dub)TEST);
  77. } /* test */

  78. voi init () {
  79.     fprintf (stderr, "init...");
  80.     genTOTO (0);
  81.     genB ();
  82.     genAB ();
  83.     genIndes ();
  84.     for (int i = 0; i < 1500; i++) INFO[i] = i * log (i);
  85. }

  86. voi genTOTO (int lev){
  87.     static kar num[4];
  88.     static int I = 0;
  89.     static int has[10];

  90.     if (lev == 4) {
  91.         copy (TOTO[I], num);
  92.         MOVE[I] = move1 (num);
  93.         I++;
  94.         return;
  95.     }

  96.     for (int i = 0; i <= 9; i++) {
  97.         if (has[i]) continue;
  98.         has[i]   = 1;
  99.         num[lev] = i;
  100.         genTOTO (lev + 1);
  101.         has[i] = 0;
  102.     }
  103. } /* genTOTO */

  104. voi genB (){
  105.     for (int i = 0; i < 961; i++) {
  106.         int count = 0;

  107.         for (int j = 0; j < 10; j++) {
  108.             if (i & (1 << j)) count++;
  109.             if (count > 4) break;
  110.         }
  111.         A_and_B[i] = count > 4 ? 0 : count;
  112.     }
  113. }

  114. voi genAB (){
  115.     for (int i = 0; i < 5040; i++) {
  116.         kar *cha = TOTO[i];
  117.         int C1   = MOVE[i];
  118.         for (int j = i; j < 5040; j++) {
  119.             kar *cha2 = TOTO[j];
  120.             int C2    = MOVE[j];
  121.             int A     = 0;
  122.             for (int k = 0; k < 4; k++)
  123.                 if (cha[k] == cha2[k]) A++;
  124.             int B = A_and_B[C1 & C2] - A;
  125.             XAYB[i][j] = (A << 4) | B;
  126.         }
  127.     }
  128. }

  129. inline
  130. voi rehashMaybe (int gue, int ab){
  131.     int I = 0;

  132.     for (int i = 0; i < LEN_MAYBE; i++) {
  133.         if (AB (MAYBE[i], gue) == ab)
  134.             MAYBE[I++] = MAYBE[i];
  135.     }
  136.     LEN_MAYBE = I;
  137. }

  138. inline
  139. int gimme (int lev){
  140.     if (LEN_MAYBE == 1 || lev == 1) return MAYBE[0];
  141.     int best = 0;
  142.     dub max  = 999999.0; // BIG NUM

  143.     for (int i = 0; i < LEN_MAYBE; i++) {
  144.         int test[14] = { 0 };

  145.         for (int j = 0; j < LEN_MAYBE; j++) {
  146.             int ab  = AB (MAYBE[i], MAYBE[j]);
  147.             int pos = INDES[ab];
  148.             test[pos]++;
  149.         }

  150.         dub toto = 0.0;
  151.         for (int i = 0; i < 14; i++)
  152.             if (test[i]) toto += INFO[test[i]];
  153.         if (max > toto) max = toto, best = i;
  154.     }
  155.     return MAYBE[best];
  156. } /* gimme */

  157. voi genIndes (){
  158.     int var[] = { 0, 5, 9, 12, 13 };

  159.     for (int a = 0; a <= 4; a++) {
  160.         for (int b = 0; b <= 4; b++) {
  161.             if (a + b > 4) continue;
  162.             int ab = (a << 4) | b;
  163.             int i  = var[a] + b;
  164.             INDES[ab] = i;
  165.         }
  166.     }
  167. }
复制代码




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

run de jieguo shi:

bash: line 1:  3567 Segmentation fault      (core dumped)


Zhege banben youyisi. Keyi xuexi ruhe maketree.
3Q~~

论坛徽章:
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-09-08 02:30 |显示全部楼层
本帖最后由 rubyish 于 2017-09-07 22:43 编辑

回复 26# 523066680


Intel(R) Atom(TM) CPU N280   @ 1.66GHz
make tree: 0.16s
  1. Clock:162568, count: 28024, avg: 5.560

  2. real    0m0.166s
复制代码


load tree: 0.03s
  1. Clock:36215, count: 28024, avg: 5.560

  2. real    0m0.039s
复制代码


Very very fast!! kanlai wode final haibuneng final.

Zhege code wo bixu zixide yuedu.
Tansuo ta ruci shensu de aomi.
3Q ~~


Zhe shi xiugai bullscows hanshu zhihou de jieguo.

Jiu wo de lijie?

  1. void bullscows (char target[4], char guess[4], AB *res){
  2. ...
  3.     if (strchr (target, guess[idx]) != 0) {
复制代码


Zhelide strchr shi cuowude shiyong.
strchr de diyige canshu bixu shi string. yejiushi yi '\0' jiewei de char array.

You yige example:
http://clc-wiki.net/wiki/strchr
In standard C, this can be implemented as:

  1. char *strchr(const char *s, int c)
  2. {
  3.     while (*s != (char)c)
  4.         if (!*s++) return 0;
  5.     return (char *)s;
  6. }
复制代码



Huoshi windows de strchr butongyu C biaozhun?

论坛徽章:
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-09-08 03:03 |显示全部楼层
What is this?
  1. char (order[SIZE])[4];
复制代码


youhe butong?
  1. char order[SIZE][4];
复制代码

您需要登录后才可以回帖 登录 | 注册

本版积分规则

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP