小町算を一瞬で生成するプログラム 例: 12*34*5+6*7-8*9 = 2010

Programming C

piがHaskellで組んでこれより速くCで組めるわけないとか挑発されたので、つい…

性能

  • 12*34*5+6*7-8*9 = 2010 のような小町算を生成します。
  • (1*2/3-4*56)/(7-8)*9 = 2010 のような、括弧を使うものも生成します。
  • 2-(3-4)のような右結合は、等価の左結合、つまり(2-3)+4、が存在するので出力されません。
  • 0.2秒とかそこらで計算できます。
  • 今のところソースしかないです。

実行例

% ./komachi 2010
1-(2+3/4*5*6)*(7-89)
1-(2+3*45/6)*(7-89)
1-(23+(4+5)/6)*(7-89)
1-((2+34)*56-7)*(8-9)
1-((2+34)*56-7)/(8-9)
1*((2+34)*56-7-8+9)
1*2*((3*4-5+6)*78-9)
1+2+3*(4*(5+6)*(7+8)+9)
(以下略)

反省

C++にすればもうちょっと簡潔に書けたのになあ。

ソース

Creates komachi-zan that makes the number you want — Gist

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

const int digits[] = {1,2,3,4,5,6,7,8,9};
#define SIZE 9
#define DP_MAX 5

#define CSIZE 10
struct expr {
    int n;
    int d;
    int type;
    struct expr* l0;
    struct expr* l1;
};
int digit_numbers[CSIZE][CSIZE];

int exprs_size[CSIZE][CSIZE];
struct expr *exprs[CSIZE][CSIZE];

void evaluate_single(struct expr* e, int type, struct expr* l0, struct expr* l1) {
    int x,y;
    switch(type) {
    case 0:
        e->n = l0->n * l1->d + l1->n * l0->d;
        e->d = l0->d * l1->d;
        break;
    case 1:
        e->n = l0->n * l1->d - l1->n * l0->d;
        e->d = l0->d * l1->d;
        break;
    case 2:
        e->n = l0->n * l1->n;
        e->d = l0->d * l1->d;
        break;
    case 3:
        e->n = l0->n * l1->d;
        e->d = l0->d * l1->n;
        break;
    }
    x=e->n, y=e->d;
    while(y) {
        int t=x%y; x=y; y=t;
    }
    if(x) {
        e->n /= x;
        e->d /= x;
    }
    if(e->d<0) {
        e->n = -e->n;
        e->d = -e->d;
    }
}
void evaluate_reverse(struct expr* e, int type, struct expr* lx, struct expr* lret, int reverse_type) {
    static const int revtypes[2][4] = {{1, 0, 3, 2},{1, 1,3,3}};
    if(reverse_type==0 || (type&1)==0) {
        evaluate_single(e, revtypes[reverse_type][type], lret, lx);
    } else {
        evaluate_single(e, revtypes[reverse_type][type], lx, lret);
    }
    if(type==3 && lx->n==0) {
        e->d = 0;
    }
    if(lx->d==0 || lret->d==0) {
        e->d = 0;
    }
}
void reevaluate(struct expr* e) {
    if(e->type==-1)return;
    reevaluate(e->l0);
    reevaluate(e->l1);
    evaluate_single(e, e->type, e->l0, e->l1);
}
void setexpr(struct expr* e, int type, struct expr* l0, struct expr* l1) {
    e->type = type;
    e->l0 = l0;
    e->l1 = l1;
    evaluate_single(e, type, l0, l1);
}
void setint(struct expr* e, int i) {
    e->type = -1;
    e->n = i;
    e->d = 1;
}
const char *operator_str[] = {"+", "-", "*", "/"};
int operator_rank[] = {0,0,1,1};
int expr_printable(struct expr* e, int parent_inherit_rank) {
    int current_inherit_rank;
    if(e->type == -1) {
        return 1;
    }
    current_inherit_rank = operator_rank[e->type];
    if(parent_inherit_rank == current_inherit_rank) {
        return 0;
    }
    return expr_printable(e->l0, -1) && expr_printable(e->l1, current_inherit_rank);
}
int expr_compare(const struct expr* e0, const struct expr* e1) {
    int n0 = e0->n * e1->d;
    int n1 = e1->n * e0->d;
    return e0->d==0 ? 
        e1->d==0 ? 0 : 1 :
        e1->d==0 ? -1 : (
                n0==n1 ? 0 : n0<n1 ? -1 : 1
        );
}
void expr_print(struct expr* e, int parent_inherit_rank) {
    int current_inherit_rank;
    if(e->type == -1) {
        printf("%d", e->n);
        return;
    }
    current_inherit_rank = operator_rank[e->type];
    if(current_inherit_rank < parent_inherit_rank) {
        printf("(");
    }
    expr_print(e->l0, current_inherit_rank);
    printf("%s", operator_str[e->type]);
    expr_print(e->l1, current_inherit_rank);
    if(current_inherit_rank < parent_inherit_rank) {
        printf(")");
    }
}
void printexpr(struct expr* e) {
    if(expr_printable(e, -1)) {
        expr_print(e, -1);
        printf("\n");
    }
}
void init() {
    int off,len, mlen;
    int i,j,k;
    memset(digit_numbers, -1, sizeof(digit_numbers));
    memset(exprs_size, 0, sizeof(exprs_size));
    memset(exprs, 0, sizeof(exprs));
    for(off = 0; off < SIZE; off++) {
        int num = 0;
        for(len = 1; off+len<=SIZE; len++) {
            num = num*10 + digits[off+len-1];
            digit_numbers[off][len] = num;
        }
    }
    for(len = 1; len <= SIZE; len++) {
        for(off = 0; off+len <= SIZE; off++) {
            exprs_size[off][len] = 1;
            if(len<=DP_MAX) {
                for(mlen = 1; mlen<len; mlen++) {
                    exprs_size[off][len] += exprs_size[off][mlen] * exprs_size[off+mlen][len-mlen] * 4;
                }
            }

            exprs[off][len] = malloc(sizeof(struct expr) * exprs_size[off][len]);
            i = 0;
            setint(&exprs[off][len][i++], digit_numbers[off][len]);
            if(len<=DP_MAX) {
                for(mlen = 1; mlen<len; mlen++) {
                    for(j = 0; j < exprs_size[off][mlen]; j++) {
                        for(k = 0; k < exprs_size[off+mlen][len-mlen]; k++) {
                            setexpr(&exprs[off][len][i++], 0, &exprs[off][mlen][j], &exprs[off+mlen][len-mlen][k]);
                            setexpr(&exprs[off][len][i++], 1, &exprs[off][mlen][j], &exprs[off+mlen][len-mlen][k]);
                            setexpr(&exprs[off][len][i++], 2, &exprs[off][mlen][j], &exprs[off+mlen][len-mlen][k]);
                            setexpr(&exprs[off][len][i++], 3, &exprs[off][mlen][j], &exprs[off+mlen][len-mlen][k]);
                        }
                    }
                }
            }
            qsort(exprs[off][len], exprs_size[off][len], sizeof(struct expr), (int(*)(const void *, const void *))expr_compare);
        }
    }
}

