File-Backed Dense Game of Life

Compute one synchronous generation of a potentially dense Game of Life board stored as rows in a file. The cell-update logic is supplied; implement the sliding window and output-append orchestration.

Finite file adapter

The read-only array fileRows represents a row-major input file. Every row is a binary string of the same positive width. Reading fileRows[r] corresponds to read(inputName, r * width, width). Appending a row to the returned array corresponds to append(outputName, row). Return one output row per input row, in order, without modifying the input.

Use O(width) auxiliary working memory, excluding the supplied immutable input and the returned append-only output. Keep only a constant number of old rows in the active window. The finite adapter uses small boards for execution; explain how the same row reads and appends scale to the report’s 1000000 x 1000000 dense board, where reading the entire file into memory is unsuitable.

Outside the board, all cells are dead. Every cell in the next generation must use the original generation. There is no wrapping, and the board may be dense; a sparse live-cell representation is not an assumption.

Supplied cell-rule helper

The helper below is supplied reference logic. You may copy it unchanged; the exercise is arranging old input rows into a sliding window and appending output rows. This row wrapper applies the already supplied cell rule to one row.

Python

def processLifeRow(top, middle, bottom):
    out = []
    for c in range(len(middle)):
        neighbors = 0
        for line in (top, middle, bottom):
            for d in (-1, 0, 1):
                j = c + d
                if 0 <= j < len(middle):
                    neighbors += line[j] == '1'
        neighbors -= middle[c] == '1'
        out.append('1' if neighbors == 3 or (middle[c] == '1' and neighbors == 2) else '0')
    return ''.join(out)

Java

private String processLifeRow(String top, String middle, String bottom) {
    StringBuilder out=new StringBuilder();
    for(int c=0;c<middle.length();c++) {
        int neighbors=0;
        for(String line:new String[]{top,middle,bottom}) for(int d=-1;d<=1;d++) {
            int j=c+d; if(j>=0 && j<middle.length() && line.charAt(j)=='1') neighbors++;
        }
        if(middle.charAt(c)=='1') neighbors--;
        out.append(neighbors==3 || (middle.charAt(c)=='1' && neighbors==2)?'1':'0');
    }
    return out.toString();
}

C++

string processLifeRow(const string& top, const string& middle, const string& bottom) {
    string out(middle.size(),'0');
    for(int c=0;c<(int)middle.size();c++) {
        int neighbors=0;
        for(const string* line:{&top,&middle,&bottom}) for(int d=-1;d<=1;d++) {
            int j=c+d; if(j>=0 && j<(int)middle.size() && (*line)[j]=='1') neighbors++;
        }
        neighbors-=middle[c]=='1';
        if(neighbors==3 || (middle[c]=='1' && neighbors==2)) out[c]='1';
    }
    return out;
}

Go

func processLifeRow(top string, middle string, bottom string) string {
    out:=make([]byte,len(middle))
    for c:=range out {
        neighbors:=0
        for _,line:=range []string{top,middle,bottom} { for d:=-1;d<=1;d++ {
            j:=c+d; if j>=0 && j<len(middle) && line[j]=='1' { neighbors++ }
        } }
        if middle[c]=='1' { neighbors-- }
        out[c]='0'; if neighbors==3 || (middle[c]=='1' && neighbors==2) { out[c]='1' }
    }
    return string(out)
}