Brut Force?

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

Brut Force?

Post by tomtex2 »

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 (+; -; /; *)
addition, subtraction, division and multiplication.

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?

Post by thundre »

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

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).
Image

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

Re: Brut Force?

Post by tomtex2 »

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?

Post by captainblack »

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?

Post by Bubbler »

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.
Image

Svartskägg
Posts: 55
Joined: Thu Mar 29, 2012 12:55 pm
Location: Sweden

Re: Brut Force?

Post by Svartskägg »

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

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

Re: Brut Force?

Post by tomtex2 »

Thank you guys. That was what I needed.

:wink:

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

Re: Brut Force?

Post by Bubbler »

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? :D )
Image

User avatar
TheEvil
Posts: 84
Joined: Sun Nov 13, 2011 10:38 am
Location: Szeged, Hungary

Re: Brut Force?

Post by TheEvil »

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
Google -> 1 2 3 4 to make 24
first page: https://answers.yahoo.com/question/inde ... 159AAFxkjq
24 = 6 / ( 1 - 3/4 )
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[4],double goal, char oper[4],int a,int b,int c,int ccase){
     double akt,akt2;
     switch (ccase){
            case 1: //((st)u)v
                 if (a==0) akt=perm[0]+perm[1];
                 if (a==1) akt=perm[0]-perm[1];
                 if (a==2) akt=perm[0]*perm[1];
                 if (a==3) akt=perm[0]/perm[1];
                 if (b==0) akt=akt+perm[2];
                 if (b==1) akt=akt-perm[2];
                 if (b==2) akt=akt*perm[2];
                 if (b==3) akt=akt/perm[2];
                 if (c==0) akt=akt+perm[3];
                 if (c==1) akt=akt-perm[3];
                 if (c==2) akt=akt*perm[3];
                 if (c==3) akt=akt/perm[3];
                 if (distance(goal,akt)<0.01) printf("((%d %c %d) %c %d)%c %d\n",(int)perm[0],oper[a],(int)perm[1],oper[b],(int)perm[2],oper[c],(int)perm[3]);
                 break;
            case 2: //(st)(uv)
                 if (a==0) akt=perm[0]+perm[1];
                 if (a==1) akt=perm[0]-perm[1];
                 if (a==2) akt=perm[0]*perm[1];
                 if (a==3) akt=perm[0]/perm[1];
                 if (c==0) akt2=perm[2]+perm[3];
                 if (c==1) akt2=perm[2]-perm[3];
                 if (c==2) akt2=perm[2]*perm[3];
                 if (c==3) akt2=perm[2]/perm[3];
                 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[0],oper[a],(int)perm[1],oper[b],(int)perm[2],oper[c],(int)perm[3]);
                break;
            case 3: //(s(tu))v
                 if (b==0) akt=perm[1]+perm[2];
                 if (b==1) akt=perm[1]-perm[2];
                 if (b==2) akt=perm[1]*perm[2];
                 if (b==3) akt=perm[1]/perm[2];
                 if (a==0) akt=perm[0]+akt;
                 if (a==1) akt=perm[0]-akt;
                 if (a==2) akt=perm[0]*akt;
                 if (a==3) akt=perm[0]/akt;
                 if (c==0) akt=akt+perm[3];
                 if (c==1) akt=akt-perm[3];
                 if (c==2) akt=akt*perm[3];
                 if (c==3) akt=akt/perm[3];
                 if (distance(goal,akt)<0.01) printf("(%d %c (%d %c %d)) %c %d\n",(int)perm[0],oper[a],(int)perm[1],oper[b],(int)perm[2],oper[c],(int)perm[3]);
                break;
            case 4: //s((tu)v)
                 if (b==0) akt=perm[1]+perm[2];
                 if (b==1) akt=perm[1]-perm[2];
                 if (b==2) akt=perm[1]*perm[2];
                 if (b==3) akt=perm[1]/perm[2];
                 if (c==0) akt=akt+perm[3];
                 if (c==1) akt=akt-perm[3];
                 if (c==2) akt=akt*perm[3];
                 if (c==3) akt=akt/perm[3];
                 if (a==0) akt=perm[0]+akt;
                 if (a==1) akt=perm[0]-akt;
                 if (a==2) akt=perm[0]*akt;
                 if (a==3) akt=perm[0]/akt;
                 if (distance(goal,akt)<0.01) printf("%d %c ((%d %c %d)%c %d)\n",(int)perm[0],oper[a],(int)perm[1],oper[b],(int)perm[2],oper[c],(int)perm[3]);
                 break;
            case 5: //s(t(uv))
                 if (c==0) akt=perm[2]+perm[3];
                 if (c==1) akt=perm[2]-perm[3];
                 if (c==2) akt=perm[2]*perm[3];
                 if (c==3) akt=perm[2]/perm[3];
                 if (b==0) akt=perm[1]+akt;
                 if (b==1) akt=perm[1]-akt;
                 if (b==2) akt=perm[1]*akt;
                 if (b==3) akt=perm[1]/akt;
                 if (a==0) akt=perm[0]+akt;
                 if (a==1) akt=perm[0]-akt;
                 if (a==2) akt=perm[0]*akt;
                 if (a==3) akt=perm[0]/akt;
                 if (distance(goal,akt)<0.01) printf("%d %c (%d %c (%d %c %d)\n",(int)perm[0],oper[a],(int)perm[1],oper[b],(int)perm[2],oper[c],(int)perm[3]);
                 break;
            default: break;
     }
}

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

int main(){
    
    start=clock();
    
    numb[0]=1.0;
    numb[1]=3.0;
    numb[2]=4.0;
    numb[3]=6.0;
    goal=24.0;
    oper[0]='+';
    oper[1]='-';
    oper[2]='*';
    oper[3]='/';
    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[0]; perm[0]=perm[i]; perm[i]=x;
                x=perm[1]; perm[1]=perm[j]; perm[j]=x;
                x=perm[2]; perm[2]=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;
}

Image

Post Reply