I will reuse some of the language I used in

an earlier post. I will use line numbers from zfind-s for reference.

zfind works similarly to gfind, so understanding gfind is helpful. zfind uses the ideas in sections 4 and 6 of David Eppstein's

"Searching for Spaceships" article.

To find a new row, zfind takes 3 known rows, A, B, and Y, and looks for a row X so that evolve(A,B,X)=Y. That is,

Code: Select all

```
AAAAAAAA
BBBBBBBB -> YYYYYYYY
XXXXXXXX
```

It does this by using two lookup tables. The first table (gRows) actually gives the rows X that we are looking for (stored as unsigned 16-bit integers). The second table (gInd) gives indices into the first table (stored as unsigned 32-bit integers). The input for the second lookup table is the three rows A, B, and Y.

More precisely, let ABY be the bitwise concatenation of the integers representing rows A, B, and Y. Then gInd[ABY] gives the index in the array gRows of the first row X such that evolve(A,B,X)=Y. Now, any other row X' satisfying evolve(A,B,X')=Y has index gInd[ABY]+i in the array gRows, where gInd[ABY]+i < gInd[ABY+1]. That is, gRows[gInd[ABY]+i] gives a row X' such that evolve(A,B,X')=Y whenever gInd[ABY]+i < gInd[ABY+1] and i >= 0.

gInd and gRows are calculated inside the function makeTables(). Lines 145-152 (of zfind-s) are where the construction of gInd begins. The for loop runs through every combination of three rows, A, B, X and calculates Y:=evolve(A,B,X). It then increments gInd[ABY]. At the end of this loop, gInd[ABY] gives the number of rows X such that evolve(A,B,X)=Y.

The next for loop (line 154) simply replaces the original value of gInd[ABY] with the cumulative sum of the original gInd[n] values for all n <= ABY.

The last for loop (lines 157-164) constructs gRows and finishes the construction of gInd. It again loops through every combination of three rows, A, B, X and calculates Y:=evolve(A,B,X). The program then reduces gInd[ABY] by 1 and places the row X in the array gRows at index gInd[ABY] (that is, gRows[gInd[ABY]]:=X).

In the end, gInd[ABY] is the index in gRows of the first row X satisfying evolve(A,B,X)=Y.