Simple recursive transformation solution in Python

Question

This simple Python code I wrote for a problem asked during an interview. The problem statement is:

Given a tuple (a, b), transform this into (c, d) by applying any of the two below operations multiple time in any order you like:

1. (a, b) -> (a+b, b)
2. (a, b) -> (a, a+b)

The program should take in a, b, c, and d. And tells us if it is possible to transform (a, b) to (c, d).

Edit: a, b, c and d can be negative integers.

This recursive solution seems correct but recursion depth increases very fast for even slight increase in input size. I feel I am missing some easy optimization here. I would be glad for any kind of inputs be it style, algorithm choice, speed etc.

def intro():
  print "This program will check if transformation (a, b) -> (c, d) is possible by recursive application of any of the below rules:"
  print "1. (a, b) => (a+b, b) \n2. (a, b) => (a, a+b)\n"

def user_input():
  print "Enter space separated four integers a, b, c and d:\n"
  a, b, c, d = map(int, raw_input().split(' '))
  return a, b, c, d
  # print 'a = ' + a + ' b = ' + b + ' c = ' + c + ' d = ' + d

def solve(a, b, c, d):
  print '(a: {}, b: {})  (c: {}, d:{})'.format(a,b,c,d)
  if a == c and b == d:
    return True
  elif a > c or b > d:
    return False
  elif a == c and b != d:
    return solve(a, a+b, c, d)
  elif a !=c and b == d:
    return solve(a+b, b, c, d)
  else:
    return solve(a+b, b, c, d) or solve(a, a+b, c, d)

if __name__ == '__main__':
  intro()
  a, b, c, d = user_input()
  if solve(a, b, c, d):
    print "Transformation possible"
  else:
    print "Transformation not possible"

Answer 1

Your code works correctly – as far as I can see – for strictly positive integers \$ a, b, c, d \$. It fails if the integers are allowed to be zero or negative. For example:

• solve(-1, -1, -2, -3) returns False although \$(-1, -1) \$ can be transformed to \$ (-2, -3) \$.
• solve(0, 0, 1, 1) fails with a “maximum recursion depth exceeded” because it calls itself with the same arguments.

The remainder of this review is based on the assumption that \$ a, b, c, d > 0\$.

The number of recursive calls increases quickly with larger input values because in most cases you have two possible branches at

return solve(a+b, b, c, d) or solve(a, a+b, c, d)

As an example, solve() is called

• \$29\$ times to compute that \$(4, 6)\$ is not reachable from \$(1, 1)\$, and
• \$8189\$ times to compute that \$(127, 99)\$ is reachable from \$(1, 1)\$.

The problem is that one does not know if \$(a, b)\$ should become \$(a+b, b)\$ or \$(a, a+b)\$ in order to reach \$(c, d)\$.

The “trick” to do the transformations backwards. If \$(c, d)\$ is reached eventually, then the previous pair must be either \$(c-d, d)\$ or \$(c, d-c)\$. But only one of these is possible, depending on the sign of \$ c-d \$.

That leads to the following implementation:

def solve(a, b, c, d):
  if a == c and b == d:
    return True
  elif a > c or b > d:
    return False
  elif c >= d:
    return solve(a, b, c - d, d)
  else:
    return solve(a, b, c, d - c)

which is considerable faster: Now solve() is called

• \$4\$ times to compute that \$(4, 6)\$ is not reachable from \$(1, 1)\$, and
• \$14\$ times to compute that \$(127, 99)\$ is reachable from \$(1, 1)\$.

The method can still fail with a “maximum recursion depth exceeded” runtime error. But with this changed algorithm it is easy to replace the recursion by an iteration:

def solve(a, b, c, d):
  while c >= a and d >= b:
    if c == a and d == b:
        return True
    (c, d) = (c - d, d) if c >= d else (c, d - c)
  return False

The algorithm itself can be improved further by replacing multiple transformations $$ (c, d) \to (c-d, d) \to (c-2d, d) \to \ldots $$ by a single transformation $$ (c, d) \to (c - kd, d) $$ with a suitable integer \$k\$. How large can \$k\$ be chosen? If that reminds you of the Euclidean algorithm for computing the greatest common divisor then you are on the right track to implement an optimal method.

Answer 2

elif a == c and b != d:
    if (d-b) % a == 0:
       return True
    return False
elif a !=c and b == d:
    if (c-a) % b == 0:
       return True
    return False

If you have correctly identified one number then the other's difference between target and current must be zero modulo the existing, else its impossible or the solution is to perform the same operation repeatedly.

E.g (1,2) -> (3, 11)

First (1,2) -> (3,2), then (11-2)%3 = 0 so it is possible with: -> (3,5) -> (3,8) -> (3,11)