[help] 3n+1 problem

Salam to Muslims,

Hi there guys,
I need some help with this problem. I have written code and it does work as far as I can tell but one of the online judges does not accept it.

Please suggest any amendments to make the code better:

Code:

---

#include <iostream>

using namespace std;

int CycleLength(int x);

int main(){
    while(1){
    int unsigned i,j,k,l,max=0;
    cin>>i>>j;
    k=i;
    l=j;

    if ((i==0)&&(j==0)) break;

    if(i==j){max=CycleLength(i);}
    else
    if(i>j){for(i;i>j;i--){
        if (CycleLength(i)>max)
        max=CycleLength(i);
                  }
        }
    {
    for(i;i<j;i++){
        if (CycleLength(i)>max)
        max=CycleLength(i);
                  }
        }
    cout<<k<<" "<<l<<" "<<max<<endl;}

}

int CycleLength(int x){
        int count=1;

        while(x>1){
            if (x%2==!0)
                x=3*x+1;
            else x=x/2;

        count++;
                }

        return count;
        }

---

Thanks.

Maybe they didn't like your style. That code isn't very easy to read. Fix the indentation, and don't do

Code:

---

if(cond)expr;

---

do

Code:

---

if(cond)
    expr;

---

Quote:

---

Originally Posted by User Name:

Fix the indentation

---

The indentation by itself is enough for me to consider you code as bad code.

Some of programmers on this site say using "using namespace std;" is bad thing to use.

Many programmers say to declare only one variable per line.

How you did it.

Code:

---

int unsigned i,j,k,l,max=0;

---

Preferred

Code:

---

int unsigned i; /* Comment saying what this Variable does */
int unsigned j;
int unsigned k;
int unsigned l;
max=0;

---

Tim S.

Quote:

---

Salam to Muslims

---

[strike]So, are only Muslims worthy of salutation?[/strike]

Sorry, I missed the second salutation... :sheepish grin:

Quote:

---

Originally Posted by User Name:

Maybe they didn't like your style.

---

I lol'ed. I don't know if it was deliberate or not, but those "online judges" are automated machines that test if the output provided is correct ;-).

Though I'm not going to bother find out what's wrong if the code is so dreadfully formatted.

Edit: actually, I did spot the two problems. Well, not just two, I expect you'll get a time limit exceeded as well, unless they're extremely friendly.

Quote:

---

Originally Posted by stahta01

Preferred

Code:

---

int unsigned i; /* Comment saying what this Variable does */
int unsigned j;
int unsigned k;
int unsigned l;
max=0;

---

---

Never!
If you ever have to provide a comment to say what a variable is for then chances are that your variable names simply suck.
There's nothing wrong with declaring multiple variables on one line. Clearly if all those variables are meant to be the same type then it's easier to change one line later rather than five, which leads me on to my next point... You broke it by no longer declaring 'max' (which incidentally is also a bad variable name).

Quote:

---

Originally Posted by rags_to_riches

So, are only Muslims worthy of salutation?

---

I would try not to be offended. To the rest of us who don't know what that word means, K12 did say "Hi" to us.

K12:
It seriously took me about 3 minutes to properly match the brakets up when reading that mess. It should not even take 3 seconds for code that long!
If you want others to help you then you need to do a lot better.
Also, whitespace is your friend.

It would help if you told us why this is not accepted.

E.g if the Judge treats warnings as errors, then you have comparisons between signed and unsigned integers.

If it is too slow, then you should be able to tell immediately that you are calling CycleLength twice as often as needed.

Quote:

---

Some of programmers on this site say using "using namespace std;" is bad thing to use.

---

Why? What are the pros and cons?

Alright, I took your advice of indentation and did my best to fix the current code in terms of indentation. Please check it and spot the problem if the indentation is satisfactory, if not, then please tell me how to improve my indentation. Thanks a lot for the help so far guys.

Here is the indented code:

Code:

---

#include <iostream>

using namespace std;

int CycleLength(int x);

