Return to Revisions

Similar to whuber's answer, we can use Groupings(introduced in version 11) to simplify the generation patterns, the number of patterns is related to the CatalanNumber, 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, still very slow, I terminate it.

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 $8$ 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 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 -Og 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