3n+1 Problem from Programming Challenges

[kheiron1729]

Hello. I am new here.
Here is the question: Consider the following algorithm to generate a sequence of numbers. Start with an integer n. If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this process with the new value of n, terminating when n = 1. For example, the following sequence of numbers will be generated for n = 22:
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for every integer n. Still, the conjecture holds for all integers up to at least 1,000,000.
For an input n, the cycle-length of n is the number of numbers generated up to and including the 1. In the example above, the cycle length of 22 is 16. Given any two numbers i and j, you are to determine the maximum cycle length over all numbers between i and j, including both endpoints.

Input
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 1,000,000 and greater than 0.

Output
For each pair of input integers i and j, output i, j in the same order in which they appeared in the input and then the maximum cycle length for integers between and including i and j. These three numbers should be separated by one space, with all three numbers on one line and with one line of output for each line of input.

Sample Input
1 10
100 200
201 210
900 1000

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


I am relatively new to programming. Anyway, I tried. It gave fine answers to me until I am submitted it online at http://www.programming-challenges.com..it said "Wrong Answer!"
Can anyone tell me what's wrong with the code. The language is C++.
#include <iostream>
using namespace std;

//iterates to find the cycle length
int cycleLen (int num, int count) {
if (num == 1)
return count;
else if (num%2 == 0) {
num = num/2;
count++;
cycleLen(num, count); }
else {
num = 3*num + 1;
count++;
cycleLen(num, count);
}
}

//Returning the Max Cycle
int maxCycle(int *list, int total) {
int max = list[0];
for (int i=1; i<total; i++)
if (list > max)
max = list;
return max;
}

//handling a range of numbers
int createArray (int i, int j) {
int total = (j-i)+1;
int* cycles;
int* elements;
elements = new int[total-1];
cycles = new int[total-1];
//placing elements into elements array
for (int x=0; x<total; x++)
elements[x] = i++;
//computing cycles for corresponding elements
for (int x=0; x<total; x++)
cycles[x] = cycleLen(elements[x], 1);
return maxCycle(cycles, total);
}
int main () {
int n1, n2;
cin >> n1 >> n2;
cout << n1 << ' ' << n2 << ' ' << createArray(n1,n2) << endl;
return 0;
}

 

[Grep]

Remember to put your code in CODE tags so it's more readable. Just put [ CODE] at the start and [ /CODE] at the end, making sure to remove the spaces I put in after the square brackets. Anyways, here it is formatted properly:

#include <iostream>
using namespace std;

//iterates to find the cycle length
int cycleLen (int num, int count) {
	if (num == 1)
		return count;
	else if (num%2 == 0) {
		num = num/2;
		count++;
		cycleLen(num, count); }
	else {
		num = 3*num + 1;
		count++;
		cycleLen(num, count);
	}
}

//Returning the Max Cycle
int maxCycle(int *list, int total) {
	int max = list[0];
	for (int i=1; i<total; i++)
		if (list[i] > max)
			max = list[i];
	return max;
}

//handling a range of numbers
int createArray (int i, int j) {
	int total = (j-i)+1;
	int* cycles;
	int* elements;
	elements = new int[total-1];
	cycles = new int[total-1];
	//placing elements into elements array
	for (int x=0; x<total; x++)
		elements[x] = i++;
	//computing cycles for corresponding elements
	for (int x=0; x<total; x++)
		cycles[x] = cycleLen(elements[x], 1);
	return maxCycle(cycles, total);
}
int main () {
	int n1, n2;
	cin >> n1 >> n2;
	cout << n1 << ' ' << n2 << ' ' << createArray(n1,n2) << endl;
	return 0;
}

You have two problems I see. One, you only read one entry, when they expect you to take an input file with multiple lines/entries. You can do it like this:

        while (cin >> n1 >> n2)
        {
            cout << n1 << ' ' << n2 << ' ' << createArray(n1,n2) << endl;
        }

However there's a much larger and serious problem. You are overflowing your arrays!

