GDD2011 Slide Puzzle

/*
 * slide puzzle answer check & solver
 *
 * goroh.kun@gmail.com
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STEP 2000
#define MAX_ANS_STEP 2000

/* 枝を刈る基準になる葉の数 */
#ifndef CUT_DETECT_NUM
#define CUT_DETECT_NUM 20000
#endif

/* 枝を刈ったあとに残す葉の数 */
#ifndef CUT_REMAIN_NUM
#define CUT_REMAIN_NUM 3000
#endif

struct nodeT;
typedef struct problemT
{
    int w;
    int h;
    char* data; // 現在のパターン
    char* goal; // 解答のパターン
    char* sequence; //シーケンス(存在すれば)
    long long wall;
    int* swap_data;
    char posChar[0x100];
    char valChar[36];
    int* eval_data[36];
    int found_answer;
    int step_max_eval[MAX_STEP];
    int cut_count;
    int node_count;
    int ans_max_eval;
    int step_count[MAX_STEP];
    int ans_step_count[MAX_ANS_STEP];
    struct nodeT* step_p[MAX_STEP];
    struct nodeT* ans_step_p[MAX_ANS_STEP];
    struct problemT* next;
    struct problemT* prev;
} problemT;

typedef struct nodeT
{
    int current; // 現在の空白の位置
    char* data; // 現在のパターン
    struct nodeT* next; // 次のパターン
    struct nodeT* prev; // どのパターンから生成されたか？
    int evalvalue; //　評価値
    char dir; // どの方向に空白が移動したか？
    char flag; // フラグ
} nodeT;

static const char dirChar[4] = {'L', 'R', 'U', 'D'};
static const char revDir[4] = {1, 0, 3, 2};

enum {
    FLAG_SKIP = 1,
    FLAG_DELETE = 2
};

static int dump_swap_data(problemT* p)
{
    int i, c;
    c = 0;
    for(i=0; i<(p->h * p->w); i++){
        printf("%d: %d %d %d %d\n", i,
            p->swap_data[c], p->swap_data[c+1],
            p->swap_data[c+2], p->swap_data[c+3]);
        c += 4;
    }
}

static void dump_problem(problemT* p)
{
    printf("%p data:%s goal:%s\n", p, p->data, p->goal);
}

static void dump_datas(nodeT* p)
{
    while(p){
        printf("%p %s: %d(%p) %d %d\n", p, p->data, p->dir, p->prev, p->flag, p->evalvalue);
        p = p->next;
    }
}

/*
 * 解答の計算
 */
static int create_answer(problemT* p)
{
    int i;
    int ch = '1';
    char* data = (char*)malloc(p->h * p->w + 1);
    memset(data, 0, sizeof(p->h * p->w + 1));
    memset(p->posChar, -1, sizeof(p->posChar));
    memset(p->valChar, 0, sizeof(p->valChar));

    for(i=0; i<p->h * p->w;){
        if(ch == '9' + 1) ch = 'A';
        if(strchr(p->data, ch)) {
            p->posChar[ch] = i;
            p->valChar[i] = ch;
            data[i] = ch;
        } else {
            if((p->wall & (1LL << i))){
                data[i] = '=';
            } else {
                ch++;
                continue;
            }
        }
        ch++;
        i++;
    }
    data[p->h * p->w -1] = '0';
    p->posChar['0'] = p->h * p->w - 1;
    p->valChar[p->h * p->w - 1] = '0';
    data[p->h * p->w] = '\0';

    p->goal = data;
    return 0;
}

/*
 * 置換座標の計算
 */
