Array Comparison and Modification

Printable View

12-21-2012
Debojyoti Das

Array Comparison and Modification

This is what my code is intended to do: When called with the following array:

Code:

{ 1, 1, 1, 2, 2, 1, 2, 3, 3, 1, 1 }

, your function should modify the array to

Code:

{1, 2, 1, 2, 3, 1}

and store it.

Code:

#include <stdio.h> #include <stdlib.h> void compact (int[], int); int main() { int arrSeries[11] = {1, 1, 1, 2, 2, 1, 2, 3, 3, 1, 1 }; int arrLength = 11; compact(arrSeries, arrLength); getchar(); return 0; } void compact(int arrSeries[], int arrLength) { int i, j= 0, counter=0, newArray[11]; newArray[0]=arrSeries[0]; for(i = 1; i != arrLength; i++) { if(newArray[j] != arrSeries[i-1]); { newArray[++j] = arrSeries[i]; } } while(counter !=6) { printf("%d ", newArray[counter]); counter++; } }

However it is not working as intended. It works as if the IF statement doesn't even exist ! Where am I going wrong?
Thanks :)
12-21-2012
Matticus

Code:

if(newArray[j] != arrSeries[i-1]);

That semi-colon at the end of your "if()" statement is making that statement do nothing.
12-21-2012
Debojyoti Das

Quote:

Originally Posted by Matticus

Code:

if(newArray[j] != arrSeries[i-1]);

That semi-colon at the end of your "if()" statement is making that statement do nothing.

Oops ! That was a typo...edited and recompiled the code. Still No luck :frown: Gives erroneous results: 1 2 2 3 1 2686632

Also how should I modify the code to satisfy this problem?

Quote:

Write a function compact ( ) which takes as parameters an array of integers and its length.The function should modify the array, so that all consecutive
occurrences of the same; integers are replaced by a single occurrence of that integer.
The function should return the length of this new array.
12-21-2012
R.Stiltskin

Quote:

Originally Posted by Debojyoti Das

Code:

if(newArray[j] != arrSeries[i-1])

Are you sure you want to compare to element [i-1]?

PS: when you see entries like 2686632 popping up, you should suspect that you might be running out of the bounds of your array somewhere.
12-21-2012
Debojyoti Das

Quote:

Originally Posted by R.Stiltskin

Are you sure you want to compare to element [i-1]?

PS: when you see entries like 2686632 popping up, you should suspect that you might be running out of the bounds of your array somewhere.

Yeah I thought that ! Thanks ! I got the error !

Code:

for(i = 0; i != arrLength; i++) { if(newArray[j] != arrSeries[i]) { newArray[++j] = arrSeries[i]; } }

gives correct output.

But another question, as arrays are static data structures in C, is this question solvable using C?

Write a function compact ( ) which takes as parameters an array of integers and its length.The function should modify the array, so that all consecutive
occurrences of the same; integers are replaced by a single occurrence of that integer.
The function should return the length of this new array.

Thanks Again
12-21-2012
R.Stiltskin

Of course it's solvable. Think.
12-21-2012
Debojyoti Das

Quote:

Originally Posted by R.Stiltskin

Of course it's solvable. Think.

Are you suggesting I use dynamic memory allocation?
12-21-2012
std10093

Many solutions.
One would be to create dynamically a new array and fill it with the elements. But your function returns only the length of the array....
So are you sure you need to create a new array??
The requirement says to modify the array!
12-21-2012
Adak

Quote:

Originally Posted by Debojyoti Das

Are you suggesting I use dynamic memory allocation?

Say you were, for a moment, the tip of the pen, and you start with index 0 of this array:

Code:

int arrSeries[11] = {1, 1, 1, 2, 2, 1, 2, 3, 3, 1, 1 };

You look ahead, and see the next number is the same as your current number.

What would you have to do to get rid of that current number, and move all the higher numbers, down by one index?

Work on it with paper and pen, and see what patterns of logic you need to follow to make this happen. Repeat it a few times, and the patterns will become evident.

And that's the backbone of your programs logic. Don't let someone give you the answer - work it out.
12-21-2012
Debojyoti Das

Quote:

Originally Posted by std10093

Many solutions.
One would be to create dynamically a new array and fill it with the elements. But your function returns only the length of the array....
So are you sure you need to create a new array??
The requirement says to modify the array!

I assume that means I should create the first array (that keeps the repeating number dynamically so that I can modify it later). Trying to code it now..
12-21-2012
std10093

Quote:

