Tough Problem [C and C++]

[stevanity]

Hi Guyz,
Here is a really tough problem to solve. Anyone can help out?

You need to encode and decode a message in a parallelogram matrix.
Eg. If input message is, "This is a problem" then you must put it inside a odd order matrix whose order is determined by the size of the message.
Then u to encode it, u must read the message in a spiral path starting from center cell. All empty spaces if any, in the matrix are filled with "/" which will not be present in the message.
Each Cell Contains 2 charachters
For the above statement the matrix is as follows,
[img]http://i55.tinypic.com/25icg79.jpg[/img]

The input and output are:

[img]http://i53.tinypic.com/2a6v1qu.jpg[/img]

[elsiekins]

So is this homework? have you written any code?

[stevanity]

So is this homework? have you written any code?

Not actually a homework
I got these questions from a teacher. They are something like brain tests. Something like practice problems for the GATE and other Campus interview tests.
I tried to solve it, but couldnt even find a proper solution to write the code.

Im not requesting the code. I need an idea or a solution to solve this problem
Thats all.

[csurfer]

Its quite straight forward right ?
Assuming int n = strlen( <Message> );

Then the order of the matrix say ord should be the smallest integer i which satisfies the equation

i*i*2 >= n ( where i is the smallest integer which satisfies this equation )

Now for any square matrix of odd order you can device an algorithm by which you can traverse the matrix in the cyclic order from middle with the matrix being implemented as an arr[2] if you want.

[stevanity]

Thats wat.
I have found out a way to compute the matrix order and store string int it.
Ive tried so hard to find out an algorithm to traverse the matrix. But its so confusing.

Please can anyone provide the algorithm only .

EDIT:
After Much Research and editing of other codes, ive found a code to traverse spirally in the matrix of order N*N.

void printSpiral(int ** arr, int N){
    for(int i=0, j = N– 1 ;  j >= 0 ;  i++, j--){
        for(int k = i ; k < j; k++){ cout << arr[i][k] << " "; } /* Printing forward */
        for(int k = i ; k < j; k++){ cout << arr[k][j] << " "; } /* Printing Downward */
        for(int k = j ; k > i; k--){ cout << arr[j][k] << " "; } /* Printing Backward */
        for(int k = j ; k > i; k--){ cout << arr[k][i] << " "; } /* Printing Upward */
    }
}

But the problem is this code traverses the matrix from element [0][0] and then goes on a spiral path. But i want to display the matrix in reverse spiral path. (i.e) from the centre cell and ending in last row's first cell.

[csurfer]

@Stevanity :
Nothing comes on a platter. do you really think you had to look at others codes for the above code snippet you have posted ? You could spend some time how you want to move in the array and yourself write the code.
Now after having the above code you want to know how to traverse the opposite way the above code is traversing(i,e from center to outside).

Logically something must be getting interchanged in the above code(if its correct) right ? Can't you put in some elbow grease in working it out ?

[stevanity]

hey im trying man
Ive been doing the same man.
Still I cant figure out.
Coz i think there is no logical relation between the two paths. Ive been trying to solve the problem for a week now. only after that Ive asked for help

[Fbody]

Start by finding the center of the matrix, then expand your algorithm from there. If you have an N x N matrix, where is the center?

[stevanity]

My matrix's order would be odd
SO the centre would precisely be the cell with index [N/2][N/2]

But how do i spiral out. It seems impossible to modify the above code.

[csurfer]

In a 3X3 matrix from the centre the flow is
1L,1U,2R,2D,2L
for 5X5 it is
1L,1U,2R,2D,3L,3U,4R,4D,4L

But in general it is always of the form:

1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,........
L,U,R,D,L,U,R,D,............................
where numbers represent the times you need to move and L=left,U=Up,R=Right,D=Down
moving left is decrementing j right is incrementing j
moving up is decrementing i down is incrementing i

Just make the computer do this... and you are done.

[stevanity]

Thanks man
Exactly wat im looking for
i think i can pick up from this.
But when to stop?

[nbaztec]

After n*n iterations, duh. (n is order). This is when you've read all the elements in the matrix.

[stevanity]

This is tough man.
I cant get the iterations right.

[Fbody]

You'll most likely have to keep track of your previous row and column values to generate the spiral. Then, if you follow the sequence csurfer cave you, you will always start at matrix[N/2][N/2] and end at matrix[N][0].

[stevanity]

Thanks for all the Help Guyz
The tip about the number of UP and DOWN and RIGHT and LEFT movements in each step opened my eye.

Ive completed the coding
Here it is

#include <iostream.h>
#include <string.h>
#include <conio.h>
#include <cstdlib>

class string
{
    public:
        char a,b;
};