static int create_swap_data(problemT* p)
{
    int c, i, j;

    if(p->swap_data) {
        free(p->swap_data);
    }

    p->swap_data = (int*)malloc(sizeof(int) * 4 * p->h * p->w);
    memset(p->swap_data, -1, sizeof(int) * 4 * p->h * p->w);

    c = 0;
    for(i=0; i<p->h; i++){
        for(j=0; j<p->w; j++){
            int c2;
            c2 = c * 4;
            if(p->wall & (1LL << c)){
                c++;
                continue;
            }
            // L
            if(j != 0) {
                if(!(p->wall & (1LL << (c - 1))))
                    p->swap_data[c2] = c - 1;
            }
            // R
            if(j != p->w-1) {
                if(!(p->wall & (1LL << (c + 1))))
                    p->swap_data[c2+1] = c + 1;
            }
            // U
            if(i != 0) {
                if(!(p->wall & (1LL << (c - p->w))))
                    p->swap_data[c2+2] = c - p->w;
            }
            // D
            if(i != p->h-1) {
                if(!(p->wall & (1LL << (c + p->w))))
                    p->swap_data[c2+3] = c + p->w;
            }
            c++;
        }
    }
    return 0;
}

/*
 * 問題文字列のパース
 */
static int parse_problem(const char* line, problemT** p)
{
    const char* s = line;
    const char* s2;
    const char* s3;
    int h, w;
    w = strtoul(s, 0, 10);
    s = strchr(s, ',');
    if( !s ) return -1;
    h = strtoul(s + 1, 0, 10);
    s = strchr(s + 1, ',');
    if( !s ) return -1;
    s++;

    if((h < 2) || (w < 2)) {
        fprintf(stderr, "*** problem too small error (%d, %d)\n", h, w);
        return -1;
    }

    *p = (problemT*)malloc(sizeof(problemT));
    if(!*p) {
        fprintf(stderr, "*** malloc error (%s:%d)\n", __FUNCTION__, __LINE__);
        return -1;
    }
    memset(*p, 0, sizeof(problemT));
    (*p)->w = w;
    (*p)->h = h;
    (*p)->data = strdup(s);
    (*p)->data[w*h] = '\0';
    if(strchr((*p)->data, ',') || !strchr((*p)->data, '0')) {
        fprintf(stderr, "*** problem parse error (%s)\n", (*p)->data);
        free((*p)->data);
        free((*p));
        (*p) = 0;
        return -1;
    }

    (*p)->wall = 0;
    s3 = s;
    while(0 != (s2 = strchr(s, '='))){
        int b;
        b = s2 - s3;
        s = s2 + 1;
        (*p)->wall |= 1LL << b;
    }
    return 0;
}

static int delete_node(nodeT* p)
{
    if(!p) return -1;
    free(p->data);
    free(p);
    return 0;
}

static int delete_problem(problemT* p)
{
    int i;
    if(!p) return -1;
    if(p->sequence) free(p->sequence);
    if(p->data) free(p->data);
    if(p->swap_data) free(p->swap_data);
    if(p->goal) free(p->goal);

    for(i=0; i<MAX_STEP; i++){
        if(p->step_count[i]){
            nodeT* p2 = p->step_p[i];
            while(p2){
                nodeT* p3;
                p3 = p2;
                p2 = p2->next;
                delete_node(p3);
            }
        }
    }
    for(i=0; i<MAX_ANS_STEP; i++){
        if(p->ans_step_count[i]){
            nodeT* p2 = p->ans_step_p[i];
            while(p2){
                nodeT* p3;
                p3 = p2;
                p2 = p2->next;
                delete_node(p3);
            }
        }
    }
    free(p);
    return 0;
}

/*
 * 解答文字列のパース
 */
