With square roots you can do this:
$(1234-5)\times6+7\times8^{\sqrt9} = 10958$
Without square roots or concatenation of the results of other operators, the best I can do is:
$\left((1+2\div3+4)^5\times6-7\right)^{8\div9} \approx 10958.1155551728$
It's just a coincidence that the best result without concatenation of results of other operators also involves no concatenation of digits.
This is the program that did the search. I wrote it a few years ago to solve another puzzle in the "stick some operators in this string of numbers" genre.
It doesn't do unary minus though, so maybe there's still room for improvement.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <float.h>
#include <math.h>
static double best;
#define MAXDIGITS 9
/* Also try MAXSQRT 1 for solution with sqrts. It's a lot slower! */
#define MAXSQRT 0
struct node {
enum {
LEAF, /* must be 0 */
ADD, /* must be first binary op */
SUB,
MUL,
DIV,
EXP /* must be last binary op */
} type;
/* valid in LEAF nodes only */
char digits[MAXDIGITS+1];
double leafval[MAXSQRT+1];
int digitsoffset;
/* valid in non-LEAF nodes only */
struct node *left, *right;
/* valid in all nodes */
int sqrtcount;
};
static void usage(const char *progname)
{
fprintf(stderr, "Usage: %s digits goal depth\n", progname);
exit(2);
}
static double getval(struct node *n)
{
double v;
int i;
switch(n->type) {
case LEAF: return n->leafval[n->sqrtcount];
case ADD: v=getval(n->left) + getval(n->right); break;
case SUB: v=getval(n->left) - getval(n->right); break;
case MUL: v=getval(n->left) * getval(n->right); break;
case DIV: v=getval(n->left) / getval(n->right); break;
case EXP: v=pow(getval(n->left), getval(n->right)); break;
default: assert(!"Unreachable");
}
for(i=0;i<n->sqrtcount;++i)
v=sqrt(v);
return v;
}
static void printexpr(struct node *n)
{
int i;
for(i=0;i<n->sqrtcount;++i)
printf("sqrt(");
switch(n->type) {
case LEAF:
printf("%s", n->digits);
break;
case ADD:
if(!n->sqrtcount) printf("(");
printexpr(n->left);
printf("+");
printexpr(n->right);
if(!n->sqrtcount) printf(")");
break;
case SUB:
if(!n->sqrtcount) printf("(");
printexpr(n->left);
printf("-");
printexpr(n->right);
if(!n->sqrtcount) printf(")");
break;
case MUL:
if(!n->sqrtcount) printf("(");
printexpr(n->left);
printf("*");
printexpr(n->right);
if(!n->sqrtcount) printf(")");
break;
case DIV:
if(!n->sqrtcount) printf("(");
printexpr(n->left);
printf("/");
printexpr(n->right);
if(!n->sqrtcount) printf(")");
break;
case EXP:
if(!n->sqrtcount) printf("(");
printexpr(n->left);
printf("**");
printexpr(n->right);
if(!n->sqrtcount) printf(")");
break;
default:
assert(!"Unreachable");
}
for(i=0;i<n->sqrtcount;++i)
printf(")");
}
int nodesused;
struct node nodes[MAXDIGITS*2-1];
#define root (&nodes[0])
int last_split_offset;
static void do_splits(int maxsplits, double goal)
{
struct node *n;
int splitnode, length, leftlength, save_last_split_offset;
double v, e;
v=getval(root);
e=fabs(v-goal);
if(e < best) {
best=e;
printexpr(root);
printf(" = %.18g\n", v);
}
if(!maxsplits)
return;
/* Try each leaf node with more than 1 digit that is not left of the last
split point */
for(splitnode=0 ; splitnode<nodesused ; ++splitnode) {
n=&nodes[splitnode];
if(n->type!=LEAF || !n->digits[1] || n->digitsoffset<last_split_offset)
continue;
/* Record the node being split, and remember the previous one */
save_last_split_offset=last_split_offset;
last_split_offset=n->digitsoffset;
/* Attach children */
n->left=&nodes[nodesused++];
n->left->type=LEAF;
n->right=&nodes[nodesused++];
n->right->type=LEAF;
/* Try each split point */
length=strlen(n->digits);
memcpy(n->left->digits, n->digits, length-1);
n->left->digitsoffset=n->digitsoffset;
n->right->digitsoffset=n->digitsoffset+length-1;
for(leftlength=length-1 ; leftlength>0 ; --leftlength) {
/* Distribute digits to children */
/*memcpy(n->left->digits, n->digits, leftlength);*/
n->left->digits[leftlength]=0;
n->left->leafval[0]=atof(n->left->digits);
#if MAXSQRT
n->left->leafval[1]=sqrt(n->left->leafval[0]);
#endif
strcpy(n->right->digits, n->digits+leftlength);
n->right->leafval[0]=atof(n->right->digits);
#if MAXSQRT
n->right->leafval[1]=sqrt(n->right->leafval[0]);
#endif
--n->right->digitsoffset;
/* Try each binary operator */
for(n->type=ADD ; n->type<=EXP ; ++n->type) {
do_splits(maxsplits-1, goal);
#if MAXSQRT==1
++n->left->sqrtcount;
do_splits(maxsplits-1, goal);
++n->right->sqrtcount;
do_splits(maxsplits-1, goal);
--n->left->sqrtcount;
do_splits(maxsplits-1, goal);
--n->right->sqrtcount;
#endif
}
}
/* Unsplit: free children and revert to leaf. n->digits[] is still good. */
nodesused-=2;
n->type=LEAF;
/* Restore remembered stuff */
last_split_offset=save_last_split_offset;
}
}
static void search(const char *digits, int maxsplits, double goal)
{
root->type=LEAF;
strcpy(root->digits, digits);
root->leafval[0]=atof(root->digits);
#if MAXSQRT
root->leafval[1]=sqrt(root->leafval[0]);
#endif
root->digitsoffset=0;
root->sqrtcount=0;
nodesused=1;
last_split_offset=0;
do_splits(maxsplits, goal);
#if MAXSQRT
++root->sqrtcount;
do_splits(maxsplits, goal);
--root->sqrtcount;
#endif
assert(nodesused==1);
nodesused=0;
}
int main(int argc, char **argv)
{
const char *digits;
char *endp;
double goal;
int splits;
if(argc!=4)
usage(argv[0]);
digits=argv[1];
if(strspn(digits, "0123456789")!=strlen(digits))
usage(argv[0]);
if(strlen(digits)>MAXDIGITS) {
fprintf(stderr, "Too many digits (max is %d).\n"
"Increase MAXDIGITS and recompile.\n", MAXDIGITS);
return 1;
}
goal=strtod(argv[2], &endp);
if(*endp)
usage(argv[0]);
splits=strtol(argv[3], &endp, 10);
if(*endp)
usage(argv[0]);
if(splits>=(int)strlen(digits)) {
fprintf(stderr, "Not enough digits to perform %d splits\n", splits);
return 1;
}
best=DBL_MAX;
search(digits, splits, goal);
return 0;
}
^operator. – aroth Apr 20 '17 at 13:39