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.

  • 1
    Please improve your question. Give a bit more context (e.g. what problem this code should solve) and I hope your code is better formatted than what you posted here. You should explain what you think is wrong with it. If it does not do what you want it to do then it is broken code and does not belong on this site. – Nobody Sep 5 '14 at 11:31
  • I have edited your question to be a bit more of the format we expect here on CR. I assumed that you want to know what is wrong with the code because the online judge declined it. If this is not the case then please explain what you meant. If it is the case then please give more detail on the reason (this page says they are rather detailed). – Nobody Sep 5 '14 at 13:04
  • what does the online judge respond to your program? – miracle173 Sep 9 '14 at 0:25
  • maybe you can use something from here for testing myprimes.eu/index.php?title=Berechnungen_zu_Collatz-Zahlen – miracle173 Sep 9 '14 at 0:26

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.

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.

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;
}
  • Please provide some more explanation of the new code. What did you change and why? – Nobody Sep 8 '14 at 17:58

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.