CODEWITHSUNDEEP
c++algorithmmath
Peter
Peter

Reputation: 41

Algorithm to turn one point into another

You're given as input four integers in the form (a,b) and (c,d).

Determine whether it's possible to get (c,d) from (a,b) if at each step you can choose between the operation (a+b,b) or (a,a+b).

So, for example, (1,2) -> (3,2) -> (5,2) -> (5,7) -> (12,7) -> (12,19) -> ...

I tried solving something with a+bx = c and ax +b = d, but that didn't work. Any ideas?

Upvotes: 1

Views: 106

Answers (3)

Maksim Solovjov
Maksim Solovjov

Reputation: 3157

Maybe there is an elegant mathematical solution with one equation that I don't know, but for me this looks like a search problem. We have a starting point (a, b) and an end point (c, d), and at every point in the search we can make two moves: either go to the state (a+b, b) or (a, a+b). A simple recursive depth first search could do. The only tricky bit here is determining when to stop searching.

Let's first solve this for the case when all integers are positive. The limiting condition, after which we cannot hope to find a solution is clear in this case: when a exceeds c or b exceeds d, we cannot hope to find a solution lower on this branch of the tree:

bool pathExistsForPositive(int a, int b, int c, int d) {
    if (a == c && b == d) return true; // success condition
    if (a > c || b > d) return false; // limiting condition
    return pathExistsForPositive(a+b, b, c, d)
        || pathExistsForPositive(a, a+b, c, d);
}

Now, generalising this for the case when the numbers are not positive is trickier, but doable. I hope that this intuition helps. Try to think about when you would have to stop searching in that case.

Upvotes: 1

user1196549
user1196549

Reputation:

The pattern of reachable points doesn't look simple. You can see it as a network of oblique lines with rational slopes, starting from reachable points.

Here is the pattern for (1, 2). The letters correspond to successive "generations".

. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. A . B . C . D . E . F . G . H . I . J . K . L . M
. B . . C . . D . . E . . F . . G . . H . . I . . J
. C . . . D . . . E . . . F . . . G . . . H . . . I
. D . C . . E . D . . F . E . . G . F . . H . G . .
. E . . . . . F . . . . . G . . . . . H . . . . . I
. F . . D D . . G . . E E . . H . . F F . . I . . G
. G . D . . . . . H . E . . . . . I . F . . . . . J
. H . . . E . E . . I . . . F . F . . J . . . G . G
. I . . . . . E . . . J . . . . . F . . . K . . . .
. J . E E . F . . F . . K . F F . G . . G . . L . G
. K . . . E . . . . . . . L . . . F . . . . . . . M
. L . . . . . G E F F G . . M . . . . . H F G G H .
. M . F . F . . . . . . . . . N . G . G . . . . . .
. N . . F . . . H . . . . H . . O . . G . . . I . .
. O . . . . . F . . . G . G . . . P . . . . . G . .
. P . G . F G F . I . . . G . I . . Q . H . G H G .
. Q . . . . . . . . . F . F . . . . . R . . . . . .
. R . . G G . . . . J F F H . . H J . . S . . H H .
. S . H . . . H . G . . . . . . . . . . . T . I . .
. T . . . . . . F . . K . . . . H H . K . . U . . .
. U . . . G . . . G . . . . . I . . . I . . . V . .
. V . I H . H G I . G . L . G . . . G . . L . . W .
. W . . . H . G . . . H . . . . . . . . . . . . . X
. X . . . . . . . . . . . M G . G J G I . I J M . .

As this doesn't look mathematically tractable at first sight, an algorithmic solution can be found by backtracking from (c, d).

(a, b)= (1, 2)

def Backtrack(c, d):
    if c == a and d == b:
        print "Reachable !"
        return

    if d > 0 and c >= d:
        Backtrack(c - d, d)
    if c > 0 and d >= c:
        Backtrack(c, d - c)

Backtrack(9, 8)

Reachable !

Unless c == d, which causes quick termination, at most one of the recursive calls is taken, so that the number of calls doesn't grow exponentially.

Upvotes: 1

Salix alba
Salix alba

Reputation: 7824

You can just loop to find all the possible solutions 

var sols = [[3,2]];

var sols2 = [];

for(depth=1;depth<5;++depth) {
    for(j=0;j<sols.length;++j) {
        var sol = sols[j];
        var sol1 = [sol[0]+sol[1],sol[1]];
        var sol2 = [sol[0],sol[0]+sol[1]];
        sols2.push(sol1,sol2);
        console.log(sol1);
        console.log(sol2);
    }
    sols = sols2;
    sols2 = [];
    console.log();
}

This just finds every possible solution. You could refine the code to filter out all the ones which fail.

A quick gcd check will eliminate any inputs which cannot work.

Upvotes: 0

Related Questions