小町算を一瞬で生成するプログラム 例: 12*34*5+6*7-8*9 = 2010
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; }