Originally Posted by Adak

And that's the backbone of your programs logic. Don't let someone give you the answer - work it out.

Tip to remeber forever!

Quote:

Originally Posted by Debojyoti Das

I assume that means I should create the first array (that keeps the repeating number dynamically so that I can modify it later). Trying to code it now..

I am not sure what you want to accomplish. I would suggest to follow Adak's advice. But before doing that read again and again the requirement!
12-21-2012
Debojyoti Das

Quote:

Originally Posted by std10093

Tip to remeber forever!

I am not sure what you want to accomplish. I would suggest to follow Adak's advice. But before doing that read again and again the requirement!

Sorry I overlooked Adak's post while refreshing the page. I get the logic, I will simply shift the digits and throw out the repeating digits...say

Array s -> 1 1 1 2 2 3 1 4 1
Fisrt Pass -> Check Index 0 and 1 > Index 0 is top -> Pop index 0 -> Set index 1 to s.top.
Next Pass - > 1 1 2 2 3 1 4 1
Next Pass - > 1 2 2 3 1 4 1 g
Next Pass - > 1 2 3 1 4 1 g g

now the indices with g has the previous value or I may set it to 0. Will that be the solution?
12-21-2012
std10093

Nice explanation and nice idea :D Bravo. Try it out and post back even though it work!! I am eager to see the result :D
12-21-2012
Debojyoti Das

Quote:

Originally Posted by std10093

Nice explanation and nice idea :D Bravo. Try it out and post back even though it work!! I am eager to see the result :D

Thanks ! Working on it !
12-21-2012
R.Stiltskin

Quote:

Originally Posted by Debojyoti Das

Sorry I overlooked Adak's post while refreshing the page. I get the logic, I will simply shift the digits and throw out the repeating digits...say

Array s -> 1 1 1 2 2 3 1 4 1
Fisrt Pass -> Check Index 0 and 1 > Index 0 is top -> Pop index 0 -> Set index 1 to s.top.
Next Pass - > 1 1 2 2 3 1 4 1
Next Pass - > 1 2 2 3 1 4 1 g
Next Pass - > 1 2 3 1 4 1 g g

now the indices with g has the previous value or I may set it to 0. Will that be the solution?

That's a viable approach and certainly worth doing, if only for the benefit of the programming practice it gives you. However, think about how many operations the computer will be performing as compared to your original program. To me, it seems a horribly inefficient way to solve an extremely simple problem. So after you finish that, you should go back to the original version and think about it some more. When you come to your `Eureka' moment you'll see what I mean.
12-21-2012
std10093

Quote:

Originally Posted by R.Stiltskin

That's a viable approach and certainly worth doing, if only for the benefit of the programming practice it gives you. However, think about how many operations the computer will be performing as compared to your original program. To me, it seems a horribly inefficient way to solve an extremely simple problem. So after you finish that, you should go back to the original version and think about it some more. When you come to your `Eureka' moment you'll see what I mean.

While I do not fully disagree, tell me about the time complexity of the operation that Debojyoti is going to make. Of course it's not optimum, but he is probably a beginner in C.

By the way I didn't know that you say Eureka too :D
12-21-2012
R.Stiltskin

We shouldn't turn this into a debate about complexity, but doesn't repeatedly shifting the entire array change it from O(n) to O(n²)?

But even ignoring the time complexity, it makes the program itself much more complicated than is necessary.

Oh, and some of us have actually heard of a fellow named Archimedes as well! :cool:
12-21-2012
std10093

Exactly :)

Of course you do :)
12-21-2012
Debojyoti Das

Quote:

Originally Posted by std10093

Exactly :)

Of course you do :)

Here's my solution (it work's :) ) but it became quite complex and due to the shifting the garbage value also shows.
Now will think on R.Stiltskin's idea.

Code:

#include <stdio.h>#include <stdlib.h> #define MAXSIZE 10 int compact(int[]); int main() { int num=0, numarray[MAXSIZE]={0,0,0,0,0,0,0,0,0,0}, i=0; int top = -1; printf("Please enter some numbers. Enter -1 to stop.\n"); while(num != -1) { scanf("%d", &num); if(top==(MAXSIZE-1) || num == -1) { printf("Done !\n"); break; } else { top+=1; numarray[top] = num; } } while(i<MAXSIZE) { printf("%d ", numarray[i]); i++; } printf("\nPrinting compact numvers.\n"); compact(numarray); getchar(); return 0; } int compact(int changeArray[MAXSIZE]) { int i=0, j=0, k=0, l=0; while(l<MAXSIZE) { i=0, j=0; while(i < MAXSIZE) { if(changeArray[i]==changeArray[i+1]) { j=i; while(j < MAXSIZE) { changeArray[j]=changeArray[j+1]; j++; } } i++; } l++; } while(k<MAXSIZE) { printf("%d ", changeArray[k]); k++; } getchar(); return 0; }

