Another small modification of dr
Posted: 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.)
dr2.c:
dr3.c:
dr2.c:
These blocks are totally absent in dr2:
· Definition of relevant variables:
· This block of code counts non-stable cells.
· Back up if number of non-stable cells exceed var[140] or number of blue cells exceed var [141].
· 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.
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. */
Code: Select all
/* Find min & max row & column of changed cells. */
Code: Select all
if (qc > maxqc) maxqc=qc;
if (var[142])
changedthis[qr][qc]=1;
}
Code: Select all
if (qc > maxqc) maxqc=qc;
}
· 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;
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;
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;
}
}
}
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;
}
}