What is wrong with my code/logic?

[TridenT]

I would use code tags, but this is for a class I am in. I suspect that if my code is actually easily read then it might be searched for on teh interwebz and thus I'd have to explain stuff.. blahblah.

Here's the deal: http://img683.imageshack.us/img683/709/fix45.jpg

I get all the tests except "other tests" to run fine. I have no idea what I am doing wrong if I get those 15 tests right. I look at it, think of how it would run and go, "no idea what's wrong."

Do you know? :/

 

[PhatoseAlpha]

What is supposed to happen if there are more 4s then 5s?

Edit: Oh, equal numbers is a given.



Hm. Wait, why does your code work at all? The logic seems incorrect.

It searches for a 5. When it finds one, it searches the list from the begging for a 4, and switches the 5 with the number after the first 4 it finds.

It looks like it will always be trying to put the 5 after the first 4 in the array. The second and later rotation is just going to swap the 5 you already put after that 4 during the first rotation.

 

[lwstory]

Your algorithm is close to being correct but it is not perfect. Consider this case: {4,5,1,1,4,1,5}. Your code would yield {4,5,1,1,4,1,5} (the exact same as the input). Hopefully this helps you to move in the right direction.

 

[lwstory]

What is supposed to happen if there are more 4s then 5s?

The problem statement says the array contains the same number of 4's and 5's which i think they mean the number of 4's is equal to the number of 5's. I solved the problem with this assumption and it works. I found the problem at http://codingbat.com/prob/p125819. Good thought though!

 

[TridenT]

Got it eventually. Rewrote the code pretty much entirely. It works.

http://img41.imageshack.us/img41/7967/fix45new.jpg

 

[Ken g6]

Good. Got a couple more questions for you:

