And now for something completely different :)

This was written to see if I could use perl's logical string operations to do the calculations need for Life.

Of course, what I really wanted was a string oriented byte-by-byte add ( a +. to go along with the brand new |. and &. ) but I couldn't find one (sigh).

However, this is a way to use three bits in the byte as a sum, provided only one bit is added at a time.
Consider the 8 bits of a byte to be 0011SSSN where the 'S' bits are the sum and a new bit 'N' is added (actually or'd) as the bottom bit. (Why the two '1' bits? Because the character '0' is 00110000 as binary and '1' is 00110001 as binary, and we can do calculations such that the result is immediately printable. We don't, but we could :)

Now if I 'or' in a neighbor character it will only (potentially) change the 'N' bit. For each neighbor, I only have to add that bit to the sum (in SSS) and then clear the bottom bit for the next neighbor.

This turns out to be a simple tr/1357/2468/ translation.

(But tybalt89, you say, you only have a three bit counter and there are eight neighbors, you can't hold a count that high. Answer: I don't have to, since any count four or greater will result in a dead cell, I only have to count to four.)

After processing all eight neighbors, the center cell is then or'd in to give the state of the neighbor count along with the state of the center cell, which can the be translated to "alive or dead" for the next generation.

In this scheme, you need to specify the size of the grid in advance, and any live cells at the grid edge get killed to avoid wraparound'


So how does this do on the challenge - simple, it fails. (Oh good, I can avoid being hired :)

You did say you wanted "to see how others go about it".

Notes:

It's "live cell count" speed invariant, as opposed to techniques that keep only live cells.
I stopped performance testing because I ran into Heisenberg problems, i.e. output seriously affects speed.
It's not infinite size, or even semi-infinite, unless you've got a really, really, really big machine.
It should probably be moved to GPUs but a) I don't have a GPU to test on, and b) it probably already has been.


I usually run it without the override lines, and uncommented print statements. It autosizes to the terminal it is running in, (at least on ArchLinux and xterm), and of course increase the number of generations.



OK, I have to go cook supper, and I'm really tired of typing, so I'll submit at this point, and look for comments later...

#!/usr/bin/perl

# http://perlmonks.org/?node_id=1197250
# Conway's life eyepopslikeamosquito

use strict;
use warnings;
use Time::HiRes 'time';

my $w = qx(tput cols) + 0; # probably linux only :)
my $h = qx(tput lines) - 7; # strange offset because of my REPL
# override for comparison with node results
$w = int sqrt 3e6;
$h = int 1 + 3e6 / $w;

my $board = '0' x $w x $h;
my $mask = '0' x $w . ('0' . "\xff" x ($w - 2) . '0') x ($h - 2) . '0'
+ x $w;

# build starting state

sub place
  {
  my ($x, $y, $pattern) = @_;
  my $offset = $y * $w + $x;
  for ( $pattern =~ /.+/g )
    {
    substr $board, $offset, length $_, $_;
    $offset += $w;
    }
  }

place( 4, 4, <<END =~ tr/-O/01/r ); # glider gun
------------------------O-----------
----------------------O-O-----------
------------OO------OO------------OO
-----------O---O----OO------------OO
OO--------O-----O---OO--------------
OO--------O---O-OO----O-O-----------
----------O-----O-------O-----------
-----------O---O--------------------
------------OO----------------------
END

place( $w >> 1, $h >> 1, <<END =~ tr/-O/01/r ); # switch engine
----------
-------O--
-----O-OO-
-----O-O--
-----O----
---O------
-O-O------
----------
END

my $generations = 0;
my @offsets = ( 1, 2, $w, $w + 2, $w * 2, $w * 2 + 1, $w * 2 + 2 );
my $pad = '0' x ($w + 1);

#print "\e[H\e[J"; # clear screen
#print "\e[H", $board =~ tr/01/ O/r, "-" x $w, "$generations\n";

my $starttime = time;

for (1..2) # loop over generations
  {
  $generations++;

  my $all = $pad . $board . $pad;

  my $sum = $all =~ tr/1/2/r;                                # first o
+ffset
  ( $sum |= substr $all, $_ ) =~ tr/1357/2468/ for @offsets; # other 7

  $board |= $mask & $sum;      # prevent overflow at edges
  $board =~ tr/1-9/000011100/; # determine alive or dead

  #print "\e[H", $board =~ tr/01/ O/r, "-" x $w, "$generations\n";
  }

my $time = time - $starttime;
printf "\nw %d h %d cells %d time %.2f generations %d gen/sec %d" .
  " nanoseconds/cell/gen %d\n",
  $w, $h, $w * $h, $time, $generations, $generations / $time,
  $time / ($w * $h) / $generations *1e9;
[download]