Joey_Brown

Hello;

I would like to compress an 1D array of arbitrary number of elements. For instance if a user inputs
IN : 111122233331
OUT: 14233411
[it shrinks/increases the array and replaces all the identical consecutive elements with a number of how many times theyve appeared.]
This task must be accomplished without using a second backup array. So. I was thinking if I could do something like this :

``````for(j=i-1,k=(i*2)-1;j>=0;j--,k-=2)
{
i++;
arr[k-1]=arr[j];
arr[k]=0;
}``````

What this does is makes a space between the elements and marks it with zero. So my output after this point is:
IN : 11223331
OUT :1010202030303010
So my numbers are on j%2==0 indexes, and zero-flagged holes are on j%2!=0 indexes. Well now im stuck. I still need to count the numbers on even indexes and shrink the array. Any hints? Thank you very much guys :)

Be definition, you don't need code to add zeroes to the array - you are compressing it, not adding to it's length.

Think along these lines:

``````for i=0, j=0; i< SIZE of array;
assign a[j] to num1
set compress = 0
while j < SIZE
if a[j] == num1
++compress
if compress > 0
a[i+1] = compress
for(k=i to j)
mark each array element with a unique value (not zero)
(maybe INT_MIN?)
j+= compress
end for loop``````

ais where the compressed digit indicator goes. a[j] is where the next digit to be looked at, is located.

Joey_Brown

Thank you oh so much Adak. Youre great. Ill look into it right away and post back !

Joey_Brown

OK Ive done it like so :

``````for(j=k=0;j<=i;j++)
{
num=arr[k];

comp=0;

while(arr[j+1]==num)
comp++;

if(comp>0)
arr[++j]=comp;

k+=comp;

}``````

But it does not work. It freezes or it doesnt alter the array ..

Joey_Brown

Be definition, you don't need code to add zeroes to the array - you are compressing it, not adding to it's length.

Think along these lines:

``````for i=0, j=0; i< SIZE of array;
assign a[j] to num1
set compress = 0
while j < SIZE
if a[j] == num1
++compress
if compress > 0
a[i+1] = compress
for(k=i to j)
mark each array element with a unique value (not zero)
(maybe INT_MIN?)
j+= compress
end for loop``````

ais where the compressed digit indicator goes. a[j] is where the next digit to be looked at, is located.

No, doesnt work. It freezes out. This little bugger is tricky. So it semms that my zero flag algorithm is also unusable, since I cant get the counters straight. hmh

``#include <limits.h>``

Either use a

``#define SIZE 12``

macro, or get size this way:
size=sizeof(a)/sizeof(a[0];

You'll need that size of the array, I'll show you why.

This is NOT refined code - I believe this is best done recursively, but recursion
is hard to follow, without some experience with it.

``````for(i=0;i<size;i++) {
j=i+1;
n=a[i];
compress=0;
while(a[j]==n && j<size) {
compress++;
a[j] = INT_MIN;
++j;
}
/*if you have a compression here
increment i and set a[i] to compress+1
and you need to shuffle the digits, down
*/
//meet shuffle time ;)
for(j=i+1;j<size;j++) {
if(a[j] == INT_MIN) {  //found an element that needs to be overwritten
--size;              //reducing the effective size of the array by 1
for(k=j;k<size;k++) { //copying down the digits
a[k] = a[k+1];
}
--j;                  //yup, tinkering

//printf("\n Size = %d\n", size);
//for(m=0;m<size;m++)
//printf("a[%d]=%d ", m, a[m]);
}
}
}//end if

}//end for``````

Work with something along those lines, Joey.

commented: gr8 guy !! +1

Joey_Brown

OK I certainly will Adak. Thank u very much for the trouble !!:)