Uva The 3n + 1 Problem - Wrong Answer Python

Question

I'm trying to solve a question from onlinejudge.org - The 3n + 1 Problem using Python.

in case the link doesn't load (that happens quite frequently), below is my summarized version of the question:

Consider the following algorithm:

1. input n
2. print n
3. if n = 1 then STOP
4. if n is odd then n <- 3n + 1
5. else n <- n/2
6. GOTO 2

Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

In the example above, the cycle length of 22 is 16.

For any two numbers i and j you are to determine the maximum cycle length over all numbers between and including both i and j.

Sample Input

1 10
100 200
201 210
900 1000

Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174

And here's my code.

inputText = input().split()

inputList=[]
for index in range(0, len(inputText), 2):
    inputList.append([int(inputText[index]), int(inputText[index + 1])])

def CycleLen(num):
    chainList = [num]
    while num > 1:
        chainList.append(num//2 if num % 2 == 0 else 3*num + 1)
        num = chainList[-1]
    return len(chainList)

for listSet in inputList:
    countList = []
    minRange = min(listSet[0], listSet[1])
    maxRange = max(listSet[0], listSet[1])
    for num in range(minRange, maxRange + 1):
        countList.append(CycleLen(num))

    countList.sort()
    print(listSet[0], listSet[1], countList[-1])

I'm aware of the memorization solution to make it more time efficient, but I planned to implement that only if the question rejected my answer for exceeding time limit. However, I'm straight up getting the wrong answer, and I have no idea why.

I used uDebug to see if there are any mistakes, and searched for other's solution. The most confusing part is how the online judge submits its input - single line by line, or all the lines at once. Different sources claim different things.

Please help. Thank you!

Answer 1

Given your code actually does generate the correct results for the given samples, it's a safe bet you're not handling the input data correctly. And, in fact, the problem statement states (my emphasis):

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 10,000 and greater than 0.

You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.

Hence, your code that gets only one pair will not be sufficient. The reason it only processes one pair has to do with a misunderstanding that the code:

inputText = input().split()

will give you all the input lines, as evidenced by the loop that tries to create a list of 2-tuples from each pair:

inputList=[]
for index in range(0, len(inputText), 2):
    inputList.append([int(inputText[index]), int(inputText[index + 1])])

However, input() only reads one line of input (see here for details), meaning that you will only process the first line of the multi-line input. To do it properly, you need to continuously read and process lines until the file ends.

---

Having said that, you may also want to reconsider the use of a lists as your first step if it exceeds the time limit. It would be far easier to just maintain the current item and a count for calculating the cycle length (for the individual cycles) and just processing input lines sequentially (for the different ranges). Neither of those aspects requires an actual list.

---

Addressing both those list issues (and the one-line-of-input issue mentioned above), you would end up with something like:

def CycleLen(num):
    # Start with one number, the one given.

    curr = num
    count = 1

    # Until you get to 1, increase count and calculate next.

    while curr > 1:
        count += 1
        curr = curr // 2 if curr% 2 == 0 else curr * 3 + 1

    return count

while True:
    # Reads a single line and splits into integers. Any problem, exit loop.

    try:
        inputInt = [int(item) for item in input().split()]
        if len(inputInt) != 2: break
    except:
        break

    # Find value in the range with the longest cycle then print it.

    maxCycle = 0
    for number in range(min(inputInt), max(inputInt) + 1):
        maxCycle = max(maxCycle, CycleLen(number))
    print(inputInt[0], inputInt[1], maxCycle)