int main()
{
    while(1)
    {
    int unsigned i,j,k,l,max_cycle=0;
    //i,j are user inputs of the two numbers. k,l store initial values of i and j respectively to be printed out later.


    cin>>i>>j;

    k=i;
    l=j;

    if ((i==0)&&(j==0)) break;

    if(i==j)
        max_cycle=CycleLength(i);
    else
    if(i>j)
        {
            for(i;i>j;i--)
            {
                if (CycleLength(i)>max_cycle)
                max_cycle=CycleLength(i);
            }
        }

    for(i;i<j;i++)
    {
        if (CycleLength(i)>max_cycle)
            max_cycle=CycleLength(i);
    }

    cout<<k<<" "<<l<<" "<<max_cycle<<endl;
    }
}

int CycleLength(int x)
{
        int count=1;

        while(x>1)
        {
            if (x%2==!0)
                    x=3*x+1;
            else
                    x=x/2;
        count++;
        }
        return count;
}

---

I tried my best to satisfy everyone, but I did not understand why it was better to declare each variable in their own line and I also changed the variable 'max' to 'max_cycle'.

Well that's much better!

Here's a relevant xkcd image, by the way.

Is there a problem description somewhere that we can read to see if this does what was asked?
It may be that the problem is integer overflow inside CycleLength.

Thanks, the image was hilarious.

You can check out the description here:

Code:

---

http://online-judge.uva.es/p/v1/100.html

---

EDIT: Judges keep on giving a wrong answer for this.

Your for loops stop one too soon (you need to compute the cycle length for j, too).

Attempted a fix:

Code:

---

if(i>j)
        {
            for(i;i>j-1;i--)
            {
                if (CycleLength(i)>max_cycle)
                max_cycle=CycleLength(i);
            }
        }

    for(i;i<j+1;i++)
    {
        if (CycleLength(i)>max_cycle)
            max_cycle=CycleLength(i);
    }

---

Also, your "hey I'm done now" check is extremely brittle -- as in, I don't see how it can work. There's not a 0 0 pair at the end of the input, and i and j don't end up at 0 along the way. If there's no data, then i and j don't get changed to 0 somehow -- the read fails, which is what you should be checking for.

The problem description does not mention how the input should stop. I just assumed a 0 0 input would end it. If you have any experience with questions like this, please tell me how to get it right.

The input stops, that's how you know it's done. You can check whether an input stream is still "good" (i.e., if every read so far has succeeded) or if it has "failed". You should do that.

Hint: istream - C++ Reference

The loop should begin like this:

Code:

---

    unsigned i, j;
    while(cin >> i >> j)
    {
    int unsigned k,l,max_cycle=0;

---

When entering values from the keyboard (rather than redirecting input to a file), you can indicate end of "file" (input) with a special key combination, e.g on Windows Ctrl+Z.

Changed the loop but still got it wrong. Thanks anon.

Regarding the iostream input buffer, I changed the code to include good(). But the code does not compile, can someone please tell me how to properly use this function.

Code:

---

#include <iostream>

using namespace std;

int CycleLength(int x);

int main()
{
    int unsigned i,j;
    bool good();
    //i,j are user inputs of the two numbers. k,l store initial values of i and j respectively to be printed out later.

    while(good())
    {
    cin>>i>>j;

    int unsigned k,l,max_cycle=0;

    k=i;
    l=j;

    if(i==j)
        max_cycle=CycleLength(i);
    else
    if(i>j)
        {
            for(i;i>j-1;i--)
            {
                if (CycleLength(i)>max_cycle)
                max_cycle=CycleLength(i);
            }
        }

    for(i;i<j+1;i++)
    {
        if (CycleLength(i)>max_cycle)
            max_cycle=CycleLength(i);
    }

    cout<<k<<" "<<l<<" "<<max_cycle<<endl;
    }
}

int CycleLength(int x)
{
        int count=1;

        while(x>1)
        {
            if (x%2==!0)
                    x=3*x+1;
            else
                    x=x/2;
        count++;
        }
        return count;
}

---

By good() it was probably meant the member function cin.good().

However, that would be a wrong way to control an input loop. You'll try to process input even if it fails, because you test for good only at the beginning of the next iteration.

The correct way to control input loops is by testing the result of the input statement, as I've shown.