static int parse_answer(const char* line, problemT** p)
{
    const char* s = line;
    const char* s2;
    const char* s3;
    const char* s4;
    char* ch;
    int h, w;
    w = strtoul(s, 0, 10);
    s = strchr(s, ',');
    if( !s ) return -1;
    h = strtoul(s + 1, 0, 10);
    s = strchr(s + 1, ',');
    if( !s ) return -1;
    s++;

    if((h < 2) || (w < 2)) {
        fprintf(stderr, "*** answer too small error (%d, %d)\n", h, w);
        return -1;
    }

    *p = (problemT*)malloc(sizeof(problemT));
    if(!*p) {
        fprintf(stderr, "*** malloc error (%s:%d)\n", __FUNCTION__, __LINE__);
        return -1;
    }
    memset(*p, 0, sizeof(problemT));
    (*p)->w = w;
    (*p)->h = h;
    (*p)->data = strdup(s);
    (*p)->data[w*h] = '\0';
    if(strchr((*p)->data, ',') || !strchr((*p)->data, '0')) {
        fprintf(stderr, "*** problem parse error (%s)\n", (*p)->data);
        free((*p)->data);
        free((*p));
        (*p) = 0;
        return -1;
    }

    s4 = strchr(s + 1, ',');
    if( !s4 ) {
        fprintf(stderr, "*** answer need sequence error\n");
        free((*p)->data);
        free((*p));
        (*p) = 0;
        return -1;
    }
    (*p)->sequence = strdup(s4 + 1);
    ch = strchr((*p)->sequence, ',');
    if(ch) *ch = '\0';
    ch = strchr((*p)->sequence, '\r');
    if(ch) *ch = '\0';
    ch = strchr((*p)->sequence, '\n');
    if(ch) *ch = '\0';

//  fprintf(stderr, "*** sequence=%s\n", (*p)->sequence);

    (*p)->wall = 0;
    s3 = s;
    while(0 != (s2 = strchr(s, '='))){
        int b;
        b = s2 - s3;
        s = s2 + 1;
        (*p)->wall |= 1LL << b;
    }
    return 0;
}

static create_eval_data(problemT* p)
{
    int i;
    for(i=0; i<p->w*p->h; i++){
        p->eval_data[i] = (int*)malloc(sizeof(int) * p->w * p->h);
    }

    // select num
    for(i=0; i<p->w*p->h; i++){
        int j;
        int val, changed;
        for(j=0; j<p->w*p->h; j++){
            p->eval_data[i][j] = -1;
        }

        // select pos
        p->eval_data[i][i] = 0;
        val = 0;
        changed = 1;
        while(changed){
            changed = 0;
            for(j=0; j<p->w*p->h; j++){
                if(p->eval_data[i][j] == val) {
                    int d, k;
                    for(d=0; d<4; d++){
                        k = p->swap_data[j * 4 + d];
                        if((k >= 0) && (p->eval_data[i][k] == -1)) {
                            p->eval_data[i][k] = val + 1;
                            changed = 1;
                        }
                    }
                }
            }
            val++;
        }
    }
}

static int dump_eval_data(problemT* p)
{
    int i,j;
    for(i=0; i<p->w*p->h; i++){
        fprintf(stderr, "=== eval_data[%d] : ", i);
        for(j=0; j<p->w*p->h; j++){
            fprintf(stderr, "%d ", p->eval_data[i][j]);
        }
        fprintf(stderr, "\n");
    }
}

/* 距離の2乗 , 答え空白位置からの距離 * 距離*/
static int eval_value(problemT *p, nodeT *np)
{
    int i;
    int num;
    np->evalvalue = 0;
    for(i=0; i<p->w*p->h; i++){
        int v;
        num = p->posChar[np->data[i]];
        if(np->data[i] == '0') continue;
        if(np->data[i] == '=') continue;
        v = p->eval_data[num][i];
//      fprintf(stderr, "%s i=%d d=%d v=%d eval=%d\n", np->data, i, num, v, v*v);
        if(v > 0) {
            np->evalvalue += v * v;
        }
    }

    return 0;
}

static __inline__ void swap_byte(char* data, int i, int j)
{
    char ch;
    ch = data[i];
    data[i] = data[j];
    data[j] = ch;
}

static void print_sequence(nodeT* p, nodeT* p2)
{
    char ans[MAX_STEP+MAX_ANS_STEP+1] = {0};
    nodeT* p3;
    int ans_i = 0;
    int i;

    p3 = p;
    while(p3){
        if(!p3->prev) break;
//      printf("%p %s: %d(%p) %d %d\n", p3, p3->data, p3->dir, p3->prev, p3->flag, p3->evalvalue);
        ans[ans_i++] = dirChar[p3->dir];
        p3 = p3->prev;
    }
    for(i=0; i<ans_i; i++){
        fprintf(stderr, "%c", ans[ans_i - i -1]);
    }

    p3 = p2;
    while(p3){
        fprintf(stderr, "%c", dirChar[revDir[p3->dir]]);
        p3 = p3->prev;
    }
}