void findrange(int off, int len, struct expr* target, struct expr** repl, struct expr** root) {
    int mlen;
    int i,k;
    if(target->d == 0)return;

    struct expr* p = bsearch((const void*)target, exprs[off][len], exprs_size[off][len], sizeof(struct expr), (int(*)(const void *, const void *))expr_compare);
    if(p) {
        while(p>=exprs[off][len] && !expr_compare(target, p)) {
            p--;
        }
        p++;
        while(p<exprs[off][len]+exprs_size[off][len]
                && !expr_compare(target, p)) {
            *repl = p;
            printexpr(*root);
            p++;
        }
    }
    if(len > DP_MAX) {
        for(mlen = 1; mlen < len; mlen++) {
            if(mlen < len-mlen) {
                for(i = 0; i < exprs_size[off][mlen]; i++) {
                    for(k = 0; k < 4; k++) {
                        struct expr new_target;
                        struct expr leaf;
                        evaluate_reverse(&new_target, k, &exprs[off][mlen][i], target, 1);
                        *repl = &leaf;
                        leaf.type = k;
                        leaf.l0 = &exprs[off][mlen][i];
                        findrange(off+mlen, len-mlen, &new_target, &leaf.l1 , root);
                    }
                }
            } else {
                for(i = 0; i < exprs_size[off+mlen][len-mlen]; i++) {
                    for(k = 0; k < 4; k++) {
                        struct expr new_target;
                        struct expr leaf;
                        evaluate_reverse(&new_target, k, &exprs[off+mlen][len-mlen][i], target, 0);
                        *repl = &leaf;
                        leaf.type = k;
                        leaf.l1 = &exprs[off+mlen][len-mlen][i];
                        findrange(off, mlen, &new_target, &leaf.l0 , root);
                    }
                }
            }
        }
    }
}

int main(int argc, char **argv) {
    struct expr *root;
    struct expr target;
    target.d = 1;
    if(argc <= 1 || sscanf(argv[1], "%d/%d", &target.n, &target.d)==0) {
        fprintf(stderr, "usage: komachi 2010\n");
        return 1;
    }
    init();

    findrange(0, SIZE, &target, &root, &root);
    return 0;
}