home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_200 / 246_01 / cycle42.c < prev    next >
Text File  |  1987-10-28  |  4KB  |  182 lines
  1.  
  2.  
  3. /* CYCLE42.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     4            /* number of states/cell    */
  11. # define NS     16            /* number of distinct sums    */
  12. # define NW    24            /* pause after so many lines    */
  13.  
  14. int  arr1[16], arr2[16];
  15. unsigned int arry[16384];
  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....3\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=256;
  38.  pass1();
  39.  pass2();
  40.  pass4();
  41.  
  42. printf("Cycles of length 5"); kwait(0);
  43.  mc=6;
  44.  cy=5;
  45.  cp=1024;
  46.  pass1();
  47.  pass2();
  48.  pass4();
  49.  
  50. printf("Cycles of length 6"); kwait(0);
  51.  mc=5;
  52.  cy=6;
  53.  cp=4096;
  54.  pass1();
  55.  pass2();
  56.  pass4();
  57.  
  58. printf("Cycles of length 7"); kwait(0);
  59.  mc=4;
  60.  cy=7;
  61.  cp=16384;
  62.  pass1();
  63.  pass2();
  64.  pass4();
  65.  
  66. } /* end main */
  67.  
  68. /* Pass 1 makes arry[i] equal to the successor of i */
  69.  
  70. pass1() {int i, j, x;
  71.   printf(" Pass1\015");
  72.   for (j=0; j<cp; j++) {
  73.     x=j; for (i=0; i<cy; i++) {arr1[cy-i-1]=x%KK; x/=KK;};
  74.     evolve(cy);
  75.     x=0; for (i=0; i<cy; i++) x=KK*x+arr2[i]; arry[j]=x;
  76.   }; }
  77.  
  78. /* calculate one generation of evolution in a ring of length n */
  79.  
  80. evolve(n) int n; {
  81. int i;
  82.   arr2[0]=binrule[arr1[n-2]][arr1[n-1]][arr1[0]][arr1[1]][arr1[2]];
  83.   arr2[1]=binrule[arr1[n-1]][arr1[0]][arr1[1]][arr1[2]][arr1[3]];
  84.   for (i=2; i<n-2; i++) arr2[i]=binrule[arr1[i-2]][arr1[i-1]][arr1[i]][arr1[i+1]][arr1[i+2]];
  85.   arr2[n-1]=binrule[arr1[n-3]][arr1[n-2]][arr1[n-1]][arr1[0]][arr1[1]];
  86.   arr2[n-2]=binrule[arr1[n-4]][arr1[n-3]][arr1[n-2]][arr1[n-1]][arr1[0]];
  87. }
  88.  
  89. /* Pass 2 flags all links with an incoming arrow */
  90.  
  91. pass2() {int j, m, x;
  92. printf(" Pass2\015");
  93. do {
  94. m=0;
  95. for (j=0; j<cp; j++) arry[j]|=0x8000;
  96. for (j=0; j<cp; j++) {x=arry[j];
  97.  if (x!=0xFFFF) arry[x&0x7FFF]&=0x7FFF;};
  98. for (j=0; j<cp; j++) {
  99.  if ((arry[j]>0x7FFF) && (arry[j]!=0xFFFF)) {arry[j]=0xFFFF; m=1;};};
  100.  } while (m!=0);
  101. }
  102.  
  103. /* pass4 - print loops which remain */
  104.  
  105. pass4() {
  106. int j, x, y, m;
  107. printf(" pass4 \015");
  108. for (j=0; j<cp; j++) {
  109.  x=j; y=arry[j]; arry[j]=0xFFFF; m=0;
  110.  while (y!=0xFFFF) {prf(x,y); x=y; y=arry[x]; arry[x]=0xFFFF; m=1;};
  111.  if (m==1) kwait(0);
  112.  };
  113. }
  114.  
  115. /* change totalistic rule to general rule */
  116.  
  117. totobin() {
  118. int i0, i1, i2, i3, i4;
  119. for (i0=0; i0<KK; i0++) {
  120. for (i1=0; i1<KK; i1++) {
  121. for (i2=0; i2<KK; i2++) {
  122. for (i3=0; i3<KK; i3++) {
  123. for (i4=0; i4<KK; i4++) {
  124. binrule[i0][i1][i2][i3][i4]=rule[i0+i1+i2+i3+i4];
  125. };};};};};
  126. }
  127.  
  128. /* print the link */
  129.  
  130. prf(j,x) int j, x; {int i, y;
  131.   kwait(1);
  132.   y=j; for (i=0; i<cy; i++) {arr1[i]=y%KK; y/=KK;};
  133.   for (i=0; i<cy; i++) printf("%1d",arr1[i]);
  134.   printf("-");
  135.   y=x; for (i=0; i<cy; i++) {arr1[i]=y%KK; y/=KK;};
  136.   for (i=0; i<cy; i++) printf("%1d",arr1[i]);
  137.   printf("  ");
  138. }
  139.  
  140. /* print arry - for diagnostic purposes */
  141. pall() {int j;
  142. for (j=0; j<cp; j++) printf("%4d",arry[j]);
  143. }
  144.  
  145. /* print cycle - for diagnostic purposes */
  146. pcy() {int j;
  147. for (j=0; j<cy; j++) printf("%1d",arr2[j]);
  148. }
  149.  
  150. /* limit j to interval (i,k) */
  151. int lim(i,j,k) int i, j, k;
  152.     {if (i>=j) return i; if (k<=j) return k; return j;}
  153.  
  154. /* keyboard status */
  155. kbdst() {return bdos(11)&0xFF;}
  156.  
  157. /* direct keyboard input, no echo */
  158. kbdin() {int c;
  159. if ((c=bdos(7)&0xFF)=='\0') c=(bdos(7)&0xFF)|0x80;
  160. videoputc(c,1);
  161. return c;}
  162.  
  163. /* pause at the end of a full screen */
  164. /* kwait(0) - <cr><lf> and count it  */
  165. /* kwait(1) - count columns          */
  166.  
  167. kwait(i) int i; {
  168. switch (i) {
  169.   case 0: printf("\n"); nc=0; nl++; break;
  170.   case 1: if (nc==mc) {printf("&\n"); nc=1; nl++;} else nc++; break;
  171.   default: break;};
  172. if (nl==NW) {
  173.   nl=0;
  174.   printf(" press any key to continue\015");
  175.   while (kbdst()) {};
  176.   kbdin();
  177.   printf("-                         \n");
  178.   };
  179. }
  180.  
  181. /* end */
  182.