## Brut Force?

Arithmetic, algebra, number theory, sequence and series, analysis, ...
tomtex2
Posts: 3
Joined: Fri Jul 18, 2014 4:26 pm

### Brut Force?

Hello,
I'm a newbie and I'm having problems with a very easy problem. Maybe one of you could help me. It is not a projecteuler Problem.

There are following integers 1,3,4,6 and you have to use the ordinary mathematic calculation rules like (+; -; /; *)

The result must be 24.

6*(1+4)-3 = 21 (so this is just an example).

How can I solve this problem? Obviously I have to use a lot of shots. I'm programming C++ with XCODE (MacBookPro).

Best regards.
Tom

thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

### Re: Brut Force?

tomtex2 wrote:There are following integers 1,3,4,6 and you have to use the ordinary mathematic calculation rules like (+; -; /; *)

The result must be 24.

6*(1+4)-3 = 21 (so this is just an example).
I think you can hit all cases by varying the following:
1. Which operators you are using -- 43 possibilities
2. The order of the numbers -- 4! = 24 possibilities
3. The order you apply the 3 operators (or parentheses) -- 3! = 6 possibilities, or 5...
Your program would be checking a total of 9216 cases. Some of these are redundant, for example if all 3 operators are +, the order of the numbers and the order you apply the operators doesn't matter, the answer will always be 14.

The closest I can come thinking about it is (6*4)+(1/3). tomtex2
Posts: 3
Joined: Fri Jul 18, 2014 4:26 pm

### Re: Brut Force?

Hello,

thank you for your effort but I just want to try this with C++.

I'm 15 years old and we are learning to solve this problem at school, specialy with C++. When I'm having 24 possibilities how can I code this? With some mergesort?

I realy don't know, maybe someone can give me a tip? I just wanna try this out by myself and need just some pushing.

Tks

captainblack
Posts: 1
Joined: Fri Jul 18, 2014 9:57 am

### Re: Brut Force?

You can represent any permitted combination of the symbols as: $((a\ o_1\ b)\ o_2\ c)\ o_3\ d$ where $(a,b,c,d)$ is a permutation of $(1,3,4,6)$ and $o_1,o_2,o_3 \in S$, where $S=\{+, -, /, * \}$.

So you need to loop over the permutations of $(1,3,4,6)$ and over the permitted values of $o_1,o_2,o_3$ evaluating $((a\ o_1\ b)\ o_2\ c)\ o_3\ d$ and keeping those solutions that satisfy the criterion you are required to satisfy.

There are $24$ permutations of $(1,3,4,6)$ and $4^3$ choices of operators so there are a total of $1536$ cases to try.

CB

Bubbler
Posts: 28
Joined: Sat Feb 23, 2013 6:12 am

### Re: Brut Force?

On generating permutations:
C++ next_permutation function
http://en.cppreference.com/w/cpp/algori ... ermutation
More explanations and code examples
http://www.codeproject.com/Articles/489 ... tions-in-C
Fully explained under the hood
http://stackoverflow.com/questions/1148 ... xplanation

On iterating over operators:
It's easy to handle this with 3 nested loops.
If you want to reduce it into one loop, you can iterate through i = 0..63 = 43-1 and extract three values i / 16, (i / 4) % 4, i % 4 to determine the three operators to use. (Think about why this works)

On iterating over parentheses:
There's no easy way to handle this step. For four numbers, the 5 ways to parenthesize a formula are:
((a ? b) ? c) ? d
(a ? (b ? c)) ? d
(a ? b) ? (c ? d)
a ? ((b ? c) ? d)
a ? (b ? (c ? d))

The concern on division:
You can use floating-point numbers(double) to save fractions, but it is not always exact. You can implement exact fractions using two ints(numerator/denominator), which is left for exercise. Svartskägg
Posts: 55
Joined: Thu Mar 29, 2012 12:55 pm
Location: Sweden

### Re: Brut Force?

tomtex2 wrote:It is not a projecteuler Problem.
It reminds me of problem 93. 320641_5486fc18ea1dcc4e9a8f29c7677a5c19 <-- my friend key

tomtex2
Posts: 3
Joined: Fri Jul 18, 2014 4:26 pm

### Re: Brut Force?

Thank you guys. That was what I needed. Bubbler
Posts: 28
Joined: Sat Feb 23, 2013 6:12 am

### Re: Brut Force?