I did not implement the size returning function as I am not very satisfied with the garbage values creeping in. Maybe I will modify to store 0/-1 instead of garbage and check conflict if user inputs the same.
12-21-2012
std10093

Spelling

Code:

printf("\nPrinting compact numvers.\n");

Of course take a shot in R.Stiltskin's idea. ;)
12-21-2012
R.Stiltskin

Nice job. Now why don't you modify the program so it counts (and prints) the number of assignments performed (i.e., how many times a number is moved from one place to another) while processing a given input. Then do the same thing with your previous program and compare the number of operations for the same input array.
12-21-2012
Debojyoti Das

Quote:

Originally Posted by R.Stiltskin

Nice job. Now why don't you modify the program so it counts (and prints) the number of assignments performed (i.e., how many times a number is moved from one place to another) while processing a given input. Then do the same thing with your previous program and compare the number of operations for the same input array.

You are recommending me to find out it's time complexity. Sure thing doing it now :) .
12-21-2012
Debojyoti Das

Quote:

Originally Posted by std10093

Spelling

Code:

printf("\nPrinting compact numvers.\n");

Of course take a shot in R.Stiltskin's idea. ;)

Why did they keep v and b adjacently on the keyboard ;) ??
12-22-2012
laserlight

Quote:

Originally Posted by Debojyoti Das

Why did they keep v and b adjacently on the keyboard ??

Shh... this is the C programming forum, not VB :p
12-22-2012
Debojyoti Das

Code:

while(l<MAXSIZE) { i=0, j=0; while(i < MAXSIZE) { if(changeArray[i]==changeArray[i+1]) { j=i; while(j < MAXSIZE) { changeArray[j]=changeArray[j+1]; j++; } stepcounter++; } i++; } l++; }

So, I added a step-counter here and also here:

Code:

for(i = 0; i != arrLength; i++) { if(newArray[j] != arrSeries[i]) { newArray[++j] = arrSeries[i]; stepcounter++; }

Attachment 12372

Attachment 12373

No doubt my previous code was much more efficient than this one. Trying to modify the previous code to make it work dynamically :) .
12-22-2012
std10093

Your attachments do not lead me anywhere :/
12-22-2012
Debojyoti Das

Quote:

Originally Posted by std10093

Your attachments do not lead me anywhere :/

It got deleted for reasons I don't know :(

Quote:

1 2 1 2 3 1
The number of steps: 5

1 1 1 2 2 1 3 3 1 1
Printing compact numbers.
1 2 1 3 1 1 1 1 1 1
Steps Performed: 63

Well it's the number of steps my first and second piece of code does for similar set of numbers. In fact the second piece of code was provided a number less yet it took substantially more steps to compute than the first step, which did the computation with one number more in the series in so less steps. Sorry for being ambiguous in my previous post :) .
12-22-2012
std10093

No problem :)

So, can you post the code that you think is the best you have until now? :)
12-22-2012
Debojyoti Das

Quote:

Originally Posted by std10093

No problem :)

So, can you post the code that you think is the best you have until now? :)

Code:

#include <stdio.h>#include <stdlib.h> void compact (int[], int); int main() { int arrSeries[11] = {1, 1, 1, 2, 2, 1, 2, 3, 3, 1, 1 }; int arrLength = 11; compact(arrSeries, arrLength); getchar(); return 0; } void compact(int arrSeries[], int arrLength) { int i, j= 0, counter=0, newArray[11], stepcounter = 0; newArray[0]=arrSeries[0]; for(i = 0; i != arrLength; i++) { if(newArray[j] != arrSeries[i]) { newArray[++j] = arrSeries[i]; stepcounter++; } } while(counter !=6) { printf("%d ", newArray[counter]); counter++; } printf("\nThe number of steps: %d", stepcounter); }

This one, but it is highly restricted as it works only with a static data set.
12-22-2012
std10093

Only one for loop in the function which is good. Well do you really need stepcounter? I would say that j has the same value with stepcounter when you reach line 31.
12-22-2012
Debojyoti Das

Quote:

Originally Posted by std10093

