Another small modification of dr

For scripts to aid with computation or simulation in cellular automata.
Post Reply
Bullet51
Posts: 662
Joined: July 21st, 2014, 4:35 am

Another small modification of dr

Post by Bullet51 » August 1st, 2021, 1:07 pm

Note: The source code of the original dr2 can be downloaded here .

Presented here is a modification of dr2 for oscillator searches. It introduces three variables, namely var[140], var[141] and var[142]. Their meanings are as follows:

If var[140] is nonzero, the program counts the non-stable cells, i.e. cells that have changed at least once. (Compare with the original change count in dr2, which counts the cells that differ from the background.) If the number of non-stable cells exceeds var[140], the program will back up to the last choice that it made.

If var[141] is nonzero, the program counts the non-stable cells that are dead in the present generation, i.e. the blue cells in LifeHistory. If the number of blue cells in some generation exceeds var[141], the program will back up.

If var[142] is nonzero, the program counts the number of changes (births+deaths) in every generation. If the number of changes exceeds var[142], the program will back up.

(I will introduce more variables to count the number of births and deaths separately some time.)

The differences of the my program and the original dr2 are listed here, as compared by fc:

dr3.c: (Comment: the array changedthis is used to record the cells changed in this generation.)

Code: Select all

  static int changedthis[81][81];    
  static int m,n;                                 
  if (var[142])
  {
      for(m=0;m<HT;m++)
           for(n=0;n<WD;n++)
                  changedthis[m][n]=0;
   }
  /* Find min & max row & column of changed cells. */
dr2.c:

Code: Select all

  /* Find min & max row & column of changed cells. */
dr3.c:

Code: Select all

          if (qc > maxqc)  maxqc=qc;

          if (var[142])
           changedthis[qr][qc]=1;   

        }
dr2.c:

Code: Select all

          if (qc > maxqc)  maxqc=qc;
        }
These blocks are totally absent in dr2:

· Definition of relevant variables:

Code: Select all

   static int changedonce[81][81],changedlast[81][81];
   static int sumchanged,sumblue,difference;
   static point* q1;
   static int maxqr_1,minqr_1,maxqc_1,minqc_1;
· This block of code counts non-stable cells.

Code: Select all

   if(var[140] || var[141])
   {
      for(m=0;m<HT;m++)
          for(n=0;n<WD;n++)
              changedonce[m][n]=0;
      for(m=0;m<gen;m++)
          for(q1=chgd[m]; q1<nays[m]; q1++)
              changedonce[q1->row][q1->col]=1;   
      for(q1=chgd[gen]; q1<chg; q1++)
              changedonce[q1->row][q1->col]=1;
· Back up if number of non-stable cells exceed var[140] or number of blue cells exceed var [141].

Code: Select all

      sumchanged=0;
      sumblue=0;
      for(m=0;m<HT;m++)
          for(n=0;n<WD;n++)
          {
                if (var[140])
                {
                    sumchanged+=changedonce[m][n];
                    if (sumchanged > var[140]) return ERR;
                }
                if (var[141])
                {
                    sumblue+=(changedonce[m][n] & (!curr[m][n]));
                    if (sumblue > var[141]) return ERR;
                }
          }

    }
· Computing the list of changed cells for var[142]. If the list chgd is ordered by rows and columns, there will be no need to use the array changedlast, like how we can print (without saving) the symmetric difference of two ordered lists of integers in linear time and constant space.

Code: Select all

  if (var[142] && gen>1)
  {

          //need to optimize for speed
          for(m=0;m<HT;m++)
          for(n=0;n<WD;n++)
                      changedlast[m][n]=0;


          for (q=chgd[gen-1], minqr_1=HT, minqc_1=WD, maxqr_1=maxqc_1=0; q<nays[gen-1]; q++)  //similar routine
                  { 
                    qr = q->row;  qc = q->col;
                    changedlast[qr][qc]=1;
                    if (qr < minqr_1)  minqr_1=qr;
                    if (qr > maxqr_1)  maxqr_1=qr;
                    if (qc < minqc_1)  minqc_1=qc;
                    if (qc > maxqc_1)  maxqc_1=qc;
                 }

          difference=0;
          for (m=min(minqr,minqr_1);m<=max(maxqr,maxqr_1);m++)
             for (n=min(minqc,minqc_1);n<=max(maxqc,maxqc_1);n++)
             {
                     difference+=(changedlast[m][n] ^ changedthis[m][n]);
                     if(difference > var[142]) return ERR;
             }
  }
Attachments
dr3.c
(77.99 KiB) Downloaded 84 times
Still drifting.

Post Reply