2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Please don't add other people's code to your question, I edited out the other example that you included. You may if you want to add a link to where we can find other "good" examples. \$\endgroup\$ – Simon Forsberg May 6 '16 at 10:37
-1
\$\begingroup\$

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".

\$\endgroup\$
  • \$\begingroup\$ you are almost there. The issue is that you are assuming that the first number (i) will always be smaller than the second number (j). Consider the all possible cases in your code. \$\endgroup\$ – Saaga Mar 4 at 12:39
3
\$\begingroup\$

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()
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @functools.lru_cache(None) \$\endgroup\$ – Peilonrayz May 6 '16 at 13:25
  • \$\begingroup\$ That may work better. I only barely use Python, and typically not be choice. \$\endgroup\$ – Zack May 6 '16 at 13:43
  • \$\begingroup\$ @benrudgers This sequence doesn't generate duplicate numbers \$\endgroup\$ – Zack May 6 '16 at 14:31
  • \$\begingroup\$ @benrudgers Yes you are correct, and that's not what using memoization is about, it's so if you call the function with the same arguments it doesn't take light years to run. \$\endgroup\$ – Peilonrayz May 6 '16 at 15:46

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.