Only one for loop in the function which is good. Well do you really need stepcounter? I would say that j has the same value with stepcounter when you reach line 31.

Yes j has the same value, thank you for making me notice :) . Changed the code and also added data acceptance from user:

Code:

#include <stdio.h>#include <stdlib.h> #define MAXVALUE 10 void compact (int[], int); int main() { int arrSeries[MAXVALUE], i=0; int arrLength = MAXVALUE; printf("Please enter %d numbers.\n", MAXVALUE); while(i != MAXVALUE) { scanf("%d", &arrSeries[i]); i++; } compact(arrSeries, arrLength); getchar(); return 0; } void compact(int arrSeries[], int arrLength) { int i, j= 0, counter=0, newArray[MAXVALUE]={0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; newArray[0]=arrSeries[0]; for(i = 0; i != arrLength; i++) { if(newArray[j] != arrSeries[i]) { newArray[++j] = arrSeries[i]; } } while(counter !=MAXVALUE) { printf("%d ", newArray[counter]); counter++; } printf("\nThe number of steps: %d", j); getchar(); }
12-22-2012
std10093

You are welcome. Now the only problem that I can see is when the user inputs as last numbers zeroes.. But still I would be happy with the code:)
12-22-2012
Debojyoti Das

Quote:

Originally Posted by std10093

You are welcome. Now the only problem that I can see is when the user inputs as last numbers zeroes.. But still I would be happy with the code:)

Thanks :) . Maybe I will prompt user not to enter 0's :D .
12-22-2012
std10093

That would be a nice solution :)
Or you could find the minimum element that the user inputted. You could that without increasing complexity.

How? When doing the scanf, you could find the min ;)

Then you could pass this min as third argument to your function and initialize the array to this value min instead of zeroes. What is your opinion on that? :)
12-22-2012
Debojyoti Das

Quote:

Originally Posted by std10093

That would be a nice solution :)
Or you could find the minimum element that the user inputted. You could that without increasing complexity.

How? When doing the scanf, you could find the min ;)

Then you could pass this min as third argument to your function and initialize the array to this value min instead of zeroes. What is your opinion on that? :)

That's a great idea ! Atleast the user won't need to see zeroes and garbage values :) . Thanks.
12-22-2012
std10093

Correct! You will print until you find the min ;) Go ahead and code! :D
12-22-2012
Adak

Adjust the number of good values, as you remove the repeated values. Print only the good values!
12-22-2012
Debojyoti Das

Quote:

Originally Posted by std10093

Correct! You will print until you find the min ;) Go ahead and code! :D

Quote:

Originally Posted by Adak

Adjust the number of good values, as you remove the repeated values. Print only the good values!

Well a new train of thought came to me. Why not I just remember the last digit in the array of number the user inputs, fill the array say (last digit+1) and during result output truncate all digits from and after last (digit + 1). Will that be more efficient?

Example:

User Inputs 1 1 1 2 2 3 3 3 4 5 5
Next Pass -> Last Digit = 5, Initialize Array to 6 6 6 6 6 6 6 6 6 6
Next Pass -> Compact Array 1 2 3 4 5 6 g g g g (g=garbage value)
Next Pass -> Print Before First Appearance of Last Digit Print 1 2 3 4 5

That way I can skip the following tests :

i.) MAXVALUE comparisons to find Minimum Digits.
ii.) Test to check if the last repeating/Non-repeating digits were the minimum value.
|----------------> if TRUE -----> Keep One Instance of Last Digit.

Please comment as I may be wrong and I am just a beginner in coding. Thanks.
12-22-2012
laserlight

Hmm... what is this thing about minimum/maximum digits? Your function should return the length of the reduced range, right? The caller is then responsible for working with the reduced range. Trying to set the "removed" part of the original array/range to some designated garbage value is unnecessary.

Incidentally, if you ever use C++ instead of C, check out the C++ standard library's std::unique generic algorithm for something along the lines of what you are supposed to do here.

EDIT:
ARGH! Looking at your post #31, you're writing a function that does too much. Let the compact function compact the array to a reduced range and return the length of the reduced range. It should not print anything at all.
12-22-2012
Debojyoti Das

Quote:

Originally Posted by laserlight

Hmm... what is this thing about minimum/maximum digits? Your function should return the length of the reduced range, right? The caller is then responsible for working with the reduced range. Trying to set the "removed" part of the original array/range to some designated garbage value is unnecessary.

