/* Number Puzzle. This program attempts to solve a 'countdown' number puzzle by brute force. The contestants are given six smallish numbers, and a three digit target. The object is to create an arithmetic expression which combines the six numbers and the arithmetic operations plus (+), subtract (-), multiply (*) and divide (%) to give the desired target. For example the six numbers 3, 6, 8, 10, 50 and 75 are given and the target is 954. One possible solution is 6*(10+50+75+3*8) = 954. Brute force uses all possible expressions using the six numbers. An upper bound for the set of all possible expressions may be calculated. This is 42*1024*720 = 30965760. 42 comes from the number of reverse Polish notation strings for non commutative operators. 1024 comes from taking five binary operators from the set of four basic arithmetic operators, plus, minus, times and divide. The 720 comes from the number of permutations of six distinct numbers. In fact many expressions are equivalent, so the figure of thirty million may be reduced to about 300000. The program uses a random selection algorithm in place of exhaustive enumeration. Flies are low numbers, and the program simulates a cat swatting flies until it finds one to eat: the target number. In practice there are recalcitrant numbers: the program gives no answer. It could be that achieving these numbers is impossible for all expressions involving the six base numbers. One way of proving impossibility is examination of all the cases, which only takes a few minutes. Example of usage: swatter -x 1 2 3 10 25 75 441 */ #include #define NRPN6 42 #define RPNLEN 11 #define OK 0 #define ERROR -1 #define IRAND(X) (rand()%(X)) int xrange[1000]; char *rpn6[] = { "AA+A+A+A+A+", "AA+A+A+AA++", "AA+A+AA++A+", "AA+A+AA+A++", "AA+A+AAA+++", "AA+AA++A+A+", "AA+AA++AA++", "AA+AA+A++A+", "AA+AA+A+A++", "AA+AA+AA+++", "AA+AAA+++A+", "AA+AAA++A++", "AA+AAA+A+++", "AA+AAAA++++", "AAA++A+A+A+", "AAA++A+AA++", "AAA++AA++A+", "AAA++AA+A++", "AAA++AAA+++", "AAA+A++A+A+", "AAA+A++AA++", "AAA+A+A++A+", "AAA+A+A+A++", "AAA+A+AA+++", "AAA+AA+++A+", "AAA+AA++A++", "AAA+AA+A+++", "AAA+AAA++++", "AAAA+++A+A+", "AAAA+++AA++", "AAAA++A++A+", "AAAA++A+A++", "AAAA++AA+++", "AAAA+A+++A+", "AAAA+A++A++", "AAAA+A+A+++", "AAAA+AA++++", "AAAAA++++A+", "AAAAA+++A++", "AAAAA++A+++", "AAAAA+A++++", "AAAAAA+++++" }; /* table of permutations */ int perm6_list[720][6]; /* relative operator frequency from "+-*%" */ char *str_4ops = "+*-%"; char *buttons = "++++***--%"; #define NBUTTONS strlen(buttons) /* fold three loop indices */ #define IDX_FOLD(I,J,K) 1+(K)+720*((J)+1024*(I)) int qv = 0; /* verbose */ int qx = 0; /* exhaustive search */ int cnt = 100000; /* iteration count */ main(int argc, char **argv) { extern int atoi(); extern int srand(); char expr[12]; int xx[7]; int idx[6]; int yy[6]; char *s; int target; int i, k = 0; int seed = 0; int rc; for (argv++, argc--; 0 < argc--; argv++) { s = *argv; if ('-' == *s) switch (s[1]) { case 'c': cnt = atoi(* ++argv); argc--; /* count */ break; case 's': seed = atoi(* ++argv); argc--; /* seed */ break; case 'v': qv = 1; /* verbose */ break; case 'e': /* exhaustive search */ case 'x': qx = 1; default: break; } else if (k < 7) xx[k++] = atoi(*argv); } if (k != 7) { printf("swatter x1 x2 x3 x4 x5 x6 target -c cnt -seed seed\n"); return ERROR; } if (qv) { printf("%d %d %d %d %d %d -target %d\n", xx[0], xx[1],xx[2], xx[3], xx[4], xx[5], xx[6]); printf("seed = %d cnt = %d\n",seed, cnt); } target = xx[6]; if (0 < seed) srand(seed); if (qx) return do_all_cases(cnt, &xx[0], target); for (i=0; i<1000; i++) xrange[i] = 0; /* values */ for (; 0 < cnt--; ) { mk_rpnstr(&expr[0]); perm6(&idx[0]); rc = rpn_eval(&xx[0], &idx[0], &expr[0]); if (rc >0 && rc < 1000) { if (qv && xrange[rc] == 0) { /* print new values */ printf ("%d <- ", rc); for (i=0; i<6; i++) printf("%d ", xx[idx[i]]); printf(" %11.11s\n", &expr[0]); } xrange[rc]++; } if (rc == target) break; } if (rc == target) print_rpn (&xx[0], &idx[0], &expr[0]); return 0; } int perm6(int *dst) /* random permutation of 6 elements */ { extern int rand(); int i; int k = 0; if (dst == NULL) return ERROR; for (i=0; i<6; i++) dst[i] = -1; while (k<6) { i = IRAND(6); if (dst[i] < 0) dst[i] = k++; } return OK; } int mk_rpnstr(char *dst) { extern int rand(); char *src = rpn6[IRAND(NRPN6)]; int i, k; for (i = 0; i<11; i++) { k = src[i]; dst[i] = (k == 'A') ? k : buttons[IRAND(NBUTTONS)]; } return OK; } int rpn_eval(int *dat, int *idx, char *str) { int stack[6]; int sp = 0; int i, k, val; for (i = k = 0; i<11; i++) { if (str[i] == 'A') stack[sp++] = dat[idx[k++]]; else { switch (str[i]) { case '+': val = stack[sp-2] + stack[sp-1]; break; case '-': val = stack[sp-2] - stack[sp-1]; break; case '*': val = stack[sp-2] * stack[sp-1]; break; case '%': val = ((stack[sp-1]==0) || (0 != stack[sp-2] % stack[sp-1])) ? ERROR : stack[sp-2] / stack[sp-1]; break; default: break; } if (val <= 0) return ERROR; sp = sp-2; stack[sp++] = val; } } return val; } /* give coherant evaluation sequence */ int print_rpn(int *dat, int *idx, char *str) { int stack[6]; int sp = 0; int i, k, val; for (i = k = 0; i<11; i++) { if (str[i] == 'A') stack[sp++] = dat[idx[k++]]; else { switch (str[i]) { case '+': val = stack[sp-2] + stack[sp-1]; break; case '-': val = stack[sp-2] - stack[sp-1]; break; case '*': val = stack[sp-2] * stack[sp-1]; break; case '%': val = ((stack[sp-1]==0) || (0 != stack[sp-2] % stack[sp-1])) ? ERROR : stack[sp-2] / stack[sp-1]; break; default: break; } if (val <= 0) return ERROR; printf ("%d=%d%c%d ", val, stack[sp-2], str[i], stack[sp-1]); sp = sp-2; stack[sp++] = val; } } printf("\n"); return val; } int do_all_cases(int cnt, int val[], int target) { int rand(); char expr[11]; char *sx; int i, j, k, rc, dzsq; if (qv) printf("examining all the cases .......\n"); set_perm6_list(); for (i = 0; i < NRPN6; i++) { /* expressions */ sx = rpn6[i]; if (qv) printf("expression type %11.11s\n", sx); for (j = 0; j<1024; j++) { mod_rpnstr(&expr[0], sx, j); for (k = 0; k < 720; k++) { rc = rpn_eval (val, &perm6_list[k][0], &expr[0]); if (rc > 0 && rc < 1000) xrange[rc]= 1+IDX_FOLD( i, j, k); if (rc == target) { print_rpn (val, &perm6_list[k][0], &expr[0]); k = 720; if (0 == --cnt) return OK; } } } } if (qv) { /* print encoded solutions target = 1 to 999 */ for(i=1; i<1000; i++) printf ("%4d %12d\n", i, xrange[i]); } return OK; } /* generate 720 permutations of 0 1 2 3 4 5 */ int set_perm6_list() { int p_next(); int i, j, k; int tmp[6]; for (j=0; j<6; j++) tmp[j]=j; for (i=0; i<720; i++) { p_next(6, &tmp[0]); for (j=0; j<6; j++) perm6_list[i][j] = tmp[j]; } return OK; } int p_next(int n, int *a) { int i, idx, j, k, min, x; for (i = n-2; i >= 0 && a[i] > a[i+1]; i--); if (i<0) return 1; x = a[i]; /* element to change */ for (j= i+1, min = n; j <= n-1; j++) { if (a[j] > x && a[j]< min) { k=j; min = a[k]; } } a[i] = a[k]; /* next possible successor */ a[k] = x; /* reverse (i.e. sort) elements a[i+1] ... a[n-1] */ for(j = i+1, k = n-1; j < k; j++, k--) { x = a[j]; a[j] = a[k]; a[k] = x; } return 0; } int mod_rpnstr(char *dst, char *src, int seq) { int i; for (i = 0; i<11; i++) { if (src[i] == 'A') dst[i] = 'A'; else { dst[i] = str_4ops[ seq % 4]; seq /= 4; } } return OK; }