static void print_answer(problemT* pp, nodeT* p, nodeT* p2)
{
    int dir[4] = {0};
    nodeT* p3;
    int i;
    char ans[1000] = {0};
    int ans_i = 0;

    fprintf(stderr, "*** %s(%p, %p)\n", __FUNCTION__, p, p2);
    fprintf(stdout,"%d,%d,%s,", pp->w, pp->h, pp->data);

#if 0
    p3 = p2;
    while(p3){
        fprintf(stderr, "%s(%d)\n", p3->data, p3->evalvalue);
        p3 = p3->prev;
    }

    p3 = p;
    while(p3){
        fprintf(stderr, "%s(%d)\n", p3->data, p3->evalvalue);
        p3 = p3->prev;
    }
#endif

    p3 = p;
    while(p3->prev){
        ans[ans_i++] = dirChar[p3->dir];
        dir[p3->dir]++;
        p3 = p3->prev;
    }
    for(i=0; i<ans_i; i++){
        fprintf(stdout, "%c", ans[ans_i - i -1]);
    }

    p3 = p2;
    while(p3->prev){
        fprintf(stdout, "%c", dirChar[revDir[p3->dir]]);
        dir[revDir[p3->dir]]++;
        p3 = p3->prev;
    }

    fprintf(stdout,",%d,%d,%d,%d,%d,%d,%d,%d,%d,%d\n",
        dir[0], dir[1], dir[2], dir[3], p->evalvalue,
        pp->node_count, pp->cut_count, CUT_DETECT_NUM, CUT_REMAIN_NUM,
        dir[0] + dir[1] + dir[2] + dir[3]);
}

static nodeT* create_node(problemT* pp)
{
    nodeT* p;
    p = (nodeT*)malloc(sizeof(nodeT));
    memset(p, 0, sizeof(nodeT));
    p->data = strdup(pp->data);
    {
        const char* s =  strchr(p->data, '0');
        p->current = s - p->data;
//      fprintf(stderr, "current=%d\n", p->current);
    }
    return p;
}

static nodeT* create_node_answer(problemT* pp)
{
    nodeT* p;
    p = (nodeT*)malloc(sizeof(nodeT));
    memset(p, 0, sizeof(nodeT));
    p->data = strdup(pp->goal);
    {
        const char* s =  strchr(p->data, '0');
        p->current = s - p->data;
//      fprintf(stderr, "current=%d\n", p->current);
    }
    return p;
}

static nodeT* create_node_step(problemT* pp, nodeT* p, int c)
{
    int i, j;
    nodeT* p2;
    char* data;

//  fprintf(stderr, "%s: %p %p %c\n", __FUNCTION__, pp, p, dirChar[c]);

    i = p->current;
    j = pp->swap_data[i * 4 + c];
//  fprintf(stderr, "current=%d next=%d\n", i, j);
    if(j < 0) return 0;

    data = strdup(p->data);
    swap_byte(data, i, j);

    p2 = (nodeT*)malloc(sizeof(nodeT));
    memset(p2, 0, sizeof(nodeT));
    p2->data = data;
    p2->current = j;
    p2->dir = c;
    p2->prev = p;

    return p2;
}

static int next_steps(problemT*pp, int step)
{
    nodeT* p = pp->step_p[step-1];

    while(p) {
        int d;

        if(p->flag & FLAG_SKIP){
            p = p->next;
            continue;
        }

        for(d=0; d<4; d++){
            nodeT* p2;
            p2 = create_node_step(pp, p, d);
            if(p2) {
                int step2 = step - 2;
                eval_value(pp, p2);
                if(p2->evalvalue > pp->step_max_eval[step]) {
                    pp->step_max_eval[step] = p2->evalvalue;
                }
                /* 同じパターン 検知 */
                while(step2 >= 0 && p2){
                    nodeT* p3 = pp->step_p[step2];
                    while(p3) {
                        if((p2->evalvalue == p3->evalvalue) && !strcmp(p3->data, p2->data)){
                            delete_node(p2);
                            p2 = 0;
                            break;
                        }
                        p3 = p3->next;
                    }
                    step2 -= 2;
//                  if(pp->cut_count) break;
                }
            }
            if(p2) {
                pp->node_count++;
                /* リストへの挿入時に評価値の低い順にソートしておく */
                if(pp->step_p[step] == 0){
                    p2->next = pp->step_p[step];
                    pp->step_p[step] = p2;
                } else {
                    nodeT* p3 = pp->step_p[step];
                    nodeT* p3prev = 0;
                    while(p3){
                        if(p3->evalvalue >= p2->evalvalue){
                            if(p3prev == 0){
                                p2->next = p3;
                                pp->step_p[step] = p2;
                            } else {
                                p3prev->next = p2;
                                p2->next = p3;
                            }
                            break;
                        }
                        p3prev = p3;
                        p3 = p3->next;
                    }
                    if(!p3){
                        p3prev->next = p2;
                    }
                }
                pp->step_count[step]++;
            }
        }
        p = p->next;
    }
    return 0;
}