Incidentally, if you ever use C++ instead of C, check out the C++ standard library's std::unique generic algorithm for something along the lines of what you are supposed to do here.

EDIT:
ARGH! Looking at your post #31, you're writing a function that does too much. Let the compact function compact the array to a reduced range and return the length of the reduced range. It should not print anything at all.

True the actual question doesn't want me to print the compact array but just for my programming practice I took on the (ARGH! :)) task :D. Thanks for the heads up on C++, I am yet to learn that :( . I know C# a bit and I know there is a function for the same Distinct()).
12-22-2012
std10093

Quote:

Originally Posted by Debojyoti Das

Well a new train of thought came to me. Why not I just remember the last digit in the array of number the user inputs, fill the array say (last digit+1) and during result output truncate all digits from and after last (digit + 1). Will that be more efficient?

Example:

User Inputs 1 1 1 2 2 3 3 3 4 5 5
Next Pass -> Last Digit = 5, Initialize Array to 6 6 6 6 6 6 6 6 6 6
Next Pass -> Compact Array 1 2 3 4 5 6 g g g g (g=garbage value)
Next Pass -> Print Before First Appearance of Last Digit Print 1 2 3 4 5

That way I can skip the following tests :

i.) MAXVALUE comparisons to find Minimum Digits.
ii.) Test to check if the last repeating/Non-repeating digits were the minimum value.
|----------------> if TRUE -----> Keep One Instance of Last Digit.

Please comment as I may be wrong and I am just a beginner in coding. Thanks.

It does not sound like a bad idea. Don't be afraid to try. From our mistakes we learn :)
12-22-2012
laserlight

Taking on that task is fine: in fact, I probably would have done it even before implementing the function because it gives me an easy way to verify that the function works. The thing is, the task should be performed in the main function, or another function that calls compact. Later on, you might write automated tests that call compact with some input and checks that the output is as expected. In such a case, you would be printing the success/failure of those unit tests rather than the contents of the array.
12-22-2012
Debojyoti Das

Here's the final code:

Code:

#include <stdio.h> #include <stdlib.h> #define MAXVALUE 10 int compact (int[], int); int main() { int arrSeries[MAXVALUE], i=0, newArrayLength; int arrLength = MAXVALUE; printf("Please enter %d numbers.\n", MAXVALUE); while(i != MAXVALUE) { scanf("%d", &arrSeries[i]); i++; } newArrayLength=compact(arrSeries, arrLength); printf("The new array length is %d.", newArrayLength); getchar(); return 0; } int compact(int arrSeries[], int arrLength) { int i=0, j= 0, k=MAXVALUE, counter=0, newArray[MAXVALUE], lastVal, readCounter=MAXVALUE; lastVal=arrSeries[MAXVALUE]; lastVal++; while(i!=MAXVALUE) { newArray[i]=lastVal; i++; } newArray[0]=arrSeries[0]; for(i = 0; i != arrLength; i++) { if(newArray[j] != arrSeries[i]) { newArray[++j] = arrSeries[i]; } } while(k!=0) { if(newArray[k]==lastVal) { readCounter--; } k--; } while(counter <= readCounter) { printf("%d ", newArray[counter]); counter++; } printf("\nThe number of steps: %d.\n", j); return ++readCounter; }

It addresses the main problem as well by returning the array length :) . Please comment :D.
12-22-2012
laserlight

Okay, looking through this thread again, I see that other than your solution in post #19, which is admittedly more complicated than necessary, your solutions use an extra array when this can be done in-place. Why not try for a simpler in-place solution? It seems that you are close. You could re-read Adak's post #9, but note that "move all the higher numbers, down by one index" is an unnecessary step.
12-22-2012
std10093

It seems ok :)

I would throw away k and use i in lines 42 to 49.
Like this

Code:

i = MAXVALUE; while(i!=0) { if(newArray[i]==lastVal) { readCounter--; } i--; }

Another thing I would change is this

Code:

while(i!=MAXVALUE) { newArray[i]=lastVal; i++; }

to this (since we know how many loops are going to be done, we should use for loop. Using while loop is not wrong. )

Code:

for( i = 0 ; i < MAXVALUE i++) { newArray[i]=lastVal; }

As a result, I would change also the part that I used i instead of k.

Code:

i = MAXVALUE; while(i!=0) { if(newArray[i]==lastVal) { readCounter--; } i--; }

to this

Code:

i = MAXVALUE; for( i = MAXVALUE ; i > 0 ; i--) { if(newArray[i]==lastVal) { readCounter--; } }

