[Jprogramming] Matrix Transformations based on local submatrices

[Roger Stokes]

There is a version of Conway's "Life" in J in Rosetta Code, and reproduced 
below.

It uses Cut ;. but shifting the plane or rotating the torus is more than a 
hundred times faster.

The timings I get for 100 iterations on a random 100x100 matrix are:

    Rosetta    3.421 seconds
    shifting   0.030    "
    rotating   0.028    "

Evidence follows,  transcript of session:

   NB. Conway's "Life"

   NB. ========================================
   NB.     Rosetta Code method
   NB. ========================================

   pad=: 0,0,~0,.0,.~]
   life=: (_3 _3 (+/ e. 3+0,4&{)@,;._3 ])@pad


   NB. ===============================================
   NB.     Lincolnshire Method, by shifting
   NB. ================================================

   sh   =: |. !. 0
   E    =: 0 _1 & sh
   W    =: 0 1  & sh
   N    =: 1    & sh
   S    =: _1   & sh
   NS   =: N + S
   EW   =: E + W
   NeCo =: NS + (+ NS) @: EW                NB. neighbour-count
   evol =: ((3 = ]) +. ([ *. 2 = ])) NeCo



   NB. ===================================================
   NB.     Test for correctness by comparing with Rosetta
   NB. ===================================================

   rp =: 3 : 0      NB. make y-by-y matrix with r-pentomino at SE corner
    w =. (y,y) $ 0
    w =. 1 (0 1 ; 0 2; 1 0; 1 1; 2 1)  } w
    4 4 |. w
)


   TX =: 4 : 0  NB. y iterations of r-pentomino in x-by-x matrix
 T =. rp x
 a =. life ^:y T      NB. Rosetta method
 b =. evol ^:y T      NB. shifting method
 assert. b -: a
 'OK'
)


   20 TX 16    NB. in a 20x20 plane, 16 iterations
OK



   NB. ====================================================
   NB.     a variation,  rotating instead of shifting
   NB.     (life on a torus rather than a bounded plane)
   NB. ====================================================


   adverb =: 1 : ('sh =. u' , LF, 'evol f.')

   revo =: |. adverb


   NB. ================================================
   NB.     timings
   NB. ================================================


   randmat =: 3 : '(y, y) $ ? (y * y) # 2'

   OBS =: 3 : 0    NB. y-by-y matrix
    M =: randmat y
    R =. 0 2 $ a:
    do =. (10j5 & ":) @: (4 & (6!:2))
    R =. R, 'Rosetta  100' ; do 'life ^: 100 M'
    R =. R, 'evol 100    ' ; do 'evol ^: 100 M'
    R =. R, 'revo 100    ' ; do 'revo ^: 100 M'
    R
)


   OBS 100
+-----------------------+
¦Rosetta  100¦   3.42198¦
+------------+----------¦
¦evol 100    ¦   0.03048¦
+------------+----------¦
¦revo 100    ¦   0.02817¦
+-----------------------+



----- Original Message ----- 
From: "Alex Giannakopoulos" <aegean at blueyonder.co.uk>
To: "J Programming forum" <programming at jsoftware.com>
Sent: Tuesday, November 13, 2012 11:43 AM
Subject: [Jprogramming] Matrix Transformations based on local submatrices


> OK, I'm trying to do some work with matrices that involves transformations
> based on local properties of a matrix (neighbouring elements).
> This is the sort of thing you may find in image-processing
> "edge-detection", etc, or in some cellular automata of the type of 
> Conway's
> "Life".
>
> In other words, I want to be able to supply a matrix, and have it so
> processed that the result is a new matrix where each new element was
> determined by a function which processed the old elements neighbours.
>
> Any direction, relevant help pages, etc, much appreciated.
> If anyone would go as far as offering some sample code that would be 
> great,
> too!
> As a trivial example, suppose I want to calculate the sum of the 
> neighbours
> of each element
> Say we have a matrix  m0 =. 3 3 $ >:i.9
> What I want is the verb "neighbours" whereby
>   neighbours m0
> 11 19 13
> 23 40 27
> 17 31 19
>
> Obviously, I am maily interested in how to extract the "neighbours"
> submatrix, without resorting to explicit looping, if that is possible.
> To make it a bit more interesting, how would I extract the neighbours if
> the matrix was a torus or infinite tiling, such that:
>   neighb-torus m0
> 44 43 42
> 41 40 39
> 38 37 36
>
> Thanks for any suggestions!
> Alex
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>