And just for fun, some random formulas with 1,3,4,6 leading to 24(not limited to + - * /)
6 * 4 * 13 = 24
4! * (6 / 3 - 1) = 24
4 * (6 - 3 / 1)! = 24 (that's just a rearrangement of 2nd one!!)
6C3 + 4 * 1 = 24 (combination, or binomial coefficient)
4P6-3 * 1 = 24 (permutation)
F6 * F4 * (F3 - F1) = 24 (Fibonacci numbers... wait, what? ) TheEvil
Posts: 84
Joined: Sun Nov 13, 2011 10:38 am
Location: Szeged, Hungary

### Re: Brut Force?

The easiest way to solve it took me only 10 seconds. The following cointains the answer, so don't read it if you don't want to see it:
Expand
Anyway for learning the basics, I post a code that works. It's not meant to be nice or short but hopefully demonstrates the basics:

Code: Select all

/*
Making 24 with 1,3,4,6 and binary operations +,-,*,/
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

double distance(double x, double y){
return x>y?x-y:y-x;
}

void isgood(double perm,double goal, char oper,int a,int b,int c,int ccase){
double akt,akt2;
switch (ccase){
case 1: //((st)u)v
if (a==0) akt=perm+perm;
if (a==1) akt=perm-perm;
if (a==2) akt=perm*perm;
if (a==3) akt=perm/perm;
if (b==0) akt=akt+perm;
if (b==1) akt=akt-perm;
if (b==2) akt=akt*perm;
if (b==3) akt=akt/perm;
if (c==0) akt=akt+perm;
if (c==1) akt=akt-perm;
if (c==2) akt=akt*perm;
if (c==3) akt=akt/perm;
if (distance(goal,akt)<0.01) printf("((%d %c %d) %c %d)%c %d\n",(int)perm,oper[a],(int)perm,oper[b],(int)perm,oper[c],(int)perm);
break;
case 2: //(st)(uv)
if (a==0) akt=perm+perm;
if (a==1) akt=perm-perm;
if (a==2) akt=perm*perm;
if (a==3) akt=perm/perm;
if (c==0) akt2=perm+perm;
if (c==1) akt2=perm-perm;
if (c==2) akt2=perm*perm;
if (c==3) akt2=perm/perm;
if (b==0) akt=akt+akt2;
if (b==1) akt=akt-akt2;
if (b==2) akt=akt*akt2;
if (b==3) akt=akt/akt2;
if (distance(goal,akt)<0.01) printf("(%d %c %d) %c (%d %c %d)\n",(int)perm,oper[a],(int)perm,oper[b],(int)perm,oper[c],(int)perm);
break;
case 3: //(s(tu))v
if (b==0) akt=perm+perm;
if (b==1) akt=perm-perm;
if (b==2) akt=perm*perm;
if (b==3) akt=perm/perm;
if (a==0) akt=perm+akt;
if (a==1) akt=perm-akt;
if (a==2) akt=perm*akt;
if (a==3) akt=perm/akt;
if (c==0) akt=akt+perm;
if (c==1) akt=akt-perm;
if (c==2) akt=akt*perm;
if (c==3) akt=akt/perm;
if (distance(goal,akt)<0.01) printf("(%d %c (%d %c %d)) %c %d\n",(int)perm,oper[a],(int)perm,oper[b],(int)perm,oper[c],(int)perm);
break;
case 4: //s((tu)v)
if (b==0) akt=perm+perm;
if (b==1) akt=perm-perm;
if (b==2) akt=perm*perm;
if (b==3) akt=perm/perm;
if (c==0) akt=akt+perm;
if (c==1) akt=akt-perm;
if (c==2) akt=akt*perm;
if (c==3) akt=akt/perm;
if (a==0) akt=perm+akt;
if (a==1) akt=perm-akt;
if (a==2) akt=perm*akt;
if (a==3) akt=perm/akt;
if (distance(goal,akt)<0.01) printf("%d %c ((%d %c %d)%c %d)\n",(int)perm,oper[a],(int)perm,oper[b],(int)perm,oper[c],(int)perm);
break;
case 5: //s(t(uv))
if (c==0) akt=perm+perm;
if (c==1) akt=perm-perm;
if (c==2) akt=perm*perm;
if (c==3) akt=perm/perm;
if (b==0) akt=perm+akt;
if (b==1) akt=perm-akt;
if (b==2) akt=perm*akt;
if (b==3) akt=perm/akt;
if (a==0) akt=perm+akt;
if (a==1) akt=perm-akt;
if (a==2) akt=perm*akt;
if (a==3) akt=perm/akt;
if (distance(goal,akt)<0.01) printf("%d %c (%d %c (%d %c %d)\n",(int)perm,oper[a],(int)perm,oper[b],(int)perm,oper[c],(int)perm);
break;
default: break;
}
}

int i,j,k,l,a,b,c,t;
double x,goal;
double numb;
double perm;
char oper;
char kilep;
clock_t start;

int main(){

start=clock();

numb=1.0;
numb=3.0;
numb=4.0;
numb=6.0;
goal=24.0;
oper='+';
oper='-';
oper='*';
oper='/';
for (i=0;i<4;i++){
for (j=1;j<4;j++){
for (k=2;k<4;k++){
for (l=0;l<4;l++) perm[l]=numb[l];
x=perm; perm=perm[i]; perm[i]=x;
x=perm; perm=perm[j]; perm[j]=x;
x=perm; perm=perm[k]; perm[k]=x;
for (l=0;l<4*4*4;l++){
t=l;
a=t%4; t/=4;
b=t%4; t/=4;
c=t%4;
isgood(perm,goal,oper,a,b,c,1);
isgood(perm,goal,oper,a,b,c,2);
isgood(perm,goal,oper,a,b,c,3);
isgood(perm,goal,oper,a,b,c,4);
isgood(perm,goal,oper,a,b,c,5);
}
}
}
}

printf("\nTime: %f sec\n",(double)(clock()-start)/CLOCKS_PER_SEC);
scanf("%c",&kilep);

return 0;
} 