I run it without changing your code and I got

Code:

Macintosh-c8bcc88e5669-9:~ usi$ ./px Please enter 10 numbers. 1 1 1 1 14 5 6 7 3 4 1 14 5 6 7 3 4 1693429850 The number of steps: 6. The new array length is 8.

Also when you print the new array length put a newline to the printf ;)
12-22-2012
Debojyoti Das

Quote:

Originally Posted by laserlight

Okay, looking through this thread again, I see that other than your solution in post #19, which is admittedly more complicated than necessary, your solutions use an extra array when this can be done in-place. Why not try for a simpler in-place solution? It seems that you are close. You could re-read Adak's post #9, but note that "move all the higher numbers, down by one index" is an unnecessary step.

An in-place solution would surely reduce space complexity and as this would be a divide and conquer method, time complexity may improve. A good proposition indeed.Working out now :) .
12-22-2012
Debojyoti Das

Quote:

Originally Posted by std10093

It seems ok :)

I would throw away k and use i in lines 42 to 49.
Like this

Code:

i = MAXVALUE; while(i!=0) { if(newArray[i]==lastVal) { readCounter--; } i--; }

Another thing I would change is this

Code:

while(i!=MAXVALUE) { newArray[i]=lastVal; i++; }

to this (since we know how many loops are going to be done, we should use for loop. Using while loop is not wrong. )

Code:

for( i = 0 ; i < MAXVALUE i++) { newArray[i]=lastVal; }

As a result, I would change also the part that I used i instead of k.

Code:

i = MAXVALUE; while(i!=0) { if(newArray[i]==lastVal) { readCounter--; } i--; }

to this

Code:

i = MAXVALUE; for( i = MAXVALUE ; i > 0 ; i--) { if(newArray[i]==lastVal) { readCounter--; } }

I run it without changing your code and I got

Code:

Macintosh-c8bcc88e5669-9:~ usi$ ./px Please enter 10 numbers. 1 1 1 1 14 5 6 7 3 4 1 14 5 6 7 3 4 1693429850 The number of steps: 6. The new array length is 8.

Also when you print the new array length put a newline to the printf ;)

Wow ! I will change and try to fix the bug :) .

EDIT:

Quote:

for( i = 0 ; i < MAXVALUE:)i++)

{ newArray[i]=lastVal; }

You missed a semicolon there :) .
12-22-2012
std10093

I will help a bit :)
What does this line do?

Code:

lastVal=arrSeries[MAXVALUE];
12-22-2012
laserlight

Quote:

Originally Posted by Debojyoti Das

An in-place solution would surely reduce space complexity

Of course :)

Quote:

Originally Posted by Debojyoti Das

and as this would be a divide and conquer method

You don't need to use a divide and conquer strategy here.
12-22-2012
Debojyoti Das

Edited. Returns correct results for me :). Added a newline character as well :) .

Code:

#include <stdio.h>#include <stdlib.h> #define MAXVALUE 10 int compact (int[], int); int main() { int arrSeries[MAXVALUE], i=0, newArrayLength; int arrLength = MAXVALUE; printf("Please enter %d numbers.\n", MAXVALUE); while(i != MAXVALUE) { scanf("%d", &arrSeries[i]); i++; } newArrayLength=compact(arrSeries, arrLength); printf("The new array length is %d.\n", newArrayLength); getchar(); return 0; } int compact(int arrSeries[], int arrLength) { int i=0, j= 0, counter=0, newArray[MAXVALUE], lastVal, readCounter=MAXVALUE; lastVal=arrSeries[(MAXVALUE-1)]; lastVal++; for( i = 0 ; i < MAXVALUE; i++) { newArray[i]=lastVal; } newArray[0]=arrSeries[0]; for(i = 0; i != arrLength; i++) { if(newArray[j] != arrSeries[i]) { newArray[++j] = arrSeries[i]; } } i=MAXVALUE; for( i = MAXVALUE ; i > 0 ; i--) { if(newArray[i]==lastVal) { readCounter--; } } while(counter <= readCounter) { printf("%d ", newArray[counter]); counter++; } printf("\nThe number of steps: %d.\n", j); return ++readCounter; }

Quote:

Please enter 10 numbers.1
1
1
1
14
5
6
7
3
4
1 14 5 6 7 3 4
The number of steps: 6.
The new array length is 7.
Process returned 0 (0x0) execution time : 21.715 s
Press any key to continue.
12-22-2012
Debojyoti Das

Quote:

Originally Posted by std10093

