API tools faq
paste
goroh_kun

GDD2011 Slide Puzzle

goroh_kun
Sep 12th, 2011
2,624
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 21.38 KB | None | 0 0
raw download clone embed print report
  1. /*
  2.  * slide puzzle answer check & solver
  3.  *
  4.  * [email protected]
  5.  */
  6.  
  7. #include <stdio.h>
  8. #include <stdlib.h>
  9. #include <string.h>
  10.  
  11. #define MAX_STEP 2000
  12. #define MAX_ANS_STEP 2000
  13.  
  14. /* 枝を刈る基準になる葉の数 */
  15. #ifndef CUT_DETECT_NUM
  16. #define CUT_DETECT_NUM 20000
  17. #endif
  18.  
  19. /* 枝を刈ったあとに残す葉の数 */
  20. #ifndef CUT_REMAIN_NUM
  21. #define CUT_REMAIN_NUM 3000
  22. #endif
  23.  
  24. struct nodeT;
  25. typedef struct problemT
  26. {
  27.     int w;
  28.     int h;
  29.     char* data; // 現在のパターン
  30.     char* goal; // 解答のパターン
  31.     char* sequence; //シーケンス(存在すれば)
  32.     long long wall;
  33.     int* swap_data;
  34.     char posChar[0x100];
  35.     char valChar[36];
  36.     int* eval_data[36];
  37.     int found_answer;
  38.     int step_max_eval[MAX_STEP];
  39.     int cut_count;
  40.     int node_count;
  41.     int ans_max_eval;
  42.     int step_count[MAX_STEP];
  43.     int ans_step_count[MAX_ANS_STEP];
  44.     struct nodeT* step_p[MAX_STEP];
  45.     struct nodeT* ans_step_p[MAX_ANS_STEP];
  46.     struct problemT* next;
  47.     struct problemT* prev;
  48. } problemT;
  49.  
  50. typedef struct nodeT
  51. {
  52.     int current; // 現在の空白の位置
  53.     char* data; // 現在のパターン
  54.     struct nodeT* next; // 次のパターン
  55.     struct nodeT* prev; // どのパターンから生成されたか？
  56.     int evalvalue; //　評価値
  57.     char dir; // どの方向に空白が移動したか？
  58.     char flag; // フラグ
  59. } nodeT;
  60.  
  61. static const char dirChar[4] = {'L', 'R', 'U', 'D'};
  62. static const char revDir[4] = {1, 0, 3, 2};
  63.  
  64. enum {
  65.     FLAG_SKIP = 1,
  66.     FLAG_DELETE = 2
  67. };
  68.  
  69. static int dump_swap_data(problemT* p)
  70. {
  71.     int i, c;
  72.     c = 0;
  73.     for(i=0; i<(p->h * p->w); i++){
  74.         printf("%d: %d %d %d %d\n", i,
  75.             p->swap_data[c], p->swap_data[c+1],
  76.             p->swap_data[c+2], p->swap_data[c+3]);
  77.         c += 4;
  78.     }
  79. }
  80.  
  81. static void dump_problem(problemT* p)
  82. {
  83.     printf("%p data:%s goal:%s\n", p, p->data, p->goal);
  84. }
  85.  
  86. static void dump_datas(nodeT* p)
  87. {
  88.     while(p){
  89.         printf("%p %s: %d(%p) %d %d\n", p, p->data, p->dir, p->prev, p->flag, p->evalvalue);
  90.         p = p->next;
  91.     }
  92. }
  93.  
  94. /*
  95.  * 解答の計算
  96.  */
  97. static int create_answer(problemT* p)
  98. {
  99.     int i;
  100.     int ch = '1';
  101.     char* data = (char*)malloc(p->h * p->w + 1);
  102.     memset(data, 0, sizeof(p->h * p->w + 1));
  103.     memset(p->posChar, -1, sizeof(p->posChar));
  104.     memset(p->valChar, 0, sizeof(p->valChar));
  105.  
  106.     for(i=0; i<p->h * p->w;){
  107.         if(ch == '9' + 1) ch = 'A';
  108.         if(strchr(p->data, ch)) {
  109.             p->posChar[ch] = i;
  110.             p->valChar[i] = ch;
  111.             data[i] = ch;
  112.         } else {
  113.             if((p->wall & (1LL << i))){
  114.                 data[i] = '=';
  115.             } else {
  116.                 ch++;
  117.                 continue;
  118.             }
  119.         }
  120.         ch++;
  121.         i++;
  122.     }
  123.     data[p->h * p->w -1] = '0';
  124.     p->posChar['0'] = p->h * p->w - 1;
  125.     p->valChar[p->h * p->w - 1] = '0';
  126.     data[p->h * p->w] = '\0';
  127.  
  128.     p->goal = data;
  129.     return 0;
  130. }
  131.  
  132. /*
  133.  * 置換座標の計算
  134.  */
  135. static int create_swap_data(problemT* p)
  136. {
  137.     int c, i, j;
  138.  
  139.     if(p->swap_data) {
  140.         free(p->swap_data);
  141.     }
  142.  
  143.     p->swap_data = (int*)malloc(sizeof(int) * 4 * p->h * p->w);
  144.     memset(p->swap_data, -1, sizeof(int) * 4 * p->h * p->w);
  145.  
  146.     c = 0;
  147.     for(i=0; i<p->h; i++){
  148.         for(j=0; j<p->w; j++){
  149.             int c2;
  150.             c2 = c * 4;
  151.             if(p->wall & (1LL << c)){
  152.                 c++;
  153.                 continue;
  154.             }
  155.             // L
  156.             if(j != 0) {
  157.                 if(!(p->wall & (1LL << (c - 1))))
  158.                     p->swap_data[c2] = c - 1;
  159.             }
  160.             // R
  161.             if(j != p->w-1) {
  162.                 if(!(p->wall & (1LL << (c + 1))))
  163.                     p->swap_data[c2+1] = c + 1;
  164.             }
  165.             // U
  166.             if(i != 0) {
  167.                 if(!(p->wall & (1LL << (c - p->w))))
  168.                     p->swap_data[c2+2] = c - p->w;
  169.             }
  170.             // D
  171.             if(i != p->h-1) {
  172.                 if(!(p->wall & (1LL << (c + p->w))))
  173.                     p->swap_data[c2+3] = c + p->w;
  174.             }
  175.             c++;
  176.         }
  177.     }
  178.     return 0;
  179. }
  180.  
  181. /*
  182.  * 問題文字列のパース
  183.  */
  184. static int parse_problem(const char* line, problemT** p)
  185. {
  186.     const char* s = line;
  187.     const char* s2;
  188.     const char* s3;
  189.     int h, w;
  190.     w = strtoul(s, 0, 10);
  191.     s = strchr(s, ',');
  192.     if( !s ) return -1;
  193.     h = strtoul(s + 1, 0, 10);
  194.     s = strchr(s + 1, ',');
  195.     if( !s ) return -1;
  196.     s++;
  197.  
  198.     if((h < 2) || (w < 2)) {
  199.         fprintf(stderr, "*** problem too small error (%d, %d)\n", h, w);
  200.         return -1;
  201.     }
  202.  
  203.     *p = (problemT*)malloc(sizeof(problemT));
  204.     if(!*p) {
  205.         fprintf(stderr, "*** malloc error (%s:%d)\n", __FUNCTION__, __LINE__);
  206.         return -1;
  207.     }
  208.     memset(*p, 0, sizeof(problemT));
  209.     (*p)->w = w;
  210.     (*p)->h = h;
  211.     (*p)->data = strdup(s);
  212.     (*p)->data[w*h] = '\0';
  213.     if(strchr((*p)->data, ',') || !strchr((*p)->data, '0')) {
  214.         fprintf(stderr, "*** problem parse error (%s)\n", (*p)->data);
  215.         free((*p)->data);
  216.         free((*p));
  217.         (*p) = 0;
  218.         return -1;
  219.     }
  220.  
  221.     (*p)->wall = 0;
  222.     s3 = s;
  223.     while(0 != (s2 = strchr(s, '='))){
  224.         int b;
  225.         b = s2 - s3;
  226.         s = s2 + 1;
  227.         (*p)->wall |= 1LL << b;
  228.     }
  229.     return 0;
  230. }
  231.  
  232. static int delete_node(nodeT* p)
  233. {
  234.     if(!p) return -1;
  235.     free(p->data);
  236.     free(p);
  237.     return 0;
  238. }
  239.  
  240. static int delete_problem(problemT* p)
  241. {
  242.     int i;
  243.     if(!p) return -1;
  244.     if(p->sequence) free(p->sequence);
  245.     if(p->data) free(p->data);
  246.     if(p->swap_data) free(p->swap_data);
  247.     if(p->goal) free(p->goal);
  248.  
  249.     for(i=0; i<MAX_STEP; i++){
  250.         if(p->step_count[i]){
  251.             nodeT* p2 = p->step_p[i];
  252.             while(p2){
  253.                 nodeT* p3;
  254.                 p3 = p2;
  255.                 p2 = p2->next;
  256.                 delete_node(p3);
  257.             }
  258.         }
  259.     }
  260.     for(i=0; i<MAX_ANS_STEP; i++){
  261.         if(p->ans_step_count[i]){
  262.             nodeT* p2 = p->ans_step_p[i];
  263.             while(p2){
  264.                 nodeT* p3;
  265.                 p3 = p2;
  266.                 p2 = p2->next;
  267.                 delete_node(p3);
  268.             }
  269.         }
  270.     }
  271.     free(p);
  272.     return 0;
  273. }
  274.  
  275. /*
  276.  * 解答文字列のパース
  277.  */
  278. static int parse_answer(const char* line, problemT** p)
  279. {
  280.     const char* s = line;
  281.     const char* s2;
  282.     const char* s3;
  283.     const char* s4;
  284.     char* ch;
  285.     int h, w;
  286.     w = strtoul(s, 0, 10);
  287.     s = strchr(s, ',');
  288.     if( !s ) return -1;
  289.     h = strtoul(s + 1, 0, 10);
  290.     s = strchr(s + 1, ',');
  291.     if( !s ) return -1;
  292.     s++;
  293.  
  294.     if((h < 2) || (w < 2)) {
  295.         fprintf(stderr, "*** answer too small error (%d, %d)\n", h, w);
  296.         return -1;
  297.     }
  298.  
  299.     *p = (problemT*)malloc(sizeof(problemT));
  300.     if(!*p) {
  301.         fprintf(stderr, "*** malloc error (%s:%d)\n", __FUNCTION__, __LINE__);
  302.         return -1;
  303.     }
  304.     memset(*p, 0, sizeof(problemT));
  305.     (*p)->w = w;
  306.     (*p)->h = h;
  307.     (*p)->data = strdup(s);
  308.     (*p)->data[w*h] = '\0';
  309.     if(strchr((*p)->data, ',') || !strchr((*p)->data, '0')) {
  310.         fprintf(stderr, "*** problem parse error (%s)\n", (*p)->data);
  311.         free((*p)->data);
  312.         free((*p));
  313.         (*p) = 0;
  314.         return -1;
  315.     }
  316.  
  317.     s4 = strchr(s + 1, ',');
  318.     if( !s4 ) {
  319.         fprintf(stderr, "*** answer need sequence error\n");
  320.         free((*p)->data);
  321.         free((*p));
  322.         (*p) = 0;
  323.         return -1;
  324.     }
  325.     (*p)->sequence = strdup(s4 + 1);
  326.     ch = strchr((*p)->sequence, ',');
  327.     if(ch) *ch = '\0';
  328.     ch = strchr((*p)->sequence, '\r');
  329.     if(ch) *ch = '\0';
  330.     ch = strchr((*p)->sequence, '\n');
  331.     if(ch) *ch = '\0';
  332.  
  333. //  fprintf(stderr, "*** sequence=%s\n", (*p)->sequence);
  334.  
  335.     (*p)->wall = 0;
  336.     s3 = s;
  337.     while(0 != (s2 = strchr(s, '='))){
  338.         int b;
  339.         b = s2 - s3;
  340.         s = s2 + 1;
  341.         (*p)->wall |= 1LL << b;
  342.     }
  343.     return 0;
  344. }
  345.  
  346. static create_eval_data(problemT* p)
  347. {
  348.     int i;
  349.     for(i=0; i<p->w*p->h; i++){
  350.         p->eval_data[i] = (int*)malloc(sizeof(int) * p->w * p->h);
  351.     }
  352.  
  353.     // select num
  354.     for(i=0; i<p->w*p->h; i++){
  355.         int j;
  356.         int val, changed;
  357.         for(j=0; j<p->w*p->h; j++){
  358.             p->eval_data[i][j] = -1;
  359.         }
  360.  
  361.         // select pos
  362.         p->eval_data[i][i] = 0;
  363.         val = 0;
  364.         changed = 1;
  365.         while(changed){
  366.             changed = 0;
  367.             for(j=0; j<p->w*p->h; j++){
  368.                 if(p->eval_data[i][j] == val) {
  369.                     int d, k;
  370.                     for(d=0; d<4; d++){
  371.                         k = p->swap_data[j * 4 + d];
  372.                         if((k >= 0) && (p->eval_data[i][k] == -1)) {
  373.                             p->eval_data[i][k] = val + 1;
  374.                             changed = 1;
  375.                         }
  376.                     }
  377.                 }
  378.             }
  379.             val++;
  380.         }
  381.     }
  382. }
  383.  
  384. static int dump_eval_data(problemT* p)
  385. {
  386.     int i,j;
  387.     for(i=0; i<p->w*p->h; i++){
  388.         fprintf(stderr, "=== eval_data[%d] : ", i);
  389.         for(j=0; j<p->w*p->h; j++){
  390.             fprintf(stderr, "%d ", p->eval_data[i][j]);
  391.         }
  392.         fprintf(stderr, "\n");
  393.     }
  394. }
  395.  
  396. /* 距離の2乗 , 答え空白位置からの距離 * 距離*/
  397. static int eval_value(problemT *p, nodeT *np)
  398. {
  399.     int i;
  400.     int num;
  401.     np->evalvalue = 0;
  402.     for(i=0; i<p->w*p->h; i++){
  403.         int v;
  404.         num = p->posChar[np->data[i]];
  405.         if(np->data[i] == '0') continue;
  406.         if(np->data[i] == '=') continue;
  407.         v = p->eval_data[num][i];
  408. //      fprintf(stderr, "%s i=%d d=%d v=%d eval=%d\n", np->data, i, num, v, v*v);
  409.         if(v > 0) {
  410.             np->evalvalue += v * v;
  411.         }
  412.     }
  413.  
  414.     return 0;
  415. }
  416.  
  417. static __inline__ void swap_byte(char* data, int i, int j)
  418. {
  419.     char ch;
  420.     ch = data[i];
  421.     data[i] = data[j];
  422.     data[j] = ch;
  423. }
  424.  
  425. static void print_sequence(nodeT* p, nodeT* p2)
  426. {
  427.     char ans[MAX_STEP+MAX_ANS_STEP+1] = {0};
  428.     nodeT* p3;
  429.     int ans_i = 0;
  430.     int i;
  431.  
  432.     p3 = p;
  433.     while(p3){
  434.         if(!p3->prev) break;
  435. //      printf("%p %s: %d(%p) %d %d\n", p3, p3->data, p3->dir, p3->prev, p3->flag, p3->evalvalue);
  436.         ans[ans_i++] = dirChar[p3->dir];
  437.         p3 = p3->prev;
  438.     }
  439.     for(i=0; i<ans_i; i++){
  440.         fprintf(stderr, "%c", ans[ans_i - i -1]);
  441.     }
  442.  
  443.     p3 = p2;
  444.     while(p3){
  445.         fprintf(stderr, "%c", dirChar[revDir[p3->dir]]);
  446.         p3 = p3->prev;
  447.     }
  448. }
  449.  
  450. static void print_answer(problemT* pp, nodeT* p, nodeT* p2)
  451. {
  452.     int dir[4] = {0};
  453.     nodeT* p3;
  454.     int i;
  455.     char ans[1000] = {0};
  456.     int ans_i = 0;
  457.  
  458.     fprintf(stderr, "*** %s(%p, %p)\n", __FUNCTION__, p, p2);
  459.     fprintf(stdout,"%d,%d,%s,", pp->w, pp->h, pp->data);
  460.  
  461. #if 0
  462.     p3 = p2;
  463.     while(p3){
  464.         fprintf(stderr, "%s(%d)\n", p3->data, p3->evalvalue);
  465.         p3 = p3->prev;
  466.     }
  467.  
  468.     p3 = p;
  469.     while(p3){
  470.         fprintf(stderr, "%s(%d)\n", p3->data, p3->evalvalue);
  471.         p3 = p3->prev;
  472.     }
  473. #endif
  474.  
  475.     p3 = p;
  476.     while(p3->prev){
  477.         ans[ans_i++] = dirChar[p3->dir];
  478.         dir[p3->dir]++;
  479.         p3 = p3->prev;
  480.     }
  481.     for(i=0; i<ans_i; i++){
  482.         fprintf(stdout, "%c", ans[ans_i - i -1]);
  483.     }
  484.  
  485.     p3 = p2;
  486.     while(p3->prev){
  487.         fprintf(stdout, "%c", dirChar[revDir[p3->dir]]);
  488.         dir[revDir[p3->dir]]++;
  489.         p3 = p3->prev;
  490.     }
  491.  
  492.     fprintf(stdout,",%d,%d,%d,%d,%d,%d,%d,%d,%d,%d\n",
  493.         dir[0], dir[1], dir[2], dir[3], p->evalvalue,
  494.         pp->node_count, pp->cut_count, CUT_DETECT_NUM, CUT_REMAIN_NUM,
  495.         dir[0] + dir[1] + dir[2] + dir[3]);
  496. }
  497.  
  498. static nodeT* create_node(problemT* pp)
  499. {
  500.     nodeT* p;
  501.     p = (nodeT*)malloc(sizeof(nodeT));
  502.     memset(p, 0, sizeof(nodeT));
  503.     p->data = strdup(pp->data);
  504.     {
  505.         const char* s =  strchr(p->data, '0');
  506.         p->current = s - p->data;
  507. //      fprintf(stderr, "current=%d\n", p->current);
  508.     }
  509.     return p;
  510. }
  511.  
  512. static nodeT* create_node_answer(problemT* pp)
  513. {
  514.     nodeT* p;
  515.     p = (nodeT*)malloc(sizeof(nodeT));
  516.     memset(p, 0, sizeof(nodeT));
  517.     p->data = strdup(pp->goal);
  518.     {
  519.         const char* s =  strchr(p->data, '0');
  520.         p->current = s - p->data;
  521. //      fprintf(stderr, "current=%d\n", p->current);
  522.     }
  523.     return p;
  524. }
  525.  
  526. static nodeT* create_node_step(problemT* pp, nodeT* p, int c)
  527. {
  528.     int i, j;
  529.     nodeT* p2;
  530.     char* data;
  531.  
  532. //  fprintf(stderr, "%s: %p %p %c\n", __FUNCTION__, pp, p, dirChar[c]);
  533.  
  534.     i = p->current;
  535.     j = pp->swap_data[i * 4 + c];
  536. //  fprintf(stderr, "current=%d next=%d\n", i, j);
  537.     if(j < 0) return 0;
  538.  
  539.     data = strdup(p->data);
  540.     swap_byte(data, i, j);
  541.  
  542.     p2 = (nodeT*)malloc(sizeof(nodeT));
  543.     memset(p2, 0, sizeof(nodeT));
  544.     p2->data = data;
  545.     p2->current = j;
  546.     p2->dir = c;
  547.     p2->prev = p;
  548.  
  549.     return p2;
  550. }
  551.  
  552. static int next_steps(problemT*pp, int step)
  553. {
  554.     nodeT* p = pp->step_p[step-1];
  555.  
  556.     while(p) {
  557.         int d;
  558.  
  559.         if(p->flag & FLAG_SKIP){
  560.             p = p->next;
  561.             continue;
  562.         }
  563.  
  564.         for(d=0; d<4; d++){
  565.             nodeT* p2;
  566.             p2 = create_node_step(pp, p, d);
  567.             if(p2) {
  568.                 int step2 = step - 2;
  569.                 eval_value(pp, p2);
  570.                 if(p2->evalvalue > pp->step_max_eval[step]) {
  571.                     pp->step_max_eval[step] = p2->evalvalue;
  572.                 }
  573.                 /* 同じパターン 検知 */
  574.                 while(step2 >= 0 && p2){
  575.                     nodeT* p3 = pp->step_p[step2];
  576.                     while(p3) {
  577.                         if((p2->evalvalue == p3->evalvalue) && !strcmp(p3->data, p2->data)){
  578.                             delete_node(p2);
  579.                             p2 = 0;
  580.                             break;
  581.                         }
  582.                         p3 = p3->next;
  583.                     }
  584.                     step2 -= 2;
  585. //                  if(pp->cut_count) break;
  586.                 }
  587.             }
  588.             if(p2) {
  589.                 pp->node_count++;
  590.                 /* リストへの挿入時に評価値の低い順にソートしておく */
  591.                 if(pp->step_p[step] == 0){
  592.                     p2->next = pp->step_p[step];
  593.                     pp->step_p[step] = p2;
  594.                 } else {
  595.                     nodeT* p3 = pp->step_p[step];
  596.                     nodeT* p3prev = 0;
  597.                     while(p3){
  598.                         if(p3->evalvalue >= p2->evalvalue){
  599.                             if(p3prev == 0){
  600.                                 p2->next = p3;
  601.                                 pp->step_p[step] = p2;
  602.                             } else {
  603.                                 p3prev->next = p2;
  604.                                 p2->next = p3;
  605.                             }
  606.                             break;
  607.                         }
  608.                         p3prev = p3;
  609.                         p3 = p3->next;
  610.                     }
  611.                     if(!p3){
  612.                         p3prev->next = p2;
  613.                     }
  614.                 }
  615.                 pp->step_count[step]++;
  616.             }
  617.         }
  618.         p = p->next;
  619.     }
  620.     return 0;
  621. }
  622.  
  623. static int next_ans_steps(problemT*pp, int step)
  624. {
  625.     nodeT* p = pp->ans_step_p[step-1];
  626.  
  627.     while(p) {
  628.         int d;
  629.         for(d=0; d<4; d++){
  630.             nodeT* p2;
  631.             p2 = create_node_step(pp, p, d);
  632.             if(p2) {
  633.                 int step2 = step - 2;
  634.                 eval_value(pp, p2);
  635.                 if(p2->evalvalue > pp->ans_max_eval) {
  636.                     pp->ans_max_eval = p2->evalvalue;
  637.                 }
  638.                 /* 同じパターン 検知 */
  639.                 while(step2 >= 0 && p2){
  640.                     nodeT* p3 = pp->ans_step_p[step2];
  641.                     while(p3) {
  642.                         if((p3->evalvalue == p2->evalvalue) && !strcmp(p3->data, p2->data)){
  643.                             delete_node(p2);
  644.                             p2 = 0;
  645.                             break;
  646.                         }
  647.                         p3 = p3->next;
  648.                     }
  649.                     step2 -= 2;
  650.                 }
  651.             }
  652.             if(p2) {
  653.                 pp->node_count++;
  654.                 p2->next = pp->ans_step_p[step];
  655.                 pp->ans_step_p[step] = p2;
  656.                 pp->ans_step_count[step]++;
  657.             }
  658.         }
  659.         p = p->next;
  660.     }
  661.     return 0;
  662. }
  663.  
  664. static int cut_datas(problemT*pp, int step)
  665. {
  666.     nodeT* p;
  667.     int i;
  668.  
  669.     /* とりあえずdeleteフラグを立てておく */
  670.     for(i=0; i<step; i++){
  671.         p = pp->step_p[i];
  672.         while(p){
  673.             p->flag |= FLAG_DELETE;
  674.             p = p->next;
  675.         }
  676.     }
  677.  
  678.     p = pp->step_p[step];
  679.     for(i=0; i< CUT_REMAIN_NUM; i++){
  680.         nodeT* prev;
  681.         prev = p->prev;
  682.         while(prev){
  683.             prev->flag &= ~FLAG_DELETE;
  684.             prev = prev->prev;
  685.         }
  686.         p=p->next;
  687.     }
  688.  
  689.     while(p){
  690.         p->flag |= FLAG_SKIP;
  691.         p = p->next;
  692.     }
  693.  
  694.     for(i=0; i<step; i++){
  695.         p = pp->step_p[i];
  696. //      fprintf(stderr, "*** step=%d\n", i);
  697. //      dump_datas(p);
  698.         while(p->next){
  699.             if(p->next->flag & FLAG_DELETE){
  700.                 nodeT* p2;
  701.                 p2 = p->next;
  702.                 p->next = p->next->next;
  703.                 free(p2->data);
  704.                 free(p2);
  705.                 continue;
  706.             }
  707.             p = p->next;
  708.         }
  709.     }
  710.  
  711.     pp->step_count[step] = CUT_REMAIN_NUM;
  712.     pp->cut_count++;
  713.     return 0;
  714. }
  715.  
  716. /*
  717.  *  解等算出
  718.  */
  719. static int solver_main(const char* line)
  720. {
  721.     int ret;
  722.     int step, ans_step;
  723.     problemT* problem;
  724.     nodeT* p;
  725.     nodeT* p2;
  726.     ret = parse_problem(line, &problem);
  727.     if (ret < 0) return ret;
  728.     problem->cut_count = 0;
  729.     problem->node_count = 0;
  730.     problem->ans_max_eval = 0;
  731.  
  732.     create_swap_data(problem);
  733. //  dump_swap_data(problem);
  734.     create_eval_data(problem);
  735. //  dump_eval_data(problem);
  736.  
  737.     create_answer(problem);
  738. //  dump_problem(problem);
  739.  
  740.     p = create_node(problem);
  741.     p2 = create_node_answer(problem);
  742.     eval_value(problem, p);
  743.     eval_value(problem, p2);
  744.  
  745.     fprintf(stderr,"*** %d,%d,%s,%s,%d\n",
  746.         problem->w, problem->h, problem->data, problem->goal, p->evalvalue);
  747.  
  748.     problem->found_answer = 0;
  749.     problem->step_p[0] = p;
  750.     problem->step_count[0] = 1;
  751.     problem->ans_step_p[0] = p2;
  752.     problem->ans_step_count[0] = 1;
  753.     ans_step = 0;
  754.     step = 0;
  755.  
  756.     while(0 == problem->found_answer){
  757.         if(problem->ans_step_count[ans_step] < problem->step_count[step]){
  758.             nodeT* p;
  759.             ans_step++;
  760.             next_ans_steps(problem, ans_step);
  761.             fprintf(stderr, "*** ans[%d] count=%d eval=%d\n",
  762.                 ans_step, problem->ans_step_count[ans_step], problem->ans_max_eval);
  763.             p = problem->ans_step_p[ans_step];
  764. //          dump_datas(problem->ans_step_p[ans_step]);
  765.             while(p){
  766.                 int i;
  767.                 for(i=step; i>=step-1; i--){
  768.                     nodeT* p2 = problem->step_p[i];
  769.                     while(p2){
  770.                         if(problem->ans_max_eval < p2->evalvalue) {
  771.                             break;
  772.                         }
  773.                         if((p->evalvalue == p2->evalvalue) && !strcmp(p->data, p2->data)){ 
  774.                             print_answer(problem, p2, p);
  775.                             problem->found_answer++;
  776.                         }
  777.                         p2 = p2->next;
  778.                     }
  779.                 }
  780.                 p = p->next;
  781.             }
  782.         } else {
  783.             nodeT* p;
  784.             step++;
  785.             next_steps(problem, step);
  786.             p = problem->step_p[step];
  787.  
  788.             while(1){
  789.                 fprintf(stderr, "*** step[%d] count=%d eval=%d,%d(%s)",
  790.                     step, problem->step_count[step], p->evalvalue, problem->step_max_eval[step], p->data);
  791.                 print_sequence(p, 0);
  792.                 fprintf(stderr, "\n");
  793.                 if(!p->next) break;
  794.                 if(p->evalvalue != p->next->evalvalue) break;
  795.                 p = p->next;
  796.             }
  797.  
  798.             p = problem->step_p[step];
  799. //          dump_datas(problem->step_p[step]);
  800.             while(p){
  801.                 nodeT* p2 = problem->ans_step_p[ans_step];
  802.                 if(problem->ans_max_eval < p->evalvalue) {
  803.                     break;
  804.                 }
  805.                 while(p2){
  806.                     if((p->evalvalue == p2->evalvalue) && !strcmp(p->data, p2->data)){ 
  807.                         print_answer(problem, p, p2);
  808.                         problem->found_answer++;
  809.                     }
  810.                     p2 = p2->next;
  811.                 }
  812.                 p = p->next;
  813.             }
  814.         }
  815.         if(problem->found_answer) break;
  816. #if 0
  817.         if(problem->ans_step_count[step] > CUT_DETECT_NUM) {
  818.             fprintf(stderr, "*** cut ansdata count=%d\n", problem->ans_step_count[step]);
  819.             cut_ans_datas(step);
  820.         }
  821. #endif
  822. #if 1
  823.         if(problem->step_count[step] > CUT_DETECT_NUM) {
  824.             fprintf(stderr, "*** cutdata count=%d\n", problem->step_count[step]);
  825.             cut_datas(problem, step);
  826. //          dump_datas(problem->step_p[step]);
  827. //          break;
  828.         }
  829. #endif
  830.     }
  831.  
  832.     delete_problem(problem);
  833.  
  834.     return 0;
  835. }
  836.  
  837. /*
  838.  *  解等チェック
  839.  */
  840. static int checkans_main(const char* line)
  841. {
  842.     int ret;
  843.     int step;
  844.     problemT* problem;
  845.     nodeT* p;
  846.     ret = parse_answer(line, &problem);
  847.     if (ret < 0) {
  848.         printf("### parse error %s\n", line);
  849.         return ret;
  850.     }
  851.  
  852.     create_swap_data(problem);
  853. //  dump_swap_data(problem);
  854.  
  855.     create_answer(problem);
  856. //  dump_problem(problem);
  857.  
  858.     fprintf(stderr,"*** %d,%d,\"%s\",\"%s\",\"%s\"\n",
  859.         problem->w, problem->h, problem->data, problem->goal, problem->sequence);
  860.  
  861.     p = create_node(problem);
  862. //  dump_datas(p);
  863.  
  864.     step = 0;
  865.     while(problem->sequence[step] != 0){
  866.         switch(problem->sequence[step]){
  867.         case 'L':
  868.             p = create_node_step(problem, p, 0);
  869.             break;
  870.         case 'R':
  871.             p = create_node_step(problem, p, 1);
  872.             break;
  873.         case 'U':
  874.             p = create_node_step(problem, p, 2);
  875.             break;
  876.         case 'D':
  877.             p = create_node_step(problem, p, 3);
  878.             break;
  879.         default:
  880.             fprintf(stdout, "### sequence error %s,%s\n",
  881.                 problem->data, problem->sequence);
  882.             ret = -1;
  883.             goto err;
  884.         }
  885.         if(p == 0) {
  886.             fprintf(stdout, "### sequence error %s,%s\n",
  887.                 problem->data, problem->sequence);
  888.             ret = -1;
  889.             goto err;
  890.         }
  891.         step++;
  892.     }
  893.     if(strcmp(p->data, problem->goal)){
  894.         fprintf(stdout, "### NG %s,%s: %s(%s)\n",
  895.             problem->data, problem->sequence, p->data, problem->goal);
  896.         ret = -1;
  897.         goto err;
  898.     }
  899.  
  900. err:
  901.     while(p) {
  902.         nodeT* p2 = p;
  903.         p = p->prev;
  904.         delete_node(p2);
  905.     }
  906.     delete_problem(problem);
  907.     return ret;
  908. }
  909.  
  910. static int checkans(int argc, const char** argv)
  911. {
  912.     if(argc < 1) return -1;
  913.     if(strcmp(argv[1], "-")){
  914.         return checkans_main(argv[1]);
  915.     }
  916.     {
  917.         char line[1024];
  918.         while(fgets(line, 1024, stdin) != 0){
  919.             checkans_main(line);
  920.         }
  921.     }
  922.     return 0;
  923. }
  924.  
  925. static int solver(int argc, const char** argv)
  926. {
  927.     if(argc < 1) return -1;
  928.     if(strcmp(argv[1], "-")){
  929.         return solver_main(argv[1]);
  930.     }
  931.     {
  932.         char line[1024];
  933.         while(fgets(line, 1024, stdin) != 0){
  934.             solver_main(line);
  935.         }
  936.     }
  937.     return 0;
  938. }
  939.  
  940. /*
  941.  *  回答提出用整形
  942.  */
  943. static int sumans(int argc, const char** argv)
  944. {
  945.     int ret;
  946.     problemT* problem = 0;
  947.     problemT* p;
  948.     problemT* p2;
  949.     char line[1024];
  950.     int count = 0;
  951.     int sum[4] = {0};
  952.     int summax[4] = {0};
  953.     int countmax = 0;
  954.     const char* s;
  955.     FILE*fp;
  956.     FILE*fp2;
  957.     int i;
  958.  
  959.     fp2 = fopen(argv[2], "r");
  960.     if(!fp2) return -1;
  961.  
  962.     fgets(line, 1024, fp2);
  963. //  fprintf(stderr, "*** line = %s\n", line);
  964.     s = line;
  965.     summax[0] = strtoul(s, 0, 10);
  966.     s = strchr(s, ' ');
  967.     if( !s ) return -1;
  968.     summax[1] = strtoul(s+1, 0, 10);
  969.     s = strchr(s+1, ' ');
  970.     if( !s ) return -1;
  971.     summax[2] = strtoul(s+1, 0, 10);
  972.     s = strchr(s+1, ' ');
  973.     if( !s ) return -1;
  974.     summax[3] = strtoul(s+1, 0, 10);
  975.     fgets(line, 1024, fp2);
  976. //  fprintf(stderr, "*** line = %s\n", line);
  977.     s = line;
  978.     countmax = strtoul(s, 0, 10);
  979.     fprintf(stderr, "*** max LRUD={%d,%d,%d,%d}\n", summax[0], summax[1], summax[2], summax[3]);
  980.     fprintf(stderr, "*** max count=%d\n", countmax);
  981.  
  982.     fp = fopen(argv[1], "r");
  983.     if(!fp) return -1;
  984.  
  985.     while(fgets(line, 1024, fp) != 0){
  986.         ret = parse_answer(line, &p);
  987.         if(ret < 0) continue;
  988.         if(problem && !strcmp(problem->data, p->data)){
  989.             //printf("skip %s\n", p->data);
  990.             free(p->data);
  991.             free(p->sequence);
  992.             free(p);
  993.             continue;
  994.         }
  995.         p->next = problem;
  996.         problem = p;
  997.         count++;
  998.         for(i=0; p->sequence[i]; i++){
  999.             switch(p->sequence[i]){
  1000.             case 'L':
  1001.                 sum[0]++;
  1002.                 break;
  1003.             case 'R':
  1004.                 sum[1]++;
  1005.                 break;
  1006.             case 'U':
  1007.                 sum[2]++;
  1008.                 break;
  1009.             case 'D':
  1010.                 sum[3]++;
  1011.                 break;
  1012.             }
  1013.         }
  1014.     }
  1015.     fprintf(stderr, "*** count=%d sum=(%d,%d,%d,%d)\n", count, sum[0], sum[1], sum[2], sum[3]);
  1016.     if(count > countmax) {
  1017.         fprintf(stderr, "*** count error\n");
  1018.         return -1;
  1019.     }
  1020.     for(i=0; i<4; i++){
  1021.         if(sum[i] > summax[i]) {
  1022.             fprintf(stderr, "*** LRUD limit error\n");
  1023.             return -1;
  1024.         }
  1025.     }
  1026.  
  1027.     for(i=0; i<countmax; i++){
  1028.         fgets(line, 1024, fp2);
  1029.         ret = parse_problem(line, &p2);
  1030.         p = problem;
  1031.         while(p){
  1032.             if(!strcmp(p2->data, p->data)){
  1033.                 fprintf(stdout, "%s\r\n", p->sequence);
  1034.                 break;
  1035.             }
  1036.             p = p->next;
  1037.         }
  1038.         if(!p){
  1039.             fprintf(stdout, "\r\n");
  1040.         }
  1041.     }
  1042.     return 0;
  1043. }
  1044.  
  1045. int main(int argc, const char** argv)
  1046. {
  1047.     if(strstr(argv[0], "solver"))
  1048.         return solver(argc, argv);
  1049.     if(strstr(argv[0], "checkans"))
  1050.         return checkans(argc, argv);
  1051.     if(strstr(argv[0], "sumans"))
  1052.         return sumans(argc, argv);
  1053. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!