puzzle

[viv0411]

4 _ 4 _ 4 _ 4 = 20
use +,-,/,* to solve it. write c++ code.

[ganesh_IT]

#include <iostream>

int main()
{
     std::cout << (4 / 4 + 4 )* 4 ;
     return 0;
}

[viv0411]

no dude. you didn't get me. i want the computer to search for possible combinations.

[iamthwee]

Interesting little challenge...

First thoughts would be to permute through all math signs (+,-,/,*)

Maybe a crude permutation generator would do well here.

++++
+++-
++--
+---
----

etc... the parenthesis adds extra complexity though.

[Sky Diploma]

Or get through it with a recursive function, End cases would be if either you finish all available values with you or total > required total.

[StuXYZ]

Assuming the problem is slightly more general you have a list of number e.g.
int items[]={4,4,4,4}; and you have a target number T.
Now you need to clarify the rules:

(i) are brackets acceptable: e.g. the given solution (4 / 4 + 4 )* 4 has to have brackets to get the problem to work. Since there is no solution that exists without that I guess you are allowing that.

If that is the case, the one way to approach the problem is to encode the operations and numbers on to a stack (reverse polish notation). Then you can iterate through the placement of a fixed number of operators and a fixed number of index values and
evaluate each step:
e.g. 1 2 3 + 4 * - ==> 1-(2+3)*4 =

Now it is just a matter of keeping the values in the list in order and iterating through the operators.

Finally, I don't think this is a good problem for recursion, simply because if the solution for some part is above/below the result it doesn't help, you could divide or subtract if you have an intermediate solution that is above the target. However, you CAN produce a recursive results. But it is has to implement a hidden stack.

Finally, what about a different language: this problem is very simple in lisp :-)

[iamthwee]

If that is the case, the one way to approach the problem is to encode the operations and numbers on to a stack (reverse polish notation). Then you can iterate through the placement of a fixed number of operators and a fixed number of index values and
evaluate each step:

Not quite sure what you mean by this? Can you clarify this please?

[StuXYZ]

In reference to the previous post: Please clarify:

It is that you can construct a stack of operations which are either "read value" or "binary op", the effect is that you can construct a stack , then evaluated it, then make a permutation on it. Since the stack can represent all possible solutions, it is a very easy thing to compute with.

E.g Consider the problem of values item={1,2,3,4} and operators P={+ - *}, your stack is {V,V P,V,P,V,P}. this is evaluated to see if it equals T. Then just iterate the item list, and after each full loop, iterate the operators list once. Obviously, after a full step of both step you can change the operators.

That example can be optimized for cases were you have order invariance but the basic form is there.

On the other hand, if you try to make a stack with brackets e.g. ( A + B) * C etc. Then you have the problem of how many brackets etc. The stack is not obviously iterable. [It can be done, it is just seems difficult]

However, I may have missed the easy way to do this problem. [In fact I feel I have]

[sundip]

Just a concept:-

char operator[]  = {'+','-','*','/'};
int  item[]      = {4,4,4,4}
int  targetValue = 20;
for operator1 in operator
{
   for operator2 in  operator
   {
      for operator3 in  operator
      {
          if((item[0] operator1  item[1] operator2 item[2] operator3 item[3]) == targetValue)
          print "item[0] operator1  item[1] operator2 item[2] operator3 item[3]";  
      }
   }
}

I hope it may be written in more optimize way