I will help a bit :)
What does this line do?

Code:

lastVal=arrSeries[MAXVALUE];

Out of bounds :(. Silly me.
12-22-2012
std10093

Everybody has gone out of bounds ;) The important thing is that you fixed it, doesn't that feel great? :D
12-22-2012
Debojyoti Das

Quote:

Originally Posted by laserlight

You don't need to use a divide and conquer strategy here.

Not exactly divide and conquer but my approach will be to divide the partition into repeating sets and then put one instance for the same and keep the non-repeating sets as is. I think it might be faster than before.
12-22-2012
Debojyoti Das

Quote:

Originally Posted by std10093

Everybody has gone out of bounds ;) The important thing is that you fixed it, doesn't that feel great? :D

It surely does :) ! Thanks :) .
12-22-2012
laserlight

Good that you noticed the out of bounds access. Now, test your program with input:

Code:

2 2 2 2 2 2 2 2 2 1

Frankly, I still don't understand why you are trying to designate a particular invalid value to pre-fill the extra array when you don't need to.

EDIT:
Oh wait, you're just printing the array based on the reduced range, which means that the output should be fine... but it also means that the whole lastVal business is utterly pointless.
12-22-2012
Debojyoti Das

Quote:

Originally Posted by laserlight

Good that you noticed the out of bounds access. Now, test your program with input:

Code:

2 2 2 2 2 2 2 2 2 1

Frankly, I still don't understand why you are trying to designate a particular invalid value to pre-fill the extra array when you don't need to.

EDIT:
Oh wait, you're just printing the array based on the reduced range, which means that the output should be fine... but it also means that the whole lastVal business is utterly pointless.

Just to do replace the garbage values I guess. And in my version of the code I get the reduced range based on my lastVal thingy. I do recognize that other workarounds are possible and I will try another way in the method you cited for getting the reduced range.
As off the data set you presented, it works perfectly for me:

Quote:

Please enter 10 numbers.2
2
2
2
2
2
2
2
2
1
2 1
The number of steps: 1.
The new array length is 2.

Process returned 0 (0x0) execution time : 5.382 s
Press any key to continue.
12-22-2012
laserlight

Quote:

Originally Posted by Debojyoti Das

Just to do replace the garbage values I guess.

But all that you are doing is replacing the garbage values with other garbage values.

Quote:

Originally Posted by Debojyoti Das

And in my version of the code I get the reduced range based on my lastVal thingy.

That is only because you did not recognise that j + 1 is your reduced range's length.

Quote:

Originally Posted by Debojyoti Das

As off the data set you presented, it works perfectly for me:

Print the entire new array, including the garbage values. If you didn't know the reduced range's length, how can you tell that the 2s that come after the 1 are garbage? But since you know the reduced range's length, what does it matter what those values are?
12-22-2012
Debojyoti Das

Quote:

Originally Posted by laserlight

But all that you are doing is replacing the garbage values with other garbage values.

That is only because you did not recognise that j + 1 is your reduced range's length.

Print the entire new array, including the garbage values. If you didn't know the reduced range's length, how can you tell that the 2s that come after the 1 are garbage? But since you know the reduced range's length, what does it matter what those values are?

Whoa..now I recognize it. Thanks for the take :) .
12-22-2012
laserlight

You're welcome :)

Now, as you figure out a simpler in-place algorithm, I'd like to return to the idea that functions should do one thing and do it well. For example, this was the program I wrote to test:

Code:

#include <stdio.h> size_t read_numbers(int numbers[], int max_size) { size_t i = 0; printf("Please enter up to %d integers (trigger EOF to stop early).\n", max_size); while (i < max_size && scanf("%d", &numbers[i]) == 1) { ++i; } return i; } void print_numbers(const int numbers[], size_t size) { size_t i; printf(">>> "); for (i = 0; i < size; ++i) { printf("%d ", numbers[i]); } printf("<<<\n"); } size_t compact(int numbers[], size_t size) { size_t i, j; if (size <= 1) { return size; } /* omitted for instructional purposes */ } int main(void) { int numbers[10]; size_t size = read_numbers(numbers, sizeof(numbers) / sizeof(numbers[0])); size = compact(numbers, size); print_numbers(numbers, size); return 0; }
12-22-2012
R.Stiltskin

Still working on this, I see. I was hoping that by the time you finished implementing the step-counting you would have realized how simply (and efficiently) you could complete the assignment with only a minor modification to your original program. Does this give you a hint?
12-22-2012
Debojyoti Das

