13

I came across this question in one of the Job Interviews & i am unable to find the correct alogorithm of the solution so, i am posting this question here:

There is a robot who can move on a co-ordinate plane in eithr of the 2 ways:

Given that the robots current position is (x,y), The robot can move equal to the sum of x & y in either if the directon like so:

(x,y)  ->  (x+y, y)
(x,y)  ->  (x, x+y)

Now given a initial Point (x1, y1) and an destination point (x2, y2) you need to write a programme to check if the robot can ever reach the destination taking any number of moves.

Note: x1, y1 , x2 , y2 > 0

Explanation:

  1. Suppose the robot's initial point is (2,3) and desintation is (7,5)

    Result in this case is yes as the robot can take this path:

    (2,3) -> (2, 2+3) => (2, 5)

    (2,5) -> (2+5, 5) => (7,5)

  2. Suppose the robot's initial point is (2,3) and desintation is (4,5)

    Result in this case is No as no matter what path the robot takes it cannot reach (4,5)

VegardKT
  • 1,226
  • 10
  • 21
Mohan
  • 4,677
  • 7
  • 42
  • 65

4 Answers4

13

A naive brute-force approach

One way would be to recursively explore every possible move until you reach the target.

Something to consider is that the robot can keep moving indefinitely (never reaching the target) so you need an end case so the function completes. Luckily the position is always increasing in the x and y axis, so when either the x-coordinate or y-coordinate is greater than the target, you can give up exploring that path.

So something like:

def can_reach_target(pos, target):
    if pos == target: 
        return True
    if pos[0] > target[0] or pos[1] > target[1]: 
        return False
    return can_reach_target((pos[0], sum(pos)), target) or \
           can_reach_target((sum(pos), pos[1]), target)

And it works:

>>> can_reach_target((2,3),(7,5))
True
>>> can_reach_target((2,3),(4,5))
False

A limitation is that this does not work for negative coordinates - not sure if this is a requirement, just let me know if it is and I will adapt the answer.

Bactracking

On the other hand, if negative co-ordinates are not allowed, then we can also approach this as Dave suggests. This is much more efficient, as the realisation is that there is one and only one way of the robot getting to each coordinate.

The method relies on being able to determine which way we stepped: either increasing the x-coordinate or the y-coordinate. We can determine which coordinate was last changed, by selecting the larger of the two. The following proof guarantees that this is the case.

The possibilities for a state change are:

1. (a, b) => (a+b, b)       a x-coordinate change

and,

2. (a, b) => (a, a+b)       a y-coordinate change

In case (1), the x-coordinate is now larger, since:

    a > 0
a + b > b  (add b to both sides)

and similarly, since b is also > 0, we can deduce that a+b is > a.

Now we can start from the target and ask: which coordinate led us here? And the answer is simple. If the x-coordinate is greater than the y-coordinate, subtract the y-coordinate from the x-coordinate, otherwise subtract the x-coordinate from the y-coordinate.

That is to say, for a coordinate, (x,y), if x > y, then we came from (x-y,y) otherwise (x,y-x).

The first code can now be adapted to:

def can_reach_target(pos, target):
    if pos == target: 
        return True
    if target[0] < pos[0] or target[1] < pos[1]: 
        return False
    x, y = target
    return can_reach_target(pos, (x-y,y) if x > y  else (x,y-x))

which works as expected:

>>> can_reach_target((2,3),(7,5))
True
>>> can_reach_target((2,3),(4,5))
False

Timings

>>> timeit.timeit('brute_force((2,3),(62,3))',globals=locals(),number=10**5)
3.41243960801512
>>> timeit.timeit('backtracker((2,3),(62,3))',globals=locals(),number=10**5)
1.4046142909792252
>>> timeit.timeit('brute_force((2,3),(602,3))',globals=locals(),number=10**4)
3.518286211998202
>>> timeit.timeit('backtracker((2,3),(602,3))',globals=locals(),number=10**4)
1.4182081500184722

So you can see that the backtracker is nearly three times faster in both cases.

Joe Iddon
  • 20,101
  • 7
  • 33
  • 54
12

Go backwards. I'm assuming that the starting coordinates are positive. Say you want to know if a starting point of (a,b) is compatible with an end point of (x,y). One step back from (x,y) you were either at (x-y,y) or (x,y-x). If x > y choose the former, otherwise choose the latter.

Dave
  • 7,460
  • 3
  • 26
  • 39
  • I've written this algorithm at the bottom of my answer. It is nearly three times faster than my original brute force recursion! – Joe Iddon Aug 27 '18 at 15:30
10

I agree with Dave that going backwards is an efficient approach. If only positive coordinates are legal, then every coordinate has at most one valid parent. This lets you work backwards without a combinatorial explosion.

Here's a sample implementation:

def get_path(source, destination):
    path = [destination]
    c,d = destination
    while True:
        if (c,d) == source:
            return list(reversed(path))
        if c > d:
            c -= d
        else:
            d -= c
        path.append((c,d))
        if c < source[0] or d < source[1]:
            return None

print(get_path((1,1), (1,1)))
print(get_path((2,3), (7,5)))
print(get_path((2,3), (4,5)))
print(get_path((1,1), (6761, 1966)))
print(get_path((4795, 1966), (6761, 1966)))

Result:

[(1, 1)]
[(2, 3), (2, 5), (7, 5)]
None
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (6, 5), (11, 5), (16, 5), (21, 5), (26, 5), (31, 5), (36, 5), (41, 5), (46, 5), (46, 51), (46, 97), (143, 97), (143, 240), (383, 240), (623, 240), (863, 240), (863, 1103), (863, 1966), (2829, 1966), (4795, 1966), (6761, 1966)]
[(4795, 1966), (6761, 1966)]

Appendix: some observations I made along the way that might be useful for finding an O(1) solution:

  • (a,b) is reachable from (1,1) if and only if a and b are coprime.
  • If a and b have a common factor, then all children of (a,b) also have that common factor. Equivalently, if there is a path from (a,b) to (c,d), then there is also a path from (n*a, n*b) to (n*c, n*d), for any positive integer n.
  • if a and b are coprime and aren't (1,1), then there are infinitely many coprime coordinates that are unreachable from (a,b). By choosing (a,b) as a starting point, you're effectively limiting yourself to some sub-branch of the tree formed by (1,1). You can never reach any of the sibling branches of (a,b), where infinitely many coordinates reside.
Kevin
  • 74,910
  • 12
  • 133
  • 166
  • I'll add: There is exactly one path from (1,1) to each reachable (a,b). This can be expressed as an integer with a number of bits equal to the length of the path, where a set bit indicates the x-axis increased on that step. (a,b) is reachable from (x,y) if the binary representation of (x,y) is a truncation of that of (a,b) (assuming both reachable from (1,1). – Dave Aug 27 '18 at 18:15
  • 1
    You can use modulo rather than subtraction to more quickly calculate this (linear in the number of changes of direction rather than the number of steps). – Dave Aug 27 '18 at 18:17
3

A recursive funtion should work fine for that. You even got the number of possibilities.

def find_if_possible(x,y,x_obj,y_obj,max_depth):
    if(max_depth < 0):
          return 0
    elif(x == x_obj and y == y_obj):
          return 1

    elif(x>x_obj or y>y_obj):
          return 0
    else:
          return(sum(find_if_possible(x+y,y,x_obj,y_obj,max_depth-1),find_if_possible(x,y+x,x_obj,y_obj,max_depth-1))
Aran-Fey
  • 39,665
  • 11
  • 104
  • 149
Frayal
  • 2,117
  • 11
  • 17