Notice this piece of code in createArray:

        elements = new int[total-1];
        cycles = new int[total-1];
        //placing elements into elements array
        for (int x=0; x<total; x++)
                elements[x] = i++;
        //computing cycles for corresponding elements
        for (int x=0; x<total; x++)
                cycles[x] = cycleLen(elements[x], 1);

Let's say total is 10. Then the array has 9 elements (total-1). You would be iterating from 0 to 9, which is 10 elements. You allocated 9. You are writing into unallocated space, and can expect some pretty hard to debug and nasty problems as a result.

Also, you're not deallocating those arrays when you're done with them, and the way you wrote it, you will have trouble doing so. You'll probably want to do something like this:

        maxCycles = maxCycle(cycles, total);
        delete[] elements;
        elements = 0;
        delete[] cycles;
        cycles = 0;

        return maxCycles;

Obviously, declare maxCycles before doing that (and maybe call it something else since it's too close to the function name 'maxCycle'). My rule of thumb is to always pair new and delete together. Whatever component called new should also be responsible for calling delete. So, in this case, I made sure it deletes them at the end of the function that allocated them.

Anyways, I get the correct output after I make those changes.

 

[D H]

Another problem, and this is a big one: The function cycleLen() does not return a value except when the input num is equal to one.

What compiler are you using, and what options did you specify? With proper warning options, your compiler should have warned you of this problem.

 

[Grep]

Another problem, and this is a big one: The function cycleLen() does not return a value except when the input num is equal to one.

What compiler are you using, and what options did you specify? With proper warning options, your compiler should have warned you of this problem.

Good catch, D H! I totally didn't notice. I also didn't have all warnings turned on when I compiled it. If I add -Wall to the compile line, I get "warning: control reaches end of non-void function", as I should.

I'm slightly annoyed that it wouldn't warn me otherwise (this is with gcc 4.4). I can't think of any instance where that would be ok (not counting main, of course), but maybe I'm missing something.

Ah well, pro tip of the day: Turn on all warnings.

 

[kheiron1729]

First of all- Thanks a lot you guys!

Remember to put your code in CODE tags so it's more readable.

 got it!

I corrected the first problem. Not really a problem but oh well...

However there's a much larger and serious problem. You are overflowing your arrays!

I feel stupid. I have no idea why I did that.

Another problem, and this is a big one: The function cycleLen() does not return a value except when the input num is equal to one.

You're right! I was using Visual 2005. I don't think it even gave me a warning. I put this in DEV-C++ and it gives me nothing except either 0s or 1s.
I tried rewriting the function cycleLen.
Here's my new code:

#include <iostream>
using namespace std;

//iterates to find the cycle length
int cycleLen (int num) {
    int count=1;
	while (num!=1) {
          if (num%2 == 0)
             num /= 2;
          else {
               num *= 3;
               num += 1; }
          }
          count++;
          return count;
}

//Returning the Max Cycle
int maxCycle(int *list, int total) {
	int max = list[0];
	for (int i=1; i<total; i++)
		if (list[i] > max)
			max = list[i];
	return max;
}

//handling a range of numbers
int createArray (int i, int j) {
	int total = (j-i)+1;
	int* cycles;
	int* elements;
	int max1 = 0;
	elements = new int[total];
	cycles = new int[total];
	//placing elements into elements array
	for (int x=0; x<total; x++)
	    elements[x] = i++;
	//computing cycles for corresponding elements
	for (int x=0; x<total; x++)
		cycles[x] = cycleLen(elements[x]);
        max1 = maxCycle(cycles, total);
	delete[] elements;
	elements = 0;
	delete[] cycles;
	cycles = 0;
	return max1;
}
int main () {
	int n1, n2;
	while (cin >> n1 >> n2) {
		if (n2>n1)
			cout << n1 << ' ' << n2 << ' ' << createArray(n1,n2) << endl;
		else
			cout << n2 << ' ' << n1 << ' ' << createArray(n2,n1) << endl;
	}
	return 0;
}

Now, I am getting the right answer. BUT. The Judge at programming-challenges.com still thinks its the wrong answer. :'(
WHATS WRONG?!?EDIT:
If you are willing to go through the hassle. Here's the link to the website
http://www.programming-challenges.com/pg.php?page=submitproblem&probid=110101
You need to register first though.

 

[kheiron1729]

My friend shared his code with me.

#include <iostream>
 
using namespace std;
 
int length(int n)
{
	int i = 1;
 
	while(n != 1) {
		if(n % 2 == 0)  {
			n /= 2;
		} else {
			n *= 3;
			n += 1;
		}
		i++;
	}
	return i;
}
 
int main()
{
	int a, b, low, high;
 
	while(cin>>a>>b) {
		if(a < b) {
			low = a;
			high = b;
		} else {
			low = b;
			high = a;
		}
 
		int max = length(low);
 
		for(int i = low + 1; i <= high; i++) {
			int l = length(i);
			if(l > max) {
				max = l;
			}
		}
 
		cout<<a<<" "<<b<<" "<<max<<endl;
	}
 
	return 0;
}

This one works :O
His code is way better. Mine has so many irrelevant stuff in it.

Anyway, my question is: What exactly is wrong with my code?
Also (bonus question), I don't like the running time of the algorithm. I am thinking if someone can come up with a better algorithm.

Can you give me some tips for programming. I really REALLY want to get good at it.And again. Thanks a bunch!

 

[Grep]

This one works :O
His code is way better. Mine has so many irrelevant stuff in it.

Anyway, my question is: What exactly is wrong with my code?
Also (bonus question), I don't like the running time of the algorithm. I am thinking if someone can come up with a better algorithm.

Your code has it's strong points, too. I wouldn't worry. You're right though, yours has needless complexity. Anyone can make something complicated. But to me, a truly great programmer is one who can make something *simple*. I always strive for simplicity (as simple as possible but no simpler, as the saying goes) and clarity in my programming. No clever but hard to understand stuff just to show off. Just clear code. Well, that's my goal, anyways. Nobody's perfect. :)

Let's look at one of the main offenders, createArray. It needs no arrays at all, in fact. I simplified it quite a bit. Compare it to yours and see how I chopped out stuff that wasn't really needed. I did rename it, as well, since the name was now completely inaccurate. And of course, changing code often means changing comments (important!). Bet it's faster now, too.

Also just noticed you were incrementing i, which was a parameter and should not be modified. It's no longer needed, nor is the maxCycles function.

/* Computes cycles for each value from i to j inclusive, and returns
 * the maximum number of cycles out of all values.
 */
int findMaxCycles(int i, int j) {
        int cycles = 0;
        int max = 0;

        for (int x = i; x <= j; x++) {
                cycles = cycleLen(x);
                if (cycles > max) {
                        max = cycles;
                }
        }

        return max;
}

I won't go through all the changes, as I think you'll get it when you look at it. It was modified directly from your code. If you don't get something, of course, ask away.

I also rewrote your cycleLen function after reading the specs carefully. I notice it ends up almost identical to the one your friend made. Not surprising, as it's pretty much the most straightforward and literal implementation of what was decribed. That second parameter didn't seem to be of any use and was removed.

//iterates to find the cycle length
int cycleLen (int num) {
        int count = 1;

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

        return count;
}

You'll note that I use curly braces even when not really needed. I find it's clearer, and leaving them out surprisingly often leads to bugs down the road. Just something to consider. Not having them isn't at all wrong. But like I said, I go for maximum clarity. Also, I used to work writing safety critical software, so any potential source of errors is mercilessly hunted down and eliminated, if possible.

Can you give me some tips for programming. I really REALLY want to get good at it.

And again. Thanks a bunch!

There's so many tips I could think of, I wouldn't know where to start. I mean with programming in general, not your code. Hopefully you've gotten a few tips throughout this thread. If I think of any specific things I haven't covered, I'll let you know. If you have problems or want our opinion, always feel free to ask!

Of course, apologies if I've made a mistake. I think it's fine, but as I said, nobody's perfect.

Also, you're welcome!

P.S. Note that I tried to keep to your coding style, not mine.

 

[kheiron1729]

Thanks a bunch Grep. You are a life saver.