Quote:

Originally Posted by R.Stiltskin

Still working on this, I see. I was hoping that by the time you finished implementing the step-counting you would have realized how simply (and efficiently) you could complete the assignment with only a minor modification to your original program. Does this give you a hint?

Code:

#include <stdio.h>#include <stdlib.h> #define MAXVALUE 10 int compact (int[], int); int main() { int arrSeries[MAXVALUE], i=0, newArrayLength; int arrLength = MAXVALUE; printf("Please enter %d numbers.\n", MAXVALUE); while(i != MAXVALUE) { scanf("%d", &arrSeries[i]); i++; } newArrayLength=compact(arrSeries, arrLength); printf("The new array length is %d.\n", newArrayLength); getchar(); return 0; } int compact(int arrSeries[], int arrLength) { int i=0, j= 0, counter=0, newArray[MAXVALUE]; newArray[0]=arrSeries[0]; for(i = 0; i != arrLength; i++) { if(newArray[j] != arrSeries[i]) { newArray[++j] = arrSeries[i]; } } j++; while(counter < j) { printf("%d ", newArray[counter]); counter++; } printf("\nThe number of steps: %d.\n", j); return j; }

Isn't this the solution you intended? Or is there an even more elegant method other than in place compacting ?
Thanks.
12-22-2012
laserlight

Since you have newArray, that is not in-place. But as I said, it looks like you're close. Remove newArray. How would you adjust your algorithm to work with just arrSeries?
12-22-2012
iMalc

I showed how to solve this kind of problem efficiently in a recent thread. Basicaly you use destination and source "iterators", copying from one to the other (even though they may initially point to the same item), and only advancing the source iterator in some cases.

Your case is slightly different here. The above should just give you the idea, and you'll still have to work out the exact the details yourself.
12-22-2012
laserlight

In the current code attempts, the "iterators" are basically the indices. The idea is already there and implemented, just that it isn't yet in-place :)
12-22-2012
iMalc

Oh so it is.
12-22-2012
Debojyoti Das

Quote:

Originally Posted by laserlight

Code:

(i < max_size && scanf("%d", &numbers[i]) == 1)

Sorry for my so less experience in coding, but I have never seen a while loop number reading like this. Can you please explain the logic so that I can implement loops like this myself? The implementation seems very elegant to me. I know that a while(1) loop is an infinite loop, but I don't' get the ==1 testing part.
Thanks !.
12-23-2012
laserlight

Basically, the idea is to keep reading integers until the max_size is reached, or there are no more integers left to read. Read up on scanf to understand its return value.
12-24-2012
Debojyoti Das

Quote:

Originally Posted by laserlight

Basically, the idea is to keep reading integers until the max_size is reached, or there are no more integers left to read. Read up on scanf to understand its return value.

Sorry for being late, here's the solution that I did, don't know how efficient it is...

Code:

#include <stdio.h>#include <stdlib.h> size_t read_numbers(int numbers[], int max_size) { size_t i = 0; printf("Please enter up to %d integers (trigger EOF to stop early).\n", max_size); while (i < max_size && scanf("%d", &numbers[i]) == 1) { ++i; } return i; } void print_numbers(const int numbers[], size_t size) { size_t i; printf(">>> "); for (i = 0; i < size; ++i) { printf("%d ", numbers[i]); } printf("<<<\n"); } size_t compact(int numbers[], size_t size) { size_t i, j=0, k=0; if (size <= 1) { return size; } else { for(i=(size-1); i>0; i--) { if(numbers[i-1]==numbers[i]) { k=i; while(k!=size) { numbers[k-1]=numbers[k]; k++; } j++; } } size=size-j; return (size); } } int main(void) { int numbers[10]; size_t size = read_numbers(numbers, sizeof(numbers) / sizeof(numbers[0])); size = compact(numbers, size); print_numbers(numbers, size); system("pause"); return 0; }
12-24-2012
R.Stiltskin

In the worst case, it's still O(n²).

You would do better to go back to your compact function in post #61 and make it in-place by simplifying it, rather than by complicating it. Essentially all you have to do is eliminate counter and newArray.
12-24-2012
Debojyoti Das

Quote:

Originally Posted by R.Stiltskin

In the worst case, it's still O(n²).

You would do better to go back to your compact function in post #61 and make it in-place by simplifying it, rather than by complicating it. Essentially all you have to do is eliminate counter and newArray.

Will try to do the same.

All times are GMT -6. The time now is 08:20 PM.