Game of Life using math/array

Show & Tell
1

Since the use of math/array came up recently in a topic here, I thought, I'll have a look at the package and see how difficult it would be to implement the game of life (Conway's Game of Life - Wikipedia) using it. Turns out it is pretty simple:

First, here is a function which encodes the game rules for an individual cell (this has nothing to do with math/array)

(define (game-rules cell neighbor-count)
  (cond
    ;; Any live cell with fewer than two live neighbours dies, as if by
    ;; underpopulation.
    ((and (equal? cell 1) (< neighbor-count 2)) 0)
    ;; Any live cell with two or three live neighbors lives on to the next
    ;; generation.
    ((and (equal? cell 1) (or (= neighbor-count 2) (= neighbor-count 3))) 1)
    ;; Any live cell with more than three live neighbors dies, as if by
    ;; overpopulation.
    ((and (equal? cell 1) (> neighbor-count 3)) 0)
    ;; Any dead cell with exactly three live neighbours becomes a live cell,
    ;; as if by reproduction.
    ((and (equal? cell 0) (= neighbor-count 3)) 1)
    ;; All else, cell remains unchanged
    (else cell)))

And here is the code to run the simulation, note that the code operates on arrays a whole, without referencing individual elements:

(define initial ;; initial configuration (this is a glider pattern)
  (array
   #[#[0 0 0 0 0 0 0 0 0 0]
     #[0 0 1 0 0 0 0 0 0 0]
     #[0 0 0 1 0 0 0 0 0 0]
     #[0 1 1 1 0 0 0 0 0 0]
     #[0 0 0 0 0 0 0 0 0 0]
     #[0 0 0 0 0 0 0 0 0 0]
     #[0 0 0 0 0 0 0 0 0 0]
     #[0 0 0 0 0 0 0 0 0 0]
     #[0 0 0 0 0 0 0 0 0 0]
     #[0 0 0 0 0 0 0 0 0 0]]))

(define (rol a dimension)               ; rotate left
  (define n (vector-ref (array-shape a) dimension))
  (append (list (sub1 n)) (build-list (sub1 n) values)))

(define (ror a dimension)               ; rotate right
  (define n (vector-ref (array-shape a) dimension))
  (append (build-list (sub1 n) add1) '(0)))

(define shifts
  `((,(::) ,(rol initial 1))            ; left
    (,(::) ,(ror initial 1))            ; right
    (,(rol initial 0) ,(::))            ; up
    (,(ror initial 0) ,(::))            ; down
    (,(rol initial 0) ,(rol initial 1)) ; up-left
    (,(rol initial 0) ,(ror initial 1)) ; up-right
    (,(ror initial 0) ,(rol initial 1)) ; down-left
    (,(ror initial 0) ,(ror initial 1)) ; down-right
    ))

(define (neighbour-count a)
  (define ns (map (lambda (shift) (array-slice-ref a shift)) shifts))
  (apply array-map + ns))

(define (advance a) ;; advance the world one time unit
  (array-map game-rules a (neighbour-count a)))

And here is what it looks like (this animation is with a more complex pattern):

gol

Here is the full program: game-of-life.rkt · GitHub

Enjoy!
Alex.

9 Likes
2

I like your code (especially your visualization), and referred to it in the SRFI 231 document.

I don't know much about these things, but my understanding is that math/array is written in Typed Racket and your program, which uses math/array, is written in (plain) Racket, and that interfacing between Typed and plain Racket introduces checks at the boundaries that slow down execution.

I'd be interested in a Typed Racket version of your program (at least for the computational kernel of it, maybe not for the visualization) that might eliminate those checks.

3

Here's a typed version. Annoyingly (apply array-map ...) can't be made to work (so I worked around it), and there were some required type annotations in the snip implementation that shouldn't have been needed. I haven't checked if it's faster:

1 Like
4

Thanks a lot! Comparing the two versions is very informative.

And it seems to be a lot faster; when I load the #lang racket version into drracket on my machine (v8.16.0.2 [cs]) , then

(time (advance glider-gun))

takes

cpu time: 58 real time: 58 gc time: 16

while your #lang typed/racket version takes

cpu time: 1 real time: 1 gc time: 0

(and at least once all those times were 0 ms).

1 Like