Re: Conway's Game of Life (cellular automata)

[Bill Richter <richter@math.northwestern.edu>]

   From: Michael Bogomolny <bogo@cs.utexas.edu>

   | Ian Stewart's book "The Collapse of Chaos" describes Conway's
   | Game of Life and claims that a "glider gun" is periodic with
   | period 30, with the additional feature that the "glider gun"
   | shoots out a stream of pulses diagonally (down & to the right).

   Generation 29 is the same as generation 89, 30 as 90, etc.
   Generation 29 is *not* the same as generation 59, due to the
   "offshoot".  So why wouldn't you say that after 28 generations it
   stabilizes to a cycle with period 60?

No, Michael!  But you found an interesting effect of my bug I
explained at the end of my code:

   ;; Still need to implement error checking: if we ever get 3
   ;; consecutive black cells on the bounding frame (an outer row or
   ;; column), then the grid is too small, and must be enlarged.

What you noticed is that as a glider heads off to the bottom edge, it
(as a result of my bug) turns into a 2x2 square, which never changes,
but annihilates the next glider coming in!  That's nice.  The true
fact, which I didn't know, is that this figure

                x           
              x x           
               xx           
                  xx        
                  xx        

disappears in 4 iterations.  (i.e. This disappearance isn't caused by
my bug, although the 2x2 square is caused by my bug.)
                            

So I crudely fixed your bug, but introduced another, with this code
below, which now pushes the problem onto the right edge rather than
the bottow:

(define (three-in-row? row)
  ;; returns #t if three consecutive black squares on the bottom row
  (letrec ((three-in-row-real? 
            (lambda (n row)
              (cond ((= n 3) #t)
                    ((null? row) #f)
                    (else (three-in-row-real? (if (char=? (car row) #\x)
                                                  (+ n 1)
                                                  0)
                                              (cdr row)))))))
  (three-in-row-real? 0 row)))

(define (make-padded-game game)
  ;; We also first error-check to see if there are 3 consecutive black squares on the 
  ;; bottom row.  If so, we add an extra row
  (letrec ((make-blank-list 
            (lambda (list) 
              ;; returns a list full of spaces of same length as list 
              (if (null? list) 
                  `()
                  (cons #\space 
                        (make-blank-list (cdr list)))))))
    (let* ((make-padded-row (lambda (row) 
                              (cons #\space 
                                    (append row 
                                            (list #\space)))))
           (game-padded-by-rows 
            ;; the game with each row padded by a SPC on both ends
            (map make-padded-row game))
           (padded-blank-row (make-blank-list (car game-padded-by-rows)))
           (padded-game 
            ;; game padded all around now
            (cons padded-blank-row 
                  (append game-padded-by-rows 
                          (list padded-blank-row)))))
      ;; Check to see if there's 3 consecutive black squares in the last row 
      ;; of game, which is the 2nd to last row of padded-game
      (if (three-in-row? (cadr (reverse padded-game)))
          (append padded-game  (list padded-blank-row))
          padded-game))))

I.e. replace `make-padded-game' with this version, and add in
`three-in-row?'.   

Now it's fine through 146, and it's now "bug-periodic" with period 60
starting with 146.   That's interesting!

So we need to error-check on all 4 sides.  `make-padded-game' isn't
the right place to do the error-checking and row-adding anyway.

BTW I goofed, it's not TLS coding I was trying to emulate, but TSS,
especially the 11th commandment:  

"Use additional arguments when the function needs to know previous
arguments to the function."

Except I consed the previous arguments into the game rather than
adding them as separate arguments.  

I.e. my function consumes a list (rectangular list of lists) in the
usual way, throwing out the car.  But I need at each stage the row I
just consumed, so I just keep it, and throw it out next turn.