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.

Edited 6 Years Ago by Adak: n/a

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

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 ..

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

Add:

#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++) {
  //your main loop
  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.

Edited 6 Years Ago by Adak: n/a

Comments
gr8 guy !!
This question has already been answered. Start a new discussion instead.