home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Guide / c-cplusplus-interactive-guide.iso / c_ref / csource4 / 244_01 / two41.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-10-26  |  6.6 KB  |  253 lines
  1.  
  2. /* program to analyze the de Bruijn diagram of a cellular */
  3. /* automaton and report all the periodic states. */
  4. /* version for totalistic (4,1), second generation */
  5. /* [Harold V. McIntosh, 4 May 1987] */
  6. /* [10 May 1987 - wait after typing 24 lines] */
  7.  
  8. # include <stdio.h>
  9.  
  10. # define MC     9                /* maximum number of columns */
  11. # define NS     10                /* number of distinct sums */
  12. # define NW    24                /* pause after so many lines */
  13.  
  14. char arry[4][4][4][4][4];            /* all states in the diagram */
  15. int  rule[NS] = 0,1,0,0,1,2,1,2,3,3;        /* transitions by sum value */    
  16. int  nc, nl;                    /* #columns, # lines for print */
  17.  
  18. main() {
  19. int i;
  20.  
  21. printf("Rule number:\n\n");
  22. printf("0..1..2..3\n");
  23. for (i=0; i<NS; i++) rule[i]=getchar()-'0';
  24. nc=0;
  25. nl=0;
  26.  
  27. kwait(0); printf("Strings conforming to (2,0):"); kwait(0);
  28. pass1a();
  29. pass2i();
  30. pass2o();
  31. pass4();
  32.  
  33. kwait(0); printf("Strings conforming to (2,1):"); kwait(0);
  34. pass1b();
  35. pass2i();
  36. pass2o();
  37. pass4();
  38.  
  39. kwait(0); printf("Strings conforming to (2,2):"); kwait(0);
  40. pass1c();
  41. pass2i();
  42. pass2o();
  43. pass4();
  44.         
  45. } /* end of main */
  46.  
  47. pass1a() {int i0, i1, i2, i3, i4, i, j, k;    /* mark sequences conforming to (2,0) */
  48. printf(" Pass1a\015");
  49. for (i0=0; i0<4; i0++) {
  50. for (i1=0; i1<4; i1++) {
  51. for (i2=0; i2<4; i2++) {
  52. for (i3=0; i3<4; i3++) {
  53. for (i4=0; i4<4; i4++) {
  54. i=rule[i0+i1+i2];
  55. j=rule[i1+i2+i3];
  56. k=rule[i2+i3+i4];
  57. arry[i0][i1][i2][i3][i4]=rule[i+j+k]==i2?'Y':'N';
  58. };};};};};
  59. }
  60.  
  61. pass1b() {int i0, i1, i2, i3, i4, i, j, k;    /* mark sequences conforming to (2,1) */
  62. printf(" Pass1b\015");
  63. for (i0=0; i0<4; i0++) {
  64. for (i1=0; i1<4; i1++) {
  65. for (i2=0; i2<4; i2++) {
  66. for (i3=0; i3<4; i3++) {
  67. for (i4=0; i4<4; i4++) {
  68. i=rule[i0+i1+i2];
  69. j=rule[i1+i2+i3];
  70. k=rule[i2+i3+i4];
  71. arry[i0][i1][i2][i3][i4]=rule[i+j+k]==i1?'Y':'N';
  72. };};};};};
  73. }
  74.  
  75. pass1c() {int i0, i1, i2, i3, i4, i, j, k;    /* mark sequences conforming to (2,2) */
  76. printf(" Pass1c\015");
  77. for (i0=0; i0<4; i0++) {
  78. for (i1=0; i1<4; i1++) {
  79. for (i2=0; i2<4; i2++) {
  80. for (i3=0; i3<4; i3++) {
  81. for (i4=0; i4<4; i4++) {
  82. i=rule[i0+i1+i2];
  83. j=rule[i1+i2+i3];
  84. k=rule[i2+i3+i4];
  85. arry[i0][i1][i2][i3][i4]=rule[i+j+k]==i0?'Y':'N';
  86. };};};};};
  87. }
  88.  
  89. /* Pass2i flags links which have an incoming arrow */
  90. pass2i() {int i0, i1, i2, i3, i4, m;
  91. printf(" Pass2i\015");
  92. do {
  93. for (i0=0; i0<4; i0++) {
  94. for (i1=0; i1<4; i1++) {
  95. for (i2=0; i2<4; i2++) {
  96. for (i3=0; i3<4; i3++) {
  97. for (i4=0; i4<4; i4++) {
  98. if ((arry[i0][i1][i2][i3][i4]&0x5F)=='Y')
  99.  {for (m=0; m<4; m++) arry[i1][i2][i3][i4][m]|=0x20;};
  100. };};};};};
  101. } while (pass3()!=0); }
  102.  
  103. /* Pass2o flags links which have an outgoing arrow */
  104. pass2o() {int i0, i1, i2, i3, i4, m;
  105. do {
  106. printf(" Pass2o\015");
  107. for (i0=0; i0<4; i0++) {
  108. for (i1=0; i1<4; i1++) {
  109. for (i2=0; i2<4; i2++) {
  110. for (i3=0; i3<4; i3++) {
  111. for (i4=0; i4<4; i4++) {
  112. if ((arry[i0][i1][i2][i3][i4]&0x5F)=='Y')
  113.  {for (m=0; m<4; m++) arry[m][i0][i1][i2][i3]|=0x20;};
  114. };};};};};
  115. } while (pass3()!=0); }
  116.  
  117. /* printf("pass3 - erase flags, mark survivors, count channges\n"); */
  118. int pass3() {int i0, i1, i2, i3, i4, l;    /* mark states still linked */
  119. printf(" Pass3\015");
  120. l=0;
  121. for (i0=0; i0<4; i0++) {
  122. for (i1=0; i1<4; i1++) {
  123. for (i2=0; i2<4; i2++) {
  124. for (i3=0; i3<4; i3++) {
  125. for (i4=0; i4<4; i4++) {
  126. switch (arry[i0][i1][i2][i3][i4]) {
  127.     case 'y': arry[i0][i1][i2][i3][i4]='Y'; break;
  128.     case 'Y': arry[i0][i1][i2][i3][i4]='N'; l=1; break;
  129.     case 'n': case 'N': arry[i0][i1][i2][i3][i4]='N'; break;
  130.     default: break; };
  131. };};};};};
  132. return l;
  133. }
  134.  
  135. /* pass4 - print loops which remain */
  136. pass4() {
  137. int i0, i1, i2, i3, i4;
  138. int j0, j1, j2, j3, j4, k, l, m;
  139. printf(" pass4 \015");
  140. for (i0=0; i0<4; i0++) {
  141. for (i1=0; i1<4; i1++) {
  142. for (i2=0; i2<4; i2++) {
  143. for (i3=0; i3<4; i3++) {
  144. for (i4=0; i4<4; i4++) {
  145. j1=i1; j2=i2; j3=i3; j4=i4; l=0; m=0;
  146. do {
  147.         if (arry[0][j1][j2][j3][j4]=='Y')
  148.     {arry[0][j1][j2][j3][j4]='y';
  149.     k=j4; j4=j3; j3=j2; j2=j1; j1=0; m=1;}
  150.   else {if (arry[1][j1][j2][j3][j4]=='Y')
  151.     {arry[1][j1][j2][j3][j4]='y';
  152.     k=j4; j4=j3; j3=j2; j2=j1; j1=1; m=1;}
  153.   else {if (arry[2][j1][j2][j3][j4]=='Y')
  154.     {arry[2][j1][j2][j3][j4]='y';
  155.     k=j4; j4=j3; j3=j2; j2=j1; j1=2; m=1;}
  156.   else {if (arry[3][j1][j2][j3][j4]=='Y')
  157.     {arry[3][j1][j2][j3][j4]='y';
  158.     k=j4; j4=j3; j3=j2; j2=j1; j1=3; m=1;}
  159.   else {l=1; if (m==1) {j0=j1; j1=j2; j2=j3; j3=j4; j4=k;}; };};};};
  160.   } while (l==0);
  161. l=0; 
  162. m=0;
  163. do {
  164.         if (arry[j0][j1][j2][j3][0]=='y')
  165.    {prf(j0,j1,j2,j3,0);
  166.    arry[j0][j1][j2][j3][0]='N';
  167.    j0=j1; j1=j2; j2=j3; j3=0; m=1;}
  168.   else {if (arry[j0][j1][j2][j3][1]=='y')
  169.    {prf(j0,j1,j2,j3,1);
  170.    arry[j0][j1][j2][j3][1]='N';
  171.    j0=j1; j1=j2; j2=j3; j3=1; m=1;}
  172.   else {if (arry[j0][j1][j2][j3][2]=='y')
  173.    {prf(j0,j1,j2,j3,2);
  174.    arry[j0][j1][j2][j3][2]='N';
  175.    j0=j1; j1=j2; j2=j3; j3=2; m=1;}
  176.   else {if (arry[j0][j1][j2][j3][3]=='y')
  177.    {prf(j0,j1,j2,j3,3);
  178.    arry[j0][j1][j2][j3][3]='N';
  179.    j0=j1; j1=j2; j2=j3; j3=3; m=1;}
  180.   else {l=1;};};};};
  181.   } while (l==0);
  182. l=0;
  183. do {
  184.         if (arry[j0][j1][j2][j3][0]=='Y')
  185.    {prf(j0,j1,j2,j3,0);
  186.    arry[j0][j1][j2][j3][0]='N';
  187.    j0=j1; j1=j2; j2=j3; j3=0; m=1;}
  188.   else {if (arry[j0][j1][j2][j3][1]=='Y')
  189.    {prf(j0,j1,j2,j3,1);
  190.    arry[j0][j1][j2][j3][1]='N';
  191.    j0=j1; j1=j2; j2=j3; j3=1; m=1;}
  192.   else {if (arry[j0][j1][j2][j3][2]=='Y')
  193.    {prf(j0,j1,j2,j3,2);
  194.    arry[j0][j1][j2][j3][2]='N';
  195.    j0=j1; j1=j2; j2=j3; j3=2; m=1;}
  196.   else {if (arry[j0][j1][j2][j3][3]=='Y')
  197.    {prf(j0,j1,j2,j3,3);
  198.    arry[j0][j1][j2][j3][3]='N';
  199.    j0=j1; j1=j2; j2=j3; j3=3; m=1;}
  200.   else {l=1; if (m==1) {kwait(0);} ;} ;};};};
  201.   } while (l==0);
  202. };};};};};
  203. }
  204.  
  205. /* print one of the links in a chain */
  206. prf(i0,i1,i2,i3,i4) int i0, i1,i2, i3, i4; {
  207. kwait(1);
  208. printf("%1d",i0);
  209. printf("%1d",i1);
  210. printf("%1d",i2);
  211. printf("%1d",i3);
  212. printf("-");
  213. printf("%1d",i4);
  214. printf("  ");}
  215.  
  216. /* print the whole list of links */
  217. pall() {
  218. int i0, i1, i2, i3, i4;
  219. for (i0=0; i0<4; i0++) {
  220. for (i1=0; i1<4; i1++) {
  221. for (i2=0; i2<4; i2++) {
  222. for (i3=0; i3<4; i3++) {
  223. for (i4=0; i4<4; i4++) {
  224. printf("%c",arry[i0][i1][i2][i3][i4]);
  225. };};};};};
  226. printf("\n");
  227. }
  228.  
  229. /* keyboard status */
  230. kbdst() {return bdos(11)&0xFF;}
  231.  
  232. /* direct keyboard input, no echo */
  233. kbdin() {int c;
  234. if ((c=bdos(7)&0xFF)=='\0') c=(bdos(7)&0xFF)|0x80;
  235. return c;}
  236.  
  237. /* pause at the end of a full screen */
  238. kwait(i) int i; {
  239. switch (i) {
  240.   case 0: printf("\n"); nc=0; nl++; break;
  241.   case 1: if (nc==MC) {printf("&\n"); nc=1; nl++;} else nc++; break;
  242.   default: break;};
  243. if (nl==NW) {
  244.   nl=0;
  245.   printf(" press any key to continue\015");
  246.   while (kbdst()) {};
  247.   kbdin();
  248.   printf("-                         \n");
  249.   };
  250. }
  251.  
  252. /* end */
  253.