static int next_ans_steps(problemT*pp, int step)
{
    nodeT* p = pp->ans_step_p[step-1];

    while(p) {
        int d;
        for(d=0; d<4; d++){
            nodeT* p2;
            p2 = create_node_step(pp, p, d);
            if(p2) {
                int step2 = step - 2;
                eval_value(pp, p2);
                if(p2->evalvalue > pp->ans_max_eval) {
                    pp->ans_max_eval = p2->evalvalue;
                }
                /* 同じパターン 検知 */
                while(step2 >= 0 && p2){
                    nodeT* p3 = pp->ans_step_p[step2];
                    while(p3) {
                        if((p3->evalvalue == p2->evalvalue) && !strcmp(p3->data, p2->data)){
                            delete_node(p2);
                            p2 = 0;
                            break;
                        }
                        p3 = p3->next;
                    }
                    step2 -= 2;
                }
            }
            if(p2) {
                pp->node_count++;
                p2->next = pp->ans_step_p[step];
                pp->ans_step_p[step] = p2;
                pp->ans_step_count[step]++;
            }
        }
        p = p->next;
    }
    return 0;
}

static int cut_datas(problemT*pp, int step)
{
    nodeT* p;
    int i;

    /* とりあえずdeleteフラグを立てておく */
    for(i=0; i<step; i++){
        p = pp->step_p[i];
        while(p){
            p->flag |= FLAG_DELETE;
            p = p->next;
        }
    }

    p = pp->step_p[step];
    for(i=0; i< CUT_REMAIN_NUM; i++){
        nodeT* prev;
        prev = p->prev;
        while(prev){
            prev->flag &= ~FLAG_DELETE;
            prev = prev->prev;
        }
        p=p->next;
    }

    while(p){
        p->flag |= FLAG_SKIP;
        p = p->next;
    }

    for(i=0; i<step; i++){
        p = pp->step_p[i];
//      fprintf(stderr, "*** step=%d\n", i);
//      dump_datas(p);
        while(p->next){
            if(p->next->flag & FLAG_DELETE){
                nodeT* p2;
                p2 = p->next;
                p->next = p->next->next;
                free(p2->data);
                free(p2);
                continue;
            }
            p = p->next;
        }
    }

    pp->step_count[step] = CUT_REMAIN_NUM;
    pp->cut_count++;
    return 0;
}

/*
 *  解等算出
 */
