Optimizing Python 3n + 1 Programming Challange
<p>I am trying to find a efficient solution for the 3n + 1 problem on <a href="https://uva.onlinejudge.org/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=3&amp;page=show_problem&amp;problem=36" rel="nofollow">uvaonlinejudge</a>. The code I have uses memoization using a dictionary. Can anyone suggest an improvement(s) that will help with the execution time of this code? At the moment I am getting a 'Time limit Exceeded' error when I submit the code. If anyone has a working solution to the problem please share it with me. PLEASE DON'T mark this post as DUPLICATE. I have already seen <a href="http://stackoverflow.com/questions/39401993/uva-online-judge-python-time-limit-exceeded">this</a> post and others on stackoverflow but they don't answer the question posted here. My code is as below:</p>

<pre><code>import sys

def recCycleLength(n,cycLenDict):
    if n==1:
        return 1
    if n not in cycLenDict:
        if n%2==0:
            cycLen = recCycleLength(n//2, cycLenDict)
            cycLenDict[n] = cycLen + 1
            return cycLen+1
        else:
            cycLen = recCycleLength(3*n+1, cycLenDict)
            cycLenDict[n] = cycLen + 1
            return cycLen+1
    else:
        return cycLenDict[n]


def maxCycle(a, b):
    i = a
    mydict = {} 
    maxLength = 1
    while i &lt;= b:
        m = recCycleLength(i, mydict)
        if m &gt; maxLength:
            maxLength = m
        i = i + 1
    return maxLength


for line in sys.stdin:
    curr_line=line.split()
    num1 = int(curr_line[0])
    num2 = int(curr_line[1])
    if num1&gt;num2:
        num1, num2 = num2, num1
    m = maxCycle(num1, num2)
    print("{} {} {}".format(num1, num2, m))
</code></pre>

<p>I found the problem in your code. Actually, you are not saving <code>cycLenDict</code> generated on the previous interval for next one. And this is why your code is so "slow" because it will generate all possible endings over and over again. Just move it in global scope or make something like this:</p>

<pre><code>import sys


def rec(n, cache):
    if n in cache:
        return cache[n]
    if n % 2 == 0:
        cycle = rec(n//2, cache)
    else:
        cycle = rec(3*n+1, cache)
    cache[n] = cycle + 1
    return cache[n]


def cycle(a, b, cache):
    return max(rec(i, cache) for i in range(a, b+1))


if __name__ == '__main__':
    cache = {1: 1}
    for line in sys.stdin:
        a, b = map(int, line.split())
        a, b = min(a, b), max(a, b)
        m = cycle(a, b, cache)
        print("{} {} {}".format(a, b, m))
</code></pre>

python optimization