Processing Life cell lists as streams in Unix

[pcallahan]

This is a pretty simple idea and I'm sure I'm not the first (actually I have done things like this before, but using a stream wasn't the point).

Code: Select all

awk '{for (i = -1; i <= 1; i++)
  for (j = -1; j <= 1; j++) {
    if (i != 0 || j != 0) print $1 + i, $2 + j
    print $1 + i, $2 + j
}}' | sort | uniq -c | awk '{if ($1 >=5 && $1 <= 7) print $2, $3}'

This can process a list of cells, such as these for a glider:

Code: Select all

0 0
0 2
1 1
1 2
2 1

It then outputs the next generation.

Code: Select all

0 2
1 0
1 2
2 1
2 2

My code looks a bit obfuscated, but it works by taking each cell (i, j) and fanning out two copies of each neighboring cell as well as a single copy of the cells themselves. When you count unique cell coordinates, the cell value is encoded as the odd/even bit (count mod 2) while the number of neighbors is on the higher bits (count div 2). You sort them and count with uniq and filter based on the count.

I didn't work hard to make this very concise. Maybe someone has something better.

More importantly, I would like to avoid the sort step. If you start with the cells in sorted order, you get "mostly" sorted after the fanout step. If you could maintain 3 pointers into the stream, you could do the count without sorting again. Is there a way to do this with unix commands without sort? (Maybe by using tee)

[blah]

Neat hack. Here's a command to (almost) convert it to RLE:

Code: Select all

dc -e"[q]sQ[_1sx]s.?sxsylxn[bo]n[?z1=Qrdly-dn[$]n0<.sydlx-1-n[bo]nsxdx]dx[!]p"

For the glider cell list it produces "0bo0$1bo1$1bo0$0bo1$1bo!". The 0s present a problem; 0b probably works on some (most?) decoders, but 0$, at least on mine, resets the x value to 0, like a carriage return with no linefeed. I could do "| sed s/0[b$]//g" but that would turn, say, "20bo" into "2o". I haven't figured out how to properly sanitise this, help would be appreciated. Also it doesn't work if there's a cell with an x value less than 0.

Also here's a C version for n00bs who can't read dc fluently (is there a way to reorganise this so there's only one scanf?):

Code: Select all

/* cell list to run length encoding */
#include <stdio.h>
int main(){
	int x,y,
	    ox,oy; /* old xy */
	scanf("%d %d",&y,&x);
	ox=-1,oy=y;
	do {
		printf("%d$",y-oy);
		if(y-oy) ox=-1;
		printf("%dbo",x-ox-1);
		ox=x,oy=y;
	} while(scanf("%d %d",&y,&x)!=EOF);
	putchar('\n');
	return 0;
}

I believe there is no constant-memory algorithm to simulate the game of life on a stream. You'd need to keep a buffer of the last 2 lines in memory which can be arbitrarily large. On multiple streams simultaneously, though, I think it's possible. Consider breaking up the cell list into 3 files like so:

Code: Select all

perl -e '
open my $a, ">", "a";
open my $b, ">", "b";
open my $c, ">", "c";
while(<STDIN>){
	my ($y,$x) = /(\d+) (\d+)/;
	if ($y%3 == 0) { print $a $y," ",$x,"\n"; }
	if ($y%3 == 1) { print $b $y," ",$x,"\n"; }
	if ($y%3 == 2) { print $c $y," ",$x,"\n"; }
}'

i.e. There are three files, 'a', 'b', and 'c', which contain alternating rows (mod 3). If you do 3 passes on these 3 files, you could compute the next generation as another set of 3 files, I think.