static int solver_main(const char* line)
{
    int ret;
    int step, ans_step;
    problemT* problem;
    nodeT* p;
    nodeT* p2;
    ret = parse_problem(line, &problem);
    if (ret < 0) return ret;
    problem->cut_count = 0;
    problem->node_count = 0;
    problem->ans_max_eval = 0;

    create_swap_data(problem);
//  dump_swap_data(problem);
    create_eval_data(problem);
//  dump_eval_data(problem);

    create_answer(problem);
//  dump_problem(problem);

    p = create_node(problem);
    p2 = create_node_answer(problem);
    eval_value(problem, p);
    eval_value(problem, p2);

    fprintf(stderr,"*** %d,%d,%s,%s,%d\n",
        problem->w, problem->h, problem->data, problem->goal, p->evalvalue);

    problem->found_answer = 0;
    problem->step_p[0] = p;
    problem->step_count[0] = 1;
    problem->ans_step_p[0] = p2;
    problem->ans_step_count[0] = 1;
    ans_step = 0;
    step = 0;

    while(0 == problem->found_answer){
        if(problem->ans_step_count[ans_step] < problem->step_count[step]){
            nodeT* p;
            ans_step++;
            next_ans_steps(problem, ans_step);
            fprintf(stderr, "*** ans[%d] count=%d eval=%d\n",
                ans_step, problem->ans_step_count[ans_step], problem->ans_max_eval);
            p = problem->ans_step_p[ans_step];
//          dump_datas(problem->ans_step_p[ans_step]);
            while(p){
                int i;
                for(i=step; i>=step-1; i--){
                    nodeT* p2 = problem->step_p[i];
                    while(p2){
                        if(problem->ans_max_eval < p2->evalvalue) {
                            break;
                        }
                        if((p->evalvalue == p2->evalvalue) && !strcmp(p->data, p2->data)){
                            print_answer(problem, p2, p);
                            problem->found_answer++;
                        }
                        p2 = p2->next;
                    }
                }
                p = p->next;
            }
        } else {
            nodeT* p;
            step++;
            next_steps(problem, step);
            p = problem->step_p[step];

            while(1){
                fprintf(stderr, "*** step[%d] count=%d eval=%d,%d(%s)",
                    step, problem->step_count[step], p->evalvalue, problem->step_max_eval[step], p->data);
                print_sequence(p, 0);
                fprintf(stderr, "\n");
                if(!p->next) break;
                if(p->evalvalue != p->next->evalvalue) break;
                p = p->next;
            }

            p = problem->step_p[step];
//          dump_datas(problem->step_p[step]);
            while(p){
                nodeT* p2 = problem->ans_step_p[ans_step];
                if(problem->ans_max_eval < p->evalvalue) {
                    break;
                }
                while(p2){
                    if((p->evalvalue == p2->evalvalue) && !strcmp(p->data, p2->data)){
                        print_answer(problem, p, p2);
                        problem->found_answer++;
                    }
                    p2 = p2->next;
                }
                p = p->next;
            }
        }
        if(problem->found_answer) break;
#if 0
        if(problem->ans_step_count[step] > CUT_DETECT_NUM) {
            fprintf(stderr, "*** cut ansdata count=%d\n", problem->ans_step_count[step]);
            cut_ans_datas(step);
        }
#endif
#if 1
        if(problem->step_count[step] > CUT_DETECT_NUM) {
            fprintf(stderr, "*** cutdata count=%d\n", problem->step_count[step]);
            cut_datas(problem, step);
//          dump_datas(problem->step_p[step]);
//          break;
        }
#endif
    }

    delete_problem(problem);

    return 0;
}

/*
 *  解等チェック
 */
static int checkans_main(const char* line)
{
    int ret;
    int step;
    problemT* problem;
    nodeT* p;
    ret = parse_answer(line, &problem);
    if (ret < 0) {
        printf("### parse error %s\n", line);
        return ret;
    }

    create_swap_data(problem);
//  dump_swap_data(problem);

    create_answer(problem);
//  dump_problem(problem);

    fprintf(stderr,"*** %d,%d,\"%s\",\"%s\",\"%s\"\n",
        problem->w, problem->h, problem->data, problem->goal, problem->sequence);

    p = create_node(problem);
//  dump_datas(p);

    step = 0;
    while(problem->sequence[step] != 0){
        switch(problem->sequence[step]){
        case 'L':
            p = create_node_step(problem, p, 0);
            break;
        case 'R':
            p = create_node_step(problem, p, 1);
            break;
        case 'U':
            p = create_node_step(problem, p, 2);
            break;
        case 'D':
            p = create_node_step(problem, p, 3);
            break;
        default:
            fprintf(stdout, "### sequence error %s,%s\n",
                problem->data, problem->sequence);
            ret = -1;
            goto err;
        }
        if(p == 0) {
            fprintf(stdout, "### sequence error %s,%s\n",
                problem->data, problem->sequence);
            ret = -1;
            goto err;
        }
        step++;
    }
    if(strcmp(p->data, problem->goal)){
        fprintf(stdout, "### NG %s,%s: %s(%s)\n",
            problem->data, problem->sequence, p->data, problem->goal);
        ret = -1;
        goto err;
    }

err:
    while(p) {
        nodeT* p2 = p;
        p = p->prev;
        delete_node(p2);
    }
    delete_problem(problem);
    return ret;
}

