home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_200 / 246_01 / cycle32.c < prev    next >
Text File  |  1987-10-28  |  4KB  |  196 lines
  1.  
  2.  
  3. /* CYCLE32.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     11            /* 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][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.  
  32. printf("Cycles of length 4"); kwait(0);
  33.  mc=7;
  34.  cy=4;
  35.  cp=81;
  36.  pass1();
  37.  pass2();
  38.  pass4();
  39.  
  40. printf("Cycles of length 5"); kwait(0);
  41.  mc=6;
  42.  cy=5;
  43.  cp=243;
  44.  pass1();
  45.  pass2();
  46.  pass4();
  47.  
  48. printf("Cycles of length 6"); kwait(0);
  49.  mc=5;
  50.  cy=6;
  51.  cp=729;
  52.  pass1();
  53.  pass2();
  54.  pass4();
  55.  
  56. printf("Cycles of length 7"); kwait(0);
  57.  mc=4;
  58.  cy=7;
  59.  cp=2187;
  60.  pass1();
  61.  pass2();
  62.  pass4();
  63.  
  64. printf("Cycles of length 8"); kwait(0);
  65.  mc=4;
  66.  cy=8;
  67.  cp=6561;
  68.  pass1();
  69.  pass2();
  70.  pass4();
  71.  
  72. printf("Cycles of length 9"); kwait(0);
  73.  mc=3;
  74.  cy=9;
  75.  cp=19683;
  76.  pass1();
  77.  pass2();
  78.  pass4();
  79.  
  80. } /* end main */
  81.  
  82. /* Pass 1 makes arry[i] equal to the successor of i */
  83.  
  84. pass1() {int i, j, x;
  85.   printf(" Pass1\015");
  86.   for (j=0; j<cp; j++) {
  87.     x=j; for (i=0; i<cy; i++) {arr1[cy-i-1]=x%KK; x/=KK;};
  88.     evolve(cy);
  89.     x=0; for (i=0; i<cy; i++) x=KK*x+arr2[i]; arry[j]=x;
  90.   }; }
  91.  
  92. /* calculate one generation of evolution in a ring of length n */
  93.  
  94. evolve(n) int n; {
  95. int i;
  96.   arr2[0]=binrule[arr1[n-2]][arr1[n-1]][arr1[0]][arr1[1]][arr1[2]];
  97.   arr2[1]=binrule[arr1[n-1]][arr1[0]][arr1[1]][arr1[2]][arr1[3]];
  98.   for (i=2; i<n-2; i++) arr2[i]=binrule[arr1[i-2]][arr1[i-1]][arr1[i]][arr1[i+1]][arr1[i+2]];
  99.   arr2[n-1]=binrule[arr1[n-3]][arr1[n-2]][arr1[n-1]][arr1[0]][arr1[1]];
  100.   arr2[n-2]=binrule[arr1[n-4]][arr1[n-3]][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, i3, i4;
  133. for (i0=0; i0<KK; i0++) {
  134. for (i1=0; i1<KK; i1++) {
  135. for (i2=0; i2<KK; i2++) {
  136. for (i3=0; i3<KK; i3++) {
  137. for (i4=0; i4<KK; i4++) {
  138. binrule[i0][i1][i2][i3][i4]=rule[i0+i1+i2+i3+i4];
  139. };};};};};
  140. }
  141.  
  142. /* print the link */
  143.  
  144. prf(j,x) int j, x; {int i, y;
  145.   kwait(1);
  146.   y=j; for (i=0; i<cy; i++) {arr1[i]=y%KK; y/=KK;};
  147.   for (i=0; i<cy; i++) printf("%1d",arr1[i]);
  148.   printf("-");
  149.   y=x; for (i=0; i<cy; i++) {arr1[i]=y%KK; y/=KK;};
  150.   for (i=0; i<cy; i++) printf("%1d",arr1[i]);
  151.   printf("  ");
  152. }
  153.  
  154. /* print arry - for diagnostic purposes */
  155. pall() {int j;
  156. for (j=0; j<cp; j++) printf("%4d",arry[j]);
  157. }
  158.  
  159. /* print cycle - for diagnostic purposes */
  160. pcy() {int j;
  161. for (j=0; j<cy; j++) printf("%1d",arr2[j]);
  162. }
  163.  
  164. /* limit j to interval (i,k) */
  165. int lim(i,j,k) int i, j, k;
  166.     {if (i>=j) return i; if (k<=j) return k; return j;}
  167.  
  168. /* keyboard status */
  169. kbdst() {return bdos(11)&0xFF;}
  170.  
  171. /* direct keyboard input, no echo */
  172. kbdin() {int c;
  173. if ((c=bdos(7)&0xFF)=='\0') c=(bdos(7)&0xFF)|0x80;
  174. videoputc(c,1);
  175. return c;}
  176.  
  177. /* pause at the end of a full screen */
  178. /* kwait(0) - <cr><lf> and count it  */
  179. /* kwait(1) - count columns          */
  180.  
  181. kwait(i) int i; {
  182. switch (i) {
  183.   case 0: printf("\n"); nc=0; nl++; break;
  184.   case 1: if (nc==mc) {printf("&\n"); nc=1; nl++;} else nc++; break;
  185.   default: break;};
  186. if (nl==NW) {
  187.   nl=0;
  188.   printf(" press any key to continue\015");
  189.   while (kbdst()) {};
  190.   kbdin();
  191.   printf("-                         \n");
  192.   };
  193. }
  194.  
  195. /* end */
  196.