Return to Revisions

Similar to whuber's answer, we can use Groupings to simplify the generation patterns, it's introduced from Mathematica 11, and use parallel computing, which is a little faster.

LaunchKernels[];
st=AbsoluteTime[];
n=7;
sets=Range[n];
target=100;

patterns=Thread[Evaluate[HoldForm/@Block[{i=1},Groupings[sets,o->2]/.o:>
  Slot[Mod[i++,Length@sets-1,1]]]]&];

OP1[x_,y_]:=-x+y;
OP2[t_Integer,u_Integer]:=10 t+u;
op=Tuples[{Plus,Subtract,Times,Divide,OP1,OP2},Length@sets-1];

SetSharedVariable[L];
L={};
ParallelDo[Block[{expr=f@@o,val:=Quiet@ReleaseHold@expr},
If[val==target||val==-target,AppendTo[L,InputForm/@expr]]],{o,op},{f,patterns}];

Length[ans=Select[L,FreeQ[#,OP2[_,Except[_Integer]]|OP2[Except[_Integer],_],-1]&]]
AbsoluteTime[]-st

For $n=\{{6,7,8}\}$, it take about $\{{1.43,\;19.69,\;860.85}\}$ seconds.
When $n=9$, it doesn't finished for $4$ hours, I terminate it.

Still very slow, I tried to convert all the patterns to C code, it's not difficult, the generated C code is more than 5,700 lines, the efficiency improvement is very obvious.

Finally, the program takes about $10$ seconds to finds $422716$ distinct solutions, same result as whuber.

Code

n=9;
gps=Block[{i=1,j=1},Groupings[Table[x,n],f->2]/.
  {f:>(F[#,Symbol["i"<>ToString@Mod[i++,n-1,1]],#2]&),x:>Symbol["n"<>ToString[Mod[j++,n,1]]]}]

gen=StringTemplate["if(check1(``)){
    sprintf(buffer, \"``\\n\", ``);
    if(check2(buffer)) printf(\"%s\", buffer);
}"][ToString@CForm@#, 
  StringReplace[ToString@#,{"F"|", "->"","["->"(","]"->")",
    "n"~~DigitCharacter:>"%d","i"~~DigitCharacter:>"%c"}],
  StringReplace[StringRiffle[#//.F[x___]:>{x}//Flatten,","],"i"->"o"]
]&/@gps//StringRiffle[#,"\n"]&;

src="#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>

#define NUM 100
#define N 6
#define EPS 1e-8

char ops[N] = {'+', '-', '*', '/', '#', '@'};
char buffer[128];

double F(double x, int op, double y) {
    double arr[] = {x + y, x - y, x * y, x / y, 10 * x + y, -x + y};
    return arr[op];
}

int check1(double x) {
    return fabs(x - NUM) < EPS || fabs(x + NUM) < EPS;
}

int check2(char buffer[]) {
    return (!strstr(buffer, \"#(\") && !strstr(buffer, \")#\"));
}

void calc(int a[]) {
    int len = 0;
    int n1 = a[0], n2 = a[1], n3 = a[2], n4 = a[3], n5 = a[4], n6 = a[5], n7 = a[6], n8 = a[7], n9 = a[8];
    #pragma omp parallel for schedule(dynamic) reduction(+:buffer)
    for (int i1 = 0; i1 < N; i1++) {
        for (int i2 = 0; i2 < N; i2++)
            for (int i3 = 0; i3 < N; i3++)
                for (int i4 = 0; i4 < N; i4++)
                    for (int i5 = 0; i5 < N; i5++)
                        for (int i6 = 0; i6 < N; i6++)
                            for (int i7 = 0; i7 < N; i7++)
                                for (int i8 = 0; i8 < N; i8++) {
                                    char o1 = ops[i1], o2 = ops[i2], o3 = ops[i3], o4 = ops[i4], o5 = ops[i5], o6 = ops[i6], o7 = ops[i7], o8 = ops[i8];
``
                                }
    }
}

int main() {
    clock_t t0 = clock();
    freopen(\"output.txt\", \"w\", stdout);
    int a[] = {1,2,3,4,5,6,7,8,9};
    calc(a);
    printf(\"Elapsed time: %g sec\\n\", (clock() - t0) / (double) CLOCKS_PER_SEC);
    return 0;
}
";
Export["main.c",TemplateApply@StringTemplate[src,gen],"Text"]

Run["gcc -O2 main.c -fopenmp"]

Run["a.exe"] // AbsoluteTiming

list=ReadList["output.txt","String"]
list // Most // Length

LeftTeeArrow[x_,y_]:=-x+y;
ans=ToExpression[StringReplace[Most@list,{"#"->"","@"->"~LeftTeeArrow~"}],InputForm,HoldForm]

ReleaseHold[ans]//Union