static int checkans(int argc, const char** argv)
{
    if(argc < 1) return -1;
    if(strcmp(argv[1], "-")){
        return checkans_main(argv[1]);
    }
    {
        char line[1024];
        while(fgets(line, 1024, stdin) != 0){
            checkans_main(line);
        }
    }
    return 0;
}

static int solver(int argc, const char** argv)
{
    if(argc < 1) return -1;
    if(strcmp(argv[1], "-")){
        return solver_main(argv[1]);
    }
    {
        char line[1024];
        while(fgets(line, 1024, stdin) != 0){
            solver_main(line);
        }
    }
    return 0;
}

/*
 *  回答提出用整形
 */
static int sumans(int argc, const char** argv)
{
    int ret;
    problemT* problem = 0;
    problemT* p;
    problemT* p2;
    char line[1024];
    int count = 0;
    int sum[4] = {0};
    int summax[4] = {0};
    int countmax = 0;
    const char* s;
    FILE*fp;
    FILE*fp2;
    int i;

    fp2 = fopen(argv[2], "r");
    if(!fp2) return -1;

    fgets(line, 1024, fp2);
//  fprintf(stderr, "*** line = %s\n", line);
    s = line;
    summax[0] = strtoul(s, 0, 10);
    s = strchr(s, ' ');
    if( !s ) return -1;
    summax[1] = strtoul(s+1, 0, 10);
    s = strchr(s+1, ' ');
    if( !s ) return -1;
    summax[2] = strtoul(s+1, 0, 10);
    s = strchr(s+1, ' ');
    if( !s ) return -1;
    summax[3] = strtoul(s+1, 0, 10);
    fgets(line, 1024, fp2);
//  fprintf(stderr, "*** line = %s\n", line);
    s = line;
    countmax = strtoul(s, 0, 10);
    fprintf(stderr, "*** max LRUD={%d,%d,%d,%d}\n", summax[0], summax[1], summax[2], summax[3]);
    fprintf(stderr, "*** max count=%d\n", countmax);

    fp = fopen(argv[1], "r");
    if(!fp) return -1;

    while(fgets(line, 1024, fp) != 0){
        ret = parse_answer(line, &p);
        if(ret < 0) continue;
        if(problem && !strcmp(problem->data, p->data)){
            //printf("skip %s\n", p->data);
            free(p->data);
            free(p->sequence);
            free(p);
            continue;
        }
        p->next = problem;
        problem = p;
        count++;
        for(i=0; p->sequence[i]; i++){
            switch(p->sequence[i]){
            case 'L':
                sum[0]++;
                break;
            case 'R':
                sum[1]++;
                break;
            case 'U':
                sum[2]++;
                break;
            case 'D':
                sum[3]++;
                break;
            }
        }
    }
    fprintf(stderr, "*** count=%d sum=(%d,%d,%d,%d)\n", count, sum[0], sum[1], sum[2], sum[3]);
    if(count > countmax) {
        fprintf(stderr, "*** count error\n");
        return -1;
    }
    for(i=0; i<4; i++){
        if(sum[i] > summax[i]) {
            fprintf(stderr, "*** LRUD limit error\n");
            return -1;
        }
    }

    for(i=0; i<countmax; i++){
        fgets(line, 1024, fp2);
        ret = parse_problem(line, &p2);
        p = problem;
        while(p){
            if(!strcmp(p2->data, p->data)){
                fprintf(stdout, "%s\r\n", p->sequence);
                break;
            }
            p = p->next;
        }
        if(!p){
            fprintf(stdout, "\r\n");
        }
    }
    return 0;
}

int main(int argc, const char** argv)
{
    if(strstr(argv[0], "solver"))
        return solver(argc, argv);
    if(strstr(argv[0], "checkans"))
        return checkans(argc, argv);
    if(strstr(argv[0], "sumans"))
        return sumans(argc, argv);
}