UVa Challenge Problem 100: 3n+1 code

Question

I have written this code for UVa Challenge 100:

#include<iostream>
using namespace std;
int main(){
int i,j,a,b,k,tot,gtot;
while(cin>>i>>j){
gtot=0;
a=i<j?i:j;
b=i<j?j:i;
for(int l=a;l<=b;l++){
tot=1;k=l;
while(k!=1){
tot++;
if((k%2)==0)k=k/2;
else k=(3*k)+1;
}

if(tot>gtot) gtot=tot;
}
cout<<i<<" "<<j<<" "<<gtot<<endl;
}
return 0;
}

The challenge is about finding the length of the longest Collatz sequence in a given range. Each input row contains two numbers, the minimum and maximum sequence start number to check. After calculating the maximum length of all sequences starting with a number in this range, this lentgh must be printed together with the given inputs.

My code produces the correct output for the given examples so I think it is correct but the online judge disagrees.

Answer 1

Formatting/Indentation

Your code as posted here has a horrible formatting which makes it hard to read and understand. You add a level of indentation for each nesting level (each {} block).

Extracting functions

All your code is in the main function which increases dependencies and reduces readability. Consider extracting independent tasks into own functions like.

• a function to get the next number in the collatz sequence from the current one
• a function to measure the length from a number to 1 in the collatz sequence
• a function to build the maximum of this length for a range of integers

Then your main function would only consist of the code for reading the input and printing the output (which might also be moved into own functions as well)

C vs C++

As you are using C++ you should take advantage of its features. For example in C++ you don't need to declare all variables up front. This allows you to declare them as late as possible (when they are needed).

C++ also does not require return 0; at the end of main. If execution reaches the end the return 0; will be automatically done by the compiler.

Use std algorithms

I don't think it is really necessary but your code stores the minimum and maximum of i and j in a and b (not necessary because the task seems to guarantee that i <= j). You are doing this calculation on your own which adds burden on the reader to understand what you are doing. There are std algorithms for this:

a = std::min(i, j);

Naming

All your variables have far too short and undescriptive naming. Ideally, a reader should know from the name of a variable what it is for. In your case this is not possible. I would suggest:

• i -> first_input (or start_number if it is guaranteed to be less or equal the j)
• j -> second_input (or stop_number)
• a, b according to the suggestions above if you still use them
• l -> current_sequence_start
• tot -> current_sequence_length
• gtot -> maximal_sequence_length
• k -> current_sequence_number

Don't using namespace std;

This can become a problem later on so don't get used to it. Typing std:: is not that bad and if it becomes too bad you still can do using std::cout; to avoid the "lengthy" names.

Putting all this together I get the following code

#include <iostream>
#include <algorithm>
#include <cassert>

/**
 * @brief Get the next number in the collatz sequence from the current one
 */
int next_collatz(int current_collatz) {
  return current_collatz % 2 == 0 ? current_collatz / 2
                                  : 3 * current_collatz + 1;
}

/**
 * @brief Count the number of steps in the collatz sequence from current_number
 *        to 1
 */
int count_collatz_steps_until_1(int current_number) {
  int counter = 1;
  while (current_number != 1) {
    ++counter;
    current_number = next_collatz(current_number);
  }
  return counter;
}

/**
 * @brief Find the maximum of the lengths of the collatz sequence for each
 *        number bewteen start_number and end_number (inclusive)
 */
int maximal_collatz_sequence_length(int start_number, int end_number) {
  assert(start_number <= end_number);
  int maximum_sequence_length = 0;
  for (int current_number = start_number; current_number <= end_number;
       current_number++) {
    int current_sequence_length = count_collatz_steps_until_1(current_number);
    maximum_sequence_length =
        std::max(maximum_sequence_length, current_sequence_length);
  }
  return maximum_sequence_length;
}

int main() {
  int first_input, second_input;
  while (std::cin >> first_input >> second_input) {

    int start_number = std::min(first_input, second_input);
    int end_number = std::max(first_input, second_input);

    std::cout << first_input << " " << second_input << " "
              << maximal_collatz_sequence_length(start_number, end_number)
              << std::endl;
  }
}

This should be an improvement in clarity but not in speed as it is the same algorithm.

Answer 2

I agree with @Nobody: your naming is extremely cryptic, and the lack of indentation makes the code even more unreadable. Putting the entire program inside a single main() function makes it even harder to follow.

Your program is non-portable, since an int is only guaranteed to hold numbers up to 32767. I would change your data type to unsigned long long; otherwise, the Collatz sequence starting with 159487 will overflow.

Answer 3

I agree with @Nobody and @200_success.

Your program fails to produce output for 1 1000000 ( Which could be part of test ).

This should work.... ( I've compiled this on MSVC 2012 )

Again, I'm not familiar with (execution) time limit....

#include<iostream>

int main()
{
    unsigned long long Upper, Lower, CycleCount, Number, MaxCycle;
    while(std::cin>>Lower>>Upper)
    {
        MaxCycle=0;
        for( long long ii = Lower ; ii<=Upper ; ii++ )
        {
            Number=ii;
            CycleCount=0;
            while(1)
            {
                CycleCount++;
                if(Number==1)
                {
                    break;
                }
                if(Number%2==0)
                {
                    Number=Number/2;
                }
                else
                {
                    Number=3*Number;
                    Number++;
                }
            }
            MaxCycle=std::max(MaxCycle,CycleCount);
        }
        std::cout<<Lower<<" "<<Upper<<" "<<MaxCycle<<std::endl;
    }
    return 0;
}