7
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Sierra Mountain Tech Jun 7 '17 at 18:43
  • \$\begingroup\$ 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. \$\endgroup\$ – user7875185 Jun 7 '17 at 18:50
4
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Mego Jun 7 '17 at 21:50
  • \$\begingroup\$ @Mego Yep, I only have Python 2.7 on the machine I was working on, so I couldn't test/post that solution. \$\endgroup\$ – Jared Goguen Jun 8 '17 at 1:38
  • \$\begingroup\$ @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? \$\endgroup\$ – user7875185 Jun 8 '17 at 14:05
6
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.