1. What is the Big-O runtime of your code? (Hint: It's not O(N).)
2. Can you make an O(N) version of that code? (Hint: I did. )

 

[TridenT]

Good. Got a couple more questions for you:

1. What is the Big-O runtime of your code? (Hint: It's not O(N).)
2. Can you make an O(N) version of that code? (Hint: I did. )

No clue. I don't think we are anywhere near talking about reducing-runtimes/optimization of code yet.

 

[Kirby]

Good. Got a couple more questions for you:

1. What is the Big-O runtime of your code? (Hint: It's not O(N).)
2. Can you make an O(N) version of that code? (Hint: I did. )

I think just by looking at it I can get O(N) + O(N/2), which is O(N).

Spoiler

I think you can loop through it once, putting the indexes of 4s and 5s (excluding {4,5} sets) in two arrays (O(N) time), then loop through the 4s (O(N/2) time) swapping where needed. I'm sure there's a much more elegant solution though.

 

[Ken g6]

I think just by looking at it I can get O(N) + O(N/2), which is O(N).

Spoiler

I think you can loop through it once, putting the indexes of 4s and 5s (excluding {4,5} sets) in two arrays (O(N) time), then loop through the 4s (O(N/2) time) swapping where needed. I'm sure there's a much more elegant solution though.

Spoiler

Swapping with what? Searching for something to swap with

is itself O(N), I think, so I doubt that will work.

My more elegant solution:

Spoiler

Recall that in the end, every 4 will be followed by a 5, and there are equal numbers of 4's and 5's. So I just make a new array, find and copy all the 4's (O(N)), put a 5 after each one. Then I search the original array again for all numbers that are not 4 or 5, and just stick them anywhere in the new array where there isn't already 4 or a 5.

 

[Kirby]

Spoiler

Swapping with what? Searching for something to swap with

is itself O(N), I think, so I doubt that will work.

My more elegant solution:

Spoiler

Recall that in the end, every 4 will be followed by a 5, and there are equal numbers of 4's and 5's. So I just make a new array, find and copy all the 4's (O(N)), put a 5 after each one. Then I search the original array again for all numbers that are not 4 or 5, and just stick them anywhere in the new array where there isn't already 4 or a 5.

Here's my inelegant solution:

Spoiler

int four_array[] = new int[nums.length];
int five_array[] = new int[nums.length];
int j = 0;
int k = 0;
boolean c = false;

for (int i = 0; i < nums.length; i++) { // O(N)
if (c == false && nums == 4 && nums[i + 1] == 5) {
c = true;
continue;
}
if (c) {
c = false;
continue;

}
else {
if (nums == 4) {
four_array[j++] = i;
}
if (nums == 5) {
five_array[k++] = i;
}
}
}

k = 0;
for (int i = 0; i < j; i++) { // O(N/2)
int temp = nums[four_array + 1];
nums[four_array + 1] = nums[five_array[k]];
nums[five_array[k++]] = temp;
}
return nums;

LMFAO, that got uglier the more I typed (especially that boolean/continue crap lulz). It was somewhat clear in my head originally. :biggrin:

So, in short, your's is better.

 

[Kr@n]

My more elegant solution: [...]

Huh, didn't see your code, so I can't make hard assumptions, but keep in mind you must not move the 4s, just other numbers.
EDIT : Oh yeah, I think I wrongly understood you wanted to append all the 4s and 5s at the start, but nothing prevents you to allocate the whole resulting array and copy the 4s at the same indexes you found them (silly me). There is still an allocation / memory efficiency issue (especially for big arrays), but this is way beyond the scope of this problem (and one has to pay the cost somewhere, be it computations or memory)

Got it eventually. Rewrote the code pretty much entirely. It works.

http://img41.imageshack.us/img41/7967/fix45new.jpg

Is it just me, or does your code breaks badly if the last number is a 4 ? That *should* never be the case per spec (because this wouldn't be solvable, given you must not move the 4s), but I always shiver when I see code that do not validate/control its input (one sure get plenty of wrong or malicious input on the web) ...
EDIT : You can just iterate while i < length - 1 (you can safely ignore the last number, because if it's a 4, there nothing you can do anyway). Marginally better performance, and no index overflow vulnerability ...

 

[TridenT]

Huh, didn't see your code, so I can't make hard assumptions, but keep in mind you must not move the 4s, just other numbers.
EDIT : Oh yeah, I think I wrongly understood you wanted to append all the 4s and 5s at the start, but nothing prevents you to allocate the whole resulting array and copy the 4s at the same indexes you found them (silly me). There is still an allocation / memory efficiency issue (especially for big arrays), but this is way beyond the scope of this problem (and one has to pay the cost somewhere, be it computations or memory)




Is it just me, or does your code breaks badly if the last number is a 4 ? That *should* never be the case per spec (because this wouldn't be solvable, given you must not move the 4s), but I always shiver when I see code that do not validate/control its input (one sure get plenty of wrong or malicious input on the web) ...
EDIT : You can just iterate while i < length - 1 (you can safely ignore the last number, because if it's a 4, there nothing you can do anyway). Marginally better performance, and no index overflow vulnerability ...

I just build to spec as fast as possible and nothing more. I wasn't really going for perfect code because that's really not possible to tell at this point. (I'd have to have more data about cpu cycles and run times. Figure out what is actually more "productive" or "efficient", etc....)

 

[Schmide]

I think we can just show the code now. Here's my solution that should be near Ken g6's solution. Probably better since you only walk the list once* and you don't have to re-find non 4-5 numbers. It also finds and skips the cases were there already is a 4-5 pair.

* There is a second pass but it only walks the effected numbers.

(I did not do thorough testing but I believe my logic is sound)

Edit: I noticed that a couple checks could be avoided by dropping into a second loop after both start positions are found.

Edit2: It is like nkgreen's solution but it doesn't require any additional storage (arrays)

Edit3: Optimized drop to second loop

		/* It basically stores the index of the next 4 or 5 at the current 
	position then walks the list copying what's after the 4 to the 5 
	postition. Skips all cases where there already is a 4 5 pair.  */

	int iStart4=-1;
	int iStart5=-1;
	int iLast4;
	int iLast5;
	int iCount=0;
	int i;
	for(i=0;i<nums.length;i++)
		if(nums[i]==4)
			if(nums[i+1]!=5)
			{
				if(iStart4<0)
				{
					iStart4=i; 
					if(iStart5>=0)
					{
						iLast4=i;
						iCount++;
						break;
					}
				} else 
					nums[iLast4]=i; 
				iLast4=i;
				iCount++;
			} else 
				i++; 
		else 
			if(nums[i]==5)
			{
				if(iStart5<0) 
				{
					iStart5=i;
					if(iStart4>=0)
					{
						iLast5=i;
						break;
					}
				} else 
					nums[iLast5]=i;
				iLast5=i;
			}
	for(;i<nums.length;i++)
		if(nums[i]==4)
			if(nums[i+1]!=5)
			{
				nums[iLast4]=i; 
				iLast4=i;
				iCount++;
			} else 
				i++; 
		else 
			if(nums[i]==5)
			{
				nums[iLast5]=i;
				iLast5=i;
			}
	for(i=0;i<iCount;i++)
	{
		iLast5=nums[iStart5];
		nums[iStart5]=nums[iStart4+1];
		iLast4=nums[iStart4];
		nums[iStart4]=4;
		nums[iStart4+1]=5;
		iStart4=iLast4;
		iStart5=iLast5;
	}

 

[JujuFish]

Move all 4s and 5s to front, one pass through array:

int cnt4 = 0, cnt5 = 1, i = 0, tmp;
while (i < nums.length) {
    if ((nums[i] == 4) && (i >= cnt4)) {
        if (i == cnt4)
            cnt4 += 2;
        else {
            tmp = nums[cnt4];
            nums[cnt4] = nums[i];
            nums[i] = tmp;
            cnt4 += 2;
            continue;
        }
    }
    else if ((nums[i] == 5) && (i >= cnt5)){
        if (i == cnt5)
            cnt5 += 2;
        else {
            tmp = nums[cnt5];
            nums[cnt5] = nums[i];
            nums[i] = tmp;
            cnt5 += 2;
            continue;
        }
    }
    i++;
}
return nums;

 

[TridenT]

Move all 4s and 5s to front, one pass through array:

int cnt4 = 0, cnt5 = 1, i = 0, tmp;
while (i < nums.length) {
    if ((nums[i] == 4) && (i >= cnt4)) {
        if (i == cnt4)
            cnt4 += 2;
        else {
            tmp = nums[cnt4];
            nums[cnt4] = nums[i];
            nums[i] = tmp;
            cnt4 += 2;
            continue;
        }
    }
    else if ((nums[i] == 5) && (i >= cnt5)){
        if (i == cnt5)
            cnt5 += 2;
        else {
            tmp = nums[cnt5];
            nums[cnt5] = nums[i];
            nums[i] = tmp;
            cnt5 += 2;
            continue;
        }
    }
    i++;
}
return nums;

I didn't read your code enough, but does yours actually move the 4's? You're not allowed to move them as part of the problem.

 

[JujuFish]

I didn't read your code enough, but does yours actually move the 4's? You're not allowed to move them as part of the problem.

Reading comprehension and I don't always get along. Oh well.

 

[JujuFish]

Pass through the array once, marking the locations of all 4s and 5s, then swap all 5s into positions following 4s.

int tmp, cnt4 = 0, cnt5 = 0;
int[] fours = new int[nums.length/2];
int[] fives = new int[nums.length/2];
for (int i = 0; i < nums.length; i++) {
    if (nums[i] == 4) {
        fours[cnt4] = i;
        cnt4++;
    }
    else if (nums[i] == 5) {
        fives[cnt5] = i;
        cnt5++;
    }
}
for (int i = 0; i < cnt5; i++) {
    tmp = nums[fours[i] + 1];
    nums[fours[i] + 1] = nums[fives[i]];
    nums[fives[i]] = tmp;
}
return nums;

Edit: seems my code is almost identical to nkgreen's. Again, oh well.

 

[Schmide]

(snip)
        k = 0;
        for (int i = 0; i < j; i++) { // O(N/2)
            int temp = nums[four_array[i] + 1];
            nums[four_array[i] + 1] = nums[five_array[k]];
            nums[five_array[k++]] = temp;
        }

 (snip)
for (int i = 0; i < cnt5; i++) {
    tmp = nums[fours[i] + 1];
    nums[fours[i] + 1] = nums[fives[i]];
    nums[fives[i]] = tmp;
}

Psst you don't have to switch, you're always writing a 5 after the 4

for (int i = 0; i < cnt5; i++) {
    nums[fives[i]] = nums[fours[i] + 1];
    nums[fours[i] + 1] = 5;
}

 

[Kirby]

/self-facepalm