home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / unix / volume17 / contest-prog / part03 / prob18.c < prev    next >
C/C++ Source or Header  |  1989-02-06  |  5KB  |  186 lines
  1. /*
  2. Problem 18:Expanding square codes
  3.  
  4.    One method of encoding messages is known as the "expanding square
  5. code."  This method encodes messages by placing the characters of the 
  6. message to be encoded in an odd order(1,3,5,7,9) square matrix row by 
  7. row, and then retrieves them (decoding) in a clockwise expanding
  8. square spiral from the center of the matrix.  If the message is not
  9. exactly the right length to fill the matrix, the rest of the matrix
  10. is filled with asterisk characters (*).
  11.  
  12.    For example, the two square matrices below show the order in which
  13. the characters are placed in a matrix(order 5), and the order in which
  14. they are to be retrieved.  Notice that the order of retrieval begins
  15. at the center, then proceeds to the right, and then spirals
  16. clockwise.
  17.  
  18.       order in                       order out
  19.  
  20.       1   2   3   4   5               21  22  23  24  25
  21.       6   7   8   9  10               20   7   8   9  10
  22.      11  12  13  14  15               19   6   1   2  11
  23.      16  17  18  19  20               18   5   4   3  12
  24.      21  22  23  24  25               17  16  15  14  13
  25.  
  26.  Examples:
  27.  
  28.    encode:
  29.      message in:  "This is a test message!"
  30.  
  31.      message out: "stssees a  a**!egmtiThis "     
  32.  
  33.    decode:
  34.      message in:  "anreh is io *.enotshAnd t"
  35.  
  36.      message out: "And this is another one."
  37.  
  38.    Your program should be able to encode and to decode messages by 
  39. this method.  The input will consist of pairs of lines; the first 
  40. line in each pair will contain either the word   encode   or the word
  41. decode   in lower case characters.  The second line in each pair will
  42. consist of a message to be either encoded or decoded by the above 
  43. method, containing a maximum of 80 characters.  There will be no
  44. quotation marks (") surrounding the messages, and you should not
  45. output your messages with "'s.
  46.  
  47.    From the length of the message, you should determine the minimum
  48. odd order required for the matrix, and perform the specified operation.
  49. The output for each operation will consist of one blank line, the
  50. given message, and the resultant message.  Each message should be
  51. on a separate line. A decoded message may not contain the asterisk 
  52. characters used to fill the matrix in the encoding process.  You 
  53. may assume that no actual message contains an asterisk.
  54.  
  55.    Your program should continue reading input lines and performing
  56. operations until something other than the words   encode  or
  57. decode  is encountered.
  58.  
  59. Here is an actual run; the input file consisted of exactly four lines.
  60. The output file consists of exactly six lines; lines 1 and 4 are
  61. blank lines.
  62. This was the input file (the next four lines):
  63. encode
  64. now is the time for all
  65. decode
  66. imroft thee **lla  snow i
  67. Here was the output file (the next six lines, NOTICE the blank lines!):
  68.  
  69. now is the time for all
  70. imroft thee **lla  snow i
  71.  
  72. imroft thee **lla  snow i
  73. now is the time for all
  74. */
  75. #include <stdio.h>
  76. #include <kindex.c>
  77. #define newline '\n'
  78. #define null '\0'
  79. int E[]={0,1};
  80. int S[]={1,0};
  81. int W[]={0,-1};
  82. int N[]={-1,0};
  83. int *dir;
  84. int x,y;
  85. int size;
  86. #define SZ 55
  87. int a[SZ+3][SZ+3];
  88.  
  89. main(){
  90.     int len,d,n,i,k,j,jj;
  91.     char line[256];
  92.  
  93.     while( gets(line)==line){
  94.     if(kindex(line,"encode")==0)goto encode;
  95.     if(kindex(line,"decode")==0)goto decode;
  96.     exit(0);
  97.     encode:
  98.     putchar(newline);
  99.     gets(line);
  100.     puts(line);
  101.     for(i=0;i<=90;i++)if(line[i]==newline ||line[i]==null)break;
  102.     line[i]=null;
  103.     len=i;
  104.     for(size=1;;size++,size++)if(size*size>=len)break;
  105.     for(i=len;i<size*size;i++)line[i]='*';line[i]=null;
  106. for(i=1;i<=SZ;i++)for(k=1;k<=SZ;k++){a[i][k]= 0;}
  107. j=0;
  108. for(i=1;i<=size;i++)for(k=1;k<=size;k++){a[i][k]=line[j++];}
  109. /*
  110. for(i=1;i<=size;i++)
  111. {
  112.     for(k=1;k<=size;k++){
  113.             printf("%c",a[i][k]);
  114.     }
  115.     putchar(newline);}
  116.     */
  117.     x=y=(size+1)/2;
  118.     n=size*size;
  119.     dir=E;
  120.     printf("%c",a[x][y]);
  121.     for(k=1;k<=size;k++){
  122.         for(j=1;j<=k;j++){ 
  123.         d=godir();if(d>0)printf("%c",d); if(d<0)goto out;
  124.         }
  125.         nextdir();
  126.         for(j=1;j<=k;j++){
  127.         d=godir();if(d>0)printf("%c",d); if(d<0)goto out;
  128.         }
  129.         nextdir();
  130.     }
  131.     out:putchar(newline);
  132.     goto getnextline; 
  133.  
  134.     decode:
  135.     /*for(i=0;i<=SZ;i++)for(j=0;j<=SZ;j++)a[i][j]=1;*/
  136.     putchar(newline);
  137.     gets(line);
  138.     for(i=0;i<=90;i++)if(line[i]==newline ||line[i]==null)break;
  139.     line[i]=null;
  140.     puts(line);
  141.     len=i;
  142.     for(size=1;;size++,size++)if(size*size>=len)break;
  143.     for(i=len;i<size*size;i++)line[i]=' ';line[i]=null;
  144.     x=y=(size+1)/2;
  145.     n=size*size;
  146.     dir=E;
  147.     jj=0;
  148.     a[x][y]=line[jj++];
  149.     for(k=1;k<=size;k++){
  150.         for(j=1;j<=k;j++){ 
  151.         d=godir();a[x][y]=line[jj++]; if(jj>n)goto out1;
  152. /*        printf("x,y= %d %d\n",x,y);*/
  153.         }
  154.         nextdir();
  155.         for(j=1;j<=k;j++){
  156.         d=godir();a[x][y]=line[jj++]; if(jj>n)goto out1;
  157. /*        printf("x,y= %d %d\n",x,y);*/
  158.         }
  159.         nextdir();
  160.     }
  161.     out1:
  162.     jj=0;
  163.     for(i=1;i<=size;i++)for(j=1;j<=size;j++)line[jj++]=a[i][j];
  164.     for(i=0;i<100;i++)if(line[i]=='*')line[i]=null;
  165.     puts(line);
  166. getnextline: ;
  167. }
  168. }
  169. godir()
  170. {
  171.     x= x+ dir[0];
  172.     y= y+ dir[1];
  173.     if(y<1 || y>size)return -1;
  174.     if(x<1 || x>size)return -1;
  175.     return a[x][y];
  176.  
  177. }
  178. nextdir()
  179. {
  180.     if(dir==E){dir=S;return;}
  181.     if(dir==S){dir=W;return;}
  182.     if(dir==W){dir=N;return;}
  183.     if(dir==N){dir=E;return;}
  184.  
  185. }
  186.