int main()
{
    char str_src[100],str_dest[150],string_temp[150],*choice;
    string str_mat[9][9];
    int i,order,j,k,m,c,len;
    fflush(stdin);
    gets(choice);

    if(strcmp(choice,"ENCODE")==0)
    {
            fflush(stdin);
            cin.getline(str_src,100);

            len=strlen(str_src);

            order=1;
            while(order*order<(len+1)/2)
                order+=2;
            for(i=len;i<order*order*2;i++)
                str_src[i]='/';
            str_src[i]=0;
            k=0;
            for(i=0;i<order;i++)
                for(j=0;j<order;j++)
                {
                    str_mat[i][j].a=str_src[k];
                    str_mat[i][j].b=str_src[k+1];
                    k+=2;
                }

          str_dest[0]=str_mat[order/2][order/2].a;
          str_dest[1]=str_mat[order/2][order/2].b;

          i=order/2;
          m;
          j=order/2;
          k=2;
          c=1;
          while(c<order)
          {
              for(m=1;m<=c;m++)
              {
                  j--;
                  str_dest[k]=str_mat[i][j].a;
                  str_dest[k+1]=str_mat[i][j].b;
                  k+=2;
              }
              for(m=1;m<=c;m++)
              {
                  i--;
                  str_dest[k]=str_mat[i][j].a;
                  str_dest[k+1]=str_mat[i][j].b;
                  k+=2;
              }
              c++;
              for(m=1;m<=c;m++)
              {
                  j++;
                  str_dest[k]=str_mat[i][j].a;
                  str_dest[k+1]=str_mat[i][j].b;
                  k+=2;
              }
              for(m=1;m<=c;m++)
              {
                  i++;
                  str_dest[k]=str_mat[i][j].a;
                  str_dest[k+1]=str_mat[i][j].b;
                  k+=2;
              }
              c++;
          }
          for(m=1;m<order;m++)
          {
            j--;
            str_dest[k]=str_mat[i][j].a;
            str_dest[k+1]=str_mat[i][j].b;
            k+=2;
          }
          str_dest[order*order*2]=0;
          cout<<endl<<str_dest;
    }
    else if(strcmp(choice,"DECODE")==0)
    {
        fflush(stdin);
        cin.getline(str_dest,150);
        //strcpy(str_dest,string_temp);
        len=strlen(str_dest);
        order=1;
        while((order*order)<len/2)
            order+=2;
        str_mat[order/2][order/2].a=str_dest[0];
        str_mat[order/2][order/2].b=str_dest[1];
        i=order/2;
          m;
          j=order/2;
          k=2;
          c=1;
          while(c<order)
          {
              for(m=1;m<=c;m++)
              {
                  j--;
                  str_mat[i][j].a=str_dest[k];
                  str_mat[i][j].b=str_dest[k+1];
                  k+=2;
              }
              for(m=1;m<=c;m++)
              {
                  i--;
                  str_mat[i][j].a=str_dest[k];
                  str_mat[i][j].b=str_dest[k+1];
                  k+=2;
              }
              c++;
              for(m=1;m<=c;m++)
              {
                  j++;
                  str_mat[i][j].a=str_dest[k];
                  str_mat[i][j].b=str_dest[k+1];
                  k+=2;
              }
              for(m=1;m<=c;m++)
              {
                  i++;
                  str_mat[i][j].a=str_dest[k];
                  str_mat[i][j].b=str_dest[k+1];
                  k+=2;
              }
              c++;
          }
          for(m=1;m<order;m++)
          {
            j--;
            str_mat[i][j].a=str_dest[k];
            str_mat[i][j].b=str_dest[k+1];
            k+=2;
          }
          k=0;
          for(i=0;i<order;i++)
                for(j=0;j<order;j++)
                {
                    if(str_mat[i][j].a!='/')
                    {
                        str_src[k]=str_mat[i][j].a;
                        k++;
                    }
                    if(str_mat[i][j].b!='/')
                    {
                            str_src[k]=str_mat[i][j].b;
                            k++;
                    }
                }

            str_src[k]=0;
            cout<<endl<<str_src;


    }



  getch();
  return 0;

}

INPUT FORMAT:
First the program accepts either "ENCODE" or "DECODE"
Then the message to encode or decode.

Eg.
Output:

if input is

ENCODE
this is a problem

OUTPUT:

a s this iprm/leob

and if input is

DECODE
a s this iprm/leob

then out put will be

this is a problem

THANKS AGAIN

Hope this might help some one else too.

[csurfer]

@stevanity : A word of advice , give the algorithm if you want but not the entire code as you did in the post above. Due to this someone may just copy it out and never learn the way you learnt. To a student learning is more important than getting the job done :)

[stevanity]

can anyone cut the code out for me
Im not able to edit it