自分のスキルでご飯食べられるといいなぁ

Programing

というわけで、これ(http://headlines.yahoo.co.jp/hl?a=20100404-00000003-zdn_ep-sci)に挑戦してみました。
実時間は3時間くらいかかったけど、合間に別のことやったりしたから実際は1時間半くらい。
簡単にソースの解説を置いておくと、

  • yaku構造体に面子を木構造で入れていって、最後に木を解体しながら出力してる感じ
    • 本当は構造体の名前はyakuじゃなくてmentsuにすべきだったけど、コーディング終わってから気づいた
  • 333345みたいな牌のときに、(333)(345)と(345)(333)と二通り出ないように、刻子と頭は前の面子の最初の要素と異なっているか確認するようにした
    • (33)(33)とか(33)[33]とかありえないから考えなくていいし。
  • 七対子って、同じ牌4子は成立しないらしいね。プログラム終わってから気づいたから直してないけど
  • "atamable"(頭にすることが出来るか)って変数名が頭悪そうな感じでちょっと気に入ってる
  • 九蓮宝燈ってちゃんと役の形になってたんだね……

実行結果とソースを下のほうにぺたり。
//あと、待ちを出力するプログラム、って当たり牌を表示するプログラムのことだろjk……。
実行結果

iselix@redwasp ~/src $ ./a.out
1112224588899
(111)(222)[45](888)(99)
1122335556799
(123)(123)(555)[67](99)
(123)(123)[55](567)(99)
(123)(123)(55)(567)[99]
1112223335559
(111)(222)(333)(555)[9]
(123)(123)(123)(555)[9]
1223344888999
[1](234)(234)(888)(999)
(123)(234)[4](888)(999)
(123)[23](44)(888)(999)
1112345678999
(111)[2](345)(678)(999)
(111)(234)[5](678)(999)
(111)(234)(567)[8](999)
(111)(234)(567)[89](99)
(111)(234)[56](789)(99)
(111)[23](456)(789)(99)
[11](123)(456)(789)(99)
(11)(123)(456)(789)[99]
(11)(123)(456)[78](999)
(11)(123)[45](678)(999)
(11)[12](345)(678)(999)
0
iselix@redwasp ~/src $

ソースコード

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

typedef struct _yaku{
    char waiting; /*0:完成 1:待ち -1:終端*/
    char hai[4];
    struct _yaku *child;
    struct _yaku *brother;
    struct _yaku *parent;
} yaku;

yaku* addbrother(yaku *y){
    y->brother = malloc(sizeof(yaku));
    y->brother->parent = y->parent;
    y = y->brother;
    y->waiting = -1;
    return y;
}

yaku* addchild(yaku *y){
    y->child = malloc(sizeof(yaku));
    y->child->parent = y;
    y->child->waiting = -1;
    return y->child;
}    

int _solve(int *hai, int num, int atamable, int waitable, yaku *result){
    int i, j, ret, res;
    if(num < 0)
        return 0;
    if(num == 0){
        result->waiting = -1;
        return 1;
    }
    result->waiting = -1;
    addchild(result);
    ret = 0;
    for(i=0; i<9; ++i)
        if(hai[i])
            break;
    if(!result->parent || result->parent->hai[0] != '1'+i){
        /*刻子*/
        if(hai[i] >= 3){
            hai[i] -= 3;
            for(j=0; j<3; ++j)
                result->hai[j] = i+'1';
            result->hai[3] = '\0';
            if(res = _solve(hai, num-3, atamable, waitable, result->child)){
                result->waiting = 0;
                result = addbrother(result);
                addchild(result);
                ret += res;
            }
            hai[i] += 3;
        }
        /*刻子(待ち)*/
        if(hai[i] >= 2 && waitable){
            hai[i] -= 2;
            result->hai[0] = result->hai[1] = '1'+i;
            result->hai[2] = '\0';
            if(res = _solve(hai, num-2, atamable, 0, result->child)){
                result->waiting = 1;
                result = addbrother(result);
                addchild(result);
                ret += res;
            }
            hai[i] += 2;
        }
        /*頭*/
        if(hai[i] >= 2 && atamable){
            hai[i] -= 2;
            result->hai[0] = result->hai[1] = '1'+i;
            result->hai[2] = '\0';
            if(res = _solve(hai, num-2, 0, waitable, result->child)){
                result->waiting = 0;
                result = addbrother(result);
                addchild(result);
                ret += res;
            }
            hai[i] += 2;
        }
        /*頭(待ち)*/
        if(waitable && atamable){
            hai[i] -= 1;
            result->hai[0] = '1'+i;
            result->hai[1] = '\0';
            if(res = _solve(hai, num-1, 0, 0, result->child)){
                result->waiting = 1;
                result = addbrother(result);
                addchild(result);
                ret += res;
            }
            hai[i] += 1;
        }
    }
    /*順子*/
    if(i<7 && hai[i+1] && hai[i+2]){
        yaku *tmp = result->parent;
        for(j=0; j<3; ++j)
            --hai[i+j];
        for(j=0; j<3; ++j)
            result->hai[j] = '1'+i+j;
        result->hai[3] = '\0';
        if(res = _solve(hai, num-3, atamable, waitable, result->child)){
            result->waiting = 0;
            result = addbrother(result);
            addchild(result);
            ret += res;
        }
        for(j=0; j<3; ++j)
            ++hai[i+j];
    }
    /*順子(リャンメン)*/
    if(i<8 && hai[i+1] && waitable){
        --hai[i]; --hai[i+1];
        result->hai[0] = '1'+i;
        result->hai[1] = '1'+i+1;
        result->hai[2] = '\0';
        if(res = _solve(hai, num-2, atamable, 0, result->child)){
            result->waiting = 1;
            result = addbrother(result);
            addchild(result);
            ret += res;
        }
        ++hai[i]; ++hai[i+1];
    }
    /*順子(カンチャン)*/
    if(i<7 && hai[i+2] && waitable){
        --hai[i]; --hai[i+2];
        result->hai[0] = '1'+i;
        result->hai[1] = '1'+i+2;
        result->hai[2] = '\0';
        if(res = _solve(hai, num-2, atamable, 0, result->child)){
            result->waiting = 1;
            result = addbrother(result);
            addchild(result);
            ret += res;
        }
        ++hai[i]; ++hai[i+2];
    }
    free(result->child);
    return ret;
}

yaku* solve(int *hai){
    int i,count = 0;
    yaku *ret = malloc(sizeof(yaku));
    ret->child = ret->brother = ret->parent = NULL;
    for(i=0; i<9; ++i)
        if(hai[i] == 2 || hai[i] == 3)
            ++count;
        else if(hai[i] == 4)
            count+=2;
    _solve(hai, 13, 1, 1, ret);
    if(count == 6){ /*七対子*/
        yaku *tmp = ret;
        while(tmp->waiting != -1)
            tmp = tmp->brother;
        addbrother(tmp);
        addchild(tmp);
        for(i=0; i<9; ++i){
            if(hai[i]){
                if(hai[i] == 1){
                    tmp->waiting = 1;
                    tmp->hai[0] = '1'+i;
                    tmp->hai[1] = '\0';
                }
                if(hai[i] == 2){
                    tmp->waiting = 0;
                    tmp->hai[0] = tmp->hai[1] = '1'+i;
                    tmp->hai[2] = '\0';
                }
                if(hai[i] == 3){
                    tmp->waiting = 0;
                    tmp->hai[0] = tmp->hai[1] = '1'+i;
                    tmp->hai[2] = '\0';
                    tmp = addchild(tmp);
                    addbrother(tmp);
                    tmp->waiting = 1;
                    tmp->hai[0] =  '1'+i;
                    tmp->hai[1] = '\0';
                }
                if(hai[i] == 4){
                    tmp->waiting = 0;
                    tmp->hai[0] = tmp->hai[1] = '1'+i;
                    tmp->hai[2] = '\0';
                    tmp = addchild(tmp);
                    addbrother(tmp);
                    tmp->waiting = 0;
                    tmp->hai[0] = tmp->hai[1] = '1'+i;
                    tmp->hai[2] = '\0';
                }
                tmp = addchild(tmp);
                addbrother(tmp);
            }
        }
    }
    return ret;
}

int print_free_tree(yaku *y){
    char close;
    if(y->waiting == -1)
        return 0;
    if(y->waiting){
        putchar('[');
        close = ']';
    }else{
        putchar('(');
        close = ')';
    }
    fputs(y->hai, stdout);
    putchar(close);
    if(y->child->waiting != -1){
        if(print_free_tree(y->child))
            return 1;
    }else{
        free(y->child);
        putchar('\n');
    }
    if(y->brother->waiting != -1){
        yaku *tmp = y->brother;
        memcpy(y, y->brother, sizeof(yaku));
        free(tmp);
        return 1;
    }
    free(y);
    return 0;
}

int main(){
    while(1){
        int hai[9];
        int i, j, num;
        yaku *y;
        for(i=0; i<9; ++i)
            hai[i] = 0;
        for(i=0; i<13; ++i){
            char c;
            do
                c = getchar();
            while(!isdigit(c));
            if(c == '0')
                return 0;
            hai[c-'1']++;
        }
        y = solve(hai);
        while(print_free_tree(y));
    }
}