Determine Collatz sequence length for given starting values

Question

I am trying to get into the habit of solving programming puzzles in my spare time but am stuck on the first one (which I know can be for a large number of reasons, hence my posting for help). Shown below is my code that is meant to solve the 3n+1 Challenge:

from sys import stdin

def main():
    curr_Line=stdin.readline()
    while curr_Line!=None:
        curr_Line=curr_Line.split()
        min_num=int(curr_Line[0])
        max_num=int(curr_Line[1])
        maxCycleLength =0
        for curr_num in range(min_num,max_num+1):
            currCycleLength =1     
            while curr_num!=1:
                currCycleLength +=1
                if curr_num%2==0:
                    curr_num=curr_num/2
                else:
                    curr_num=3*curr_num+1
            maxCycleLength=max(currCycleLength,maxCycleLength)
        print(min_num,max_num,maxCycleLength,sep=" ")
        curr_Line=stdin.readline()
    return 
main()

When I run this, the UVA online judge says that I've exceeded the 3 second time limit.

I've tried the following:

1. changing the the while loop to for line in stdin:

Any suggestions would be much appreciated.

Answer 1

This what I've come with:

import sys

cache = {1: 1}  # {number: cycle_length, ...}


def get_cycle_length(num):
    cycle_length = cache.get(num)
    if cycle_length is None:
        cycle_length = get_cycle_length(num // 2 if num % 2 == 0 else 3 * num + 1) + 1
        cache[num] = cycle_length
    return cycle_length


def main():

    for line in sys.stdin:
        min_num, max_num = map(int, line.split())
        assert 0 < min_num < 1000000 and 0 < max_num < 1000000

        max_cycle_length = max(map(get_cycle_length, range(min_num, max_num+1)))

        print(min_num, max_num, max_cycle_length)


assert get_cycle_length(1) == 1  # 1
assert get_cycle_length(2) == 2  # 2 1
assert get_cycle_length(3) == 8  # 2 10 5 16 8 4 2 1
assert get_cycle_length(22) == 16  # 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

main()

For the 4 test cases and the example in the task it works correctly, but unfortunately after submission the verdict is "Wrong answer".

Answer 2

You need functions. The first one you can make is the collatz_conjecture. First off I'd say make it recursive. If you ignore the currCycleLength you should get:

def collatz_conjecture(curr_num):
    if curr_num == 1:
        return 1
    if curr_num % 2 == 0:
        curr_num = curr_num / 2
    else:
        curr_num = 3 * curr_num + 1
    collatz_conjecture(curr_num)

The best way to make this better is to use functools.lru_cache(None). This is a wrapper, but it'll give you speed for just adding one line! (This is what Zack was talking about) You also should add the depth too, this is just adding one onto the previous depth. The if's are actually pretty ugly, so you can change it to the turnery operator.

@functools.lru_cache(None)
def collatz_conjecture(curr_num):
    if curr_num == 1:
        return 1
    return collatz_conjecture(3 * curr_num + 1 if curr_num % 2 else curr_num / 2) + 1

Finally I don't like that if n == 1. I'd reimplement lru_cache and supply it with that at the beggining.

def memoize(cache=None):
    if cache is None:
        cache = {}
    def wrapper(fn):
        def inner(*args):
            try:
                return cache[args]
            except KeyError:
                r = fn(*args)
                cache[args] = r
                return r
        return inner
    return wrapper


@memoize({(1,): 1})
def collatz_conjecture(n):
    return collatz_conjecture(3 * n + 1 if n % 2 else n / 2) + 1

As for the rest of your code, I'd use input with map, I'd use a comprehension passed to max and I'd also add if __name__ == '__main__':

This should get you something like:

def main():
    while True:
        user_input = input()
        if not user_input:
            break
        start, end = map(int, user_input.split()[:2])
        print(start, end, max(collatz_conjecture(i) for i in range(start, end + 1)))


if __name__ == '__main__':
    main()

Answer 3

Caching

You can increase performance by caching the result. For each number generated by the sequence, cache the number and it's length in a dict. The later, if the sequence generates a number you've already seen, you can abort the sequence and add in the remaining length.

For really long sequences this can save you a lot of time.

Note: you should be caching across all runs, so that the work you do in earlier tests can be preserved during later tests.