home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Guide / c-cplusplus-interactive-guide.iso / c_ref / csource4 / 246_01 / cycle31.c < prev    next >
Text File  |  1987-10-29  |  4KB  |  194 lines

  1.  
  2.  
  3. /* CYCLE31.C                     */
  4. /* program to analyze the cycles of a cellular   */
  5. /* automaton and report all the periodic states. */
  6. /* [Harold V. McIntosh, 21 May 1987]         */
  7.  
  8. # include <stdio.h>
  9.  
  10. # define KK     3            /* number of states/cell    */
  11. # define NS      7            /* number of distinct sums    */
  12. # define NW    24            /* pause after so many lines    */
  13.  
  14. int  arr1[16], arr2[16];
  15. unsigned int arry[19683];
  16. int  binrule[KK][KK][KK], rule[NS];
  17. int  cy, cp, mc, nc, nl;
  18.  
  19. main() {
  20. int  i;
  21.  
  22. printf("Rule number:\n\n");
  23. printf("0..1..2\n");
  24. for (i=0; i<NS; i++) rule[i]=kbdin()-'0';
  25. printf("\n");
  26.  
  27. totobin();
  28.  
  29. nc=0;
  30. nl=0;
  31. /* cp=KK^cy; */
  32. /* cp=4^5; */
  33.  
  34. printf("Cycles of length 4"); kwait(0);
  35.  mc=7;
  36.  cy=4;
  37.  cp=81;
  38.  pass1();
  39.  pass2();
  40.  pass4();
  41.  
  42. printf("Cycles of length 5"); kwait(0);
  43.  mc=6;
  44.  cy=5;
  45.  cp=243;
  46.  pass1();
  47.  pass2();
  48.  pass4();
  49.  
  50. printf("Cycles of length 6"); kwait(0);
  51.  mc=5;
  52.  cy=6;
  53.  cp=729;
  54.  pass1();
  55.  pass2();
  56.  pass4();
  57.  
  58. printf("Cycles of length 7"); kwait(0);
  59.  mc=4;
  60.  cy=7;
  61.  cp=2187;
  62.  pass1();
  63.  pass2();
  64.  pass4();
  65.  
  66. printf("Cycles of length 8"); kwait(0);
  67.  mc=4;
  68.  cy=8;
  69.  cp=6561;
  70.  pass1();
  71.  pass2();
  72.  pass4();
  73.  
  74. printf("Cycles of length 9"); kwait(0);
  75.  mc=3;
  76.  cy=9;
  77.  cp=19683;
  78.  pass1();
  79.  pass2();
  80.  pass4();
  81.  
  82. } /* end main */
  83.  
  84. /* Pass 1 makes arry[i] equal to the successor of i */
  85.  
  86. pass1() {int i, j, x;
  87.   printf(" Pass1\015");
  88.   for (j=0; j<cp; j++) {
  89.     x=j; for (i=0; i<cy; i++) {arr1[cy-i-1]=x%KK; x/=KK;};
  90.     evolve(cy);
  91.     x=0; for (i=0; i<cy; i++) x=KK*x+arr2[i]; arry[j]=x;
  92.   }; }
  93.  
  94. /* calculate one generation of evolution in a ring of length n */
  95.  
  96. evolve(n) int n; {
  97. int i;
  98.   arr2[0]=binrule[arr1[n-1]][arr1[0]][arr1[1]];
  99.   for (i=1; i<n-1; i++) arr2[i]=binrule[arr1[i-1]][arr1[i]][arr1[i+1]];
  100.   arr2[n-1]=binrule[arr1[n-2]][arr1[n-1]][arr1[0]];
  101. }
  102.  
  103. /* Pass 2 flags all links with an incoming arrow */
  104.  
  105. pass2() {int j, m, x;
  106. printf(" Pass2\015");
  107. do {
  108. m=0;
  109. for (j=0; j<cp; j++) arry[j]|=0x8000;
  110. for (j=0; j<cp; j++) {x=arry[j];
  111.  if (x!=0xFFFF) arry[x&0x7FFF]&=0x7FFF;};
  112. for (j=0; j<cp; j++) {
  113.  if ((arry[j]>0x7FFF) && (arry[j]!=0xFFFF)) {arry[j]=0xFFFF; m=1;};};
  114.  } while (m!=0);
  115. }
  116.  
  117. /* pass4 - print loops which remain */
  118.  
  119. pass4() {
  120. int j, x, y, m;
  121. printf(" pass4 \015");
  122. for (j=0; j<cp; j++) {
  123.  x=j; y=arry[j]; arry[j]=0xFFFF; m=0;
  124.  while (y!=0xFFFF) {prf(x,y); x=y; y=arry[x]; arry[x]=0xFFFF; m=1;};
  125.  if (m==1) kwait(0);
  126.  };
  127. }
  128.  
  129. /* change totalistic rule to general rule */
  130.  
  131. totobin() {
  132. int i0, i1, i2;
  133. for (i0=0; i0<KK; i0++) {
  134. for (i1=0; i1<KK; i1++) {
  135. for (i2=0; i2<KK; i2++) {
  136. binrule[i0][i1][i2]=rule[i0+i1+i2];
  137. };};};
  138. }
  139.  
  140. /* print the link */
  141.  
  142. prf(j,x) int j, x; {int i, y;
  143.   kwait(1);
  144.   y=j; for (i=0; i<cy; i++) {arr1[i]=y%KK; y/=KK;};
  145.   for (i=0; i<cy; i++) printf("%1d",arr1[i]);
  146.   printf("-");
  147.   y=x; for (i=0; i<cy; i++) {arr1[i]=y%KK; y/=KK;};
  148.   for (i=0; i<cy; i++) printf("%1d",arr1[i]);
  149.   printf("  ");
  150. }
  151.  
  152. /* print arry - for diagnostic purposes */
  153. pall() {int j;
  154. for (j=0; j<cp; j++) printf("%4d",arry[j]);
  155. }
  156.  
  157. /* print cycle - for diagnostic purposes */
  158. pcy() {int j;
  159. for (j=0; j<cy; j++) printf("%1d",arr2[j]);
  160. }
  161.  
  162. /* limit j to interval (i,k) */
  163. int lim(i,j,k) int i, j, k;
  164.     {if (i>=j) return i; if (k<=j) return k; return j;}
  165.  
  166. /* keyboard status */
  167. kbdst() {return bdos(11)&0xFF;}
  168.  
  169. /* direct keyboard input, no echo */
  170. kbdin() {int c;
  171. if ((c=bdos(7)&0xFF)=='\0') c=(bdos(7)&0xFF)|0x80;
  172. videoputc(c,1);
  173. return c;}
  174.  
  175. /* pause at the end of a full screen */
  176. /* kwait(0) - <cr><lf> and count it  */
  177. /* kwait(1) - count columns          */
  178.  
  179. kwait(i) int i; {
  180. switch (i) {
  181.   case 0: printf("\n"); nc=0; nl++; break;
  182.   case 1: if (nc==mc) {printf("&\n"); nc=1; nl++;} else nc++; break;
  183.   default: break;};
  184. if (nl==NW) {
  185.   nl=0;
  186.   printf(" press any key to continue\015");
  187.   while (kbdst()) {};
  188.   kbdin();
  189.   printf("-                         \n");
  190.   };
  191. }
  192.  
  193. /* end */
  194.