# 3n + 1 programming challenge in Python

I am trying to find a efficient solution for the 3n + 1 problem on uvaonlinejudge. The code I have uses memoization using a dictionary. I am getting a 'Time limit Exceeded' error when I submit the code. Can anyone suggest an improvement(s) that will help with the execution time of this code.

I have already seen this post and implemented the proposed improvements. All other posts related to this are either for C++ or Java.

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 <= b:
m = recCycleLength(i, mydict)
if m > 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>num2:
num1, num2 = num2, num1
m = maxCycle(num1, num2)
print("{} {} {}".format(num1, num2, m))

• Welcome to Code Review. Hope you get good answers. Commented Oct 10, 2016 at 20:09
• You should probably read up on the PEP8 Style Rules for Python - there's some stuff that seem to be violating PEP8 (function names). Also this is for Python 3 yes? Commented Oct 10, 2016 at 22:46
• what times do you achive for 1<x<10**6? Commented Oct 11, 2016 at 9:55
• for 1<x<10**6 I am getting a time of 2.5-2.7 seconds. The brute force C implementation (using no memoization) takes around 0.5 seconds Commented Oct 12, 2016 at 7:41

You should separate your responsibilities. Currently your function recCycleLength (which should be named rec_cycle_length to conform with Python's official style guide PEP8) does two things, calculating the return value and caching it in a passed dictionary. It would be better to outsource the latter to a decorator, like this one (which is the fastest memoization decorator for a single-valued function I know of):

def memodict(f):
""" Memoization decorator for a function taking a single argument """
class memodict(dict):
def __missing__(self, key):
ret = self[key] = f(key)
return ret
return memodict().__getitem__

@memodict
def rec_cycle_length(n):
if n == 1:
return 1
elif n % 2 == 0:
return cyc_len = rec_cycle_length(n//2) + 1
return rec_cycle_length(3*n+1) + 1


You can even use this decorator on maxCycle when changing it to accept only one argument, the tuple (a, b). You could also be using max with a generator expression here:

@memodict
def max_cycle(bounds):
a, b = bounds
return max(rec_cycle_length(n) for n in range(a, b + 1))


(Use xrange in case you are using python 2.x.)

Your code on module level should be guarded by a if __name__ == '__main__': guard. You could also use map and sorted to get rid of quite a few lines of code:

if __name__ == '__main__':
for line in sys.stdin:
bounds = tuple(sorted(map(int, line.split())))
print(" ".join(bounds), max_cycle(bounds))


This allows you to do e.g. from filename import rec_cycle_length in another script to reuse a function defined here.

Note that even though str.format is awesome, it is not needed here.

Since you seem to be using python 3.x, you might want to use functools.lru_cache instead of this decorator, like so:

import functools

@functools.lru_cache(2**10)
def rec_cycle_length(n):
...


At least on my machine it is a lot faster for some use cases (because the cache will not grow without bounds, making it better when there are few repetitions, i.e. many cache misses.) It is, however, only included in python >= 3.3.

• long time no see. Could the memorization be done with decorators in such a way that 5->16->8->4->2->1 not only save 5, but also path length for 16, 8, 4, 2? Commented Oct 11, 2016 at 8:58
• yeah I went ahead and confirmed that realizing that the decorator toke the dict as super. Confirmed this magic. But dict don't have a __missing__() called by __getitem__(), how does that work? And the garbage collector don't collect because of the call to __getitem__() in the return statement? Commented Oct 11, 2016 at 9:26
• I have already tried functools.lru_cache but had no luck. I beginning to think that the uvaonlinejudge system has not been adjusted for Python. Commented Oct 11, 2016 at 9:47
• Ah, I remember reading that section, d[key], apparently not realizing it's potential. Commented Oct 11, 2016 at 9:49
• by 'no luck' I mean I am still getting the 'Time limit Exceeded' error. Yes I am beginning to suspect that they have not accounted for the slowness of python. A brute force (no memoization) implementation in C is accepted by the uvaonlinejudge system but my python implementation is not. I measured the execution time for both the C and Python solution and Python is around 4 times slower. Commented Oct 12, 2016 at 7:38

Your performance problem is that you throw away the memoization cache after each test case.

Also, in Python, iteration should be more efficient than recursion.

• yes you are right, it got accepted when I corrected this flaw(plus another, I was printing the output in the wrong sequence). I also implemented a iterative version with memoization, but surprisingly it takes more time than the recursive version. Thanks Commented Oct 12, 2016 at 9:57

after changes suggested by 200_success, here is the code that got accepted:

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, mydict):
i = a
maxLength = 1
while i <= b:
m = recCycleLength(i, mydict)
if m > maxLength:
maxLength = m
i = i + 1
return maxLength

memDict = {1:1}
for line in sys.stdin:
curr_line=line.split()
num1 = int(curr_line[0])
num2 = int(curr_line[1])
if num1>num2:
num1, num2 = num2, num1
m = maxCycle(num1, num2, memDict)
print("{} {} {}".format(num1, num2, m))


After changes suggested by 200_success. The code that accepts the 3n + 1 problem on uvaonlinejudge:

Made some changes to accept the problem on the platform uvaonlinejudge. The code answered was giving Wrong Answer. Based on OP comment, he was right and I rearranged the output:

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, mydict):
i = a
maxLength = 1
while i <= b:
m = recCycleLength(i, mydict)
if m > maxLength:
maxLength = m
i = i + 1
return maxLength

memDict = {1: 1}
array = []
value = False
for line in sys.stdin:
curr_line=line.split()
num1 = int(curr_line[0])
num2 = int(curr_line[1])
if num1>num2:
num1, num2 = num2, num1
value = True
m = maxCycle(num1, num2, memDict)

if value:
array.append("{} {} {}".format(num2, num1, m))
else:
array.append("{} {} {}".format(num1, num2, m))
value = False
for i in array:
print(i)

• Note that it is not the same code as the Community Wiki answer by the OP of the question Commented Dec 18, 2023 at 5:32
• You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. Commented Dec 18, 2023 at 8:36