Recursive function and memorization to find minimum operations to transform n to 1

Question

I'm a new, self-taught programmer working on the Google FooBar challenge. I've submitted my answer (code at bottom) and it was accepted, but I'd like suggestions on how to improve my solution.

Challenge: return minimum number of operations to transform a positive integer to 1. Valid operations are: n+1, n-1, or n/2.

My solution I started with a recursive function, but ran into a runtime error with very large numbers. I added memorization using a global variable to store values that had already been computed, but this seems inelegant. (I think it's discouraged to use global variables?)

Suggestions on how I might improve the below solution?

paths = {1:0, 2:1}
def shortest_path(num):
 if num in paths:
 return paths[num]
 if num % 2 == 0:
 paths[num] = 1 + shortest_path(num / 2)
 else:
 paths[num] = min(2 + shortest_path((num+1)/2), 
 2 + shortest_path((num-1)/2))
 return paths[num]
def answer(n):
 num = int(n)
 return shortest_path(num)

Test cases:

n = 15 --> 5
n = 293523 --> 25
n = 191948125412890124637565839228475657483920292872746575849397998765432345689031919481254128901246375658392284756574839202928727465758493979987654323456890319194812541289012463756583922847565748392029287274657584939799876543234568903 --> 1029

• The input number can be up to 309 digits long hence the final test case

• Mike - SMT: Take a look at this post. If you issue is with larger numbers and you are getting a maximum recursion depth exceeded error then the post might help you.
• user7875185: thanks! I actually don't have a problem with recursion - sorry if that was confusing in my post. The code I posted works even with very large numbers. I was just wondering if there's a more elegant way to write it instead of using the global variable paths.

Answer 1

Sure, you could remove the global variable by moving the memoization to a decorator and adding a base case scenario to the function.

from functools import wraps
def memoize(func):
 cache = {}
 @wraps(func)
 def inner(*args):
 if args not in cache:
 cache[args] = func(*args)
 return cache[args]
 return inner
@memoize
def shortest_path(num):
 if num <= 2:
 return num - 1
 if num % 2 == 0:
 return 1 + shortest_path(num/2)
 else:
 return min(2 + shortest_path((num + 1)/2), 
 2 + shortest_path((num - 1)/2))

To address the recursion depth error, you could either change sys.setrecursionlimit, or you could rewrite your initial solution to use paths as an argument to avoid the global variable.

def shortest_path(num, paths=None):
 paths = paths or {1: 0, 2: 1}
 if num in paths:
 return paths[num]
 if num % 2 == 0:
 paths[num] = 1 + shortest_path(num/2, paths)
 else:
 paths[num] = min(2 + shortest_path((num+1)/2, paths), 
 2 + shortest_path((num-1)/2, paths))
 return paths[num]

Or, as suggested in the other answer, test the number modulo 4 to figure out which path to take and avoid recursion all together.

def shortest_path(n):
 count = 0
 while n > 1:
 if n % 2 == 0:
 count += 1
 n = n / 2
 elif n % 4 == 1 or n == 3:
 count += 2
 n = (n - 1) / 2
 elif n % 4 == 3:
 count += 2
 n = (n + 1) / 2
 return count

• user87373: Better yet: from functools import lru_cache (3.2+). However, if I remember correctly, foobar uses Python 2.7, so it's only useful for the general case.
• Jared Goguen: @Mego Yep, I only have Python 2.7 on the machine I was working on, so I couldn't test/post that solution.
• user7875185: @JaredGoguen Yup it's only 2.7. I tried your solution with a test case (I've edited my original post to include the test case+answer) and am getting a recursion depth error. Any suggestions?

Answer 2

The problems you've encountered usually signal that the approach is not the best.

Consider the very first step in your algorithm: you are definite that if the number is even, the best action is \$n\rightarrow \frac{n}{2}\$ (why?).

Try to apply the same logic one step further. Let \$n\$ be odd. Either \$\frac{n+1}{2}\$ or \$\frac{n-1}{2}\$ is also odd (why?). The best action is to pick that which is even (why?).

As soon as you prove all the why statements, a straight-forward non-recursive algorithm is easy to obtain.