Applying a sequence of operations from N to obtain the value M

Question

This is homework! Please do not give me the solution, just a hint!

The problem is to apply a sequence of operations from N to find M. The input is 6 numbers: A, B, C, D, N, M, where A corresponds to addition, B to subtraction, C to multiplication, and D to division. Here is an example:

10 4 2 3
21 32

We will try to find the number 32 starting from 21 using the those operations

ADD 10     // "A" number
SUB 4      // "B" number
MUL By 2   // "C" number
DIV By 3   // "D" number

the possible answer is:

32 = ((((21 * 2) + 10) - 4) / 3) * 2

the program outputs 1 if there is a sequence of operation otherwise 0. Can somebody give me a hint how to solve this?

Answer 1

You could do some kind of graph search, but with four numbers and four possible operations to perform with those numbers there are going to be 16 branches at every node and it'll probably get big quickly.

Answer 2

It seems that the biggest problem will be to determine if there is no answer. If GCD(A, B) is 1, then the answer is 1, because this means there IS a sequence of ADD A and SUB B operation that increments or decrements the source value by 1, so if you repeat this sequence enough times, you will reach ANY number from ANY other number. If it's not 1, and your DIV operation rounds the value, search if you can reach target mod GCD(A,B) value using all 4 operations. This value should be fairly small, so you can do the aforementioned graph search, clipping the result of next step via mod LCM(A,B) AND equalling branches that produce equal value of modulo GCD(A,B) operation. So, if you would reach a single value that equals target mod GCD(A,B), you can output a 1, if none reached, output a 0. The graph walk will eventually cease, as there is a fixed amount of different values in (0, LCM(A,B)-1) interval, and if properly programmed, will satisfy both memory and time requirements.

Yes, you have to take care about special situations, like A=0, B=0, C=1, or D=1. For example, a sequence 0 3 1 3 81 5 will result in an 1, while 0 3 1 3 81 29 in a 0. Edit: revised the modulo in clipping, and posted correct abbreviation functions of A and B.

Answer 3

you can solve that with brute force, if you use polymorphic functors for the operations and just go on trying. you would need a good break criteria though (like limit the number of applied operations to 10 or something like that).

answer on functors: C++ Functors - and their uses

polymorphism should be findable on the web.

example:

class operation {
public:
    enum TYPE { ADD = 0, SUB };

    virtual int operator()(int left, int right) = 0;
}

class add : public operation {
public:
    int operator()(int left, int right) {
        return left + right;
    }
}

class sub : public operation {
public:
    int operator()(int left, int right) {
        return left - right;
    }
}

int main() {
    std::vector<operation*> foo;
    foo[0] = new add();
    foo[1] = new sub();
    foo[2] = new add();


    int bar = 21;
    for (auto& op : foo) {
        bar = (*op)(bar, 2);
        std::cout << bar << std::endl;
    }
}

those classes are functors. Using such constructs, you can treat algorithms or basic operatios like variable, that you can assign or shuffle or randomize or whatever you like. since the have all the same interface inherited from operation, they all know what () means, but act differently.

having such things allows you to store and backtrack the used operations and simple loop through the permutations. while you do that, you should be aware, that you should limit the number of possible maxumum combinations of operations for each set, or you will run into endless loops / recursion.

Answer 4

This answer is based on the accepted answer to this question on math.stackexchange:

https://math.stackexchange.com/questions/354625/how-to-compose-given-add-sub-mult-div-functions-to-map-an-integer-m-to-n

Given the six inputs (a, b, c, d, M, N)

• a: the number we can add
• b: the number we can subtract
• c: the number we can multiply
• d: the number we can divide
• M: the starting number
• N: the ending number

I assume they are all integers, and a > 0, b > 0, c could be positive or negative, d not equal to 0.

Then there is a way to transform M to N by applying add, sub, mult, div,

if and only if

there exist integers m and n such that

So, the first thing to do is to find the greatest common divisor of a and b (I recommend Euclid's algorithm as described here. Call the gcd "g".

The mod is applied to both sides to verify equality.

So, start making a list of possible values the left hand side can take for different m:

(M*( Pow(c,m) )) % g

Then, start making a list of possible values the right hand side can take for different n:

(N*( Pow(d,n) )) % g

You will want to start m and n at zero and work your way up.

Eventually, both sides will start repeating, since you are using mod.

If at any time you find a match, i.e. left hand side equals some right hand side, return 1.

Otherwise, once you have exhausted all left hand values and right hand values, with no matches, return 0.

Note, that the mod operator (%) in C++ does behave different for negative numbers than the above math describes. You will need to adjust the results of mod to always be in the range 0 <= result < g

Lastly, this only works fully for cases where division acts according to normal math, i.e. 3 / 2 = 1.5 and so on.

In your case, you would need to modify the formula slightly to accept integer division. In particular the right hand side of the equation deals with division. Kind of like how the following equation works, we can take a divide, move it to the other side and it becomes a multiply.

x / 3 = 1

x = 1*3

You will need to allow the rhs to take multiple values each time you perform a power on d. For example, in the above example, we need to allow 1*3 to equal 3,4, or 5.

So, if d = 3, then

• Pow(d,0) = 1.
• Pow(d,1) = 3 or 4 or 5.
• Pow(d,2) = 9 or 10 or 11     or     12 or 13 or 14     or     15 or 16 or 17

You will see that 9 = 3*3, 12 = 4*3, and 15 = 5*3. So the pattern should be easy to replicate, even for different values of d.

I haven't tried this last part out, so I'm not entirely sure this exactly covers all cases of the integer division, but I think it does, although it is kind of tedious.