Created
January 13, 2010 11:31
-
-
Save qnighy/276122 to your computer and use it in GitHub Desktop.
Creates komachi-zan that makes the number you want
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment