home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_200 / 244_01 / one31.c < prev    next >
Text File  |  1987-10-26  |  6KB  |  219 lines
  1.  
  2. /* program to analyze the de Bruijn diagram of a cellular */
  3. /* automaton and report all the periodic states. */
  4. /* states with period 1 and displacements zero (1,0) or one (1,1) */
  5. /* are analyzed for a four-state, nearest neighbor (3,1) automaton */
  6. /* [Harold V. McIntosh, 4 May 1987] */
  7.  
  8. # include <stdio.h>
  9.  
  10. # define MC     9                /* maximum number of columns */
  11. # define NS      7                /* number of distinct sums */
  12. # define NW    24                /* pause after so many lines */
  13.  
  14. char arry[3][3][3];
  15. int  rule[NS];
  16. int  nc, nl;
  17.  
  18. main() {char c; int i;
  19.  
  20. printf("Rule number:\n\n");
  21. printf("0..1..2\n");
  22. for (i=0; i<NS; i++) rule[i]=getchar()-'0';
  23.  
  24. nc=0;
  25. nl=0;
  26.  
  27. do {
  28. printf("  a=still  b=glider  0,1,2=constant  q=quit\015");
  29. c=kbdin();
  30. switch (c) {
  31. case 'a':
  32. printf("Sequences satisfying the condition (1,0):       "); kwait(0);
  33. pass1a(); pass2i(); pass2o(); pass4(); break;
  34. case 'b':
  35. printf("Sequences satisfying the condition (1,1):       "); kwait(0);
  36. pass1b(); pass2i(); pass2o(); pass4(); break;
  37. case '0':
  38. printf("Sequences mapping into a constant string of 0's:"); kwait(0);
  39. pass1x(0); pass2i(); pass2o(); pass4(); break;
  40. case '1':
  41. printf("Sequences mapping into a constant string of 1's:"); kwait(0);
  42. pass1x(1); pass2i(); pass2o(); pass4(); break;
  43. case '2':
  44. printf("Sequences mapping into a constant string of 2's:"); kwait(0);
  45. pass1x(2); pass2i(); pass2o(); pass4(); break;
  46. default: break; };
  47.  } while (c!='q');
  48.  
  49. } /* end main */
  50.  
  51. /* Pass 1a marks all the configurations which fulfil (1,0) */
  52. pass1a() {int i,j,k;
  53.   printf(" Pass1a\015");
  54.   for (i=0; i<3; i++) {
  55.   for (j=0; j<3; j++) {
  56.   for (k=0; k<3; k++) {
  57.   arry[i][j][k]=rule[i+j+k]==j?'Y':'N';
  58.   };};}; }
  59.  
  60. /* Pass 1b marks all the configurations which fulfil (1,1) */
  61. pass1b() {int i,j,k;
  62.   printf(" Pass1b\015");
  63.   for (i=0; i<3; i++) {
  64.   for (j=0; j<3; j++) {
  65.   for (k=0; k<3; k++) {
  66.   arry[i][j][k]=rule[i+j+k]==i?'Y':'N';
  67.   };};}; }
  68.  
  69. /* Pass 1x marks all the configurations mapping into a constant */
  70. pass1x(c) int c; {int i,j,k;
  71.   printf(" Pass1a\015");
  72.   for (i=0; i<3; i++) {
  73.   for (j=0; j<3; j++) {
  74.   for (k=0; k<3; k++) {
  75.   arry[i][j][k]=rule[i+j+k]==c?'Y':'N';
  76.   };};}; }
  77.  
  78. /* Pass 2i flags all links with an incoming arrow */
  79. /* Pass 2o flags all links with an outgoing arrow */
  80. /* Then pass 3 discards all unflagged links */
  81. /* Passes 2 and 3 alternate until no change is observed */
  82.  
  83. pass2i() {int i, j, k, m;
  84. do {
  85. printf(" Pass2i\015");
  86. for (i=0; i<3; i++) {
  87. for (j=0; j<3; j++) {
  88. for (k=0; k<3; k++) {
  89. if ((arry[i][j][k]&0x5F)=='Y') {for (m=0; m<3; m++) arry[j][k][m]|=0x20;};
  90. };};}; } while (pass3()!=0); }
  91.  
  92. pass2o() {int i, j, k, m;
  93. do {
  94. printf(" Pass2o\015");
  95. for (i=0; i<3; i++) {
  96. for (j=0; j<3; j++) {
  97. for (k=0; k<3; k++) {
  98. if ((arry[i][j][k]&0x5F)=='Y') {for (m=0; m<3; m++) arry[m][i][j]|=0x20;};
  99. };};} } while (pass3()!=0); }
  100.  
  101. /* Pass 3 - erase flags, mark survivors, count changes */
  102.  
  103. int pass3() {int i, j, k, l;
  104. l=0;
  105. printf(" Pass3\015");
  106. for (i=0; i<3; i++) {
  107. for (j=0; j<3; j++) {
  108. for (k=0; k<3; k++) {
  109.   switch (arry[i][j][k]) {
  110.     case 'y': arry[i][j][k]='Y'; break;
  111.     case 'Y': arry[i][j][k]='N'; l=1; break;
  112.     case 'n': case 'N': arry[i][j][k]='N'; break;
  113.     default: break; };
  114. };};};
  115. return l;
  116. }
  117.  
  118. /* pass4 - print loops which remain */
  119. pass4() {
  120. int i0, i1, i2;
  121. int j0, j1, j2, k, l, m;
  122. printf(" pass4 \015");
  123. for (i0=0; i0<3; i0++) {
  124. for (i1=0; i1<3; i1++) {
  125. for (i2=0; i2<3; i2++) {
  126. j1=i1; j2=i2;l=0; m=0;
  127. do {
  128.         if (arry[0][j1][j2]=='Y')
  129.     {arry[0][j1][j2]='y';
  130.     k=j2; j2=j1; j1=0; m=1;}
  131.   else {if (arry[1][j1][j2]=='Y')
  132.     {arry[1][j1][j2]='y';
  133.     k=j2; j2=j1; j1=1; m=1;}
  134.   else {if (arry[2][j1][j2]=='Y')
  135.     {arry[2][j1][j2]='y';
  136.     k=j2; j2=j1; j1=2; m=1;}
  137.   else {l=1; if (m==1) {j0=j1; j1=j2; j2=k;}; };};};
  138.   } while (l==0);
  139. l=0; 
  140. m=0;
  141. do {
  142.         if (arry[j0][j1][0]=='y')
  143.    {prf(j0,j1,0);
  144.    arry[j0][j1][0]='N';
  145.    j0=j1; j1=0; m=1;}
  146.   else {if (arry[j0][j1][1]=='y')
  147.    {prf(j0,j1,1);
  148.    arry[j0][j1][1]='N';
  149.    j0=j1; j1=1; m=1;}
  150.   else {if (arry[j0][j1][2]=='y')
  151.    {prf(j0,j1,2);
  152.    arry[j0][j1][2]='N';
  153.    j0=j1; j1=2; m=1;}
  154.   else {l=1;};};};
  155.   } while (l==0);
  156. l=0;
  157. do {
  158.         if (arry[j0][j1][0]=='Y')
  159.    {prf(j0,j1,0);
  160.    arry[j0][j1][0]='N';
  161.    j0=j1; j1=0; m=1;}
  162.   else {if (arry[j0][j1][1]=='Y')
  163.    {prf(j0,j1,1);
  164.    arry[j0][j1][1]='N';
  165.    j0=j1; j1=1; m=1;}
  166.   else {if (arry[j0][j1][2]=='Y')
  167.    {prf(j0,j1,2);
  168.    arry[j0][j1][2]='N';
  169.    j0=j1; j1=2; m=1;}
  170.   else {l=1; if (m==1) kwait(0);};};};
  171.   } while (l==0);
  172. };};};
  173. }
  174.  
  175. /* print one link of the de Bruijn diagram */
  176. prf(i,j,k) int i, j, k; {
  177. kwait(1);
  178. printf("%1d",i);
  179. printf("%1d",j);
  180. printf("-");
  181. printf("%1d",k);
  182. printf("  ");}
  183.  
  184. /* print the whole array */
  185. /* mostly for debugging */
  186. pall() {int i, j, k;
  187. for (i=0; i<3; i++) {
  188. for (j=0; j<3; j++) {
  189. for (k=0; k<3; k++) {
  190. printf("%c",arry[i][j][k]);
  191. };};};
  192. printf("\n");
  193. }
  194.  
  195. /* keyboard status */
  196. kbdst() {return bdos(11)&0xFF;}
  197.  
  198. /* direct keyboard input, no echo */
  199. kbdin() {int c;
  200. if ((c=bdos(7)&0xFF)=='\0') c=(bdos(7)&0xFF)|0x80;
  201. return c;}
  202.  
  203. /* pause at the end of a full screen */
  204. kwait(i) int i; {
  205. switch (i) {
  206.   case 0: printf("\n"); nc=0; nl++; break;
  207.   case 1: if (nc==MC) {printf("&\n"); nc=1; nl++;} else nc++; break;
  208.   default: break;};
  209. if (nl==NW) {
  210.   nl=0;
  211.   printf(" press any key to continue\015");
  212.   while (kbdst()) {};
  213.   kbdin();
  214.   printf("-                         \n");
  215.   };
  216. }
  217.  
  218. /* end */
  219.